イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。

127. AtCoder参加記録（AtCoder Beginner Contest 261）

プログラミング AtCoder

31回参加でレート 1316 です。

今回はパフォーマンス 1258 です。

ABCDEを通して、FGExは未解答です。A, Bでそれぞれ1ペナ。

各問題の思考過程など。

A

初回提出3分34秒、そこからACまで2分37秒。

何故か気が向いて、カッコよく分岐だけで解こうとしてしまいました。案の定バグらせたので素直にループ回して数え上げました…。

B

初回提出8分39秒、そこからACまで1分44秒。

「誰が誰に勝ったのか」「誰が誰と引き分けたのか」を辞書で持って全探索しました。もっと賢いやり方はあったと思いますが…。

実装をバグらせて1WA。やっぱり変に実装長くなる解法は避けたい…。

C

3分38秒。

C# は文字列の一致判定を $O(1)$ で行えるとみなしてよく、辞書のキーとしても持てるので、普通にループ回してやればよいです。本当にやるだけでした（なんでC問題？）

D

7分28秒。

最近DPばかりやってたので、すぐ見えました。

$dp[i, j ] := (i 回コイントスした直後にカウンタが j であるときの貰えるお金の合計最大値)$

状態数は $O(N^2)$ 、連続ボーナス判定は予め辞書を持っておけば $O(1)$ でできて、各回遷移は表裏2状態しか取らないのでこれでOK。

初期状態は $dp[0, 0] = 0$ で、それ以外 $-\infty$ で初期化しておきます。 $-\infty$ 以外の状態から配るDPをして、 $i$ 回連続ボーナスを $B_i$ とすると、

表の場合: $dp[i + 1, j + 1] = \max(dp[i, j] + X_{i+1} + B_{j + 1})$
裏の場合: $dp[i + 1, 0] = \max(dp[i, j])$

答えは $\max_{j}(dp[N, j])$ 。

E

71分33秒。ギリギリで解けたのは良かったですが、時間使いすぎ～～～

初め60分近く考えていた方針は、「操作 $1$ ～操作 $i$ の結果を事前計算して、ループごとにこの値を使って演算する」でした。ところが、結合則の成り立たない演算が混じっているのでかなり大変で、実装してみたもののそもそもサンプルが合いませんでした。というか、後ろから先にやって大丈夫なのかあんまり自信が無かったです。

サンプルが合わない時点でこの方針は間違っているな…と思い、半ば諦め気味でしたが、ふと「ビット演算はビットごとに独立して考える」という言葉が浮かび、急に解法を閃きました…。

あるビットが操作 $1$ ～操作 $i$ によって変換される結果は常に等しい
各ビットは高々2状態しか取らず、操作対象の数も高々30ビット。
各位置のビットについて、 $0, 1$ それぞれが操作 $i$ まででどのビットに変換されるか保持しておく。このメモ変数自体はループを通して保持し、操作の適用はループごと1回ずつ行う。
ループごとに、 $X$ の各ビットがどちらになっているか確認して、先ほどのメモからどのように変換されるか確認する。その後、そのビットから数を再構成する。

思いついたのが終了10分前とかで、かなり焦りながらバグらせつつ実装しました。なんとか終了1分前に入力例1の合う実装になって、この解法なら1つ合えば他も大丈夫なはずとぶん投げてAC。

F, G, Ex

見てないです。

Bまで遅すぎ・ペナ出しすぎで良くなくて、Dはかなり早くてOK、Eは…変な方針に固執しすぎちゃイカン、という感じでした。ここのところ調子よくないですね…。