549.1

これ解けない自分って...。

250

二つの円錐を重ねたときに、下の円錐の方が径が大きくて、上の円錐の方がとがっているような、円錐のペアは最大で何組作れるか、という問題。上用の円錐と下用の円錐は分離されている。

要は二部グラフマッチングをやるだけ。適切なソートで工夫すれば解けるだろうけれど、考えるのがめんどくさいので...という明らかに出題者の意図を無視した解法。(だけどこれに関しては出題者が悪い気もする。)

上下どちらの円錐か覚えておいて、とんがり度合いでソートする。上に乗せるヤツは自分よりとんがってないヤツの上に乗れると思うことにして、そのときに自分よりも大きいヤツのうち最小のヤツを選択していくことにする。以降では上に乗せるヤツはよりとんがったヤツが出てくるので、径の制約を無視すれば、乗っかれる円錐の集合はどんどん大きくなる。先にできるだけ小さいヤツを使っているので、以前の選択でより小さいのを選択することはできないし、もしそれしか使えないのだとすると、それを使ったヤツもそれにしか乗れないので、ペアの数は増えない、とかそういう感じ。

600

二次元盤面上にコインが隠されている。コインがあり得る場所が与えられていて、実際にコインがある数は、行と列ともに、あり得る場所の数と実際にある数の偶奇が一致するという条件を満たす。このとき、調べて良い回数が与えられるので、最悪の状況でも回収できるコインの枚数を答えよ、という問題。

DPすれば、正しい配置の有無が分かることは分かる。それだけ...。頭が悪過ぎて分からない...。

950

見てない。戦略的に見ても良かった気はするが、リハビリ中につき...。