コンテスト中にサーバーが落ちてしまい残念だけど、Div1は問題セットとしてかなり残念だと思う。
複数人writerでtester権限がないと他の人が書いた問題が見られないので、ちゃんとそういうのを共有して
ジャンルが偏らないようにするべきだと思う。
Div1Hard以外のwriterをやっていました(Div1Hardはdreamoonさん)。講評を書きます。
http://topcoder.g.hatena.ne.jp/rng_58/20101006スタイルで書いていくことにします。
点数の横に書いてあるのは 2500 / 2000 / 1500 の人の目標時間です。
OkonomiyakiShop (DivII 250, 2/2/3)
これはやるだけだと思います。実際に以前Cat SnukeとWolf SotheでOkonomiyaki shopに行きました。
LostCharacter (DivII 500, 5/7/10)
greedyです。
文字列iが何番目に入るか調べたいときは、文字列iの'?'を全部'a'として、他の文字列の'?'を全部'z'にしてソートすればよいです。
TreeCutting (DivII 1000, 15/20/30)
dfsして、ある頂点を見たときに後何個数字があまってるかor足りないかを返していきます。
あとは頂点それぞれでvalidかどうかを見ますが、何通りか場合わけすればよいです。
OkonomiyakiParty (DivI 250, 2/5/15)
ソートして二つとって差がK以下ならば真ん中からM-2個選ぶ方法の個数を足す、とか、左端を総当りしてどこまでいけるかを
数えてM-1個選ぶ方法の個数を足す、とか。Div1Easyのなかではかなり簡単だと思います。
MakingTournament (DivI 500, 20/45/-)
説明が難しい2^K*2^Kの行列で行列累乗します。トーナメントを常に右の人が勝つものだと置き換えて、
「右に参加者を足すときにround iまで勝ったことがある人が1人以上あまっている」みたいな集合を1つのものだとします
round iまで勝つ人を追加できるのはround iまでのものはすでにフラグがついているときで、これを追加すると
round i-1まではすべてフラグが消えます。
