ABC112

ちょっと毛色の違うABCで面白い。CもDも解く前提でDを先にやる、みたいなムーブもあった。

A - Programming Education

分岐するという、こんなんがAでいいのかと思う複雑さ（まあAらしくはある）。これを1分ちょうどでACできたのはいい動きだった。

B - Time Limit Exceeded

「スマートウォッチであるあなたは」っていうの読んでなかったなあ。やるだけではあるが、条件がやや複雑。提出したとき、簡単なのに思ったより時間かかったなと思った。

C - Pyramid

かなり難しい問題設定。しかも（？）サンプル2なんか中心位置の制約を使ってかなりヤバい推理をしている。とりあえずピラミッドの絵を描く（向きを45度間違えて認識しないよう確認）。2次元なのできつい。1次元なら2つの情報から推定できそうなのに。特定できるという制約を使うんだろうけど100個のバラバラな情報を統合する方法が見えない。開始10分まで考えたところでDを見る。
Dから戻ってくると、中心座標の全探索が見える。普段のCDと逆で、Dを軽く（時間はかかったけど）やっつけてからCに臨むというパターンだ。これで腰を据えてCに取り組むことができる。ということろで全探索が見える。高さの範囲が広いので思いつかなかったのかなあ。Cなので、何か数学的なかっこいい技で解けるというイメージ（思い込み）もあった。さて、特定できるという制約から、矛盾がなければそれを答えとして出力していいことになる。中心座標とh_i>0を仮定すると、各情報からピラミッドの高さを推定して不一致がないことを確認すればいい。h_i==0の場合だが、これは高さが一定以下という条件になる。そういう情報も別に持とうかとも思ったが、それは複雑になる。矛盾がないか確認するだけだから、まずh_i>0の情報だけで矛盾がないことを確認し、その上でh_i==0の情報を加えて矛盾するか見ればいい。構造体のソートは気軽にできるようになっている。h_iの降順でソートし、その順に処理して矛盾がなければそれが答え。一応正しい答えになるようきちんと考えたつもりだが、これだけ道を歩いてきたら何か穴がないか不安にもなる。ACで、ノンペナ全完は嬉しい。力を出せた。

D - Partition

これはさすがに解ける見た目をしている。とういことで、Dを先にやる。まず「最大公約数って元の数より大きいんだっけ小さいんだっけ」というところから。大きくないね。その最大公約数をxとおくと、a_iはxの整数倍だ。それらを総合したMはxの「N以上の整数」倍。つまり、O(M)でいいなら簡単だ。NからMまでの整数を全部試して、最初に割れたやつ。Mの約数列挙はO(√M)でできるから、これもできるはず。それはわかったが、具体的に実装しないといけない。NからMまでというのに条件を加える？Nが小さかったりMが素数だったりするけど全部に対応できる方法は？Nが1のときを別に処理する？簡単なのはわかっているので、O(M)のコードを見ながら√M回のループを書き進める。約数が2つ出てくるが、「少なくとも片方がN以上」なら使える。N以上のやつじゃないほうのmaxをとるのだが、それがN以上ということもある。両方が「N以上のやつじゃないほう」であることもある。複雑だよねえ。普通にACしてCへ。
もうちょっと順位いいと思ったけど、Cで悩んだし、Dの実装で手間取ったし、まあそうか。CとDがちょっと変わってたので、22時に間に合うか不安になってた（始まる前は当然間に合うと思っていたが）。22時からは、ブログ書くのを中断して、かみ・まはーら戦の放送を見る。ほんとは21時のおいうリーグも見たかったけど、それはどうやっても無理。解説放送のために途中で抜けるchokudaiさんを見て申し訳なく思った。

ARC103

自分の状態がわからん。今はとにかくつらい。

C - /\/\/\/

タブに表示されるタイトルは￥だったけど、ページの中身を見ると意味がわかる。まあ解けそうな見た目。偶数番目と奇数番目で2系統に分かれてて、それぞれで一番多いやつに合わせればいい。ただ、「ちょうど2種類」という条件がきつい。サンプルの最後にもあったが、それを回避するのはけっこう複雑な処理になる。ふとvが10^5通りとかしかないんじゃないかと思って制約を見るとやっぱりそうだった。とはいえ、多いやつが何かとその個数を2番目まで求める必要があるのでかなり厄介ではある。頑張ってそのまま書いた。ここの一発ACは嬉しかった。

D - Robot Arms

問題文を読むのに8分くらいかかった。1分くらい考えて解けるわけがないと思いEへ（Eが難しければまたDを考える気になる）。

E - Tr/ee

構築いいよね。Dと違って思わず解きたくなる。まず根付き木で考えてみる。取り除く辺は指定されていないので思ったよりわかりやすい。木を解析するみたいな気分だったが、問題設定は自分で好きに構築できるというもの。葉から出てる辺を切れば1とn-1に分かれる。そのまま伸ばせば2や3は作れる。逆に2を作りたくないなら枝分かれさせればその部分では作れなくなる。色々試していると、どうも伸ばすかぶら下げるかでコントロールできそう。また、文字列の情報は真ん中で対称になっている必要がある。これは楽勝と思い詳細を詰めていくが、真ん中の部分がかなり複雑だ。nが奇数と偶数で場合分けして、なんとかできそうだと思うところまで行けた。わかるところから実装するが、真ん中の接続部分がなんかわかんなくなって1時間が過ぎた。対称にもう半分のグラフを作るのもなんかできてないことにだいぶあとになってから気づいた。そんな簡単なことができないとか思わんわ。うそだろって感じで残り時間がゼロになった。

ABC110

うーっし。ABCでいい順位を取ると気持ちがいい。

A - Maximize the Formula

やたら難しい。サンプルも見ると、2桁+1桁にするみたい。たしかに、+を間に入れる必要があるので2桁の数しか作れない。となるとソートして大きい順に98+7とかすることになる。最初、12+3のようにしててサンプルが通らなかった。

B - 1 Dimensional World's Tale

まあこれはやるだけだが、X<Z<=Yの条件がいやらしい。配列上に都市を置いていく方針も考えたが、最大値最小値でいい。そして、xの最大値（yの最小値）を求めるときに、X（Y）を初期値にすればいいと気づいた。不等号の等号があったりなかったりでややこしいが、隣り合ってるのはOKということ。
ここまでサクサク解いてきたつもりが意外と時間を食っている。やはり難易度が高い。

C - String Transformation

一応、Sに含まれない英小文字を選んでもいいことを確認する（サンプル1でやってた）。状況はわかった。同じ文字は同じ文字に対応してるってこと。英小文字が26種類と少ないので不安もあったがまあ対応してればいいから問題ないか。よって、各文字列を先頭から見ていって、最初に現れた文字を全部0に、次に現れた文字を全部1に置換とやっていって、SとTが一致するかを見ればよい。O(N)でやるには文字の変換テーブルを持てばいいのかな。めんどくさそうだと思ってたところ、SからTへの変換テーブルを作ろうとして矛盾が起きるか見るだけでいいじゃんと気づく。サンプルが合わないが、テーブルが26しか確保してないのに'a'を引いてなかったことに気づく。それでも合わない。Sの同じ文字が同じ文字に行く、だけじゃダメじゃん。変換された先の文字たちに重複があってもいけないんだ。大きな見落としがあったので、実装しても不安だが、提出してAC。きれいな問題なので、きれいに書きたかった。

D - Factorization

aが昇順みたいな条件が付いてるとまた別の問題だが、これは全部数えるので、同じ数が多く含まれているほど少なくカウントされる。さてどう数えるか。基本的な方針としては、Mを素因数分解して、各素因数が何個含まれてるかで数列の要素同士を区別する。あ、簡単じゃん、独立に動かせるから各素数についてコンビネーションを掛けていけばいい。ライブラリで瞬殺。しかしサンプルが合わない。ん、p^cのcよりNが小さかったら？ていうか最大で1個しか含まれない前提にしてるじゃん、酷い。これは、仕切りを入れるやつだ。c個のpにN-1個の仕切りを入れてN個に分け、そのc+N-1個の中からN-1個を選ぶコンビネーション。
普段のABCのDを文系とすると今回のDは理系なイメージだった。わりとスピードが出せて順位もかなりよかった。記憶より順位が1つ下がってるけど、これはB問題リジャッジの影響っぽい。X<Yを満たさないテストケースがあったらしく、自分のやり方だと影響ないけど、Zを全通り試すみたいな方針だと確かにWAりそう。

AGC027

やっと、ratedコンテストのやり方を思い出した気がする。コンテスト中に、「ああ、AtCoderってこんな感触だったな（集中する感じ、考察する充実感）」と思っていた。パフォーマンスも2000に乗せ、結果も出たことで、だいぶ気が楽になった。今週は、解けなかった問題の復習をぼちぼちやれていて、時間的にはぷよぷよがメインだったけど、まあそういうことをして普通に時間を使えていたので、いけそうな雰囲気はあった。

A - Candy Distribution Again

ソートして小さい順に取るという方針はすぐ見える。問題は、ちょうどa_i個にしないといけないことだ。答えがNでないときは、余ったお菓子を喜ばない子供に押し付けることができるので、お菓子が足りないときもちょうどのときも多いときもこれでいいかなという感じにソースを修正。ソースが冗長になっている感覚はあったが、少し見直して提出、AC。あとから考えると、お菓子の数がちょうど以下なら簡単で、そうでなければN-1なので、簡単だ。

B - Garbage Collector

(k+1)^2というのを見て、最小二乗法みたいに（ていうか分散の式変形みたいな）上手いことできるのかなあと思った。状況がけっこうつかみにくいので、ソースにコメントをどんどん書いていった。考察は紙のノートでやっているが、文章はPCのほうが速く書けるし取り回しも便利だ。まず、どんなトレードオフがあるかを頑張って認識する。ゴミをまとめると、移動距離と捨てるコストで得して、移動コストで損する。捨てるコストの部分がXに依存してる。各ゴミには距離の違いしかないというのを忘れがち。部分点の制約を見るとO(N^2)みたいだが、ゴミを拾う順番の通り数はめちゃくちゃ多いのにどうなってるんだろう。貪欲でいいのに俺だけそれに気づかないとか嫌だなあ、とか思ってた。ただ、一番遠いゴミを最初に拾うとしてよいことには気づいた。行きに拾う意味はないから。さて、例えば1往復で4個のゴミを拾うとき、2個目があることでコストがどれだけ上乗せされるか？2乗の差なので奇数の列が出てくる。単独で拾うなら2*X+2*x_iのコストがかかるが、ついでに拾ってもらうことでX+3*x_iの追加コストになる（と思っていたのだが、実際は2*X+5*x_iとX+5*x_iだった、確認のために部分点を実装したときにサンプルが通らず頑張ってデバッグして気づいた、書いた図が4個の点から成っていたが左端はゴミじゃなくてゴミ箱だった）。3個目以降はその奇数の部分が2ずつ増えていく感じ。2乗だからそういうふうになりそうだと思ったし、計算したらそうなった。これで、単独で運ぶよりいいかどうかの判定はできるが、だから何だ。単独で運ぶよりいいからといって他のゴミとの兼ね合いもあるので手順は何も決まらない。これが解けるなら、ばらばらに取っていくような複雑な手順であるはずがないと思うのだが。
ついでに拾ってもらったときの追加コストが計算できてるのだから、何番目に拾われるかに注目すればいいのでは？そうだ、何番目に拾われるかさえわかれば合計コストが計算できる！何番目を選ぶかには制約があるはず（それこそ貪欲でよくなってしまう）。制約を考えると、k番目よりk+1番目の人（ゴミ）のほうが多いのはダメ、そうじゃなければよい。1番目がいい人は1番目にしてよくて、2番目がいい人がそれより多いなら、1番目か3番目に回ってもらう。特に、3番目は2番目に対してデメリットしかない。ゴミは距離だけなので距離でソートして（入力がソート済みなのでreverseするだけ）遠いのを1番に、近いのを3番に、3番も一杯なら4番に。境界が曖昧で、これも全然解けそうにない。ただ、よく考えると1番目のゴミの数を決めれば全部決まるんだった。遠い順に1番2番としていくだけ。これで部分点はいけそうなので、提出するかはともかく、書いてサンプルを試す。今回はグローバル関数ではなくラムダ式を使った（なんかメモリ使用量が増えるので最近は敬遠していたがきれいに書けるので）。コストを計算する関数を書いたら、あとは1番目のゴミの数を1からNまで全探索するだけ。ここで上述のバグに出くわす。コストを細かく表示させて、1番目のゴミの移動コストを計算に入れてないことに気づいた。単独で運ぶのにもけっこうコストがかかるのね。そこを直すとサンプルが通った。さて、三分探索が現実のこととして迫ってきた。そういえばごく初期の段階で三分探索は頭をよぎっていた（どういう探索をすると思ったのかは覚えていないが）。とりあえず三分探索をしない解法を少し考えてみる。AtCoderならそういう解法がありそうだし、まあ見た目もO(N^2)から落とせそうな気はする。でも差分計算とかしようにもガンガン変わっていくので無理っぽい。じゃあ書くしかない。原理的にはできることなのだ。見た目にこだわらなければ書けない理由がない。とりあえずライブラリから自作のupper_boundを持ってくる。傾きの二分探索というのが記憶にあった。計算量の定数倍は考えず、とにかくシンプルに。f(k + 1) - f(k)が初めて負でなくなる場所を見つける。範囲は1からn。kには1からn-1までの値が入り得る。戻り値は1からnまで。nが返ったときは、ずっと負だった、減り続けていたということだから、f(n)が最小になる。あれ、そのままf(k)が答えでいいんじゃね。なんか超シンプルに書けた。サンプルも通った。正しいように思える。三分探索が使える証明はできてないけど、どう考えても使える。少しソースを確認してから提出、ドキドキ、AC。えー、恐れていた整数三分探索これだけか。はー。
ここ数日は「Median of Medians」をやってて、解説を見て解けそうだと思っているのに全然進まなくて、整数の三分探索もそんな感じで恐れていたけどやればできるんだな。
ただし、三分探索が使えたのは結果オーライなだけ。感覚的に三分探索が使えるに決まっていると思ってもそれが正しくないことはある。感覚が正しくなかったというのはAtCoderでも何回か経験していたはず。
ソースがきれいだったので、Cに行く前にソースを少し見直した。

C - ABland Yard

無向グラフと書いて有向グラフと読んでいた。1時間以上あったけど、気づいたときには残り20分だった。Bを解ききったことについて、難しい問題でありがちな問題文の勘違いをよく1回もせずにできたなと思っていたのだが、Cでそれをやってしまった。900点は解けないと思っていたのでやや集中を欠いていたかもしれない。でもそれはあんまり関係なさそう。
有向グラフだと難しい。文字列を作ることに貢献するところだけを抜き出した部分グラフを考えると、その各頂点はAにもBにも行ける。そういう頂点たちだけで構成されている。と考えて間違いに気づいた。ある頂点がAとして、AAとABのルートがあればいいけど、ABとAAAとAABでもいい。AとB片方にしか行けないような通過点があってもいいのだ。なんか足して1になるイメージで、長さlogMまでの文字列を保持し合併が1になるかを1つの頂点になら計算できる。DP的な工夫をすれば全頂点についてもできるのではないかと考えていた。
無向グラフだとすると異様に簡単そうだ。AからBに行ったとして、そのBからはAに行ける。あとはBに行ければいい。そしてBに行ける必要がある。そう考えると、AABBの繰り返しで（1番目のAと2番目のAは区別した上で）元の位置に戻ってくればOKということになる。なんかDFSを4回やるだけで行けそうなので、時間はないがとりあえず書いてみる。しかしYesとしか出てこない。ああそうか、フラグを4層に持っていたがこれではごちゃまぜになってしまう。ダメだと気づいたときには残り1分だったので終了。