200.1

300

窓の大きさと中に書かれている文字が与えられるので、指定された領域に書かれている文字を答えよという問題。

各座標について、一番上にある窓の文字を答えれば良い。何も考えないなら、下から窓をチェックしていって、ヒットすれば上書きというのをやれば良い。窓が密にある場合は上からチェックした方がいいけれど、時間的には問題なので、簡単に書けるルーチンを選んだ方が得かも。

500

掛け算のキャリーなし表記が与えられるので、元の整数の組のうち差が一番小さいものを答えよという問題。

ひたすら実装あるのみ。こういうのをさっくり書けるようにならないといけないなぁ...。

二つの数の桁をまず決める。桁数が近いものから順番にやれば、矛盾しないものが答えになる。上の桁から順に今まで決まっている桁を利用して計算する。ただし最初の桁は二つの数の積なので、例外処理が必要。後は今までの桁から決まる部分を削除したものを、決める桁と先頭の桁との積から計算。最後に全部決まった後に出現する数字が矛盾がないかどうかをチェックする。特にメモする必要はないし、そもそもメモできないくらいには桁の値が大きく変わる。

1000

ある文字の中からN文字選ぶ、というのを複数の集合に対して行う。すべての文字は一度までしか使えず、今までに使った文字が与えられる。後何文字使えばすべての集合の条件を満たせるかを計算し、アルファベット順で先頭にくる文字列にして答えよという問題。

最大流のグラフに変形すればおしまい。各集合をノードとみなして、各文字もノードとする。その集合で必要な文字からその集合への大きさ1の枝をはり、必要な文字数の大きさの枝を仮想点としての終端点にはる。この変形をした後に、既に使用した文字から流せるだけ流し、残りに必要な流量分だけ、使っていない文字から流す。このときアルファベット順で先にくる文字から流し始めれば良い。流し終わればそこでおしまい。終わらなければ問題の指示に従ってその旨答えれば良い。