268.1

250

辞書の中の語を二つ組み合わせてできる語を考える。既に辞書にある場合や、組み合わせが複数通りあるものの数を答えよ、という問題。

辞書と新規にできた語を覚えておいて、出てきた回数が複数回のものをカウントすれば良い。同じのが出てきたらカウント済みでなければカウント、というのでも同じ。

500

グラフが与えられるので、オイラーパスができるように追加する最小の辺数を答えよ、という問題。

取り敢えず連結成分に分解して、各ノードの次数をカウントする。できるだけ奇数次の点を使って、連結成分を結合するように辺を追加する。最後に奇数次の点が2個よりも多いなら、それらの間に辺を追加する。というのを地道に計算するだけ。こういうのをサックリ書けるようにならないといけない。

1000

/*と*/でできるコメントの入れ子がある。入力はvalidではないが、validな最長部分を除去した後の文字列の長さを答えよ、という問題。

区間iからjの文字列の長さをDPで求める。入力がvalidでないケースもあるので、再度DPで0からN文字目までの長さを求める。実装が面倒。(うまくやればDPを一つにまとめられるかも知れない。)

そもそも問題文の細かい仕様を理解できなかったので、取り敢えず全探索するものを作ってみたところ、validじゃない入力のケースで大幅にうまくいかない模様。単純なメモだと、JavaのHashSetが重いせいか、問題の解決にはならなかった。実際には全探索じゃなくてDPの方がすっきりコードが書けるような問題設計になっていたらしい。英語読めない...。