コンテストへのリンク
A - Next Alphabet
Pythonならchr(ord(C)+1)と書けます。
B - Achieve the Goal
N*Mから今までの合計を引きます。満点がKなので、Kより大きいとき-1。
C - Welcome to AtCoder
実装問題。今、コンテスト時の提出を見るとちょっと面倒くさいことをしていた模様。全ての問題に対して、その問題でACできたか？ を前処理していました（ので、インタラクティブだったら対応できないコードになっていました）。そうしなくてもできますね。
けど、それを前処理した方が分かりやすい気もするので、一概に悪いとも言えないか。
D - Maze Master
全点からBFSしました。
ワーシャルフロイドやダイクストラも考えましたが、BFSが書きやすいかな、と。
E - Max-Min Sums
ABC150のE、第6回 ドワンゴからの挑戦状 予選のBと似たタイプの期待値の問題。
ただし、この問題では、最大値・最小値を別々に考えるという工夫が必要だった。それに気付きさえすれば大体同じように考えられる。
F - Enclose All
典型問題だそうですが、知りませんでした。
私がした実装は、
・まず、全体を正方形にする
・その正方形を100*100に分割し、その中で一番、最小包含円の半径が小さくなる点を見つける。
・その点を中心に、元の正方形の一辺の長さの1/2の正方形を作って、同じことを繰り返す。
といった感じです。
最初は、ある点からx,y方向それぞれへの傾きを調べて……みたいなことをしようとしたのですが、WAになったので切り替え。
最小包含円の半径を値として持つ関数を考えたとき凸性が成り立つので、ACした解法は、嘘じゃないと思うけど……。
ともかく、凸性を利用した解法を考えていたのですが、コンテスト中はその凸性にあまり自信を持ててませんでした。（だから、厳密に凸じゃなくてもACできそうにも思えるコードを書いていたと思う）
公式youtube解説放送も、凸性を利用して三分探索していますね。解説放送を見たせいもありますが、（証明を厳密に記述するのは多少難しいかもしれないけど）凸になるのは当たり前な気もしてしまう……。
少なくとも、コンテスト中に「一次元のときと同様に上手くいくよね」くらいの気持ちは持ちたかった。
0 件のコメント:
コメントを投稿