2020-10-26

ARC106 D - Powers (畳み込み解)

NTT

解法

まずは式を分解していきます。ループの中、つまり $(A_{L} + A_{R})^{X}$ に注目すると、これは二項定理そのもので
$\displaystyle (A_{L} + A_{R})^{X} = \sum_{i = 0}^{X} \,_{X}C_{i}A_{L}^{i}A_{R}^{X-i}$
となり、さらにコンビネーションを分解すると、
$\displaystyle \sum_{i = 0}^{X} \left( X! \times \frac{A_{L}^{i}}{i!} \times \frac{A_{R}^{X-i}}{(X-i)!}\right)$
となります。 $X!$ は最後にかければよいので、 $\frac{A_{L}^{i}}{i!} \times \frac{A_{R}^{X-i}}{(X-i)!}$ の部分が高速に計算できればよいです。
ここから、答えを計算しやすくするため、ループの部分のインデックスをいじることについて考えます。

$\displaystyle \sum_{L=1}^{N-1}\sum_{R=L+1}^{N}(A_{L} + A_{R})^{X}$
$\displaystyle \sum_{L=1}^{N}\sum_{R=1}^{N}(A_{L} + A_{R})^{X}$

上記の2つの式を比較すると、上の式を2倍した後、 $\sum_{i=1}^{N}(A_{i} + A_{i})^{X}$ を足したものが下の式になっています。
なので、下の式が求められれば、上の式の値もなんとか求められそうだ、となります。この後は下の式を計算することについて考えていきましょう。
ループの中の式について、分解した後のものを当てはめてみます。
$\displaystyle X! \times \sum_{L=1}^{N}\sum_{R=1}^{N}\sum_{i = 0}^{X} \left( \frac{A_{L}^{i}}{i!} \times \frac{A_{R}^{X-i}}{(X-i)!}\right)$
結局、以下の値を求められれば良いことになります。
$\displaystyle X! \times \sum_{i = 0}^{X} \left( \sum_{L=1}^{N}\frac{A_{L}^{i}}{i!} \times \sum_{R=1}^{N}\frac{A_{R}^{X-i}}{(X-i)!}\right)$
よって、 $\displaystyle B_{i} = \sum_{p=1}^{N}\frac{A_{p}^{i}}{i!}$ とすることで、
$\displaystyle X! \times \sum_{i = 0}^{X} \left( B_{i} \times B_{X-i}\right)$
となり、シグマの部分が畳み込みの式そのものになっています。
よって、NTTを用いてこれを計算すれば、 $\sum_{L=1}^{N}\sum_{R=1}^{N}(A_{L} + A_{R})^{X}$ が求まることがわかりました。
さて、この値を2で割った後、最後に $\sum_{i=1}^{N}(A_{i} + A_{i})^{X}$ を引かなければなりません。ですが、こちらは以下のように式変形します。
$\displaystyle \sum_{i=1}^{N}(A_{i} + A_{i})^{X} = \sum_{i=1}^{N}\left(A_{i}^{X} \times \sum_{p=0}^{X}\,_{X}C_{p}\right)$
最初と同様、コンビネーションを分解し、
$\displaystyle \sum_{i=1}^{N}\left(A_{i}^{X}X! \times \sum_{p=0}^{X}\left(\frac{1}{p!} \times \frac{1}{(X-p)!}\right)\right)$
とすると、同様に畳み込みの式が出てくるので、NTTを用いて計算できます。
まぁ、 $2A_{i}$ を $X$ 乗すれば良いですが…
ということで、これで全ての欲しい式がそろったので、あとは計算するだけです。

感想

NTT、FFTは最近始めたばかりなので、今回の問題を自力でコンテスト中に通せたのは嬉しいです。
コンビネーションがNTTに落とし込めるのを既に学習していたのが大きいかもしれません。
逆に、想定解の方法が全然思い浮かびませんでした…

D、最近でぐわーさんのPDFでAGCのコンビネーションを分解してNTTに投げる問題やったおかげで解けた
— ツバサ (@emtsu_ba) 2020年10月24日

2020-10-26

ICPC2020模擬国内参加記

番外編 ICPC

とまとさん、るぎうさんと組んでの出場です。

準備
流れ
結果
終わり

準備

前日はライブラリの印刷をしました。去年はwordに貼り付けて適当に印刷していましたが、読みづらい(シンタックスハイライトが欲しい)上、量も増えてきたので以下のサイトを利用しました。

pazzle1230.hatenablog.com

僕らはオフラインで試しにやってみる、という話になっていたのですが、当日、急遽とまとさんがオンライン参戦に変更になったので、通話等の準備で少しばたばたしました。

流れ

僕がA、とまとさんがB、るぎうさんがCを読みます。
Aをサクっと通したのでとりあえずDを読みました。
Bは情理オリで出た問題に似ているらしく、しばらくしたらACしていました。
Dを読み終わって、C担当のるぎうさんがやりたくなさそうにしていたので考察に参戦すると、適当に正方形の辺をメモしてBFSっぽいことをすればいいね、となりました。これはとまとさんがやるのがよさそう！って二人で決めつけ、Bが終わったとまとさんに~~押し付け~~お願いしました。

その後は、とまとさんがCの実装、るぎうさんがD、僕がEを担当することになり、それぞれ格闘していました。
しばらくすると、るぎうさんが考察を終えたらしく実装を開始し、とまとさんもCをズバッと通してくださりました。

とまとさんがEに合流したのとほぼ同時くらいで僕がEの2-SATに気づき、とりあえず3乗解を書いてしまおう、となり実装を開始します。
僕の2-SATライブラリは、2-SAT部分とSCC部分に分かれていたため、とまとさんが2-SATの部分、僕がSCC部分をそれぞれ写経してドッキングしました(今回ならではっぽいムーブでニコニコしていました)。
その後、実装を終えてやっぱり遅いな～って言っていたところで、とまとさんが「二分探索でよくない？」と言っていたので書き直すと、そこそこの速度で実行が終わり、ACできました。しゃくとりは辺の削除ができないから難しいなーって言っていたのに二分探索のことを忘れていたのでちょっと悲しいです(そもそも、setでグラフを持てば辺も削除できます…)。

https://twitter.com/emtsu_ba/status/1320278050727055360

るぎうさんがDに苦戦しているので、時々声をかけつつ、残った二人は一番通っていたHへ。
(よくよく考えると、とりあえずFを先に見ておいて、どちらか一人をFに縛り付けるのが最適だったかもしれません…)
Hを考えていると、閉路があるときは0になって、あとはDAGパターンがわかればいいねーとなり、いろいろ考えていました。
サンプルが $-1/m$ になっていたので、絶対違うけど出しちゃうか！ｗって二人で笑いながら出し、もちろんWA。その後しばらく、Hでペナを吐いたチームが自分達だけだったので少し恥ずかしくなりました…

Dがやばそうなので駆けつけると、どうやらテストケースに対し、1つだけ明らかにおかしい答えがでていました(文字列をリバースして解いても答えが同じになるはずなので、assertを入れていたそうですが、それにひっかかるケースが1つだけあるとのこと)。
そのケースは長すぎてデバッグ不可能だったので、自分が長さ18以下で全部の文字列を列挙するコードを適当に生成しつき合わせてみます。
長さが13以降の文字列に対し、なぜか上記のassertで落ちるケースが存在していましたが、どうやら、元の文字列とリバースした文字列の答えのmaxが、正しい答えになっているみたいでした。
H問題でペナを出してハイになっていた僕が「とりあえず、maxで出してみませんか？ｗ」と言って、るぎうさんに無理やり提出させると…なぜかAC(?????????)。
よくわかりませんが、これでEまでの5完になり、そこそこの順位になりました。

最後は全員Hに集合して、~~この手の問題に強そうなるぎうさんが解くのを横で眺めて~~三人で力を合わせて考察していましたが、時間も無く途中で終わりました。

結果

対象チームの中で16位でした。この調子でいけば、自分の大学からはうちのチームと、後輩チームが1つ抜けるみたいです。わーい。

終わり

並列実装が結構あったので恩恵はやっぱりでかそうです。昨年弊学トップチームのメンバーだった先輩二人にキャリーしてもらうのは楽しい！

2020-10-16

AGC037 D - Sorting a Grid

二部マッチング Dinic法(最大流,最小カット) 構築

問題
 提出コード

解法

当たり前ですが、ある数字 $X$ を取ってくると、最終的にどの行、どの列にいるべきか、というのが決まっています。
そこから逆算すると、3回目の操作開始時点では、

全ての数について、いるべき行は正しい

という条件が成り立っていればよいです。なので、そこからさらに逆転して、2回目の操作開始時点では、

それぞれの列について、そこに存在する数字における最終的にいるべき行は全て異なる

という条件が必要なことがわかります。これが成り立っているとき、2回目の操作では、正しい行に移動してあげる、という操作をすればよいです(=それぞれの列ごとに数字をソートすればよいです)。
1回目の操作では、行の中で自由に順番を入れ替えることができます。
それぞれの数字について、最終的にいるべき行が決まっていて、1回目の操作後は、それぞれの列についてその値がバラバラになるようにする…
つまり、バラバラになるように"マッチング"をさせればよいです。
ということで、それぞれの列について順番に、合計 $M$ 回マッチングを行います。
$i$ 回目のマッチングでは、 $i$ 列目について、 "数字を置く行数"と、"最終的にいるべき行の値がなんであるか"をマッチングさせればよいです。
これを繰り返せば、フローを流し、復元を行うことで答えを求めることができます。

感想

フローと復元を行ったので実装が特別軽くはなく、AGCっぽくないと感じまてしまいました…

2020-10-11

京都大学プログラミングコンテスト 2020 H - Beans on the Grid

グランディ数 Segment Tree(セグ木)

問題
 提出コード

解法

豆は自由に選んで操作できるので、定石通り、それぞれの豆に対してグランディ数を求め、最後にxorを取れば良いです。
まず、とりうるグランディ数の値を考えると、遷移先としてあり得るのが{右、左、下}の3パターンが最大です。よって、グランディ数は最大でも3にしかなりません。
そこで、例えば左右の2方向にしか移動できないとしたとき、下方向のグランディ数は4であったと考えても、答えは変わりません。これを利用して、遷移できない部分(皿がないマスやマス目外、一周して同じ方向に進めない場合)の遷移先のグランディ数は4であった、と置くことにします。

豆については、大きく2つのパターンがあります。

ゲーム開始時、もしくは下に移動した直後であり、左右(+下)のどちらも選べる状態
すでに左右どちらかに進んでいて、同じ方向(+下)にしか進めない状態

1のパターンが最終的に欲しいグランディ数になります。下の行から上の行に向かって、順にグランディ数を計算していきます。

今、 $i$ 行目のマス目についてグランディ数を求めるとします。このとき、 $i+1$ 行目については求まっています( $i = H$ であれば、下は全て4です)。
先ほどの2つのパターンのうち、2番目を先に計算します。左に進む場合と右に進む場合は、文字列をリバースすればやることが同じなので、片方についてのみ話します。
$i$ 行目のあるマスにて、左側に進んでいる状態だとします。自分の左隣のマスのグランディ数を0 ~ 4のうち1つ決めると、左と下の遷移先のグランディ数が決まるので、自分自身のグランディ数も決まります。全てのマスについてこれを計算します。
すると、これは区間マージができます。
ある区間について、左端の1マス左隣のグランディ数が $x(0 \leq x \leq 4)$ だったときの、区間の右端のグランディ数 $g_{x}$ 、という情報の持ち方をします。
よくあるダブリングと同様、2つの区間をマージする場合、
マージ後の区間における、左端の左隣が $x$ だったときの、右端のグランディ数は
$rg_{\ lg_{x}}$ となります( $lg_{x}$ で、マージ前の左側の区間に対するグランディ数だとします、 $rg$ も同様)。
また、今いるマス目に皿がなかった場合、 $g_{x} = 4$ です。
こうすることで、今 $(i,j)$ で左に進んでいて、 $(i,k)$ のマスまでしか左に進めない、としたときにおけるグランディ数が、セグメント木を用いることで $O(\log W)$ で計算できるようになりました。具体的には、先ほどの区間マージを繰り返し $[k,j]$ にした後、 $g_{4}$ を見ればよいです。
もし、途中に皿がないマスがあったとしても、その地点でいったんグランディ数が4でリセットされるので正しく計算できます。これにより、皿が無いマスの有無を気にすることなく、好きな地点で左に進み始めた場合のグランディ数が計算できます(とりあえず一周できると仮定して区間マージしてみればよいです)。

では、パターン1のグランディ数を求めます。
下方向の遷移先のグランディ数はすでに求まっています。
左に進んだ場合、遷移先のグランディ数はパターン2のグランディ数になります。
よって、 $(i,j)$ から左に進むとしたとき、 $(i,j-W+1)$ までしか左に進めない場合における、 $(i,j-1)$ のグランディ数を計算すればよいです。
右も同様です。
3つの遷移先のグランディ数がわかったので、自分自身のグランディ数は定義通り計算できます。
これで、欲しかった情報が手に入ったため、あとはxorを取って0かどうか判定すれば答えがわかります。
実装は、 $W,1$ の行き来をスムーズにするために、それぞれの行における文字列を2回繰り返せばより実装が楽になります。

感想

実装しやすいな、と思っていたのにバグらせました…
時間内に終わらせられたらよかったのですがなかなか難しいです。

2020-09-21

ACPC2020 3日目

番外編

最終日！です

内容
- A(0:05)
- B(0:07)
- C(0:11)
- E(0:37, 2ペナ)
- D(0:56, 2ペナ)
- F(1:27)
- G(2:49)
結果
おしまい

内容

通した順です。

A(0:05)

なんで4方向じゃないのだろう…とぼやきながら頑張って実装しました。
幸いバグらせることはほぼなかったのでよかったです。Bに先実装を渡すか悩みましたが書いた方がはやいかなと思い先に書きました。

B(0:07)

とまとさんが累積和ーと言いながらサクサクとおしてくださりました。ありがとうございます。

C(0:11)

$\mod{K}$ を状態に持ってDPをしてくださいとるぎうさんに言われたので、バトンタッチしてサクサク実装しました。これは結構はやく書けたと思っています。

E(0:37, 2ペナ)

最初僕が読みましたがわからず、Dをやっていたとまとさんと問題をスワップ。これがうまくハマり、とまとさんが方針をパッと出してくれて、そのまま実装→AC。
剰余をとると値が半分以下になる、言われればそれはそうですが気づきません…

D(0:56, 2ペナ)

とまとさんとるぎうさんで最初に出した方針が2ペナしたので、とまとさんと僕をスワップしました。と、考察ミスにるぎうさんが気づき修正してもらい、実装がまるっきりかわるので1から実装しなおしました。
scc上の頂点idと元の頂点idを混在させてしまいバグらせたので少し時間はかかりましたが、なんとかACでした。

F(1:27)

Dをやっている間にとまとさんとるぎうさんが考察をしてくださっていたので、その最後の詰め部分から参戦でした。
とまとさんがModIntを持っていなかった(PCが普段と違う)ので僕が実装しました。~~るぎうさんに、僕がやる意味ある？って言われましたが、実装がしたくなってしまったのであんまり聞こえなかったことにしておきました。~~
とまとさんに実装を見てもらいペアプロをしつつ、無事ACしました。

G(2:49)

3人でいろいろ考えるも何も方針が立たずだったのですが、るぎうさんが $O(N)$ の計算が $O(M^{2})$ くらいに圧縮できることを伝えてくださったあたりから考察が動き始めました。
僕が $O(M^{2}2^{M})$ くらいのDPを思いついたので画面共有をONにして一人で実装を始め、ガリガリ書きました。
バグらせ(答えるときにdp配列を参照せずreturnするという凡ミス)つつも、なんとかサンプルを合わせ、提出。

3人「ありがとうありがとうありがとうありがとうありがとうありがとうありがとう…」
ジャッジ「AC」

やったぁ！
ありがとうと連呼するの、噛みませんか？

結果

7完22位でした。
やっぱり20位台前半から抜け出せたいのでどうにかしたいですね…
f:id:emtubasa:20200921171228p:plain

おしまい

WUPC、HUPC、ACPCが終わりました！携わっていた皆さまありがとうございました！！！楽しかったです！

2020-09-20

ACPC2020 2日目

番外編

ICPCチームです。

内容
- A(0:00)
- B(0:06)
- C(0:26)
- E(0:45)
- F(1:31)
- J(3:53)
- G
結果
おしまい

内容

また通した順です。

A(0:00)

2 * a + 3 * bを出力するタイピングコンテストです。

B(0:06)

とまとさんが実装しました。問題内容は何もしらず…

C(0:26)

るぎうさんが実装しました。問題文が読みづらくてつらそうでした。

E(0:45)

パッと読んでDPっぽいと思ったのですがすぐにわからなくて、るぎうさんに投げたらこのDPは僕がやるべきって突き返されました。
泣きながらDPを書き上げると、問題文の 残りの白い石の数がw_mより小さい場合は白を選ぶことはできない。 という文章と、 黒い石が残っていない場合、ゲームを終了する。という文章を見落としていることに気づき、慌てて考え直しました(本質部分が抜けた全然違う問題を解いていませんか？)。たまたま書いていたDPが白い石の個数を添え字にもつやつだったので、少し修正して無事ACしました。

F(1:31)

Eの実装をしている際、
るぎうさん「こういうのはツバサ君が実装をするといい感じに書いてくれる」
とまとさん「たしかに、そうしよう」
という話が聞こえて、Eを解き終わったらFの実装を押し付けられました。
再び泣きながら実装し、すこし時間はかかりながらもなんとかACしました…
1次関数の値を求めるのにいもすをしてもう一度累積和をとる(座圧上で)というのは初めてやったので、バグらせて終了させることがなく安心しました…

J(3:53)

割とずーっとこの問題を考えていましたが全然解けず、残り30分少し前くらいに、るぎうさんが クエリ平方分割みを感じる… と言っていたのでその中身を聞くと、確かにそれっぽいとなりまた僕が泣きながら実装しました。
実装が終わっても全然サンプルが合わず、画面共有をして3人で泣きながらデバッグをしていると、残り7分でようやくサンプルが合いました。おそるおそる提出して…1発AC！気持ちよかったです。

G

とまとさんが担当していて、僕やるぎうさんも時々顔を出していましたが、結局BFSの辺が多くなりすぎてわからずでした…

結果

6完ペナ無しで18位。後輩チームにも一応勝ったのでとりあえず一安心です。
f:id:emtubasa:20200920173847p:plain

おしまい

今日は何故か実装をたくさん押し付けられましたがペナは無かったのでとりあえず仕事はできたかなと思います。
あと1日、後輩チームに完数でも差を付けたいですね！(出場するのか知りませんが…)

2020-09-19

ACPC2020 1日目

番外編

全日程 Ramen as a Service で参加予定です。

内容
- A(0:02)
- B(0:31)
- D(1:09)
- C(1:15, 3ペナ)
- G(1:58)
- E(2:36, 2ペナ)
- F
結果
おしまい

内容

通した順です。

A(0:02)

どうせ割り算すると誤差死するんだろうなと思ったので、きちんと手元で立式しました。
普段より時間はかかりましたが、問題ないスピードでACです。

B(0:31)

何も知らないので何もいうことがありません。とまとさんが危なげなく通していました。

D(1:09)

問題は最初に読みましたが、結局僕がCへ行くため、るぎうさん考察→とまとさんが実装の流れに。
詳しい中身をあまり知りませんが、DPとか二分探索とかセグ木とか言っていたような…

C(1:15, 3ペナ)

いい感じの考察をるぎうさんから受け取り自分が実装。
最小全域木をすればよくて、x本の道を敷いた後テレポーターを割り振る部分が嘘になっていたのでペナを生やしまくりました。冷静になると、制限付きテレポーターを使う場合と使わない場合で2回似たことをすればよかったのに気づき、ようやくAC。

G(1:58)

問題を知りません。三分探索ってワードが聞こえました。この問題の位置にしては簡単というのも聞こえた気がしますが何もわかりません(無責任)

E(2:36, 2ペナ)

序盤のDP部分の後数え上げるところは僕がやるのがよさそう、と先に見ていたるぎうさんが指示してくださったので僕がやりましたが、思ったより包除パートの正しい考察に気づくまで時間がかかってしまいギリギリに…
$O(N^{2}S)$ のDPでModIntを使ったらTLEして泣く泣くintに直してようやくAC...
と思っていたのですが、コンテスト後に確認してみると二項係数の割り算で毎回計算量が $\log MOD$ だけ増えていたせいだったぽいです(↓参照)、たまたまそこも書き換えていたので気づかなかっただけっぽい？

E、TLEして、ずっと前半のDPパートでTLEしてると思って定数倍高速化をしてたんだけど、よく考えるとそこは余裕で、本当の原因は後半で二項係数の計算で逆元を求めるときに毎回log MODつけてることだった
— SSRS/AOJ-ICPC550点埋め (@SSRS_cp) 2020年9月19日

F

Eが終わって駆け付けると考察はとっくに終わっていて、提出後のバグ修正中でした。考察は自分が考えたものと先輩方のものが同じだったのでおそらく大丈夫だろうとは思っていたのですが、クエリごとに辺を書き換える部分で無限にバグっていたっぽいです。

結果

6完23位でした。ペナが生えているのが自分の担当箇所のみなので反省しています…
f:id:emtubasa:20200919164023p:plain

おしまい

冷えてるか～～～(実際冷えていて結構焦っていました)

Bバグらせて3完の時、順位表見たらgetKOKOROもRamen_as_a_Serviceも3完で、冷えてるか〜〜〜って言ってた(結局抜かされましたが……)
— かっつ (@_KKT89) 2020年9月19日