pretestはDまで。
Eはコンテスト五分前に正しい解法にたどりついた。
B. Inflation
・他の要素に足すより、P[0]に足した方が得だと気付く
・二分探索
でOKだけど、第一点目は結構思いつきにくい気も。
なお、二分探索の上限の見積もりを間違えて1WA（k=100のときが一番大きくなるかと思った。本当はk=1のとき）。安全に上限を定めておくべきでした。
E. Pattern Matching
さっきのyukicoderでもトポロジカルソート関係の問題が出てたんだから、これは解けなくちゃいけなかった。
難読（だし、日本語で簡潔に説明するのも難しい気がする）だけれど、読み解ければ、各string sに対して、それとパターンマッチするものたちを列挙したとき、その中でmt（並び替える前のPの中でmt番目のもの）が最初になるように並び替えれば良い、という問題になる。
パターンマッチするものを列挙するところでO(n*m)かかる気がしたのだけど、k<=4なので2^4でいける。
k<=4にちゃんと着目すべきだった。
0 件のコメント:
コメントを投稿