ABC235

6完。最近はコンテスト外で競プロやってないけど、プログラミングはしてて、いい感じの生活。1週間ぶりのコンテストで（直前も全然関係ないことしてて）、やや「慣れ」のなさは感じたが、体の動きは鈍ってなかった。

A - Rotate

これをループなしでどう解けと。数値として受け取り、10で割ったあまりを100倍して上に乗せる（元の数は足す前に100で割る）のを3回繰り返した。1分は超えたものの、体感でけっこう素早くやれた。今思うと、文字列で受け取ってstd::rotateしてstd::stoiだったなあ（stoiがパッと出てこない）。

（解説を読んで）うわあ（時間ないとはいえ）桁和の111倍に気づかないのゴミか？

B - Climbing Takahashi

サンプル3にもあるが、高さが同じときは移動しないことに注意。これは簡単。入力も、高橋君が止まったところまでしか受け取らない実装にした。

C - The Kth Time Query

数xが現れたときインデックスをunordered_map<int, vector<int>>に入れていけば、k回目に現れたものはvectorのk番目に入っている。存在するかの判定は、vectorのsizeとkを比較。まあ座圧もできそうだけど、C問題でけっこう知識要求してくるなと思った（これが知識に分類されるかは知らんけど）。

D - Multiply and Rotate

10^6なのでグラフでできる。rotateはA問題と同じように（桁数が一定ではないので対象となる数以下で最大の10冪を求める処理が入る）。で、最初はN以下の数を考えていたが、Nを超えてから戻ってくるルートもあると気づき、幸い10^6「未満」という制約なので（桁数が減る操作は存在しない）常に999999までの頂点を持つようにした。いやあ危なかったと思って提出したらRE。10^6の2乗はintに収まらない。これはけっこう面白いペナだった（あまり見ない場所でのオーバーフロー）。

E - MST + 1

「一意に定まる」を見て「いやそんなわけないでしょ」みたいなことを口に出した気がする。でもクラスカル法の手順を思い浮かべると確かに全てのステップで一意なんだよね。クラスカル法わかってないので仕方ないです（完全に道具として使ってる）。さて、その一意に定まる手順の中で追加された辺の番が回ってきたときにどうなっているか。これはクエリ先読み。今思うと元の辺とクエリをまとめてソートしてもよかった。コンテスト中に実装したのは、別々にソートしてしゃくとりみたいにして、今の段階で選ばれるクエリの辺をまとめて処理するもの（番兵として辺を1個増やす）。典型かつ天才みがあってABCの問題として良い。

サンプルが合って提出したがサンプル以外全部WA。ソートしたらインデックスわかんなくなるじゃん。クエリ先読みの基本を忘れている。今回はコンテスト体験を重視できていたのでペナを出してもそんなに嫌な気持ちにならなかったが、それでも自分のミスで他の問題を考える時間が減るのはやはり嫌だった。

単純グラフと書いてあると思い込んでいたが、自分が見た文字列は「無向連結グラフ」だった（AtCoderで「単純」と書いてないことがなさすぎて「ああいつものね」で終わらせてしまう）。辺を追加したときに多重辺となりうることは気づいていたけど。

F - Variety of Digits

桁DPっぽいので少し前に書いたブログを読む。10進法の場合のコードも載せてるのほんとえらいし、DPの添え字の意味も2進法の側にちゃんと書いてあってほんと助かる（桁DPマジで難しいので身に付かない）。しかしその上でも難しい。まず、和ではなく個数を求めてみる。「全て含む」というのが厄介で、「一つでも含む」なら条件を達成したかどうかのフラグだけでいい（「一つも含まない」でも同様）。なるほど10^4と制約がやけに小さいのは、2^10通りの状態を持つからか。これ（コピペしたコード）は配るDPなので、10通り試して行き先を愚直に求めて足していけばいい。先頭が0であってはいけないので、けっこう混乱してかなりの時間がかかった。個数が求まったら、次は和。この問題、解ける確信がないまま書き進めるしかない。どうやら個数も必要そう？和は普通に配るだけでよくて、桁を追加したぶんの寄与を個数を掛けて求める必要がある。自分の実装だと、DPテーブルのメモリ節約をしていないし、追加する桁を10通り全部試しているので、定数倍がかなり心配になる。まあ通るやろ（1204ms）。

G - Gardens

Fで詰まったときにちょっと覗いたが、無限人解きそうな数え上げに見えて確かに難しい。そこで順位表を見てすぐFに戻った。Fを通して戻ってきたが、「すべての庭に少なくとも 1 株以上の苗を植える。」の条件がなくても、二項係数のO(1)では求まりそうにない和が必要になる。しばらくして、使う和が連続した位置にあるので差分計算できる可能性に気づいた。パスカルの三角形で考えていて、一つの和をO(N)で求めたらO(1)で更新していける。あとは包除パートだと思ったら、できない。残り時間も少なかったけど、これは時間があっても無理だった。「苗を植えてない庭がK個以上」の場合の数を求めることができない。他のアプローチも思いつかない。

（追記）庭iに何も植えないと決めたときの植え方たちという集合がN個ある状況を考えると、まんま包除原理。包除パートは完全にいつものなんで、これが見えないのは単に包除原理そのものの難しさだ。

ABC234

6完。競プロは面白いと思っていたけど、問題の面白さに関係なく負けるとつまらないクソゲーだった。ぷよぷよみたいだな。

A - Weird Function

「f(f(f(t)+t)+f(f(t)))」を問題文からコピペ。

B - Longest Segment

std::hypotを使う。

C - Happy New Year!

2進法みたくなるっぽい。下位からやってreverse。

D - Prefix K-th Max

priority_queueかmultisetを2個使うやつが思い浮かぶ。それで解けるはずではある。出力回数がN-Kより1回多いのも難しかった。考え続けると、そこまでの上位K個の集合を持ってその中の最小を出力すればいい。priority_queueが1個あればいい。pushしてpopするのを繰り返すだけ。相当頭が混乱した。これは瞬殺できない。

E - Arithmetic Number

難しそうに見えるが、冷静になると「等差数」は初項と公差と長さだけで決まるので全列挙できる。列挙するときは、初項と公差を決めて長さ1から伸ばしていく。桁が負や10以上になったら終わり、X以上の数を追加したら終わり。最後はlower_boundを使うと楽。

F - Reordering

各文字がいくつあるかだけが重要。その中から各文字をいくつずつ使うか決めると、例えば5個と6個と3個だとすると(5+6+3)!/(5!*6!*3!)通りになる。こういうのの和を求めたいが、全くわからない。しばらくすると、分子がいい性質を持っていることに気づく。合計何個選んだかが同じなら、1/(5!*6!*3!)みたいのを和でまとめることができる。この形の和は見えにくい。「合計何個選んだか」は最終的に、できた文字列の長さになる。各長さについて階乗ぶんを掛けて足していくと答え。この方針は難しかった。提出したときもよくわかってなかった。

G - Divide a Sequence

1個ずつ足していく方法で2乗にはなる。しかしこれの高速化は無理そう。分割統治みたいにやろうとしても、結局これより速くなる要素がない。となると最大最小を利用することだが、最大値でぶった切っても最小値がどこにあるかわからんし、各区間の寄与を考えるにも結局端の情報が必要になる。

PAST202112-OPEN

MN以外の88点。最近のPASTは面白い。途中で雪が降ってきた（外の雪かきの音で知った）。

A - アトラクション/Attractions

自分で書いた雑CSSのせいで問題文が見えず少し時間をロス。以上と以下であることに注意して書く。簡単。

B - 穴の開いた硬貨 / Perforated Coin

いきなりこの考察難度の高さ。客がどんな出し方をしようが（例えば40円のものを買うのに140円出すとか無駄な出し方をしても）単に差額を最小枚数で出すだけ。使う50円玉の枚数は、差額を100で割ったあまりを50で割って切り捨てればいい。

C - 最速正解者/Fastest Answer

FAを記録していく（上書きをしないように）。

D - 試験/Examination

stable_sortを使う。

E - キーボード/Keyboard

同じ手を使うかの判定が、どう書いたら楽か悩む。配列で左手に相当する部分だけ値をセットしておきそれを参照するとかも考えたが、結局 '1' <= c && c <= '5' のように書いて前回と比較した。

F - 将棋のように/Like As Shogi

ベタ書きしようかと思ったけどやっぱ大変そうなのでグラフ構築。BFSで新しい場所に来た回数をカウント。

G - 連結/Connectivity

ちょっと驚く制約。O(N^2*Q*α(N)) でまあ間に合うけど「Pythonで通るのかな」とか思う（普段これを思うのは計算量的に嘘解法な疑いがあるときなので（しかし定数倍の軽い10^8なので100ms））。

H - 最長非共通部分列/Longest Non-common Subsequence

LCSさすがに書いたことあるだろと思ったけど短時間では見つけられず。今調べるとEDPCのFだった。当時の復習とほぼ同じコードを今回も書いた。なんか本家より簡単そうに見えるのに結局同じDPになるんだな（意外だった）。頑張って正面から考えていったけど、結局DPになり、いつもの形になった。貰うDPをするとき、最後同士がペアになる場合は簡単で、そうでないなら少なくとも片方はペアにならないということなので片方ずつ持ってくる。これでどんなペアの作り方に対してもDPの経路が存在する。なんか当時はけっこうてきとうにやってたな。

I - 直通エレベーター / Direct Elevator

ダイクストラ法。辺の数を抑えるにはどうしたらいいか。階段を使うのはエレベーターが止まる階と1階とN階を行き来するときのみで、対象の階は階段で順番につながっているのでその間だけ辺を張ればいい。座標圧縮してグラフ構築。階段のコストが圧縮前の値で決まったりして気持ちのいい座標圧縮。ダイクストラで辺のコストが10^18だと心配になるが、どこかの階への最短距離（階段があるので10^18以下）に10^18足されるだけなので2*10^18まで扱えればよく、問題ない。

J - 回転と反転/Rotate and Reverse

テキトーにやってたらサンプル以外全部WA。これまでの問題もそうしてきたがたまたまみんなACだっただけ。簡単な処理で解けることは明らかだが、操作の種類が多くてかなり怖い見た目だった。早いとこACだけ取ってしまいたいが、わからないので一旦飛ばした。

最後までやって、JLMNOの中で解けそうなのがこれしかなくなり、30分くらいかけてやった。マス目を区別し、(0, 0)と(1, 0)と(0, 1)がどこへ行ったか管理する。これはまあ簡単。マス目の状態は元のやつで管理する（(0, 0)がどこへ行ってもそこが塗られたらメモリ上のs[0][0]を変更する）。さっきは逆回転させていたが、ちゃんと逆変換を考える。(0, 0)が今そこにあるなら、与えられた(x, y)は元の座標でどこなのか。たくさんの混乱や勘違いを経て、手で作った撃墜ケースとサンプルが通り提出してAC。

K - Gas Station/ガソリンスタンド

これが最後の簡単な問題だった。各ガソリンスタンドからBFSするだけ。

L - 嘘つきな生徒たち/Honest students

嘘が絡むと問題文を読む難易度が上がる。要するに、最小で何個 A_i を変更すれば狭義単調減少にできるかという問題。LISっぽい。狭義単調減少でなければならないのは、A_i を A_i + i で置き換えればいい。得点が0以上P以下でなければならないというのが難しい。

i を足したときの状態を図に描いて、ここで広義単調減少ならいいので、よく見るとLIS（の逆）にN-1以上P以下の値しか含まれていなければ他の値を変更して条件を満たすようにできる。逆にそうでない値が含まれていたら不可能なので、そのように値をフィルターしながらLISをやればいい。LISはいつものを貼ったので、upper_boundへの変更で広義単調にして（ここ何も考えてない）、符号反転で単調減少に対応させた。

M - 名前の変更/Deadnames

いかにも平衡二分探索木という見た目。しかし持ってないので他のアプローチを考える。出現する名前を全部先読みしてソートして番号に変換してBITに載せればいいんじゃない？BIT上の二分探索でX番目の人の名前もわかる。が、その名前の中で指定番目の人がだれかがわからない。しばらく考えてわからなかったので、平衡二分探索木がないと無理な可能性も考え他の問題を優先した。必須なのは今まで出会ったことない気がするのでそうだとしたら嬉しいが。どーなんだろね。（この問題だけ自力で解けておらず解説もまだ見てない）

（追記）解説を見たら、平衡二分探索木は予想通りだけど、トライ木の解法もある。いや無理でしょと思いながら解説ページを閉じて少し考えると確かにできる。いやこれは思いつきたかった。なんかだいぶ実装に時間かかったけどトライ木でAC。今回も平衡二分探索木は実装する気が起きなかったよ（かつて平衡の工夫のないやつは実装経験があり、まああれでさえ実装も定数倍も重かったからなあ）。ただ、またトライ木の理解が広がった。

（追記）コメントで教えてもらった平方分割でAC。ソート済みの列をsqrt(N)個くらいに等分しておけばそりゃあ愚直に挿入削除をやってそこそこ高速だけど、言われなきゃ全く発想にない。前も思ったけど、自分はよほど頭が固いのか、あるいは平方分割を何もわかってない。挿入とかを繰り返して個数が偏ってきたとき愚直に再構築しても、挿入sqrt(N)回がO(N)で再構築がO(N)なのでオーダーが悪化しない。ほえー。実装はかなり時間かかったけど初めてだからまあこんなもん。

N - 共通部分 / Intersection

なぜ凸なのかがわからないが、凸だとけっこうパターンが限られるのか？交差したところを新たな頂点として、ふたりでぐるっとやればいいか。いや、突き抜けて交点が4つになることもある。ていうか完全に含まれている場合もあるじゃん（交点がなくても答えが正になりうる）。これは無理。

ちょっと考えていた、原点を頂点に持つ2つの三角形の共通部分の面積を求める方法に戻ってきた。原点から見て頂点が斜め上にあることが保証されるよう斜め上に少し平行移動させておく。手で色々試すと、やはり1つの頂点を共有する三角形同士だと考えやすい。交点と相手の三角形の内部にある頂点を求めて、ソートして面積を普通に求めればよさそう。交点はライブラリがある（線分の外は交点とみなさないように改造）。内部判定は、そこを中心に三角形で面積を求めて符号が変わることがなければ内部（2頂点がその頂点から見て反時計回りに並んでいるとは限らない（元の多角形ではないので）ことに気づかずはまった）。

バチャ終了。ソートしたら符号の情報が消えることに気づいてなかった。てきとーだけど元の2辺の符号の掛け算っぽいと予想し手で試してそれっぽいので、それで実装。苦労のデバッグで、反対側の線分がスカってるケースを処理してないことに気づき、まあ色々あってサンプルが通り、AC。自信はない。

O - ペアスコア/Pair Score

各ペアの寄与を考える。一つのペアについて、差がWなら置き場所はN-W通りで他の数の置き方が(N-2)!通り。B_iが小さいので、各値が何個あるかカウントして、あとは九九の表みたいのを斜めに足したものが高速に求められればいい。しかしわからない。この問題特有の性質を使うのかとも思ったが、そうなるとS_iまで絡んでくるので余計無理そう。

内積だよなあとか思ってたら、FFTを思い出した。FFTに気づくときと気づかないときの違いは何なんだ。NとB_iの種類数を混同して（添え字が繊細なこともあり）大変だったが、まあatcoder::convolutionを使うだけの楽な問題ではあった。

【バチャ】CODE-FESTIVAL-2016-QUALC

3完+Dの部分点。今回はDがとっかりなくて座ってるだけバチャになるかと思ったが、Eが（全く解けないけれども）考えがいがあってよかった。これでCODE FESTIVAL 2016の予選3回のバチャが終わった（予選3回は多くない？）。

A - CF

前から順に見てCを拾い状態（最初0）をインクリメント、Fを拾い状態をインクリメント、状態が2になっていたらYes。貪欲に拾っていけばいい。

（解説を読んで）二重ループという手があるのか。

B - K個のケーキ / K Cakes

200点がわかんなくて焦る。しばらく考えて、過半数のものがなければ答えは0でありそうなことに気づく。重要なのは、複数種類のケーキが過半数を占めることはないということ。一番多い種類が何個あるかだけ注目すればいい。ここからもやや大変。同じ種類をK個並べた状態だとK-1が答えで、そこから1個を違うものに置換するたびに答えは2減る。

答えが0のときに具体的な順番を構成する方法がわからないまま提出した。0101010121222みたいな出力しそう。いやーわからん。

（追記）解説のように挿入するときに、残り数が一番多い種類を使えばいいか。挿入が終わったとき、残った一番多い種類の個数は2番目よりも高々1個多いだけになっている（最初に一番多いものへ挿入したので次に多いのだけ使ったら多くても1個しか残らない）。あとは残ったもので同じ問題を解けばいい。

C - 二人のアルピニスト / Two Alpinists

これもパッと見なにもわからない。糸口をつかんだところでトイレへ（つかむ前に行ったほうが効率はいいが仕方ないので実装もトイレで頑張って想像した）（緊張も少しはあるけど、食べ過ぎたのが大きい）。最大値が更新されたときは、その山の高さがそれであることが確定する。そうでないときは、山の高さはそれ以下であることがわかる。その情報を2人ぶん合成すればいい。実装をまとめるのがかなり大変。まず入力を受け取り、各山について情報を合成する。区間の共通部分ではあるけど、それもめんどくさそうなので4通りに場合分けした。

D - Friction

1列ずつ処理するのが最適かと思いきや、同じ色が出会わないように交互に動かすケースもありそう。考えても、この問題が難しいという結果しかでてこない。何もとっかかりがない。

部分点があったことに気づく。DPでできそうなので、残り時間をこれに使う。DPテーブルのサイズがO(H^3)で、更新がO(1)でできればいい。そのために、隣り合う2列の沈めた回数から一致する個数を前計算しておく（2乗でできそうだが愚直に3乗で間に合う）。そして後ろから貰うDPをする。15分くらいで実装しきれたのはえらい。

E - 順列辞書 / Encyclopedia of Permutations

ある順列が辞書順で何番目か求める処理を考える。例えば入力例5なら、最初に3より小さいものを選ぶと3が3番目から2番目になり番号の和が全部なんかの階乗くらい減る。そういう寄与を全部上手く集めればいけるんじゃないかと思った。解けそうな見た目になった。しかし、あまりにも遠い。自分の能力を超えていそうで考える（進む）のが嫌になる。しかしそれを1時間考えたら解けるということもたまにはあるので、少しずつでも考え続ける。確定している数の立場で自分より左に自分より小さいものがちょうど何個のが何通りというのはなんとか求まりそう。だが計算量が部分点でも不安だし、そもそもそれをてきとうに足したところで答えになっているのか全然わからない。