PAST202107-OPEN

バチャやってHM以外を解いた。前半重いのは相変わらずだけど、そこまで重いのはなかったし、典型だけど天才っぽさを感じられるのがあったりで、好みのセットだった。

A - チェックディジット/check digit

言われた通りに実装する。15文字目は足さないように注意。

B - 蒸気圧/Vapor Pressure

シミュレーション。ストーリーの意味を考えると混乱するので、問題文の通りに実装するだけ(あまり好みではないが)。

C - 入力チェック / Validation

余分な0の有無は先頭が0かどうかで判定できる(と思ったらサンプル通らず0が例外だったまたお前か)。あとは10^100くらいになる数との大小関係だが、上から10倍しては足ししていきRより大きくなればNoで、最後まで行ったら普通に判定する。

(解説を見て)不要な0の判定が済んだら、単に文字列の長さでいいのね。不要な0がある場合はL以上R以下の判定が不要というの、なかなか気づきづらい。

D - 書き換え/Replace

難しそうな見た目だが、aiueoに気づいて一安心。同じ文字を取り合うことがないので、左から貪欲に取って損しない(当時はここまではっきりとは考えられなかったが)。aiueoかの判定は p["aiueo"[i]] = 1; というテーブルを作っておけばよい。そしてxを全探索。

E - 青木君のいたずら/Aoki's Trick

愚直に全探索。二重ループになるのでちょっとややこしいか。一重ループで書きたいところだけどね。

F - ダブルブッキング / Double Booking

ミーティングは全て1時間単位なので、日毎に何時が埋まってるかをビットで持つ。

ここまで、理不尽に重い問題がなくて快適。

G - べき表現/Power Expression

いよいよ力を試される問題が出てきた。緊張して便意。Gはほぼ解けていたので、後ろのほうからすぐ読めるものを探しNを頭に入れてからトイレへ。

天秤で量るとき3冪の分銅があればいいみたいな話は有名だが、それについて考えてなかったなと思い焦る。下から合わせていくのを思いついて解けた。3進法で最下位は1で合わすしかないので、0なら使わず、1なら1を、2なら-1を使う(それ以外の選択ではNを作れない)。引いて3で割ってまた同じことをする。

H - 折れ線グラフ/Line Chart

なにこれ。どうせ簡単な貪欲だろと思ったら何もわからない。また0に戻ってくるのが厄介だよね。上に凸になる気はするけど、どんなケースでもいけるこれという方法は浮かばない。後ろのほうを解いてから戻ってくると、DPを思いつく。Aは和だけが重要。しかし和が10000近くまで行くので計算量がやばい。ギリギリ行けそうな気もするが、ここでそんなのやらせるか?必要な探索はそこまで多くなさそうだけど、簡単に厳密さを求めるとやっぱりデカくなる。隣との高さの差でコストが決まる。幾何なのか幾何無関係DPなのか全然わからない。

(追記)解説覗いて計算量見て気づいたけど、総和が100以下という制約見落としてた(????)。幾何無関係DPだった。ただのDPだから書けるけど、実装はかなり時間がかかった。やはりちょっとでも慣れない要素が入ると自分の中のDP苦手な面が出てくる。

I - ほくろ/Nevus

落ち着いて考えないとだめなやつ。まず、目と目の中点が原点に来るように平行移動。次に左目の角度をatan2で求めてそれが0度になるように回転。結局は簡単だが、この方針に到達するまでにかなりの時間を要した。最初は右目を基準にしようとしてたし、Eも求めちゃったしね。実行時間が予想より長かったけど、fixed << setprecision(9) を毎回付けてるの遅いんか。

(追記)C++の標準機能で出力するとどうやっても遅かった。えー知らなかった。解説見て、atan2なしで解けることに気づいた(この回転最近やってなかったな)。

J - 終わりなき旅/Never Ending Journey

有向グラフの閉路検出。苦手。ACLのSCC使うことも考えたくらい。DFSして祖先ノードに到達すれば閉路ある、そうでなければ閉路ない(ないことの証明ができない)。全頂点からDFSする予定だったのに頂点0からしかしてなくて1WA。

K - 急ぎ旅/Flying Trip

最短経路だけならダイクストラ。少し考えて、満足度も組み込めるのでダイクストラで行ける。景観が辺ではなく頂点にあるのが厄介だが、その頂点に向かう辺のコストにしてしまえばいい(サンプルが合わなかったが、満足度の計算でスタート地点が入ってなかった)。ダイクストラ法のコスト計算で、通常の距離が同じなら満足度が高いほうがよい(コストが小さい)とする。これだけだが、ライブラリはそこまでは抽象化してないので書き換えに手間がかかった。priority_queueで使うため比較演算子を逆にしてあるのでそこも大変だった。ラスト6問、このへんからACが嬉しくなる。

L - たくさんの最小値/Multiple Min Query

unorderd_mapで各値に対しsetを持つという地獄を思いついたが、なんとかセグ木だけで解けてよかった。jの列挙が要らないならセグ木で簡単。そこで、セグ木に少し実装を足して対応した。遅延セグ木の再帰コードを持ってきて、セグ木の一番上からクエリの区間を含みかつ最小値がpのところを掘る。一番下に到達したらその位置自体が答えなのでvectorに突っ込んでいく。このコードがなかなか動かず時間を食った。まず、最小値がpのところだけを見るのではだめで、p以下のところを見ないといけない(区間外のより小さい値があるかも)。そして、最小値を関数に渡したとき再帰側では渡し忘れていた(デフォルト引数を使っていたのでコンパイルエラーにならなかった)。

(解説を見て)あー!最小のjを得るセグ木、典型だった。まあ自分なりの良い方法で解けたのでよし。

(追記)上で書いたunordered_map<int, set<int>>とノーマルセグ木で275msだった。地獄どころか普通に実用レベル。実装もそんなに時間かからなかった。

M - 分割/Divide

ラスト3問は難しい。ここでぱったりとACが止まる。並列に考えていく。

誤読して簡単じゃんとDPを書くが、サンプルでより大きい答えになる。部分列だから連続するとはかぎらなかった。色々なDPを考えるが、まとめて扱えるものが見つからなかった。

(追記)数日間苦しんだ。解説の通りに辺を張って(意味がわかってないので間違えないように張るだけでも大変だった)サンプルが通ることを確認し、そのコードを元に図を描きイメージをつかもうとする。全然わからない。部分列としてではなく、誰かのお尻に付けてもらうことでコストCを免れるという捉え方に気づいて進展した。N個の頂点を2セット用意し、左右2列に並べる。Sから左へコスト0で1ずつ流す。右へはコストCを払えば最初から行ける。Cを払うのが嫌なら差の絶対値を払って自分より後の番号へ左から右へ行ける(左へ入るのも右から出るのも1なので分岐や合流のない列になる)。右からTへ1ずつ流し、流量はN。部分列に沿って流すのではなく、各A_iについて自分が先頭になるかそうでないなら誰のお尻に付くかを選ぶ感じ。

N - モノクロデザイン/Monochrome Design

トイレで考えていたときは何もわからなかった。座圧からのいもすすらできない制約だ。落ち着いて考えると平面走査ができそうだ。左から右に見ていく。Y座標は座標圧縮して圧縮後の1マスの長さを別に保存しておく。クエリは長方形を左右2つの線分に分ける(左右どっち由来かは区別する必要がない)。遅延セグ木は区間和と、和に含めるかどうかを区間反転。さっき保存しておいた長さはここで使う。反転は区間全体の長さから現在の和を引くだけ。実装に時間がかかるし、遅延セグ木で本当に表現できるのかも最後まで確信が持てないしで、大変だった。

O - コンピュータ/Computer

かなり難しい。とりあえずBは広義単調増加になるよう変更していい。後ろから考えたくなり、しばらく考えてそれを元に前から見ていく2乗のDPを書くが計算量を落とせる気がせず一旦諦める。しばらくして、貰うのではなく配れば連続した区間で扱えそうなことに気づく。実装にめちゃくちゃ時間がかかった。買うコンピュータはB_iに出現する価格に限定してよく、ギリギリになってから(場合によっては未来を見据えて高いものを)買うとしてよい。遅延セグ木では、今日のために過去(今朝を含む)買ってもらったときの今日の所持金の最大値を管理する。未来のためにコンピュータを買うときは、今日のためのコンピュータを持っていないときの所持金の最大値を持っておき、お金が足りるならば何日後のぶんまで買えるか二分探索で求め、買える区間に対しmaxをかける。遅延セグ木も不安だったが、最終的には区間max(変更するほう)だけでよくなった。具体的には、収入の累積和を計算しておき、遅延セグ木にかますときはそれを引いてから、1点取得するときにはそれを足してコンピュータ代を引いてから使う。このゴツい問題を通せたのは嬉しい。