645.1

前回はなかった。

250

区間が与えられて、隣接グラフができるので、それの最小点被覆問題のような気がする。

要は開始と終了があるので、接しているどれか一つを選ぶと接しているのも選ばれたことになるから、全体を選ぶように最小に選ぼうという問題。

区間なので、終わりの小さい順に、できるだけ遠くまで行ける範囲は選択済みにして、使用済みのも使いつつ、がんばればいいだけらしい。適当なDPをがんばっても通るとは思う。

500

点集合を指定された点のいくつかのうちの一つと点対称に移動するという操作を延々と繰り返して、目的の状態にできるか答えよ、という問題。

どうやら点集合の操作の回数の偶奇が同じなら相対位置は変わらないらしい。(回転操作だから当たり前っぽい。)で、ある点に注目したときに、移動できる点の集合は、点対称の中心へのベクトルの二倍の任意の組み合わせで決まる。問題はそれぞれについて移動回数の偶奇が分からない(考えていない)ことと、目的の点に移動できるか考えていないこと。

取り敢えず最初の点を決めて、全部の点を対象に偶数回で移動できるか奇数回で移動できるか調べて、後は他の点を相対位置から算出してやって、全部の点とマッチするのがあるか調べれば良さそう。

900

見てないけれど、素直な問題だったらしい。良く知らない。