全完。ただし、Iが当時のジャッジサーバーだとTLEになっていた可能性が高い。
今回からURLが変わっている。また、第16回の過去問公開もやけに早かった。
A - ペナルティ/Penalty
ABCのAだ。言われたとおりに計算する。なんか掛け算の順序を逆に書いていた（気づいたけど時間をかけたくないのでそのまま提出）。
B - 殿堂入り / Hall of Fame
Hだけを使う。これもABCのAだ。
C - 円の描画/Drawing Circle
こういう自分で絵が出せる問題いいね。-NからNまでで大変そうだが、点(-N, -N)に対応する文字を最初の行の最初の文字として出力するだけなので実装は楽。何もかもを逆にしてしまい、サンプルに合うように修正して提出。'#'に壁のイメージがあったので円の外をそれにしてしまっていた。座標の向きは、バチャ中はなぜ間違えたかわからなかった。よく読むとXY平面とも言ってなくて、(X, Y)のXが右向きとも下向きとも言ってなくて、点(X, Y)はこのように出力してねという指示があるのでそれに従えばよかった。
D - レコーダー/Recorder
これはしんどい。意味をとるのが大変だし、その過程で文章が曖昧になっていそうな感触を持ちながら読み進めるのはしんどい（実際は曖昧じゃないけど関係なく）。実装もそこそこきつい。確実に放送が終わっているところまでシミュレーションする。録画するのは時間1単位で考えていい。各時刻で録画したかの配列を用意して問題文の通りに塗り潰していく。細切れになっていてもいいらしいので、さっきの配列で全部録画できているかチェック。9分ちょっとでAC。ABCのBで出たらキレてるやつだけど、PASTならまあ。
E - 合計得点/Total Score
制約がeなのはすぐ気づいたけど、WTF19のeだと気づくまでにはやや間があった（そういう問題設定なのに察しが悪い）。気づくとニヤニヤしちゃう。さて、各A_iの寄与が明らかに同じだけど、Nがめちゃくちゃ小さいのでnext_permutationでも解ける。これは迷うけど、さすがに正面からやりたい。合計を求めて、選び方の個数を求めて、K/N倍にする。コンビネーションをintで求めるやつ普段使わないからこういうとき気軽に使えるライブラリがない。結局普通に書いた。8なので普通にやってオーバーフローもない（解説にある計算方法（の正当性）をなぜか忘れていて避けてしまった）。
F - 番号付け / Numbering
これはわりと好きな処理（？）。インデックス付きでstable_sortして順番がわかるので書き戻す。
G - N-SAT
abを保存するのが面倒だと思ったけど、存在・すべて・存在というヤバ配置で、長さ2^15のbitsetは使うことになった。最内ループで2^N回すやべーコード。k個それぞれについて存在するかチェックし、一つもなかったやつは脱落。脱落してないのがあればYes。
H - 和で表現/Magical Sticks Again
やったことあるような問題。小さい正整数から貪欲に使っていけばみたいなのをなんとなくでやっていた。二分探索する。
今気づいたけどカックロ（ただしどれだけ大きい数を入れてもいい）でどれだけ長くできるかという話だな。それならさっきの貪欲が自明に感じる。まあカックロは上限があるから24=9+8+7みたいに決まるんだけど。
I - 最大公約数の最大値/Maximum GCD
最大公約数というのは最小値のようなもの。ある数（の倍数）が作れるかということなら、そういうのがK個あればいい。ソートや二分探索も考えたが色々な方向へ伸びていくから無理だよな。8分ほど使って解ける気がしないので飛ばした。さすが前半のボス問。
最後までやったので戻ってくる。最大公約数のもう一つの典型、最大公約数は約数のどれかになる。当たり前だけど以前ABCかなんかで出たときは思いつかなかった。約数が、N個中何回現れたかをカウントしてK回以上現れた中で最大のものが答え。これはO(N*sqrt(max(A)))でできるが、Nがかなり大きく実行時間制限もなぜか1秒なので、ギリギリに思える。提出してみると、916msで通った。C++でこれは実質TLE。
線形篩で素因数分解してそこから約数を構成すれば速くなると思っていたので終了後実装するが、720720には約数が240個あり、しかも列挙には素因数の種類数が掛かってくる。よってもう一工夫が必要。100万以下の正整数の約数の個数の合計を調べると10^7より大きいという程度だったので、これの上位50万個でもまあ行ける。といって一度計算した結果をmapなどで保存しておくのはそれも重いので、ソートしてランレングス圧縮して、同じのが3個あったらそれの約数のところに3を足すといったやり方にした。これで167msまで高速化。素因数の種類数が掛からないように再帰でやったらもうちょっと速くなった（素因数が0個のときにバグっててTLE）。
解説見たら天才で草。
J - 忍者 / Ninja
これもDみたいな感じで読むのがしんどい。基本を後攻と考えて、地上にいるのは体力が1小さいことにする。飛んでいる魔物を落とすのは2ターン分の価値がある。あとはpriority_queue（ソートでいいけどこっちのが実装楽そうなので）でダメージの大きいところから手裏剣でカバーしていけばというイメージ。結局はそれでよかったんだけど、飛んでいる魔物を落とすところがずっと不安だった。体力が2以上のとき、手裏剣1枚で2回攻撃分の価値がある。
K - 入れ替えてソート/Swap to Sort
てきとーにバブルソートすれば最小コストになるのかが問題。自分より大きい数が左にあったら、それらを通す必要がある。大丈夫そう。あとは転倒数求めるときみたいにBITを使うだけ。これは2本必要か？まとめることはできるけど実装に時間がかかるのでやめておく。0次のBITと1次のBITを用意して、左にある個数の合計と数の合計がわかるようにする。
L - ビット行列/XOR Matrix
なんか全部作れそうな気もしてくるが、サンプルはそうじゃないと言っている。ビット位置毎に考えることができる。AをBにxorしておいてオール0からそれを作れるかという話。角から01を決めていくことを考えていたが、なるほどこれはH+W種類の操作をするかしないかという情報量しかない。方針を定めるのに時間を食ったが、行列の要素に対して縦操作と横操作が一致しているかどうかが決まるのでそれでグラフを作り連結成分毎に矛盾がないか調べていく。自由度がよくわからなかったけど、H+W個全部逆にしても同じ結果なので最初は好きに決めてよさそう。ACしたが、思ったより実行時間が長い。頂点数がH+Wだから速いと思っていたが、辺の数は最大でH*W*2だった。
なんかできた気がしてUnionFindでやりたいと思い「UnionFind 二部グラフ」でググったりもしていたが、頂点数が2倍とかよく知らないやつだったのでやめた。終了後、実行時間の短いコードを見て調べていると、そもそも30回繰り返さなくていいことに気づいた。縦操作と横操作のxorが何になるか定まってるわけで、これはポテンシャル付きUnionFindでできる。+をxorに書き換えて、なぜかサンプル通らなかったけど、xorの演算に括弧を付ける必要があった（コンパイラが警告出してくれてたのに見てない）。普段はしないミスだが、この文脈だとうっかりしやすい。普段は注意力があるからミスしないのではなく、慣れた文脈だから間違えないだけだ。いやこんな簡単に解けるんだね。
M - 点の距離/Distance on the Line
bitsetでできそう。左右対称というか、距離だから、0以上だけ持てばいい。しかし、bitsetで一部を左右反転させるのはめんどくさい。あと、マックスの距離も100万程度でいいのだろうが正確な上限がわからない。ということで、絶対に全部収まるし左右反転も要らない、-200万から200万まで長さ400万と1のbitsetを持った。M=200万として、bs[M]を真ん中にすると見やすい。最小値を求めるときは、左右対称なので片側だけでいい。
N - 度数分布/Frequency Table
それだと最小値になるんじゃ？と思ったけどちゃんと読んだら下限になっていた。偶数個のときの中央値の定義が書いてない。サンプルを見ても真ん中2つの平均だけど、それが一般的ってことかな。で、2つ見なきゃいけないとしたらとんでもなく難しそう。さて、数が動ける範囲はそんなに広くない。全員左に詰めたときと右に詰めたときで高々1しか違わない。つまり、平均の範囲も幅1。で、答えが0になるならいいけど、平均の範囲に置けない形でしかも中央値に使う数が左右に割れてたりすると不可能に思える。14分ほど考えて飛ばす。
平均の範囲が半分かかってて左寄せの状態から平均を中央値が追いかける形を考える。等比数列の無限和みたいなのに見えてしまうが、冷静に考えるとこれは右端まで追ってしまえばいい。これで追い越せないならそこが最適だろうし、追い越してしまったなら答えは0だ。これで希望が見えた。まず中央値の位置最大2個を列挙する。何番目の要素かを最初に書いて、それがどの区画の（区画内で左から）何番目の要素かを求める。左に寄せて、暫定の平均と中央値を求める。大小関係2通りをやりたくないので、中央値のが大きかったら全体を左右反転してやり直す（Cをreverseしてやり直すだけなので簡単）。そしたら、中央値に関係するもの（動かさざるをえないものを含む）を右端まで動かす（差分計算できる）。これで中央値のが大きくなってたら中間に0もあったはず。そうでなければその右端に動かしたのが最適。
いやーどうなることかと思ったけど、O・I・Nと通して全完。難しい問題は20分前後（他にはJ・L）、Nは1時間くらいかかった。他を5分とかで通せているのが大きい。
O - 数列と素数 / Number Sequence and Prime
素直ではあるが、ボス問らしいしっかりとした難しさ。篩をやればいいと思うが、素数pの倍数を高速に列挙する必要がある。Sの要素は10^12以下なので、10^6以下の素数全部でやる。等差数列が両側へ無限に続いているとして、その中にpの倍数があるかextgcdで調べる。Aの倍数とpの倍数の和がBになるものがあるか、まずgcdがBを割り切るかで判定。割り切れるなら両辺を何倍かしてpの倍数が見つかった。そしたら数列の中で添え字が0以上になるギリギリの位置を見つけて移動し（p/gcdの倍数に切り上げる処理を使った）、そこから反対の端まで処理する。たまたまN回全部とか当たる素数もあるかもしれないが、まあそうそう当たらん。10^6以下の素数も塗り潰されてることに気づかずサンプル通らなかった。数列に1が入ってないのは親切。正しいことをしていたつもりではあるが、自信は持てなかったので、ACしてよかった。
