Codeforces 96

英語読解力と実装力のテストにはちょうど良いみたいです。

A

文字列が与えられるので、各文字間の差分をビット列で逆順にしたものを出力せよ、という問題。(意訳かつちょっと違うけど。)

英語を読んでやるだけです。

B

矩形の形状に色が塗られている盤面がある。左上の矩形から初めて、指定されたルールで移動するとき、特定ステップ数経過した時点で滞在している矩形の色を答えよ、という問題。

状態数が比較的少なくてすぐにループするはずなので、最後に到達したときを覚えておいてその分スキップするだけ。実装を頑張る。

C

後ろを向く操作と向いている方向に進む操作の文字列が与えられる。K箇所変更(同じ箇所の複数回変更は可能)することにして、終了位置をできるだけ遠くにしたい。そのときの距離を答えよ、という問題。

取り敢えず進むべき方向を決めて、そちらに向かうべく頑張る。後ろを向くという操作を進む操作に変更することだけを考えて取り敢えず頑張り、余ったら適当に使い潰せば良さそう。そうなると、ある文字までに変更した回数で、進行方向は決まるので、進行方向が決まるなら、当然目的の方向にたくさん行っている方が良いので、という風にやってみた。

(追記)下手なことしないで、flipを何回するかを各文字ごとに決めて、そのときの位置として可能な範囲をメモしておけば良い感じ。どの文字をflipしようが、flip使った回数で進行方向は決まるので。

D

二進数が与えられるので、2のべき乗の数の加減算でできるだけ少ない項数で表現しなおせ、という問題。

1が複数個並んで0を一個挟んで1が複数個並ぶような場面でのみ0の部分に1を立てる操作をして、その後で、連続する1は両端の差分で実現して、一個だけの1はそのまま実現して、とやるだけ。もっとまじめに計算できるとは思うけれど...。

E

見てないけど既出らしい。