TopCoder Member SRM491 Div1

250

1からNまでの数を立方体に書いて、サイコロを作る。向かい合う目の和はどれも等しく、K以上じゃなきゃいけない。同じ数を2回以上使っちゃいけない。回転させて同じになるものは1通りとして考える。何通りできる？

やるだけ。同じ目の組み合わせで、回転を同一視したとき2つのサイコロが考えられるのは有名

600

16個以下の文字列が与えられる。同じ文字列の中で文字をどんな風に並べ替えてもいいから、Trieを作ったらノードの数が最小になるとき、そのTrieのノードの数を求めよ。

おそらく、ビットDP。

900

2つのpileがあって、次のことをK回繰り返す。
「両方のpileから1つずつの数字を取り出し、それをA,Bとする。Jiroはmax(A+B, A*B)点を、Harukoはmin(A+B, A*B)点を得る。」
(Jiroの点数)/(Harukoの点数)の最大値を求めよ。

二分探索×最小費用流？　で行けるんじゃなイカ？って思ったけど最小費用流書けないorz

結果

600で「ab bc ca」で2人落とせた（「a→b,c」と「c→a」はつなげてノード節約できない）。
900はgreedyみたいなことをしているひとが2人いたけど落とせるケースを持ってないので落とせなかった。
でも寝た後見たsystem testで600が落ちてた…

oxx +100 338.67 72位（1完だけど最下位で済んだ）
結果がなかなか出ない。no gameになってしまいそう…
2日経ってRatingが出た。2167 -> 2239