ABC342

6完。最後の10分で2問通してるのは、(レーティングの意味で)効率はいいけど、たまに失敗して破滅する。まあ、早解きできた人にはGを考える時間も与えられて羨ましいね。

A - Yay!

150点だけど簡単じゃんと思ったら、けっこう大変だった。文字数をカウントして1のものを探す(Sの長さは3以上なので一つしかない)。位置を知る必要があると気づき、同時に位置も(文字毎に)記録する(知りたいのは文字数が1のものなのでこれでOK)。なんか簡単な方法がありそうだけど、ないのか。

B - Which is ahead?

各人が前から何番目に並んでいるかを求めておく。

C - Many Replacement

各英小文字がどこへ移るかを求めればいい。

D - Square Pair

ソートしていい。0はどうにでもなる。合わせて平方数になるのがどういうときか考えたけど、平方数で割れるだけ割った残りが同じっていういつもの条件だ。素因数分解した状態で考えていたので、残った素因数のvectorをmapに突っ込むとか思ってしまったが、それらを掛けた数でいい()。mapでカウントしたら、a[i]も書き換えてしまって、各a[i]について相手が何個あるかを足していく。0は別に数えておく。順序違いや自分自身とのペアはカウントしない設定だが、全部数えてNを引いて2で割ることにする。0は全員とペアになれる。そうでないとき、自分と同じのと0が相手になる。

順序違いや自分自身や0の扱いが難しくてサンプルがなかなか通らなかった。0は当然平方数と思っていたけど、「各素因数が偶数個入ってる」という特徴付けで平方数を捉えると、全部無限でほんとに平方数かってなるし、「何と掛けても平方数ってそんなことある?」ってなる。

ABC254が類題だった。当時はmapじゃなくてソートとランレングスで数えてた。同じ悩み方してて草。

(追記)解説にあったエラトステネスの篩みたいな方法でできた。「平方数で割れるだけ割った残り」になりえるものを見つけたら、それに2以上の平方数を掛けてできたものは平方数で割れるだけ割ったらそれになる。また、mapでカウントだけしておけば、入力を受け取りながら簡単に処理できた。

E - Last Train

最終時刻の意味がよくわからなかったけど、ちゃんと最も遅い出発時刻の意味だった。ダイクストラやるだけに見えるが、等差数列みたいだったり後ろからだったり、ひねりがたくさんあってきつそう。逆から見てスタート時刻は10^18+10^9で、2^60にそこそこ近いけど余裕を持って小さい。時刻2^60から始めて、大小逆のダイクストラみたいにやっていく。辺のコストが動的に(?)決まるやつ(遅く来たほうが得するみたいなのがなければOK?)。等差数列は怖いけど、落ち着いてやればそこまででもない。移動時間Cと基準時刻Lを引いて、これが0未満なら間に合わない。そうでないときDで割ってK-1とのminをとる。これで何番目の電車を使うかわかったので出発時刻もわかる。

なぜかサンプルが合わず、飛ばした。Fを通して戻ってきて、サンプル3で正解よりも良い(遅く出発して間に合う)回答になっている。ダイクストラということでなんか手癖が発動し無向辺になっていた(有向辺のダイクストラも普通にあるけど出題頻度が低いというそれだけの理由で)。慎重に、未来から過去への辺だけを残し、AC。

F - Black Jack

ディーラーのほうは戦略が固定なので求めてしまえる。yの各値について、通過する(そこで終わる場合も含む)確率を求める。幅Dの区間に足す必要があるが、いもす法みたいにしてできる。最終的な値の確率は、L以上の通過確率がそのまま使える。自分のほうは、各値で終わったときの勝率がわかればいいかと思ったが、実装しながら詰めていくと、その時点での勝率を後ろから求めていくことができて、x=0の時点の勝率(答え)もそのまま求まる。ディーラーの確率を累積和とって、xからNまでが負けだからその区間の和を求める。自分の勝率も累積和を作りながらやって、そこで操作をやめるかサイコロを振るか勝率が高いほうを選ぶ。

サンプルがなかなか合わなかった。いもす法が普通に間違っていた、ディーラーのL未満を0にするのを忘れた、区間和をDで割るのを忘れていた、区間加算するときもDで割ってなかった。

(追記)ディーラーのほう、配り終えたら自分を0にすれば、全体の確率の和が1のままできるしL未満は0になるじゃん。vectorも2本使ってたけど1本でできる。勝率は、区間和ではあるけどyがNより大きいところは使わないので、y=Nになる確率から順に足していくだけでいい。自分の勝率も累積和にして、最後だけ和をとらずに抜ければいい。

G - Retroactive Range Chmax

読んだだけ。

(追記)解説を読んで考えて書く。要素の追加と削除ができて最大値がわかるデータ構造が要る。とりあえずmultisetでやった。「区間更新クエリが可換」というのが重要なんだね。言われてみれば、セグ木の区間クエリで見る場所のmultisetに出し入れすればできそうだ。双対セグ木は未経験だったが、意外と実装は軽かった。提出して2045msでAC。次にmapでやってみたところ、1512msと速くなった。メモリ使用量はほぼ同じ。意外だった。で、以前実装した優先度を変更できるpriority_queueを試そうと思ったが、ちょっと用途が違う感じ。なので、解説にある「消せる priority_queue」を素直に実装した。310msとけっこう速くなる。今回は(multisetなどの)インスタンスの個数が多い(N*2程度)のでやや特殊なケースかもしれない。