ABC221

5完。Eまで解いてFGを考えて難しいので順位表見たらかなりいい順位でびっくりした。しかしそこから1問も解けず普通の順位に。時間あったのにずっと焦ってた感じで、こういうの久しぶりで悔しい。Hは読んでないが、今回初めてGHの逆転が起こった模様(わりと想定外だった)。

A - Seismic magnitude scales

AとBの大小関係で混乱。forでBからAまで回す間32倍していく。最初逆に書いてしまった。制約を見直す時間も惜しいのでlong longを使った。今見ると(2^5)^6なのでintにギリギリ収まる。

B - typo

まず等しいかチェックして、swapしては戻しをN-1回。

C - Select Mul

制約を見てN=1だったらどうするか書いてないぞと焦るが、他の制約も見るとNが2桁以上であることは保証されていた。こういう制約の書き方珍しいね(嫌いじゃない)。かなり自由度が高そうで難しい。まあ文字列として受け取るのはそう。ソートもしていい。積は正にできることが明らかなので、0を先頭にしてはいけないなどの条件も気にする必要がない。答えは感覚的に10^9未満となりそうだが、実際5桁と4桁の積は10^9未満なのでオーバーフローの心配もない(一般にn桁と9-n桁でもそう)。さて、ここまで来れば頭の中で解けている。数字が大きい順になってなかったらそこをswapすれば数としても必ず大きくなるので、降順ソートしたものをbit全探索すればいい。

せっかくすんなり解けたのにサンプルが合わない。シフトの向きが逆だった。確かになんか違和感はあったけどそうかあ。

D - Online games

やや見慣れない問題で読解に時間がかかる。ここでトイレへ(おしっこ)(最近ABCでは全然ウンコが出なくなった)。10^9日間を前から見ていく。時刻A(A日目の始まり)に+1、時刻A+B(A+B-1日目の終わり)に-1、オンラインでいもす法やるみたいなやつ。そのN*2個をソートして、値が変化するというイベントが起こる直前に、答えの配列の現在の人数にあたるところに一つ前のイベントからの時間を足す。

E - LEQ

要するに、O(N^2)個ある2要素のペアのうち条件を満たすものを固定したら中身の通り数は2冪で、これをO(N*log(N))とかでやれという問題。座標圧縮が必要かけっこう迷ったが、結局使う。そういえば大小関係だけが重要なので、座圧してしまって何も損しない。転倒数よりもう少し難しい感じ。転倒数ならBITでできるが、問題は端同士が1離れる毎に寄与が2倍になること。昔のものを一括で2倍にしたいが、感覚的にそんな処理はしたくない。実質的にそうしたことになるような処理として、BITへの加算を半分にしていくやつがある。これで「1離れる毎に寄与が2倍になる」は(左端については)達成できる。ただしこれでは右へ行くほど寄与が半分になっていくのでBITから和を得たときに掛ける係数を2倍にしていく。BITにはmodintを乗せる。

これもすんなり解けた。上に書いたことは全て典型で自分にとっては息をするように使えるものばかりだが、これだけの数があると問題としての難易度はかなり高いと思った。

(追記)tokuminiさんの提出を見て。インデックスをソートしてもいいのか。Aでソートするけど同じときは左から順に置いて処理していく(iでも比較するの面倒なのでstable_sortを使った(たぶん速度的には微妙))。2冪は(0乗からN-1乗まで)事前計算しておき、最後に2^-Nを掛けて出力。2通りの解き方があるの不思議な感じだ(ということは理解が甘いんだろうな)。

F - Diameter set

木の直径を求めるアルゴリズムに対する理解が浅い。とりあえず、直径は求まる。ある頂点から一番遠い頂点はみんな直径候補になる(そこを端点とする長さが直径のパスが一つ以上存在する)。その候補の一つから見た遠いやつも直径候補になって、たぶんこれで全部。例として考えたのはある頂点から3方向(以上)に深さD/2の木が出てるやつと、ある辺から(2方向に)深さ(D-1)/2の木が出てるやつ。これ塗るのがちょうど2個ではないのがやばい。提出したやつ(普通にWA)も最後にちょうど2個と勘違いして提出したものだった。属するグループからは高々一つしか出せない。まあ掛け算して、選ぶのが1つのケースと0つのケースを除けばいいと思った。「中心」みたいなものがわかればそこから全方向を見て候補の個数を得れば答えがわかりそうな気もする。DFSで色々考えたが結局それになってしまった。深さがそれっぽくなったら周りを見る。しかし提出したときには勘違いがあり、残り5分で修正するもサンプルが合わない理由もわからなかった。たっぷり1時間あったのに何をしていたのか。妥協の仕方が下手。

(追記)バグを修正するが、夜の間にはACできず。翌日、とりあえず解説の通りに実装してACを取る。考え方はともかく、元の実装自体は解説とかなり近いものになっていた。それだけにWAの原因がわからない。ACとWAのコードの間を二分探索する感じで提出していく(めちゃくちゃしんどい作業)。中心の判定が間違っている可能性が高そうというところでバグを発見。DFS中、中心へ向かって半分を超えて進んだときに同じグループの候補へ戻りながら深さD/2になるケースを見落としていた。半分以下の絵しか描いてなかったね。これは見えない。いや半分を超えてからそんな長いひげ出していいと思わん。ここで言う半分は中心までの距離の半分だからD/4で小さいんだねー。

G - Jumping sequence

「Robot Arms」を思い出すが、見に行ったら違った。ΣDとabs(A)+abs(B)を比較して余ったぶんをどう分配するか(余りの半分だけ逆向きに進む)。3.6*10^6なら線形でDPしろってことかな。いや線形では無理そう。bit高速化も考えたがいくらなんでも間に合わないような。そしてDPなら復元もあるのでうそだろって感じ。FGを少しずつ考えて、ここで初めて順位表を見てFに専念した。