NOMURA2020

2完。頭が苦しい。

A - Study Scheduling

繰り下がりを考えたが、単に時と分をそれぞれ引き算するだけでいいと気づいた。この問題文を読むのはかなり大変だが、起きてる時間からK分を引けば答え。

B - Postdocs

問題文やサンプルを見ていると、どうしても「DP」という文字列が目に入ってくる。DPで解けるのか気になるけど、まあフラットに問題を考えていく。ある'?'に'P'を入れたときの「博士・PD 指数」（この名称長すぎん？）への寄与と'D'を入れたときの寄与を考えると、'D'を入れれば1（以上）増えることに気づく。一方、'P'を入れても"D"は増えないし"PD"が高々1増えるだけ。ということで、'D'を入れて損しない。'?'を'D'に変えればいいので実装は簡単。

C - Folia

なんか脳が働かなくなった。よくあるじゃん漫画とかで。ロボットが難すぎる問題を与えられてショート（？）するの。

葉の数はわかっているので、その葉たちの親の個数の範囲を考える。最大値っていうけど、要するに誰かの親であるようなノードの数をどこまで増やせるかという話だ。しかし、N+1種類の深さのうち、深さ0と深さNの2つも特殊なものがあるので厳しい。上と下から攻めて値が確定するようなイメージでかなり難しそう。まず上から考えて、できるだけ多くの子を作り葉をA_i個以上にできるか判定する。できるなら、下から不要なものを削除していけばちょうどA_i個にできるはず。どれだけ削除すればいいかは、削除対象である親の数とその子の個数の最大値でわかる（子が少ないときは子は1個だけにするのがよさそう）。親の数とか具体的に何なのか無限に混乱した。そのままだとノード数がO(2^N)になるのでA_iの最大値の何倍かくらいで切る。それだけあれば次の子を作らせてもまだ大量に残るので（どうやらここが間違っていたようだ（子を2個にしているが、存在判定はそれでできても最大化のためには子を1個にする必要がある場合がある））。

頑張って実装してやや遅くなったが提出してWA。何度見直しても正しい。考察は正直そんなに自信なかったが、考え直すと正しいようにしか思えない。ということで虚無デバッグで終了した。これはつまらない。解けないのは仕方ないとして虚無の時間が長すぎる。最近ARC格が少なかったから「2年前の自分はARCをもっと楽しめばよかったのに」とか思ってたけど、こういうことね。これは楽しめない（毎回こうだとは思わないけど、こういうのが多いのはかなり厳しい）。

AGC044

0完（NoSub）。AとBを交互に考えていたが解けなかった。今日という日を楽しみにしていたが、AGCを楽しみにするのは思い上がりだったし、だからってAGCが楽しみじゃない人生は無なので、この人生はおしまいです。

A - Pay to Win

操作は逆にもできる。操作回数はO(log(N))でそんなに多くない。逆に考えたとき、5で割るには5の倍数になるまで増やすか減らすか。もっと離れた5の倍数にする意味はなさそう（割ったあとで動かした方がいいので）。Nが10000くらいまでならDPできるよなと思って書いてみたが、だから何。Dだけ極端に小さい場合が危険そう。10^8まで増やしてそこから3倍するとか。割る操作を続けて最後に-1の連続で減らすという順序のはずで、-1の部分は簡単なので、割る回数ぶんくらいの遷移でダイクストラ法とかできる？計算量がわからない。いきなり1/2や1/5になるから到達しうるノード数はNよりだいぶ少なそうなのにexp(log(N))（つまりN）くらいとも思える（パスカルの三角形のようにけっこう合流するのを見落としていた（だからといって計算量はわからないが））。書けば通るような気もしたが、この時点で残り1時間とかで、レーティングのことを考えるとB問題に注力するしかないところ。計算量がわからないのに、コンテスト中の時間を使って書く気にはならなかった（書くのも時間かかりそうだった）。

B - Joker

空席ができたことにより退出コストが減る範囲は広いのでさすがに愚直は無理。セグ木みたいので効率化できないか？さすがに形が複雑すぎるかなあ（よくイメージできてない）。空席はUnionFindで扱えそう。しかも、いなくなった人のコストがそのままその空席塊からのコストになる。逆から考えることもできて、人を入れていく。順方向と逆方向の情報を上手く合わせてできないかと考えていたが、何も考えてなかった。わからないことを2時間も考え続けると気持ち悪くなってくる。集中もできないし。スピードがないからどこへも行けない（スピードこそが質に直結するんよ）。思考をばらけさすことができない。コンテスト後、初期状態のコストの総和がO(N^3)なの気づいてなくてほんとひどいと思った。

夢

明日の病院で昼食が必要なので弁当を注文する。当日受け取り場所の地図。そこは敷地内だと思っていたが隣接する公園とのこと。おいしそうで楽しみ。

帰り道、腹が減ったので食べていくことにする。小さなフードコートみたいな場所。注文した弁当はチャーハンのようなものだったので、ラーメン（の一番安いやつ）にする。普通ならこれだけだが、いつもと違ってピンクの甘いものも一緒に頼みたい気分（デザートというより交互に食べる意図）。

餃子（普段はあまり食べないがここのはおいしそう）という選択肢もある。麺が伸びたりするのを踏まえ、食べる順番を考える。色々考えてかなり行ったり来たりしている。そろそろ変な目で見られそう。

ピンクのやつはいつの間にかミルモの黄色いプリン（カラメル無し）のイメージになっていた（「ミルモでポン！」とプリンて関係あるか？ミルモの髪が黄色いからか？「恋するプリン！」は影響してないという感覚だが）。のはずが、ぷよぷよフィーバーのプリンプになっていた（これも黄色いイメージ）。

ABC168

5完。今週無精進で心配だったけど、めちゃくちゃ楽しい問題ばかりでめちゃくちゃ楽しかった。

A - ∴ (Therefore)

3種類のサンプルがあるので、そちらのコピペミスは検出される。一の位が3は普通にif文書くとして、問題は0,1,6,8を書き間違えないかだ。結局、慎重にif文書いてACしたけど、できれば0,1,6,8をコピペしたいよね。ただそうするとコード量が無駄に増える。0,1,6,8をコピペして、そこからキーボードの数字を使わず n == 0 || n == 1 || n == 6 || n == 8 に書き換えればよかったかなあ（n %= 10; してある）。

B - ... (Triple Dots)

ちょうどK文字のケースはそのまま出力することに注意して書く。少し考えて s.resize(k); s += "..."; とした（文字列に対するresize珍しくて緊張した）。

C - : (Colon)

時計を傾けたり裏返しにしたりしても答えには影響しない。あとは座標求めて距離を計算するだけ。例えば長針（あ、長いとは限らないから分針という表現なのね）のx座標は B * cos(2π / 60 * M)。と思ったらサンプルが合わない。「各針は常に一定の角速度で回ることに注意してください」の意味がずっとわからなかったが、はい。よく考えたらそんな動きする時針あったら怖いわ（秒針はそういう動きするのも多い）。

D - .. (Double Dots)

ダイクストラ法の経路復元だと思ってyosupo judgeの自分の提出を取ってくる。しかしよく見ると「最小の移動回数」だ。えー絶対「最小コスト」とかそういう文字列が書いてあったよー（幻覚でしたね）。ということでBFSを貼る。BFS中に、その場所へどこから来たかを記録していく。

E - ∙ (Bullet)

(A, B)という座標にいるとして内積が0同士は一緒に選べない。しかし、入力は10^18までありえるため掛け算できない（いざとなれば__int128_tが使えるとは思ったけど）。

先に面倒なところを潰しておく。1匹以上とあるが、0匹以上とすることで1通り増えたものを求めることにする。また、(0, 0)に1匹以上いたら、それらは単独でしか使えない（3匹いたら3通り増やしてその3匹は除く）。

さて、ここからはベクトルとして考えてちょうど90度のペアを除く方法を考えればいい。ベクトルの向きを90度の違いを無視して分類できれば（分類したらその中で同じ向きと90度違いはすぐわかりそうなので）よさそうだが、それが難しい。入力は整数なので、同じ向きということは、ある（整数の）ベクトルの3倍と5倍みたいな関係になっていそう。つまり、GCDをとって割れば正規化できるのでは？あとは偏角ソートとか要らなくて単に同じものを数えるだけ（適当な基準でソートすればO(NlogN)で数えられる）。a/b=c/d（どっちも既約分数）と仮定するとa=bc/dなのでbc/dが整数であるためにはb/dが整数である必要がある。同様にd/bも整数でないといけないので、やはりGCDで割って符号も合わせればそれでよさそうだ。具体的には、y座標は非負かつ、x座標が負ならy座標は正、とする。さらに、x座標が正かどうかで2種類に分ける（x座標が0以下のものは90度回転させてから格納する）（片方の種類しか使えない）。これを、最初の分類内で各種類が何個あるか数えて、各種類がk個とl個あったら2^k+2^l-1を掛けていくのを分類した個数分やる（0個選んだときは、どちらの種類を選んだか区別できないので1引く）。実装にかなりの時間を使ってしまったが、なんとか一発AC。

F - . (Single Dot)

Eを考えながら問題文だけは読んであった。難しそうだが、座標圧縮すれば線分を2次元配列上に描けるのでは？2倍すれば隙間ができるし。2*2のグリッドを描いて、4点と4つの辺と真ん中の空洞1つ、その9個が3*3の正方形に収まってて、これを広くすると元のグリッドの4倍の面積で表現できる。じゃあ座標圧縮をしてBFSしよう（面積がまた難しいと思ったが、座標がどっちも奇数のときだけカウントとかでできそう）。残り20分で、まあ無理だけど書く。なんと時間内にとりあえず最後まで書きあがった！しかし手元で実行してREなので終了。しかも、座標圧縮したぶんを考慮して面積しなければいけないことに気づいてなかった。

全体として、難易度は低めだが、ちゃんとした理解と実装力が要求される、という問題が多かったと思う。楽しかった！