B2までの三完でした。レートは若干下がったものの、Aで三十分かかったことを考えれば良い出来かと。
A. Searching Local Minimum
Aで出題されて、インタラクティブなら、二分探索系以外ありえない！ ……と問題を開いたときすぐ思ったけど、解くまでかなり時間がかかってしまった。
しかし、「二分探索を使いそう」以上に、この問題から得るべき知見はない気もする……。
「極値を求めるから三分探索」としてシステムテスト落ちした人は結構いたようです。noshi91さんの昔のツイートが話題になっていた。
うーん、でも今回みたいな離散的なやつなら、三分探索で極値が求まるっていう気はあまりしないので、私は引っ掛からないかな……。凸関数じゃないと求まらないイメージがあったけど、この記事を読むと、それで大体正しそう。
B. Painting the Array
B1もB2も最初に考えた解法は間違っていた。（B1は本当にただの貪欲を、B2はDPの遷移がおかしかった）
けど、WAを出している人が多かったのを見てそれを提出せず、全パターンの色塗りを試すを愚直全探索＆ランダムケースでテストしたおかげでACできた。
このテストを書かなければ正しい解法に至れたかも怪しいので、今回は、愚直を書いたのは正解だったんだと思うけれど、どういうときに書くべきなのかは分かっていない。それなりに時間がかかることだしね。
C. Continuous City
この問題の類題。
類題経験があったから解けるべきだった気もするけど、ちょっと条件が違うので、「２ベキを使う」ということ（これは、類題経験がなくても分かる）以外は生かしにくいので仕方ない気もする。
二頂点間にパスは一つしか引けないが、引くパスの数は制限されていない、というのが重要。
・4→3→2→1→ゴール
というパスを考えたとき、
・1からはゴールに長さ1のパスを。
・2からは1とゴールに長さ2のパスを。
・3からは2と1とゴールに長さ4のパスを。
・4からは3と2と1とゴールに長さ8のパスを。
という風にしていけば、1から15までの長さのパスは作れる。スタート地点から、これら全てにLのパスを繋げれば、スタートからゴールへ、長さLからL+15のパスが作れる。
それだけではLからRの全てのパスは作れないけど、後の残りは、スタートから各ノードへ割り振る感じにすれば良い。
先の決め方で、
・1からは長さ1～1のパス
・2からは長さ2～3のパス
・3からは長さ4～7のパス
・4からは長さ8～15のパス
が出ているため、各ビットが立っているかを見る感じで決められる。
（なお、最初からこの決め方をするのは負辺が必要になるため、無理）
0 件のコメント:
コメントを投稿