210.1

前回気付いていたものの、書き忘れ。古い問題セットが復活していた。

250

ドット抜き記法でIPアドレスが与えられたときに、可能なIPアドレスをすべて答えよという問題。

すべての箇所にドットを入れてみて、うまくいったら正解。O(N^3)回すだけで、後はちょっとした実装。

500

あるノードの親子関係が与えられるので、各ノードの子孫の数を答えよという問題。木じゃない場合は空リストを返す。

すべてのノードについて子リストを持っておいて、処理の終わっていない子を持たないノードを順番に処理していく。処理が終わらなければループしているので木ではない。処理が終わっても、ルートノードの子孫の数が足りなければ、木に含まれないノードがあるので木ではない。各ノードの子孫の数は、自分の子リストの子孫の和＋子の数。

1000

グラフが与えられるので、任意の二点間の距離の和を指定された長さにするには、グラフを何度傾ければ良いか答えよ、という問題。(があり得ないくらい長い英語で書いてある。)xy平面での距離についてのみ言及されていて、z軸方向の距離がなくなる。(つまり傾ければそれだけ短くなる。)傾ける方向はx軸を中心にy軸方向。

グラフの辺の長さを傾きに応じて変更しながら、バイナリサーチすればいいだけの問題。任意の二点間の距離はWarshall-Floydを回せば簡単に求まる。

Warshall-Floydを回す前に自分自身への長さを0にするのを忘れたり、距離の計算をintでやってオーバーフローしたりしたことを除けば、おおむね最初に思い付いたことを実装するだけ。実際のSRMで出たら解けないと困るなぁ、というレベルの問題だと思う。最近の難易度から考えると500点問題扱いになってもおかしくないかも。(問題を簡潔に書いておけば。)