ABC191

5完1ペナ。自分はunratedだし録画しようと思ってたけど、体調が悪めなので結果を出すことに専念した。unratedなコンテストで黄パフォ相当を出すの初めてなのでよかった(ホッとした)。BEは素直だったけど、ACDにかなりの癖があり、Fが難しかった。得意セットだったとは思う。

A - Vanishing Pitch

いや最近のA難しすぎるでしょ。まあよく読むとT秒後の位置は整数にしかならないし「両端を含む」とわかりやすく書いてあるし、その通りに書けばいい。

B - Remove It

簡単。入力を読みながらXと異なるのだけ出力していく。AtCoderなので最後に余計な空白が入ったり改行がなくても大丈夫。

C - Digital Graffiti

すぐには意味がわからないし、わかっても難しそう。問題文にある3つの条件をよく読み込む。辺はタテヨコにしかないので、それぞれ数える方針。ヨコになっている辺は、縦につながった2マスの色が異なるときに存在している。横に連続していたらまとめる。周囲は白マスなので(端は辺でないので)、左から見ていって辺かどうかが何回変化したかわかればいい。変化回数を2で割れば答え。

D - Circle Lattice Points

Cを通して順位表を見ると正解者0なので驚く。面積からわかるのかなとか考えるけどまあ無理。10^5なので候補のy座標を全部試すことはできる。よく見ると整数で考えても10^9くらいにしかならず、円の中にあるか判定できそう。オーバーフローについてもっと詰めていく。絶対値が8*10^18くらいまでならlong longで表せる。2*10^9の2乗の2倍がいけるということで、これなら整数だけで判定できそうだ。ということで、10000倍して整数に変換して、10000の倍数の格子点を数えることにする。負の数も含めきっちり範囲内最小の10000の倍数とかが知りたいが、頑張る(Y-Rの符号で場合分けして切り上げ、今考えると不要だったか?)。各yに対して二分探索でxの範囲を求めるが、範囲なので単調性がない。そこで、x座標がX行ってるかで分けて2回二分探索する。二分探索の範囲はX-RからX(境界はちゃんとする)。二分探索の結果においても負の数の処理が必要だと気づいて、頑張って手抜きした(10000の倍数だけ考えることにして、範囲は両端を1伸ばせば安全で、Xからはみ出た部分は手動で(?)trueかfalseを返す)。しかしWA。ほとんどの提出がペナルティを出している中、自分もそうなのはとても悔しい。自分では解けているつもりなので、コンテスト中にミスを探すのは不毛だと考えそのままEへ。

Fが行き詰まったときにチラチラ見ていたが、終わりが近くなって見直したらdoubleからllへの変換で0.5を足していた。こんな一番最初の簡単なところで負の数を見落としてたのね。ありがちではある。roundに変えて、脳内で確認して、提出、AC。これで通らなかったらかなり機嫌悪くなってたと思う。

E - Come Back Quickly

これはN回ダイクストラするだけなので簡単。しかし、自己辺や多重辺があるのでしっかり考える必要がある。自己辺は場合分けしてもいい。自己辺の多重辺があるかもしれないことに注意する(忘れてて実装してて気づいた)。他の多重辺は問題なさそう。さて、戻ってくる必要がある。例えば、1手で行ける町とコストを列挙し、それらの町からのコストがわかればいい(逆辺でダイクストラ)。しかし実装が煩雑で、できればダイクストラ法の処理に手をつっこんでなんとかしたい(ライブラリの中身がわかっている前提の行動をとりたい(わかってないなら時間がかかって仕方ないし、わかってるならいい処理を思いつきそう))。出発地点のコストをいじるのは危険そう。出発地点へ戻ってくるような辺を処理しているとき、自己辺も含め戻ってくるコストの候補というか最小値を与えるような辺が必ず現れるからその最小値をとれば答えでは?自己辺を特別扱いする必要もなく、ライブラリにちょっと手を加えただけのコードでAC。理想的な動き。今考えると、あと1手で戻れる町までの最小コストがわかったときにそこからの辺を処理するので、わりとそのままだった。

F - GCD or MIN

gcdだけとして簡単なのか?いやそれは順番によらず全部のgcdだから1通りだ。では、minを入れる順番とかに無意味なものはないか?いくつかのgcdをとったものとminをとるときのことを考え、そもそもgcdは大きくならないし、色々わかってくる。要するに、1個以上選んだgcdでmin(A)より小さいものをいくつ作れるかという問題だ。わかってみればそりゃそうで、min(A)よりも大きいものは作れないし、min(A)は作れるし、それより小さいgcdは他のものとminをとり続ければ作れる。さて、0個以上を選んでgcdとったときの値の集合は、最初のi個の中から選んだときというDPで(計算量はともかく)できそうだ。setを使うとか考えたけど、vectorに入れてってsort, uniqueしてもいい(定数倍の問題だけど)。ただ、計算量というか、小さめの素数をたくさん持ってるとgcdでかなり多くの数が生成されそうだ。8個のA_iで256個できるよね。小さい素数はそんなにないけど、2000個もあればかなり大きくできるんじゃないかなあ。途中でA_0の約数がわりと少ないことに気づいて実装始めちゃったけど、よく考えたらそんなのが2000個あるんだからね。これを落とすケースを作る自信はないけど、さすがに想定解として明快に間に合うものがあるはずで、それを探し続ける。Dを通してないけどFに専念できるのは、unratedのメリットだと思った(ABC本番には違いないから、集中して考えることもできる)。しかし、行き詰まった。コンテスト中は時間の関係でできないけど、もうちょっと周辺を調べたいと思った(ほんとか?(何を調べるんだ))。