日記 11/1–11/15

11/1

おやすみ

11/2

競プロ

ARC150 のバチャをやった。D は簡単だったが、C で関節点列挙などを考えてしまい手こずった。

B が A の部分列かどうか判定するためには、B の要素を前から見て、初めて A で現れる場所を貪欲に取っていく、という方法をとる。

逆に、「なるべく B が部分列として完成しないようにする」ためには、「最小で B の何番目の要素までにとどめられるか？」というのを計算すればよく、これは 01BFS で計算できる。

11/3

競プロ

PCK 本選の練習として、TeraPad (本番環境のエディタ) + cygwin g++ で 2018 年度の過去問を解いた。
なんとかペナを出さずに解けたが、シンタックスハイライトがない白黒の環境だとかなりストレスが溜まる…
あと Manhattan MST が出てきたのは驚いた。

11/4

競プロ

明日は PCK 本選。ライブラリの確認と、一応知っておくべきと思ったものを勉強した
実は多項式の除算を初めて学んだ。reverse して inv をかけるだけでいいのか

多項式補間のアルゴリズムを今まで「適当にセグ木っぽくやればいけるでしょ」と思っていたが、よくよく考えてみるとそんなに簡単じゃなかった

11/5

競プロ

PCK 本選。割と達成感のある結果だったと思う

その他

ABC276 の Writer をしていた

11/6

競プロ

パソコン甲子園本選、優勝！！！

11/7

組合せゲーム理論

hot/cold/tepid なゲームの復習と、cooling による解析と temperature を求める練習
hot なゲームは解析が難しい (PSPACE 完全) ので、完全にお気持ち解析

11/8

競プロ

暖色埋め

https://atcoder.jp/contests/abc276/submissions/36324137

\displaystyle [x^M] (1-x)^{-2}\left(\frac{x+x^2}{1-x^3}\right)^{N-1} が答え

これを (1-x)^{-2} (1-x^3)^{1-N} と (x+x^2)^{N-1} に分ける
前者は、sparse な形式的冪級数の pow を微分で漸化式を導出して計算する方法を用いて (1-x^3)^{1-N} を求め、2 回累積和をとる
後者はただの二項定理

https://atcoder.jp/contests/abc275/submissions/36324465

f(X) は、 a^\top x \leq X, b^\top x \leq X を満たす成分が非負整数のベクトル x に対する c^\top x の最大値
\displaystyle \frac{f(X)}{X} について調べたいので、 x の各成分を X で割りたい気持ちになる

そこで、 a^\top y \leq 1, b^\top y \leq 1 満たす成分が非負実数のベクトル y に対する c^\top y の最大値を考える
成分が非負有理数のベクトル y であって最大値 M を達成するものが存在する。成分の分母の LCM を L とすると、 y の L 倍は成分が非負整数であり、もとのナップサックの解になる

X = nL に対して \displaystyle \frac{f(X)}{X} = M であり、 nL \lt X \lt (n+1)L のとき

M \geq \frac{f(X)}{X} \geq \frac{f(nL)}{(n + 1)L} = \frac{n}{n+1} \times M

ゆえに n \to \infty で \displaystyle \frac{f(X)}{X} \to M

M を求められればよい。前述の LP の双対をとると、 sa + tb \geq c を満たす非負実数 s, t に対する s+t の最小値、となる。 K = s+t を固定して二分探索をすると簡単で、 sa_i + (K-s) b_i \geq c_i が全ての i に対し成り立つような s の集合 (区間) が空でないか判定すればよい。

https://atcoder.jp/contests/abc255/submissions/36326840

座圧 + 遅延セグ木

11/9

競プロ

https://atcoder.jp/contests/abc261/submissions/36341690

「dp[l][r][c] := c を T[l..r) に一致させる最小コスト」を頑張って計算
置換する文字列の長さが 1 かそうでないかで処理を変える

https://atcoder.jp/contests/abc255/submissions/36345250

X_i の小さい順に Grundy 数を頑張って計算する

n の Grundy 数を g(n) と表す。g(n) = k となる n が 2 個以上あるような k は多くないので、このような k と対応する n の値を全て管理する。すると mex の計算に必要な情報が集まる

11/10

競プロ

https://atcoder.jp/contests/abc254/submissions/36365523

上下移動は必ず |Y_i - W_i| のコストがかかる。水平移動を最小化する問題

dp[i][k] を i 階から 2k 回エレベーターを使ってたどり着ける最上階として、ダブリングを行う

Y_i < W_i ならば、スタート地点を含むエレベーターでなるべく登っておき、ゴールを含むエレベーターでなるべく降りておいてから処理する

X_i = Z_i または Y_i = W_i の場合に注意

11/11

競プロ

https://atcoder.jp/contests/abc262/submissions/36383071

S, X は常に単調増加であり、最終的に S は空になるとしてよい

S に追加する集合を固定し、前から順に a_1, ..., a_n とおく。a_i を S から取り除くのは、

  • a_i 以降ではじめて a_i より大きい数を S に追加する直前
  • a_n を追加した後

のいずれかである。前者の場合に X が単調増加でなくなってしまうのは、a_i を X 追加するより前に a_i より大きい数を X に追加してしまった場合であり、これが起こるのは a_i < a_j < a_k を満たす整数 j < k < i が存在する場合のみである。よって、このような 3 整数が存在しないように a_1, ..., a_n を最大個数選ぶ問題となる

「A_l, ..., A_r のうち d 以上 u 以下のもののみを選ぶときの最大個数」を dp[l][r][d][u] とおき、これをメモ化再帰によって計算していく

l = r は自明で、l < r のとき

  • A_l を選ばないなら dp[l + 1][r][d][u]
  • A_l を選ぶなら、dp[l][x][d][A_l] + dp[x + 1][r][A_l][u] を全ての x について試す

とすればよい

11/12

競プロ

cerr デバッグライブラリを整備した。今日だけで結構 C++ に詳しくなったかもしれないな… とりあえず

  • 「引数それぞれに対してある処理をする」のようなマクロは書けない
  • マクロに MACRO(std::vector<int>{1, 2}) みたいなのを投げるとカンマのせいで壊れる。MACRO((std::vector<int>{1, 2})) にすると直る

というのは知らなかった。

Detection Idiom を使って型 T に対し std::ostream.operator<<(const T&) が定義されているか調べようとしたときに、modint のコンストラクタを explicit にしていないせいで std::vector<modint> が modint に変換可能と判断され、std::vector<modint> に対し operator<< が定義されていると誤って判定されるという罠を踏んだ

書いたもの↓

https://github.com/KodamaD/kod-library/blob/main/src/misc/debug.cpp

+α 今日の ABC の G を解いた

https://atcoder.jp/contests/abc277/submissions/36403640

ある移動方法について、頂点に書かれた 01 の列を b_1, ..., b_n と並べると、

  • b_i = b_j = 0, b_k = 1
  • i < k, j < k

を満たす i, j, k の組の個数がスコアになる

これを i < j < k を満たす組と i = j < k を満たす組に分類する。それぞれ DP で「 i, j, k のうち何個目まで決め終えたか？」を持って計算

11/13

競プロ

ライブラリについて

ラクするためのユーティリティだけ整備して、難しいデータ構造やアルゴリズムは他の人が準備したものを使えばよいのでは？と思った。多岐にわたるライブラリを自己製で最速・最良の状態で用意しておくのは非効率的な気がする とはいえ、どこまで自分で用意するかの境界を決めるのが難しい。平衡二分木とかになると流石に要らないと思うけど、畳み込みや FPS は (ACL に convolution があるとはいえ) 持っておきたい

解いたもの

https://atcoder.jp/contests/abc277/submissions/36465459

NM 変数の two-sat 各 X_i について M 個の bool 変数 b_{i, 1}, \dots, b_{i, M} を用意し、 b_{i, k} = 0 ならば b_{i, k+1} = 0 が成り立つように条件を課す。すると b_{i, 1}, \dots, b_{i, M} は 1,\dots,1, 0, \dots, 0 のように並び、 b_{i, j} = 1 であるものの個数を X_i として定めると、 X_i \lt k \Leftrightarrow b_{i, k} = 0 と言い換えられる。これを用いると各条件は O(M) 個の clause で書ける

5h

PTZ Summer 2022 Mirror Day 2 をやった。前回よりは活躍できた

C に「 A_i \neq P_i であるような順列 P を構成せよ」という問題があって、自分は綺麗な解法が思いつかなかったが、想定解が面白かった。

A_i が全て同じ値なら構成不可能。そうでない場合は必ず構成できる。

先頭 N-1 項は、すでに決めた整数が 1, \dots, N の円環上で常に区間をなすように決めていく。すると、つねにちょうど 2 通りの選択肢があるのでかならず条件を満たすように決められる。 P_N は一通りしかないので条件を満たさない可能性があるが、その場合 (A_N = P_N) は A_i \neq A_N となる i をとると(仮定より必ずとれる)、 P_N = A_N \neq A_i, P_i \neq P_N = A_N より P_i と P_N を swap すればよい。

11/14

射影幾何

調和点列の定義と、いくつかの性質の証明

競プロ

AHC016 をやり始めた

11/15

競プロ

AHC016 をやった 昼に提出したら 150 位くらいで、夜に改善して 95 位にした 折角だしメモとっておいて参加記出そうかな