AtCoder Beginner Contest 098に事後参加してみた
「事後参加」って変な言い回しだな。「の問題を解いてみた」が正しい・・・
例によってPythonで。
第１問
入力値二つの和、差、積のうちの最大値を出力する問題。本当に問題文のまま実装・・・
第２問
文字列sを分割して、「どちらにも出てくる文字」の種類数を最大化する問題。やはり問題文のまま実装・・・
というのはつまり文字列を分割した場合の二つ組を列挙して、文字をset化して、intersectionをとって、その長さの最大値を計算する、という流れ。
第３問
西向きの人、東向きの人が混ざった一列のなかからリーダーを選んで、他の人にリーダーの方を向いてもらう場合、振り向く必要のある人数を最小化する問題。
a = accumulate(c=='W' for c in 'X'+s[:-1]) b = reversed(list(accumulate(c=='E' for c in 'X'+s[-1:0:-1]))) print(min(x + y for x, y in zip(a, b)))
itertools.accumulateを使ってちょっとだけ気の利いたことをしている。
accumulateは例えば整数のリストをとって、各添字までの合計値のリストを返すような関数。（実際には引数・戻り値ともにリストではなくiterable/iteratorだが）。
各ポジションで東側にいる西向きの人数、西側にいる東向きの人数を足したシーケンスの最小値を探している。特に東向きのほうはreverseして計算して再度reverseしているのですこしコードがごちゃついているのが不満。iteratorはreversedできないのでいったんリストに直しているのも個人的には減点・・・
第４問
整数のリストのどの部分においてすべての要素のxorと+が一致するか、という問題。
a xor b <= a + bなことを利用すると、a xor b xor c == a + b + cが成り立つためにはa xor b == a + b、 b xor c == b + cが成り立つ必要があることがわかる。
というわけで左右の添字を少しずつずらしていく解法が成り立つ。答えた後に調べたところ、「しゃくとり法」というらしい。
添字を手動でインクリメントしていったり、状態をいろんな変数に保持して分岐したりと、ひたすら実装がダサい。もうちょっときれいな書き方を思いついたら是非書き直したい・・・
感想
最後の問題以外では比較的シンプルにPythonの機能を使って書けた。第３問が100ms強、第４問が250ms強なので時間制約もあまり気にならない。しゃくとり法だけもうちょっと書き方を研究したい・・・
