日記 11/16–11/30

11/16

競プロ

AHC をずっとやっていたが、全くスコアが上がらず。残念

11/17

競プロ

AHC 進捗ダメです

解いたもの↓

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

行に対する操作 / 列に対する操作は順番を入れ替えても同じ。行 / 列それぞれについて昇順にできるか解けばよい

行は簡単。上の行の max <= 下の行の min が成り立たなければならず、これは適当にソートしてそれが条件を満たすか確かめればよい

列は、「ある列が別の列の左側でなければならない」を辺として表した有向グラフが DAG かどうか判定すればよい。グラフの構築は各行ごとに行う。中間ノードを導入してやると、辺の本数が二乗から落とせる

群論

競プロのやる気が出なかったので久しぶりに本を手に取った xH が左剰余類なの混乱するな…

11/18

競プロ

今日も今日とてライブラリの設計を考えていた 最近、std::size_t を使うかどうかで悩んでいる

メリット

  • 美的感覚に合う
  • C++ STL に合わせられる
  • 0 以上の整数であることを型で明示できる

デメリット

  • 普段使いするには面倒
  • 符号付き整数と混ぜて使うと注意を要する
  • 環境によっては int よりメモリを食う

どうしようか…

ところで、C++20 の機能を調べていたら欲しくなったので、AtCoder に導入されるとうれしい

11/19

機械学習

二年前くらいにかってそのまま置いてあった「Kaggleで勝つデータ分析の技術」を唐突に読み始めた なんで Python を使わなければいけないんだろう

競プロ

今週は ABC278 の tester をしていた。D, E の原案で、ADEG の tester をした

ジャッジ側がコンテスタント側より難しい。 g_i \oplus g_j = x となる (i, j) のうち i + j が最大となるものを各 x について管理する、という方針でできる

11/20

競プロ

ARC152 に参加、あまりにひどい結果に… 言い訳したくなるレベルだが、本気で出てこれなので逃げてはいけない

昔なら「今日は調子が悪かった」「問題との相性が悪かった」と逃げていたところだが、自分よりワンランク上の赤コーダーがこのような失敗をするのは想像できないので、ちゃんと実力不足を認めるべきだなあ、と思う

最後の JOI 春合宿や IOI でこのようなことが起こらないようにするためにも、ちゃんと練習しよう

upsolve↓

どの 2 点から出発しても、必ず 2 回出会う。出会う地点を X, Y とおく X から Y に行くまでに 2 人が歩く距離を a, b とおくと、

  • X で出発してから Y で出会うまでに片方が |a - b| 待つ
  • X で出会うまでと Y で出会った後で、2 人が歩く距離は 2L - a, 2L - b なので、合計 |a - b| 待つ

よって 2L + 2|a - b| が下界となる。これは、2 人が X から出発することで達成できる |a-b| の最小値を求めればよい

反省点 :

  • 1 回目、2 回目の出会うタイミングの間に注目するのは考察ノートに書いていたので、詰めるべきだった
  • 自明な下界が実は達成可能という方向の考察をすべきだった
  • 同じ場所から出発するとしてよいという大胆予想を試すべきだった

https://atcoder.jp/contests/arc152/submissions/36694047

2 要素のときは、差を d、小さい方を m として、 d + (m \bmod d) が答え 要素が増えた場合、m を最小値、d を最大値と最小値の差として考える。d は不変なので、d を中心にして考察すると良さそうだという気持ちになる 要素が増えても d + (m \bmod d) は達成できるので、 m \bmod d を最小化する問題になる

s に関して flip すると m \bmod d は 2(s - m) \bmod d 増える さらに、2 要素の差は不変なので、元々 s であった値による flip ではどう頑張っても \pm 2(s-m) \bmod m しか動かせない

これらを踏まえると、 d, 2(A_1 - m), \dots, 2(A_N - m) の gcd を g として、 m \bmod g が下界となる そして、これは実際に達成できる これについては、 \pm 2(s-m) \bmod m 動かす操作を要素が負になることなく何度でも行えることを示せばよく、最大値による flip を好きに挟むことにより可能である

反省点 :

  • 不変量として「全体の gcd」しか思いつかず、(4, 7, 10) のようなケースの扱い方がわからなかった
  • 実際に操作をすると、差分は「2 要素の差の 2 倍」となり、単なる差の gcd よりも若干厳しくなるので、そこに注目するべきだった
  • d を中心として考えたり、2 要素の差が不変であることに注目したりするのは典型なので、一度冷静に考え直すべきだった

https://atcoder.jp/contests/arc152/submissions/36691068

11/21

競プロ

N が偶数なら作れない N が奇数なら実は作れる (明らかに、辺は \frac{N-1}{2} 本)

2K > N なら、K を N-K で置き換えた場合を解いて、頂点番号を reverse ( u \leftarrow N - u - 1) すればよい

2K < N なら、 q = \left\lfloor \frac{N}{2K} \right\rfloor として、

  • (0, 1), (1, 2), \dots, (K-1, K)
  • (2K, 2K+1), \dots, (3K-1, 3K)
  • \vdots
  • (2(q-1)K, 2(q-1)K + 1), \dots, ((2q-1)K-1, (2q-1)K)

を追加したのち、 r = \frac{N - 2Kq - 1}{2} として、

  • (2qK + 1, (2q-1)K + r+1), \dots, (2qK + r, (2q-1)K + 2r)

を追加するとうまくいく。気持ちとしては、

  • N = 2K + 1 なら簡単
  • N > 2K + 1 の場合でも、最初の方は同じ方法で埋めて最後をうまく調整すればできないか？

となる。

https://atcoder.jp/contests/arc152/submissions/36703299

組合せゲーム理論

Subtraction Game の解析 手が有限なら periodic で、手が無限でも禁じ手が有限なら arithmetic periodic になるらしい

射影幾何

perspectivity と projectivity の定義とその性質について projectivity による群 PJ(l) の導入など

11/22

競プロ

最初は全て左側に沿わせた経路を作り、その経路を "ひも" だとおもって上下に引っ張ったときにできる経路を求めればよい

上から順にひもを伸ばしていく。現在のひもの経路を P_1, \dots, P_n として、末尾の3点を p, q, r とする p, q, r をこの順に結ぶひもを引っ張るときに q からひもが離れるとする。引っ張った結果、区間の右側に引っかかる場合があるが、引っかかる点は O((\log N)^2) くらいで求められる。引っかかる点を s として、 P_1, \dots, P_{n-3}, p, s を結ぶひもを (再帰的に) 引っ張る。そして、s, r を結ぶ線分が引っかかるかどうか判定し、引っ掛からなくなるまで同様の処理を続ける。

https://atcoder.jp/contests/arc001/submissions/36722593

11/23

競プロ

DAG であることが問題文に明確に書かれていない気がする…制約には f \lt t であると明記されているが

dp[u][h] を「頂点 u で戦闘後 HP が h のときにゴールするのにかかる時間の期待値の最小値」と定義し、ゴール側から順番に計算する。ここで、「スタート地点に戻る」という選択肢が現れるが、問題の答え (スタート地点からゴールにかかる時間の期待値の最小値) x を決め打ちすると計算できる。最後に dp[1][H] >= x かどうかを判定する。この判定方法が正しいか気になるところだが、遷移式をじっと睨むと、傾きが 1 以下の直線の min をとった形になっており、x - dp[1][H] が単調増加になっていることが確認できる (はず)

https://atcoder.jp/contests/arc016/submissions/36728723

グリッドを 45 度回転して考える。加算クエリは愚直に処理し、全ての x+y, x-y について、そこに足された値を持っておく

最大値クエリが難しい。ここで、直角三角形型のクエリが、辺の長さに対する線形時間で簡単に処理できることに着目する (x+y を増加させると、使える x-y の集合は増える一方で減らないので、chmax していけばよい) 。長方形を正方形に分割し、さらに二つの直角三角形に分割することで、O(N) で処理できる。

https://atcoder.jp/contests/arc047/submissions/36732773

11/24

競プロ

値の重複は取り除いてよいので、集合として考える。また、0 は取り除いておく。

まずは簡単なケース。

  • \mathrm{empty} なら Win
  • {1} なら Lose
  • {2} なら Lose
  • n \geq 3 のとき、 {n} なら Win ( n-1 で割る)

次に、複数の種類の値がある場合を考える。とりあえず 2 で割ってみると、

  • 2 以上の要素があり、かつ奇数が存在するなら Win

がわかる。3 で割ってみると、

  • 割った結果が {}, {1}, {2} になるなら簡単だが、 {1, 2} になる場合はすぐにはわからない。

4 で割ってみると、奇数が存在する場合はすでに解決しているので、

  • {2} になるなら Win

ということが新たにわかる。ここまでで、全て 4 の倍数の場合以外は解決した。

  • 全て 4 の倍数のとき
  • 3 で割ると {1, 2} になるとき

が分からないので、実験コードを書いて上の両方の条件を満たすケースを入れてみると、

  • {4, 8} は Lose
  • {8, 16} は Win で、先手は一手目で 12 で割らなくてはならない

ということがわかる。ここで、3 で割るのではなく 12 で割るというのがヒントになる。 全て 4 の倍数で、3 で割ると {1, 2} となるとき、12 以上の要素が存在するならば、

  • 12 で割ることで {4, 8} になるので Win

とわかる。これにより、全て 12 の倍数の場合以外は解決した。

ここで一旦立ち止まって制約を眺める。 a_i \leq 200 なので、全て 12 の倍数であるような集合は高々 2^{16} 通りしかない。これは愚直にメモ化再帰しても間に合う。 よって、全て 12 の倍数のときは bitDP で別に処理すればよく、そうでない場合は、 {1}, {2}, {4, 8} を除いて Win である。

https://atcoder.jp/contests/arc134/submissions/36759552

11/25

競プロ

部内で JOI 対策バチャがあった。後ろから解いていたら、Cake (難易度 12) を解いただけで 80 分使ってしまった まぁ、ちゃんと解けたので OK

その他

ちょっとだけ Pandas の勉強をした。メソッドの仕様などをいちいち検索するのが面倒

11/26

機械学習

(機械学習というよりはデータサイエンスだけど) Kaggle 本を少し読み進めた。評価関数だけでこんなにあるのか…という感じ 多分実践しないと身につかないけど、なかなかコンペのためのまとまった時間を取れず、どうしようか

競プロ

久しぶりに CF のバチャをやった。

0 を +1, 1 を -1 で置き換える。累積和を y_i として、S に入れられるのは y_l = y_r を満たす区間である。

「-1 される全ての箇所がいずれかの区間に含まれる」という条件を達成するには、次のようにする。

  • n = 0, 1, 2, 3, ... に対し、初めて y_i = n となる位置を f_n とおく
  • [f_k, f_{k+1}-1] を S に追加する

ある場所を flip することで、集合 {f_n} は高々 2 要素しか出入りしないので、変化する区間は高々 4 つである。よって 4N 回の出し入れで解ける。 f_n を見つけるためには区間加算の遅延セグ木で二分探索をする。

https://codeforces.com/contest/1758/submission/182595283

11/27

競プロ

[x^{M - N}] (1-x)^{-2N} \prod_{n=1}^{\infty}(1-x^n) が答え。

M-N \leq N という制約があるおかげで五角数定理が使える。次数 M-N 以下の項は O(\sqrt{N}) 個しかないので、それぞれに対し (1-x)^{-2N} の対応する項の係数をかけて足し合わせる。

二項係数の計算には Lucas の定理を用いる。

https://atcoder.jp/contests/abc279/submissions/36849042

五角数定理関連、面白そうな話が多いので読みたい。

↓分割数を O(N \log N) で

https://suu-0313.hatenablog.com/entry/2022/06/15/160626

↓ヤング図形との関連？

https://zenn.dev/koboshi/articles/306304c0381c1e

11/28

競プロ

Codeforces Round #829 (Div. 1) バチャ

0 がない場合は簡単。N が偶数でなければならず、逆に偶数の時は、前から 2 個ずつグループ分けし、グループの 2 数が異なるならそれらをさらに一つずつに分割すればよい。

0 がある場合は、1,-1 が連続する連続部分列に分け、それぞれに対し↑のように分ける。すると各グループの総和は -1,0,1 のいずれかになるので、0 を含める / 含めないによって調節して上手く総和を 0 にする。

もともとの総和が偶数の時は必ず構成でき、そうでないときは絶対にできないのでこれで OK

各 1 \leq n \leq x について n! が足される回数を数える。このとき、 n! が n+1 回足されたら (n+1)! が一回足されたとみなす。

すると、n < x ならば n! が足された回数は 0 回でなければならない。1 回以上のものがあるなら、最小のものを k とおくと、 (k+1)! で割った余りが 0 にならず不適。

終了条件を考える。0 の個数を Z として、先頭 Z 項がすべて 0 になっていればよい。

先頭 Z 項に 1 が k 個あるとすると、操作によって k は変化しないか 1 減るかのどちらかである。1 減る操作は k^2 通りあるので、期待値 \frac{N(N-1)}{2k^2} 回で 1 減る。あとはこれを各 k について足す。

それぞれのベッドはたかだか 1 回しか動かないとして良い (未証明。こうじゃなきゃ解けないだろの気持ち) 。ベッドではなく空きマスが動くと考え、グラフを作り、それぞれのマスについてそのマスを空きマスにするための最小コストをダイクストラ法で求める。市松模様に分けると、隣接する 2 マスを空けるとき、2 つのマスを空けるための操作は干渉しないことがわかるので、OK

11/29 以降

多忙につき休止。12 月中旬に再開するつもり 大量に Scrap を作成するのが気持ち悪くなってきたので、一つにまとめるか悩んでいる それに Zenn の Scrap を日記に使うという方法自体おかしい気がするんだよな