AHC013 参加記

問題文を開く

どう頑張っても実装がだるそうでやる気がなくなる

サンプルコードが配布されていることに気づく

そのまま出すと全人類だしてる点数が出る

メンバのメルセンヌ・ツイスターをグローバルに出して時間いっぱい solver を回して一番いいやつを出力する

ここまで 10～20分くらい

提出頻度制限が解除されていたので提出して寝る

470位 1138perf でした

【Jstris】20+n TSD のやり方

はじめに

みんな大好き20TSD, 普通にLSTすれば21くらいまではワンチャンあるけどそれより上はどうすへばいいの？

そんなあなたにJstris！ 僕と記録を競いませんか？

前提知識

テトリスの致死判定について

これは

  • テトリミノの出現位置にすでにブロックが存在している
  • 20段目より上にテトリミノを置く

の2通りがあります

テトリミノは画面外の 21, 22 段目に出現します この出現位置に既にブロックが存在していた場合, NEXTがそこに突き刺さって終わります

画面に映っている1番上の段が20段目です つまり画面外にテトリミノを設置してはいけません ただし, 18〜20段目に設置したミノが画面外にはみ出るのは問題ありません

出現位置と負け判定(旧) - テトリスのかけら - atwiki（アットウィキ）

この記事がわかりやすかったです

Jstris の仕様について

まず 20TSDモードについて

上記のものに加えて, TSD以外でライン消去を行った場合にも致死判定を受けます つまり, 連続で何回TSDを打てるのか競えるモードですね

ここまで聞くとどう頑張っても20+2,3回くらいが限界に思えます

実際, ぷよぷよテトリスにおいて最強のAIとの呼び声高い Cold Clear さんでも, 24回が限界なようです

[PPT AI] Cold Clear - 24 T-Spin Doubles - YouTube

人力で24回 (置きミスがなければ25回) を達成している方もいらっしゃいました すごすぎ

【ぷよぷよテトリス2】24TSDs 【20TSD】 - YouTube

しかし, Jstris の仕様を利用することでこの限界を突破できます

それが Line Clipping です！

Line Clipping in Jstris 20 TSD - YouTube

この動画を見ると, 明らかにおかしな点があると思います 既にブロックが存在している場所にミノを置いているように見えますよね

Jstris では, 設置したミノの画面外にはみ出した部分が消える というすごい仕様があるため, このようなことが可能になっています

初めて気づいたときにはバグかと思ったのですが, REN の弱体化のための仕様なのではないか という話もありました

正確には, 22段目以上の部分は消える 21段目の部分はそのまま残るが, 同じ位置に別のブロックを重ねることが出来る

っぽいです 厳密な仕様は知りませんが, いろいろ試した感じ多分これで合っていると思います

やり方

方針

とにかくたくさんミノを消したい, できるだけTspinをする場所に積み上げたくない

ということで, ドネイトをします

開幕TSDをしたときの2巡目でたまにやるかっこいいドネイトですが, これは乗っけた分を全部消してるので積み上がりません

このドネイト

TSD 二回打つと全部消える

このドネイトを無限に行うことで, 高さを稼いでいきます すると余るミノが大量に出てくるので, これを 右三列に積み上げ, Line Clipping で消していくわけです

ドネイトに使わないミノはすべて右三列に積まないといけないので普通に難しいですが, これは慣れるしかないです

ネクストをよく見てドネイトの先読みもして何とかします

途中経過 J Z を置くとドネイトになる

何回かこれを挟んで, 限界になったら右の更に 1, 2 列を埋めて普通の LST をする というようなことをすると 30TSD ほど出すことができます

【Jstris】29 TSDs【20TSD】 - YouTube

Line Clipping でミノを消す必要がありますが, 21 段目のブロックは消えずに残ってしまうので, 画面外がどうなっているのか を把握しながら消していく必要があります (特に SZ)

ここからさらに回数を増やすためには, Oミノと Iミノが邪魔になってきます

Oミノが邪魔な理由は, 21 段目は消えないということは高さ 2 しかない Oミノは消すことが不可能 (重ねるのはできるが) なので, どう頑張っても右三列だけでは処理しきれなくなるため, Iミノが邪魔な理由は, どう回転しても右三列に乗らないためです

そこで, Oミノ専用の置き場所を作ることを考えました

J をひっかけて伸ばしている

このように, 限界がきたらミノをひっかけて2列左に伸ばします

このとき, 右三列は 21段目を埋め, 伸ばした二列は開けるようにします

すると, 次に TSD を打つと二列下がって図のようになります

TSD 打った

右三列は Line Clipping をして, Oミノは空いたところに置きます

一巡置きました

するとまた先ほどの状況に戻りますね

伸ばした部分が一番下に来るまでこれを繰り返します

Oミノがきれい

この方法の利点は, Oミノの部分は 21段目が開いているので Iミノの致死判定を回避できることです

また, Oミノを置いた後でもどのミノも180°回転を駆使することで右側に持っていくことができます (Zミノの回転法則わかってないですが, なんか越える)

一番下まで来たら, うまく隙間を埋めてあとは LST を頑張ります

LST に移行

こうすると, 50 TSD くらい出すことができます

【WR】52 TSDs in 6:50.853 【Jstris】 - YouTube

おわりに

暇だったので書きました 暇な人は挑戦してみてください

上手くいった とか もっといい方法見つけた とか ここ教えてほしい とかあったら教えてもらえると嬉しいです

意識してることとかは暇なときに追記するかもしれません

セグ木に関数を持たせるのやめて代数的構造を作ることにした

しました

動的セグ木とかいろいろ作ったやつはまだ放置しています(ポインタとか適当すぎたしどうせならまとめて書き直したい)

セグ木を最近生やさなすぎてどんな代数的構造を用意しておけばいいのか全然思いつきません 誰か教えてください

無駄に区間等差数列更新とか作ってみました 一生使う気がしません

ICPC 2022国内予選 参加期

実は出ていた

競プロ自体モチベがなくてそこまでやる気はなかったが, せっかく誘ってもらったので頑張るかぁという感じ

とりあえず最初はABC並列で解くことになっていたが, 何故かAtCoderのレートは僕がいちばん高かったのでCに回される 去年の嫌な記憶が蘇ってきた

前日

気晴らしに去年のC問題を解く 全然いい実装が思いつかなかったので提出コードを見てみた 二分木になることがわかっているので累積和みたいなことをしなくていい(全方位木DPの計算量コーナーケースであるところのウニがない)ということで pair で子供を持って全パターン書いた 割と綺麗にかけたかな？

結構バグったので, 去年の自分だと最初から取り掛かっていても結局解けていなさそうだなぁと思いつつAC 久々に構文解析を書いたのでまぁよし

当日

バイトが入っている日だったので非常に怖かったが, 例年通りの時間だったので余裕で間に合う ついでにMonsterを買ってくる

今年もトラブル起きるかなぁと話しながら待っていると何事もなく始まった 運営さんありがとうございます

Cを開いてみるとなんか普通の問題 とりあえず数列の和を求める関数書くかめんどくさ って思ったが冷静に考えるとただの二乗だった 親切

DPが頭によぎったがどう考えても計算量が落ちない

こんなのどうせ貪欲に長くとって等間隔に切ればいいだろと思って切る個数を全探索するコードを書く 小さいケースがコーナーになってそうなので early return もする

サンプルが合わない 焦ったが冷静に考えると合うわけが無い 植木算ができていなかった 小学生からやり直せ

添字をガチャガチャしていたらAが通ったらしい 自分もサンプルがあったので提出したら通った

合流してDを見る 何故こんな所に NTT-friendly な mod での数え上げがあるんだ

問題を理解したがやばそう DPするしかなさそうだがどう見ても状態数が多すぎる

fps という単語が脳裏によぎった 最近その辺の勉強したつもりだったけどまだまだ何もわからん

とりあえずほかの問題も読んでみることにする

Eを見てみる なんかやばそうなやつを復元するらしい 端っこの列くらいしか埋まる気がしない

Fを見てみる 出たな構文解析 けど構文解析は本質じゃなさそう 全探索は無理だし貪欲も嘘っぽい 激ヤバ区間DPくらいしか思いつかないが計算量がやばそう

Gを見てみる 出たな幾何 決め打ち2分探索にしか見えないが決めうったところで判定が簡単になっている気がしない なんかいい感じの性質がありそうだが見える気がしない

Hを見てみる 変なイラストが見えたが問題文が頭に入ってこない 疲れているのか焦っているのか

そういえばBが解けていないらしい 読んでみるとやるだけっぽいが実装がゴミすぎ 無限にコーナーケースが思いつく

ちょっと書いてみたが挫折した Dに逃げる

後ろからやればいいのではと言われた 確かにそれは嬉しそう けどなんか3次元DPとかになりそう

t の隣接項が減少していたら絶対同じ列にしないとダメと言われた 確かにそう それを削れば単調増加列になると言われたがそれは嘘 3,1,2 のようなケースがすぐに思いつく

3,1,2 は 3,2 じゃなくて 3 にすれば単調増加になると気づいた ホントっぽい

二乗がギリギリ許されてる制約なので愚直に erase するコードを書く stackとかで上手くやれば線形になりそうだけど無視

一生サンプルが合わないが, 削除は上手くできていそう DPの遷移を間違えていた

直したらサンプルが通ったがACが出ない 焦る

まだDPの遷移を間違えていた サンプル合うなよ 投げる ACが出ない

全然バグが見当たらないので, チームメイトをラバーダック代わりにして考察を垂れ流しながらコードを追う

よく見ると自分の出力の行数が明らかに足りていない そういえば si の位置を逆引きする配列のサイズを削ったあとの要素数分しか用意していなかった そのせいで配列外参照してセグフォで落ちていたっぽいかな？

エラー出せよC++ 何も言わずに終了されたので全く気づいていなかった

直したらACが出た 嬉しいが悲しい 1時間くらい無駄にした

順位表を見た感じ後通せそうなのがEくらいしかないので眺める

無理だろこれ かっこ列の存在判定, 復元っぽいけどどう見ても無理がある

線形計画問題に見えてきたのでワンチャンフローでも流すのか？ とか考えたがそんなわけない

無理すぎて笑いながらFの構文解析部分だけ書いた

時間切れになったのでTLを見る みんな嬉しがったり悔しがったりしていて楽しそう

東工大は20年振り？ とかで東大に勝って1位らしい すごいね

すごいスピードで解説が上がっていたので眺める

Dはだいたい考察通り 問題の E を見ると何も書いていなかった これ解説なんですか？ 解説に書いてあることくらいは4秒でわかったが, その次どうすればいいのか全然わからなかった 実力が全く足りていなさそう

Fもだいたい思った通りだった Eに使ってる時間とDのセグフォに気づいていない時間投入したらワンチャンあったかなぁ どうせバグり散らかして間に合ってなさそうな気もする

Regional, 横浜まで行くのめんどくさい… オンラインにならんかなと不謹慎なことを思いつつこれからのことを考えてみると, 去年の問題の感じで来られると良くて1完だなということに気づく

困った どうしようかな 特に問題文が英語なのがやばい 誰か代わりに出てくれ

分割数 p(n) を高速に求める

競技プログラミング

競プロにおいて分割数は p(n, k) = n を k 個の非負整数の和で表す方法の数 (ただし, 順番は区別しない) であり, 計算量オーダーが \Theta(nk) である dp が(蟻本などに載っており)有名である

しかし, 一般に数論の世界で分割数というと p(n) = n を自然数の和で表す方法 であり, p(n) = p(n, n) である

これは同じ dp をすると \Theta(n ^ 2) かかってしまうが, n = k である場合に限りより高速な方法がある

まず, p(n) の母関数を考える

1 を何個使うか, 2 を何個使うか.... ということを考えると,

 \begin{align}
\displaystyle\sum _ {n  = 0} ^ {\infty} p(n) x ^ n &= (1 + x + x ^ 2 + \cdots )(1 + x ^ 2 + x ^ 4 + \cdots ) \cdots \cr
&= \prod _ {n  = 1} ^ {\infty} (1 + x ^n + x ^ {2n} + \cdots )
\end{align}

と書くことができる

 1 + x + x ^ 2 + \cdots = \dfrac{1}{1 - x}

と表せるため,

 \begin{align}
\displaystyle\sum _ {n  = 0} ^ {\infty} p(n) x ^ n &= \prod _ {n  = 1} ^ {\infty} \dfrac{1}{1 - x ^ n}
\end{align}

として, p(n) の母関数を求めることができた

できたが, 求めるのが簡単にはなっていない

ここで, 右辺の逆数である \prod _ {n = 1} ^ {\infty}(1 - x ^ n) について考えてみる

これは, オイラーの五角数定理 より

 \begin{align}
\prod _ {n  = 1} ^ {\infty}(1 - x ^ n) = \displaystyle\sum _ {n  = -\infty} ^ {\infty} (-1) ^ n x ^ {n(3n - 1)/2}
\end{align}

と書くことができる

凄まじく非自明だが, 証明も大変

ヤコビの三重積 から証明する方法, ヤング図形との対応から頑張る方法, Shanksによる天下り式な証明 などがあります 暇だったら書きます

0 \le n \le N について求められればいいので

 \begin{align}
\prod _ {n  = 0} ^ {N}(1 - x ^ n) = 1 + \displaystyle\sum _ {1 \le n \land n(3n - 1)/2 \le N} (-1) ^ n x ^ {n(3n - 1)/2} + \displaystyle\sum _ {1 \le n \land n(3n + 1)/2 \le N} (-1) ^ n x ^ {n(3n + 1)/2}
\end{align}

と書ける

これは簡単に求めることができて, NTT-friendly な mod でならニュートン法を用いて逆数を O(n\log n) で求めることができる

そうでない場合, さらに式変形をする

 \begin{align}
\displaystyle\sum _ {n  = 0} ^ {\infty} p(n) x ^ n &= \prod _ {n  = 1} ^ {\infty} \dfrac{1}{1 - x ^ n}
\end{align}

と

 \begin{align}
\prod _ {n  = 1} ^ {\infty}(1 - x ^ n) = \displaystyle\sum _ {n  = -\infty} ^ {\infty} (-1) ^ n x ^ {n(3n - 1)/2}
\end{align}

を掛け合わせて

 \begin{align}
\left( \displaystyle\sum _ {n  = 0} ^ {\infty} p(n) x ^ n \right) \left(  \displaystyle\sum _ {n  = -\infty} ^ {\infty} (-1) ^ n x ^ {n(3n - 1)/2} \right) = 1
\end{align}

と書ける

x ^ n の項の係数に注目することで

 \begin{align}
p(n) - p(n-1) - p(n-2) + p(n-5) \cdots = 0
\end{align}

という式が出てくる

したがって, 漸化式

 \begin{align}
p(0) &= 1 \cr
p(n) &= \displaystyle\sum _ {1 \le k \land k(3k - 1)/2 \le n} (-1) ^ {k-1} p\left(n - \dfrac{k(3k - 1)}{2}\right) + \displaystyle\sum _ {1 \le l \land l(3l + 1)/2 \le n} (-1) ^ {l-1} p\left(n - \dfrac{l(3l + 1)}{2}\right)
\end{align}

が得られる

この式を用いて愚直に求めていくことで, O(n \sqrt{n}) で求めることができる

Library Checker さんの Partition Function で verify できる

AHC011 参加記

AtCoder 競技プログラミング

絶対いらないけど色変したしてきとうに

順位表

1152826674点で228位でした

二時間ちょいくらいで取って色も変わったのでコスパ的にまぁまぁかなという気持ち

やったこと

  • 問題の第一印象

とても面白そう + めちゃくちゃめんどくさそう

  • 初回提出

こんかいの自明は白紙提出 Text の AC 数 が増えました

  • スコア計算を書く

辺を UnionFind に突っ込みながら閉路があったら記録 (既につながっている連結成分を繋ごうとしたら閉路) 残った中で一番大きいやつになんかかけたらおわり

辺を切る操作ができないから動かして変えてってできないからどうしようかなーという気持ちになった

  • 第一感

スライドというのを無視してとりあえずあるものを頑張って組み合わせて木を作る → 番号を振ってスライドパズルを解く

をすればいいのかなと思った めんどくさかったのでやめた

  • 適当

山登りみたいなことをしたい

一手ごとに評価していってもあんまり意味ない + めちゃくちゃ時間かかりそうだったので適当な手数進めてよくなったら更新をした 13499173点

局所解がひどすぎる + 時間がめっちゃ余っていたのでてきとうに 20回くらい同じことをして一番いいやつを出してみた 18356575点

どうせならいいやつを深くやりたい → 途中経過を全部保存しといてある程度たまったら score の降順に sort, ある程度で切り捨てて残ったやつで同じことを試す をしてみた → 19322128点

  • やらなかったこと/終わってから思ったこと

手元実行とか一度もしなかったのでどんな感じに動いてたのか不明

結構時間余ってそうだったし序盤は BFS で全部試してみてもよかったかなーという気持ち

盤面の重複探索除去のために vector<vector<int>> の比較をしていたが, 制約的に一列併せて一個の int に入りそうだったしそれくらいはしてもよかったかなー

zobrist hash は真っ先に思いついたけどめんどくさいしいいやって思ってやめてしまった

UnionFind 用の配列は一回作ったやつ使いまわせばよかった...

半分くらいバイト中にやったので完璧な時間の有効活用だった

おしまい

Count Subset Sum

はじめに

Library Checker さんの \# _ p Subset Sum

Library Checker

を解いたのですが, 日本語の解説がぱっと見なさそう？ なので書いておきます

(タイトルに数式を入れる方法がわからなかったので Count Subset Sum としました やり方知ってる方がいたら教えてください)

本文

概要

整数列 s_0, s_1, \cdots, s_{n-1} があったときに, 各 t \in [1, T] について, 総和が t になるような部分列の数を \bmod 998244353 で求めます

制約

  • 1\le n \le 10 ^ 6
  • 1 \le T \le 5\times10 ^ 5
  • 1 \le s_i \le T

解法

みんな大好き形式的冪級数で考えます

s_i を使う/使わない を 1 + x ^ {s_i} と表現すれば

f(x) = \displaystyle\prod_{i = 0}^{n-1} (1 + x^{s_i}) としたときに f(x) の x ^ t の項の係数が t に対する答えです

さて, これは次数がとても大きくなりうるので高速に計算するのはつらいです

ということで, 積を計算するのはつらいので和に変換します

f(x) = \exp(\log f(x)) = \exp( \displaystyle\sum_{i = 0}^{n-1} \log (1 + x^{s_i}) )

形式的冪級数の \exp はニュートン法を用いることで項数を n として O(n\log n) で求めることができるので, \displaystyle\sum_{i = 0}^{n-1} \log (1 + x^{s_i}) を求めることができれば O(T\log T) で答えが求まります

ということで \displaystyle\sum_{i = 0}^{n-1} \log (1 + x^{s_i}) を求めます

ここで, \log (1 + x) のマクローリン展開を考えると

\log (1 + x) = x - \dfrac{x ^ 2}{2} + \dfrac{x ^ 3}{3} - \cdots = \displaystyle\sum _ {k \ge 1}\dfrac{(-1) ^ {k-1}}{k} x ^ k

と書けるので,

\log (1 + x ^ {s_i}) = \displaystyle\sum _ {k \ge 1}\dfrac{(-1) ^ {k-1}}{k} x ^ {k{s_i}}

です 無限に続きますが, 今回次数は T あれば十分です

さて, c_k を s_i = k となるような i の数 とすると

\displaystyle\sum _ {i = 0} ^ {n-1} \log (1 + x ^ {s_i}) = \displaystyle\sum _ {k = 1} ^ {T} c_k \log (1 + x ^ {k})

と書けますが, 各 k について上の式を計算すると計算回数は調和級数で抑えられます

ということでこちらは O(n + T\log T) で求めることができます

全体でみても O(n + T\log T) で求めることができました

おわりに

【競技プログラミング】形式的冪級数の応用テクニック(前編) - Qiita

https://arxiv.org/pdf/1807.11597.pdf

この辺見たらわかると思います