Round3

最後のオフラインラウンドにして、最後の戦い。この上がいきなり100位通過になる時点で、抜けられるわけないじゃん。偶然いい入力を拾って命拾いしたみたい。(点数がばらつくようにするために、意図的にやっている可能性もあるけれど。)マシン落ちたり、解けない問題最初に開いたりしたのがなければボーダーより上にいけたとは思う。

関係ないけど、サブミットした瞬間にチェックするように修正入ったんだろうね。

A

全ての角が90度をなす多角形の外部の点で、その多角形にx軸方向ないしy軸方向で挟まれている点の数を答えよ、という問題。

多角形求めることすらできず断念。

B

ある点から目的の点まで移動する。壁にビームを照射すると2点を連結することができる。目的地までの移動最小マス数を答えよ、という問題。

現在位置とビームの照射場所を一つ覚えておいてBFSする。ビームの照射場所を覚えないでも通るようにsmallが設定されているっぽい。ビームの照射場所の二つ目は壁に到達したときに作成すればいいので覚える必要がない。という感じ。

C

試験時に他人の解答を覗けないように座席を選択するとき、最大何人まで同時に試験を受けられるか答えよ、という問題。

smallは全探索。largeは制約からグラフを作成して全ての点の次数が0になる部分グラフの最大点数を求めればいいらしい。制約が二部グラフになるらしい。

D

ナイトが右下方向のどちらかに移動して、目的地を目指す。途中にいくつか通れない場所があるとき、目的地に到達する方法が何通りあるか答えよ、という問題。

smallはDPするだけ。largeは色々組み合わせなどを用いるらしいが詳細は不明。通れない場所は高々10箇所程度しかないので、それ以外は高速に単調な処理ができるっぽい。

座標を変換すると単純な格子にできることを使えば問題は大分クリアになるかも知れない。