AtCoder AGC030 1完 つらい (附) B 貪欲解法概略

　配点をみてやばいとは思ったがその通りになった。1完でレーティングが更に落ちる。

AGC030 プレイスタイル

　Aの計算、単純なのでこれ間違えたらヤバいと何回も検算してしまい、結局毒入りと解毒剤を混乱したりして提出に19分もかけてしまった。ということでその時点でかなりケツの方になる。でももう一問くらい解けたら挽回だ。とは思いつつできもしないのにDくらいまで見てしまって終わり。

B

概要

　Bはケツから決めていったら一意だからN*順逆でそんなに計算量ないとはおもったが、それをコードに落とせず。入力例2であれこれ書いてたのがこれ。

Bのメモ

　2→1→3→0→4→原点と逆算していったら一意。区間をN-1決めて順逆試すだけ。性懲りもなく計算で一発で出そうとしてるのが絵に出ている。

(20181230 朝) ということでこの方針で通しました。こんな簡単な方針は時間内に整理したいとこだけど、現実には細かいところで間違えてバグ取りに時間とられるのでこの方針で出すのはつらいか。たとえば↓これでは折れ曲る回数を計算で出してるけどそんなのやってると絶対間違える。そのへんがこのハゲ頭の計算能力の限界か。

atcoder.jp

貪欲解法概略

　問題の条件より一周したら終わる = 一周以上はできないという制約があるのでできる。先頭と最後は別にしてその中間のN-1の区間を見て(上図の)一番下にその最も長い区間を取り、その後折り返し原点を挟んで未到達の木(点)で一番遠いところを押さえていき、原点を挟んでこれ以上折り返せなくなったときスタート地点に立つ。区間は順逆の2通りある。先頭と最後は順逆一方通行の2通り先頭へ逆回りと最後まで順回りの2通り試す。これは木(点)の分布で一意に決まるので絵を書くときは距離を考えず点が何個あるかだけに集中して書けばよい。木(点)間の距離の大小でこの距離が変化し、その変化がわからないので(N-1) * 2 + (2*2) 2 = 2N 通り試すのだから問題ない。(N==1のとき2通り)(N==1のとき、先頭へ逆回りと最後へ順回りで両側押さえられる)。

　上図の区間だと

• 2→1→3→0→4→原点

• 1→2→0→3→原点

　の2パターン取れる。繰り返しになるが、とれる線は決まるがどちらが最長かはこれだけではわからない( = 他の区間とどっちが長いのかもわからない )ので全部試す必要がある。 ここまでは時間内に出せて、これから先、コードに落とすのが時間内にできなかった。一時間くらいあったので、これは余裕とおもいながらできなかった。結局は手が遅い。つらい。

レーティング

さらに落ちたレーティング

　まぁでもなんとか緑から落ちるのは免れた。うーむ。この歳でこんなことに時間をいつまでも溶かしてはいられないのでもういいかげんやめたいところだがやめ時が見えない。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造