ABC151

なんとか全完。Dではまってもう俺はダメなのかと思ったが、lowestは更新せずに済んだ。さすがに精神状態がよくないなあ。

A - Next Alphabet

予想はできていたけどcout << c + 1 << endl;ではダメ(足し算した時点でintになって、代入とかもないのでcharに戻らない)。charにキャストして提出したが、提出後、c++;しとけばいいと気づいた。今、cout << ++c << endl;でいいと気づいた。いい問題だな。

B - Achieve the Goal

Bで既に問題文が読めない。いやさすがに読める。合計点をN*M以上にしたいという話。K点取ってもダメなときは-1を出力。K点超え(スキーのジャンプを連想してた)だけでなく0点未満もないことに気づかずサンプルで引っかかる。直して提出すればさすがにACなんだけど、自分できっちり考えたいところだった。

C - Welcome to AtCoder

こっち系のCかあ。複雑で怖いし時間がかかる。AC後にACしてもペナルティ付かないのは知ってたが、AC後のWAもそうなのは明示的には知らなかった。WAの回数を各問題で持っておいて、ACしたらビットマスクをかけて区別する。自分がこれを早解きするのは無理なので仕方ない。

D - Maze Master

最大で20*20なので(N=max(H, W)として)O(N^4)で行けそう。グリッド上のBFSのライブラリを取ってくる(使い慣れないので不安だが、まさに使い慣れないことによるミスが出た)。スタートとゴールを全探索すればいいが、スタートからBFSすれば全部のゴールについて最短距離がわかる(ここで最短距離がO(N^2)になることに気づく(あんま関係ないけど))。で、WAになった。壁の中からスタートしてるやん!ということで直して提出してもWA。これは声が出た。少し考えて正しいコードにしか思えないのでEへ。

EFを解いて戻ってきた。時間がないのでBFSを改めて書き直すのはきつい。頑張って考えると、スタートも未訪問マスも0としていた。スタートへ引き返す動きができてしまう!ライブラリの元コードを読んだときの違和感はこれか。未訪問は-1、それ以外は最短距離として区別していたんだ。直してAC。ここで全完できたのは大きい(Dを通せてなかったらlowestを更新して精神がもっとまずいことになってた)。

E - Max-Min Sums

最大と最小の差。ということは、Aをソートして選ぶ区間を固定すればよさそう。幅Wの区間なら、端は選ぶとしてW-2個からK-2個を選ぶということになる(区間同士で重複はない)。これだとO(N^2)なのでもう少し考えるが、なかなか難しそう。ということで、両端ではなく片方だけでいいのではないかということに思い至る。これは天才。最大値の寄与と最小値の寄与は別々に計算できるのだ。Aを昇順ソートして、最大値としてありえるのはA[K-1]からA[N-1]まで(0-indexed)。端を除いてi個からK-1個を選んでA[i]を掛ければいい。最小値も同様だが、Aをstd::reverseすればなんと全く同じコードでいい(こういうのに気づいた瞬間が楽しいよね)。最大値のから最小値のを引けば答え。

F - Enclose All

最終的に、どれか3点の外接円になっているはず。ということでN点から3点選ぶのを全通り試して外接円の半径の最大が答えだと考える。しかし、サンプルを見てN=2のケースもあると気づく。これは例外処理して、しかしサンプル3は通らない。なるほど、ある3点について外接円がそれらを含む最小の円だとは限らないのか(一つの角が180度近いと外接円がクソでかくなる)(今気づいたが答えがどれか3点の外接円になってないケース普通にあるな)。その3点を含む最小の円は、その三角形の最も長い辺を直径とするものだ。さて、3点を含む最小の円が外接円になるかどうかはどう判定する?辺の長さが直径になるときその辺の向かい側にある角は90度なので、90度を超えるかでいいか。それも、一つでも90度を超える角があったらダメだ。ここで、3点を順番も区別して全探索する方針に切り替える。3点が一直線上にある場合によりバグりやすくするため。バグが隠蔽されるコードは怖い。できればサンプルでバグってくれと。あとは書いていく。サンプルにも助けられて一発AC。

外接円の半径の求め方はググった。ここは「ごめんあとで勉強するから今時間ないから」と言って公式を信用した。こういうのあまり好きじゃないけど、コンテスト中は本当に時間がないので仕方ない(まともに考えてたら1時間くらい吹っ飛ぶ)(もちろんこの問題で使えるくらいの理解は必要)。角度は内積で求めるのが普通だと思ったけど、余裕がないので思考停止atan2した。

この解法の正当性を考える(解いてる当時はちゃんと考えてるつもりだったがやや怪しかった)。最小の円が3点以上と接しているなら、その3点の外接円になっている。ここで、90度を超える角がない3点を選べる保証はあるか?いやなんもわかってなかったな。確かに、選べなかったら円をより小さくできそうだし小さくできないようにばらしたら選べそうだしな。でも証明できない。じゃあ、最小の円が、90度を超える角がない3点と接している場合で考えればいいか。そのときは、そういう3点の外接円は探索されるし、より大きい外接円を作る3点も存在しない(存在したら、その3点を含む最小の円が全体を含む最小の円より大きくなってしまう)。また、この最小の円の直径を超える辺がないのは明らか(全部の点を含む円なので)。ということで、この場合は正しく求まる。そうでない場合は、いや眠くなってきたので略(ダメ)。