429.1
問題自体は簡単なセットのはず。250が一番難解だった。
250
高々100x100の二次元文字列が与えられる。その内部に部分的に矩形を全通り取り出して、それに含まれる文字を種類ごとにカウントする。最終的に各文字は何回カウントされるか、という問題。
何も考えずにやって100^5になってたのを100^4にしたら通った。実際には100^2でできるというか、?瑤兵阿鬚舛磴鵑伐鬚韻个いい蕕靴ぁＮ狼擦任笋辰燭里濃?屬???辰燭??進?彘芦鬚垜鈇??屬??辰燭隼廚Α?
500
AとBをX:Yで混ぜる、という式がN-1個ある状況で、N個の全体の混合比を求めよ、という問題。
混ぜたものを同じグループと見てグループを併合していく時に、各グループをそれぞれ何倍すればいいかを計算する。最後にgcdを取る必要はあるけれど、途中は取らなくても整数溢れはなさそう。特定のものから開始して、一つずつ追加していく方式だと、多対一のマージをやるだけでいいので実装が楽になるのかも？
1000
ある図形に、二つの図形を敷き詰める方法を答えよ、という問題。敷き詰め方が複数ある場合は辞書順で先頭のものを答える。
図形は1x2のBと2x4から上段中央の二つを除いたのAの二つ。一番上の行から順に敷き詰めていくことを考えるとき、二つ並んでいる状態ならBを置かざるを得ないし、一つしかないならAを置かざるを得ない、みたいな感じでgreedyな敷き詰めを試す。最後に2x4のBのうちA+Bに置き換えられるものを右上から順番に探す。辞書順に先頭のものを答えるのが目的なので、置き換えることが可能な場所があったら置き換えて次の候補を検査すれば良い。置き換えられるかどうかは、実際に置き換えてみて、すべてのBの隣にちゃんとBがあることを確認すれば良い。
