GCJ 2014 Round2 - れどこだ目指すよ！　(；`・ω・）

1494位あたりでTシャツゲットならず。。。(TシャツラインはABとD-small早解き)
いくつか既出な問題だったようで、日頃勉強してないのが悔やまれる。

戦略としては毎度のごとくptの小さい問題から解いていった。
結果は、A、B-small、D-small。

解けた。

複数のCDに複数のファイルを、「同じCDに3つ以上のファイルを入れない」「一つのファイルを複数に分割しない」という制約を満たしつつ書きこむ。必要なCDの最小枚数を答える。
大きい容量のファイルからペアを作って書き込んでいくgreedyで解いた。

「more than two files」を「2つ以上」と読んでしまってサンプルが意味不明で提出が遅れた。。。

smallだけ解けた。

ある数列が与えられ、隣接要素を交換することが許されている。数列がA_1A_{M+1}...>A_Nとなるように必要な最小交換回数を答える。(ただし、A_iはすべて異なる数)
若干のDP臭を感じてsmallだけ全探索で解いた。

既出関連問題は「たのしい家庭菜園」というJOIの合宿の問題らしい。
http://www.ioi-jp.org/camp/2014/2014-sp-tasks/index.html

解けなかった。

グリッドで表現された川の途中にいくつか建物があり流れをせき止めている。南端のグリッドから北側へ流量1が流れるとき、北端での流量はいくつか答える。ただし、各グリッドは流量1しか通さない。
xoo
ooo
oox
の場合だと、真ん中のoセルが流量1しか流さないので、答えは1。

あからさまにノードに制約がある場合の最大流(蟻本でやってた)で、やるだけと思ったらグラフのクリア忘れをしてどんどん追加するようなことをやらかして、解けなかった。(クラス化しておこう・・・)

グラフは各有効なセルの上下左右(戻るのもあり得る)に張ればよい。各セルは2つのセルに分割して、sから南端、北端からtへ辺を張ってs-t最大流。

smallだけ解けた。

複数の単語をN個に分けて、trie木を作る。各trie木で必要なノード数の合計の最大値とその最大値となるパターンの数を答える。
全探索以外に思いつきそうにもないので、シミュレーションした。