ABC216

ギリギリで7完。Hを除けば簡単な問題ばかり、しかし実装が重く、コンテストに占める考察時間の割合が小さくつらかった。コンテスト外であればこういう実装も楽しいのだけど。

A - Signed Difficulty

なんと2分半かかっている。整数部分の取得方法で迷ってstringで受け取るほうにする(doubleで受け取って10倍してroundして整数化も考えたがあまり簡単にならないと判断)。小数部分を整数として保存してから2回pop_back()して出力、必要であればプラマイを出力して終わり。

B - Same Name

計算量の工夫は必要ないが、一番楽な方法をと考えて、SとTをスペース(英小文字でなければ何でもいい)で結合してsort+uniqueして個数がN個のままかで判定した。a aaとaa aが区別される罠に気づいて怖いと思った。そういえばstd::setに突っ込むという手もあったな。

C - Many Balls

Nは2^60より小さいので2回で2倍にすれば間に合う。操作を逆からやっていく。奇数なら1を引いて、偶数なら2で割る。reverseして出力。

D - Pair of Balls

問題文が長く、ここでトイレへ。解けて戻ってきて実装するが、ここで調子が悪いことを自覚する。終わってみて体調は特に悪くなかったと思うが、なんかこういうタイプの実装をこなすパワーがなかった。頭が痛い(比喩)というか、やる気が出ない。

取り出せるボールは取り出して損しないのでシミュレーションすればいい。そのためには取り出せるものがすぐにわかる必要がある。最初に全部チェックしてキューに入れておく。取り出したときにも新たに先頭になったものを2個目ならキューに入れる。相方を見つけるために、N色それぞれについて2個のボールがどの筒にあるかを前計算しておく。キューが本当に必要なのかよくわからなかった(難しい)。筒はdequeで、底から入れて先頭から取り出した。トイレの中では気づいていなかったが、実装がめちゃくちゃに重い。「え、こんな処理も必要なの」とか思いながらやっていく。頭の中だけだと細かい部分まで考えが至らず、ここは仕方ないとは思っているけど、できる人はできるんだろうなとも思う。

望みの色が先頭にあるか見るとき筒が空でないことの確認忘れと、キューに入れるものを c[j] にしてたけど正しくは j だったので2WA。わりとすぐに見つかる傷の浅いミスで、実装時にこれを入れ込んでしまうのは力不足。確かに実力は測れるが、やりたくない問題だなあと思った。

E - Amusement Park

8問ABCらしい軽めのE。と思っていたら、解けてみるとけっこう苦手なやつだった。ソートしてしまっていいので降順にソートする。処理を簡単にするために最後に0を追加する。まず二分探索を思いつくが、簡単にならなそうなので使わないことにした。棒グラフを描いて、上から貪欲に取っていけばいい。上からN段に分けて、1段ずつ取っていく。次の1段がK個以下ならそこで終わりなので分岐して処理(上の長方形部分と残りの半端に分けて足す)、そうでなければ普通に1段ぶん足すだけ。3乗になるんじゃないかと不安になる見た目だが、Kが小さいのでlong longで耐えている。不等号の向きを逆にしていてサンプルがしばらく通らなかった。

F - Max Sum Counting

maxとsumで違ってて狂ってんのかと思った。どちらかに合わせてソートできるのはわかっていたが、AはmaxなのでAで昇順ソートすれば最も右の選ぶ場所を固定してそこまでのBの和がA_iになる通り数を求めればいい。DPをN回はできないが、全部Bの先頭からのDPなので1回のDPで全部の情報が得られる。もう少し考えて、in-placeでDPできるのでそうした。必要な情報を保存しておこうと思っていたが、その都度計算して足していけばいいと気づいて、定数倍の軽い書き方になって嬉しかった。とりあえず書き上がって、「和がちょうどA_iになる通り数」を求めていたことに気づいた(知りたいのはちょうどではなく「A_i以下」)。素直に足しても間に合うが、これはDPの初期化をいじればいい(ここはちゃんと考える)。「和がちょうど0になるのが1通り」を「和がj以下になるのが1通り」に変更(1個だけ1だったのを全部1にする)。

G - 01Sequence

Fまで通して、GHを両方読んだ。Hのが得意そうかなと思って少し考えるが難しいので順位表をここで初めて見るとHが全く解かれていないうえにGがかなり解かれている。そう思って考えるとGの解法はすぐに見えた。

最初「フローか何かか?」と思って思考が止まっていた。落ち着いて考えると、ソートして貪欲に取れそうだ。Lでソートしてもはっきりしなかったが、Rでソートすればよかった(対称だからこの書き方は変だけど)。残っている中でRの一番小さい区間を見ると、1にするのは右から貪欲で損しない(右に行くほど他の残った区間に含まれるようになる)。ただ、1になっていない場所が飛び飛びになるので高速に処理できない。std::setを使い0になる場所を管理することにした。実は似た処理を昼間にやっている(「2D Plane 2N Points」をフローを使わず解き直した)。しかしサンプルがなかなか通らない。既に区間内で1になっている個数も知る必要がありBITを使う。また、erase後のイテレータはすぐ後のになるのでデクリメントしないといけないのを忘れていた。ここでもbegin()かをチェックして先頭ならそこで終わり。計算量を抑える工夫がたくさん必要になる。残り3分で通した。Dの2ペナが響いて黄パフォ相当とはならず。