AtCoder Beginner Contest 171
2020-06-22
コンテスト中に挑戦した問題についての感想とか.
A - αlphabet
小文字大文字判定をする. CLだとchar<=とかで判定できる.
(正確にはANSI Common Lispでは, ASCIIを拡張したような文字コード前提ではなかった様な気がするが, ソレはまた別の話.)
まあ, この問題だとその他色々方法があると思う.
B - Mix Juice
KがN以下という条件あるので, K個選べないパターンはない.
ソートして小さいものからK個足す.
C - One Quadrillion and One Dalmatians
名前の長さ毎に26進表記になっていると考えると分かりやすい.
まず名前の長さを求めて, それから10進表記->26進表記変換に変換すれば良い.
長さlの名前になる最小の数は26^0 + 26^1 + 26^2 + ... + 26^(l-1) = (26^l - 1) / 25と求められる. (等比級数)
なお, 一度計算間違えてWAになってしまった. 焦らずやっていこう.
D - Replacing
和を求めるので, 数列の並びは関係ない. また, 毎回数列をなめていると間に合わないので, 数列中に出てくる数の個数を配列(ハッシュマップ)で持つ.
また, この形式で毎回和を求めていたらやはり間に合わないので, 先に和を求めておく.
毎回の操作で次の2つの更新を行う.
- 和の更新: 変化する数の個数と1つあたりの増減がわかるのでソレを足す.
- 配列の更新: Bの個数だけCが増えて, Bは0個になる.
コードで書くと,
(incf s (* (aref a b) (- c b)))
(incf (aref a c) (aref a b))
(incf (aref a b) 0)
問題がうまく誘導してくれた, もし最後の状態の和のみを求める場合だったら, ちゃんと気付かなかったかもしれないので注意したい.
何を求めるのか, そのためにはどういった情報が必要なのかということに注目して問題文を読むように注意しようと思う.
先に和を取っておいて差分を計算していくというのは一つのお決まりのパターンのような気がする.
E - Red Scarf
xorのことを知ってたから解けたという感じでは有ったが, 初めてE問題が解けた.
とはいえちゃんと理解しきっていなかったので実装は少し変になった.
素直な実装は, 与えられたa_iのxorをSとして, i番目の数をa_i xor Sで求める.
xorは, 結合的で可換で, A xor A = 0という性質がある.
与えられた数すべてのxorを取ると求めたい数をそれぞれN-1回xor取ったもののxorを取ったものとなり, これは, N-1が奇数であることより, xorの性質から求めたい数すべてのxorを取ったものと一致する.
a_iは求めたい数のi番目のもの以外のxorを取ったものなので, これと先程求めたSのxorを取れば求めたい数が求まる.