結果
TOEFLの対策とABCどっちやるか迷ってABCやった。
苦しい結果になった。
振り返り
A
やる。'A' <= c && c <= 'Z'の部分はなにかしらのかたちでテンプレにぶち込んでいいのかなと思いながら実装してた。けどテンプレがでかくなりすぎるのが個人的にあんまり好きじゃないので悩む。
追記: isupperについて
twitterでdrogskolさんにisupperなる関数がstdに既に存在していることを教えてもらった。
https://t.co/Dx8Y6fJVY8
— drogskol (@cureskol) February 26, 2023
isupper は std にあります
このほかtoupperなど様々な便利関数があるらしい(
locale - cpprefjp C++日本語リファレンス)。どこかの解説放送でisdigit関数だけ見たことがあり、それだけ知ってた。テンプレを膨らませなくて良くなったので嬉しい。
B
ソートして平均取る。こういうのかいてるときrepマクロを整備しといて良かったって気分になる。
C
めんどい。移動をシミュレーションしながら座標をsetに入れて最後にsetのサイズを見ればいい。LRUDをそれぞれ0123に対応させたり進行方向に変換させたりしてくれる何かを持っていた方がいいかもしれん、とちょっと思った。
D
DPした。添え字をA[(表裏)][(カードの番号)]にしたせいでネストの順番と添え字の順番が逆なってしまい、きもいな…直そうかな…と悩んでるうちに実装が終わった。
E
トポソして、それが一意か見ればいいだけ。トポソをするときにqueueを使っているのでqueueのサイズが常に $1$ であることを確認する方針が最初に浮かんだ。入力を書いてる内に、どうせならqueue使わないで現在の頂点を保存する変数を1つだけもてばいいか？と思い、そっちを書き始めたが、書いてるうちに場合分けがだるそうな気がしてきたので最初の方針に戻した。
F
\[ \begin{aligned} pre[i] &= 都市1から都市iまで移動するのに必要な最少のテレポート回数\\ pos[i] &= 都市iから都市Nまで移動するのに必要な最少のテレポート回数 \end{aligned} \]を求める。$pre[i]$ は配るDPで、$pos[i]$ は貰うDPで書けばいい。後は $i \rightarrow j$ のワープが存在するなら各 $k (i< k < j)$ に対して $ans[k] \leftarrow \min(ans[k], pre[i] + pos[j] + 1)$ と更新するようにすれば答えが求まる。これ書いて提出したらWAがでて謎すぎた。しばらく眺めてみると $pre, pos$ をint型でとっていた上1 << 30で初期化してたせいで、どちらも1 << 30の時にオーバーフローしてた。intからlong longに直したらACした。
この時点でExがGよりも解かれててビックリした。とりあえずいつも通りG→Exの順番でやろうとしたら間違えてExから解いてた。
G
わからん。ビットごとに分けて考える。今考えてるビットの列を $a$, $b$ として、$a$ を $0, 1, 2, 3, …$ とシフトさせたときのORの和をすぐに計算出来れば良さそう。$1$ の個数を考えるよりも$0$の個数を考えれば楽で、シフトした後の数列 $a^{\prime}$と数列 $b$ でどちらも $0$になっている要素の数が分かればよい。つまるところ、数列 $a, b$ それぞれの $0$ となっている要素のインデックスの差分を列挙、カウントすればいよい。どっかで見たことあるけど分からなかった。セグ木とか平方分割とか考えたけど全然できなかった。そもそも全シフトを試すのが違うのか？とか考えたけど、これ以外の方針も浮かばず、うんうん唸ってたらコンテストが終わってしまった。
Ex
Gと勘違いして解いてた。重心分解して重心をくっつけていくという解法が最初に浮かんだが「ABC-Gで重心分解は、やばいだろ」と感じ想定解は多分違うんだろうな～と思ってしばらく別解を考えてた。適当に根をきめてDFSで潜りながら上手い事ずらしていく方法などを考えたが、実装が重そうだし細かい部分がよくわからんから重心分解を書くことにした。一応自作ライブラリ見たけどやっぱり重心分解はなかったのでネットから強奪してくるか自分で書くか～という気分になった。重心分解書いてる間にEx考えようと思って別タブでExを開いたら同じ問題が出てきてビックリした。試しにG開いたら知らない問題が載ってた。Exなら重心分解でても納得だな、と思いながら人のライブラリ探しに行った。けどどうやって使うか理解するのが億劫になって自分で書いた。一発でACできたのは結構うれしい。
感想
ここ最近オーバーフローでペナを出し過ぎてる気がする。あと差分列挙を完全に忘れてたのがマジでよくない。ABC196-Fをupsolveしたときに感動したんだけど、そのまま忘れてた。コンテスト終わってからしばらくは「なんで畳み込みを考えなかったのかのか自分でも謎だな…」と思ってたが、そもそも僕が畳み込みを使えるか考えるのは$998244353$の時だけかもしれないと気付いた。今後は$998244353$関係なく畳み込みを考えられるようにしたい。 $O(N\log N)$ での重心分解の実装が思ってたよりも軽かったのと、それをすぐに書けたのは良かった。
upsolve
G
TLで畳み込みという情報だけ手に入れてupsolveした。 ABC196-Fとほぼ同じ。言われてみればいかにも畳み込みっぽい形なので、典型とか関係なしに畳み込みの気分になるべきだったかもしれんと思った。畳み込みは次数の和が一定となる組合せの積の和をもとめるので、差分について求めるためにはどちらかの数列を反転してやればよい。あとは次数について $\pmod N$ を考えるように注意しながら数え上げてAC。実装自体は軽かった。