今年最後のSRMなんだけど、結局いまいちな結果に終わってしまった。 250 一直線上に木が立っているので、木の一番上の点が同一直線状に乗るように木を削るとき、少なくとも何本削らないとダメか答えよ、という問題。 直線として考えられるのは元の木のうちの…

2章付近 クロスフリーとかラミナーとか後の方で使うっぽい話がされているけど、良く分からないので保留。木構造で表現できるのがクロスフリーで、DAGっぽくなるとクロスしちゃってるってことなんだろう、多分。(くらいのいい加減な認識。) 強連結成分の取得…

A点からB点への移動コストが与えられるので、0番目の地点にN人の人がいて、それぞれ、1,2,...,N番目の地点に行って帰ってくるとき、最小のコストを求めよ、という問題。 行くだけのコストならダイクストラをやるだけ。帰ってくるコストについては、開始点が…

連結なグラフが与えられるので、各ノードを除去したときにいくつの連結成分に分かれるか答えよ、という問題。 全部試すだけの問題だった。ノード数が1000なので最悪ケースのときにTLEすると思うが、そんなケースは来ていない。問題はノード番号の付け方で、…

取り敢えずこの本には読書タグをつけておいたらしい。別のタグにしときゃいいけど、多分そんなに本なんて読まないしメモしない。 アウトラインというよりは、大事そうなところだけ拾い読みしてるっぽい雰囲気を出しつつメモ。(一応全部読んではいるけど、理…

250 1からNまでの数字を高々1度だけ使って、サイコロを作る。向かい合う面の値の和が等しく、かつK以上にする方法は何通りあるか、という問題。 和を決めると、数字のペアが何通りあるか分かるので、3つ取り出す。後はそれをサイコロにするので2倍するだけ。…

250 Mの倍数すべてについて、それより以上で最小なNの倍数との差分の期待値を答えよ、という問題。 GCDを見てやれば、Nで割ったときの余りとして出現するものが分かり、それがループするので平均するだけ。 550 見てないけど実装系だったらしい。 1000 無限…