PCT's Soliloquy

数学と競プロについての忘却記

AC黄色になりました

PCTです。AtCoder黄色になることができました!

 色変記事です。色々書きます。

 はじめに

競技プログラミングをしているPCTといいます。数学をしている人に勧められて競技プログラミングを初め、それが面白くてハマってしまいました。

そして先日、3月20日にあったABC196でついに黄色になることができました。

精進記録

f:id:PCTprobability:20210405152856p:plain

f:id:PCTprobability:20210405153111p:plain

f:id:PCTprobability:20210405153203p:plain

最近は、高難易度に強くなりたいので黄diff以上を埋め始めています。

また、レートを上げるには遠回りになるかもしれませんが自分の興味を持った分野を深く勉強してみる。なども少し始めています。

学習したもの

青から黄になるまでで学習したものを上げていきます。

 

グラフライブラリ

dijkstra、BellmanFord、トポジカルソートの機能をつけたグラフライブラリを制作しました。

最低限の機能といった感じですが、ABCを解く上ではこれがあればあまり困らないと思います。

どうしても定数倍の重いコードを書いてしまいがちで、困っています。どうすれば定数倍の軽いコードを書けるのでしょうか...

これは今後の課題だと思っています。

 

形式的べき級数

青から黄の期間で始めた、ということではないのですが本格的に武器に出来るようになったのはこの期間だと思っています。

ライブラリも作りました。modがNTT-friendlyでない時も使えるように任意mod版も作っています。(任意版ではかなり定数が重くなってしまったので、まぁまぁ使いにくいです...)

ライブラリを使わなくても考察で使うことによって問題を解ける。解けるとまではいかなくても考察が楽に進められるなどといったことが多くとても便利に感じています。使っていて楽しいです。

まだまだ知らない使い方があるので、マスターしていきたいです。

 

Trie木

文字列を管理できる木構造です。

これ、とても賢いな~と感じました。Trie木を使ったことはまだ1回しかありません。いつか使える日が来ることを願って...

 

Mo

これもまだ1回しか使ったことがないですが、仕組みを理解しライブラリにもしました。

ふと思い出してツイートしてみたら物理好きさんが詳しく教えてくれてMoを使う問題

まで教えてくれてとても感謝しています。分割統治についても教えてもらいました。

これは雑談になりますが、私がNPCAに入部した年に物理好きさんが卒業してしまったのは少し寂しいです。

 

知っているが未学習のもの

フローアルゴリズム

使えるには使えるのですが、計算量が特殊な時に落ちたり、逆辺を貼ったりするのがまだいまいち理解できていません。仕組みを知らないでブラックボックスとして使ってしまっているのはいい状態とはどう考えても言えないので、理解したいです。

 

Dirichlet積

形式的べき級数の指数法則が積になったverととらえています。これも数え上げに使えそうでとても面白そうなのですが理解が遅くまだいまいち自分のものに出来ていません。

ライブラリは積と単位元ゼータ関数のみ作っていて、ARC116-Cを高速に解けることを確認しました。

 

 これからについて

黄色になれたのは嬉しいのですが、レートを稼げていたABCがunratedになってしまって停滞するのではないか。という恐怖を感じています。

f:id:PCTprobability:20210405155212p:plain

f:id:PCTprobability:20210405155253p:plain

速解きタイプなのが見てわかると思います。ある程度の難易度までを高速に解き、残りの時間を高難易度に費やして解けずに少し温まって終わってしまう。ということを青の時から繰り返してしまっています。

これが一番の今後の課題で、コンテスト中に安定して黄diffまでを通せるようになる。というのをしばらくの目標にします。

そのために4月10日にあるAGCでは大爆発したいです。1036prfを取れば青落ちはしないので、よっぽどのことがない限り黄のままでいられると思います。

目標は橙prfを取ってレートを2100に乗せることです。頑張ります。

 

終わりに

あまり内容の濃くない記事になってしまったと感じています。いかがだったでしょうか。

これからは今までのような速解きだけでは通用しにくいと思っているので、高難易度を解けるようにしていきたいです。得意分野を橙diffまで解けるように。苦手分野でも青diffは確実に解け、黄diffもたまに解けるレベルまで持っていけたらと感じています。

前のようなStreakを繋げるための精進をやめて、高難易度を考える習性をつけようとしているのでこれがいつか実力となってくれたら嬉しいです。

 

そして、レートの目標をたてたいと思います。かなり厳しめの目標を立てます。

・6月にレート2200達成

・8月にレート2400達成

*1

とても厳しい目標だと思います。けど、ここで甘えていては一生赤になどなれないと感じたのでこの目標をここで宣言します。

ただ、学業も少しずつやらないといけないのでそちらの方も頑張ります...

次回のAGCは、NoSubしないように初めにFにCE提出を必ずします。これでレートが下がってしまっても勉強料だと思うことにします。

頑張るぞー!

*1:言ってから気付きましたが、これ8月までに安定して黄diffを通し50%の確率で橙diffも通す。ということですよね。頑張らないと...

JMO春合宿参加記(問題についての言及は一切ありません)

JMO春合宿に参加しました

 

外出できなくてかなしかった

 

バイキング難しすぎない?ほぼ食べてないし朝昼に至っては1回も行ってすらいません

 

そういえば春合宿中に参加したABCでAtCoder黄色になりました、嬉しいね

 

ARCでもレート上がったよ、これで青落ちの可能性はかなり薄くなったよ、安心!

 

f:id:PCTprobability:20210324204300p:plain



はやく橙なりたいな~

 

ABCWriterとかしてみたいね、できるのか知らんけど

 

春合宿に出ても生活習慣は直らなかったよ(完)

 

4時くらいまでなかなか寝ようとしても寝付けないんだよな 助けてくれ

 

来年もいきたいねー 多分JJMOは予選免除かからないだろうし今年もJMOでます

 

学校に残ることが出来ればですが(学校生活、金diffだろ)

 

がんばろ~

yukicoder278-F 「おーじ君をさがせ」

始めに

これ面白いですね。まさか行列累乗がこんな感じで使えるとは思ってませんでした。

 

問題

No.1340 おーじ君をさがせ - yukicoder

 

N 頂点 M 辺の有向グラフが与えられる。始めおーじ君が頂点0にいて、毎秒おーじ君辺の先に進む時、T 秒目にいることが出来る頂点の数を求めよ。ただし移動できない場合おーじ君は消滅する。

 

制約

1 \le N \le 100

1 \le M \le 10000

1 \le T \le 10^{18}

 

解説

始めに頂点 0 にいる状態から毎回移動することを、行列で持ちます。頂点 j から頂点 i に移動することが出来る時、(i,j)=1 でそれ以外は 0 であるような行列を考えこれを T 乗します。しかしこれだけでは不十分です。

なぜなら T 秒ちょうどでないといけないため、ある頂点 i に対して j から移動してこれるかの OR を取る必要があります。移動してこれるかの判定は、頂点  j にいることが出来たかと頂点 j から頂点 i への有向辺があるかのANDです。

ORとANDで行列積を取れるかを考えると、以下の条件を全て満たすため取ることが出来ます。

結合法則A\ OR\ (B\ OR\ C)=(A\ OR\ B)\ OR\ C 

単位元の存在:A\ OR\ 0=0\ OR\ A=A

交換法則:A\ OR\ B=B\ OR\ A

結合法則A\ AND\ (B\ AND\ C)=(A\ AND\ B)\ AND\ C

単位元の存在:A\ AND\ 0=0\ AND\ A=0

分配法則:A\ AND\ (B\ OR\ C)=(A\ AND\ B)\ OR\ (A\ AND\ C)

分配法則:(A\ OR\ B)\ AND\ C=(A\ AND\ C)\ OR\ (B\ AND\ C)

そのため、上で述べた頂点 j から頂点 i に移動することが出来る時、(i,j)=1 でそれ以外は 0 であるような行列を T 乗し、(0,i) の和が解になります。行列累乗の実装の際に T=0 となるケースを忘れないようにしましょう。

提出コード

https://yukicoder.me/submissions/604839

感想

行列累乗をこのような風に使えるのが勉強になりました。面白かった~

エイシング プログラミング コンテスト 2020 F「two snuke」O(1)解説

始めに

「ごり押しは最強」

 

エイシング プログラミング コンテスト 2020 F「two snuke」の解説記事です。解き方が解説記事にないものだったので、解説記事を書こうと思います。公式解説はO(logN)ですが、本記事はO(1)です。

atcoder.jp

 

問題

正整数 N が与えられるので、以下を満たす整数の組 (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2) について、(s_2-s_1)(n_2-n_1)(u_2-u_1)(k_2-k_1)(e_2-e_1) の和を  \pmod{10^9+7} で求めてください。この問題は T ケース与えられます。

f:id:PCTprobability:20210112215401p:plain

 制約

1 \le T \le 100

1 \le N \le 10^9

 

解説

とりあえず、O(N)は出来ません。公式記事はO(logN)で解いていますが、O(1)で解くことを目標にします。

ステップ1ーO(N)で解く

N \le 4 の場合は 0 なので、始めに除いておきます。

まず、s_3=s_2-s_1 となる変数 s_3 を導入します。他も同様にします。

すると条件は 2s_1+s_3+2n_1+n_3+2u_1+u_3+2k_1+k_3+2e_1+e_3 となります。

s_3+n_3+u_3+k_3+e_3=A となる時の s_3n_3u_3k_3e_3 の和について考えます。形式的冪級数で考えると、\frac{x^5}{(x-1)^{10}}x^A の係数となります。

これは何故かというと、1 変数に対して、和をとるための情報を指数に持たせ、積を取るための情報を係数に持たせた式 x+2x^2+3x^3+...5 変数あるので 5 乗したため、こうなります。

 \frac{1}{(1-x)^n} = \sum_{k=0}^{∞} \binom{k+n-1}{n-1}x^k が成り立つため、s_3+n_3+u_3+k_3+e_3=A となる時の s_3n_3u_3k_3e_3 の和は \binom{A+4}{9} です。

2s_1+2n_1+2u_1+2k_1+2e_1=B となるような非負整数の組の数は、B が奇数ならば 0、そうでないならば \binom{ \frac{B}{2}+4}{4} 通りです。

これらを A+B \le N となる全ての非負整数の組 A,B に対して足し合わせたものを求めます。

ここでホッケースティック恒等式を使います。ホッケースティック恒等式とは、\sum_{k=r}^{n} \binom{k}{r}= \binom{n+1}{r+1} のことです。

求めるべき値は、\sum_{a=9}^{N+4} \sum_{b=4}^{\lfloor \frac{2N-a+1}{2} \rfloor} \binom{a}{9} × \binom{b}{4} です。ホッケースティック恒等式を使うことにより、これは  \sum_{a=9}^{N+4}  \binom{a}{9} × \binom{\lfloor \frac{2N-a+3}{2} \rfloor}{5} と変形できます。これでとりあえずO(N)で解くことは出来ました。ここからO(1)に落としていきます。

ステップ2-高速化

何気なく \binom{a}{9} などと書いてきましたが、これは a に対する 9 次関数です。\binom{\lfloor \frac{2N-a+3}{2} \rfloor}{5}5 次関数です。これらの積は 14 次関数です。14 次関数の和を取るため \sum_{a=9}^{N+4}  \binom{a}{9} × \binom{\lfloor \frac{2N-a+3}{2} \rfloor}{5}15 次関数です。ここまで言えば何がしたいか分かった方もいるのではないでしょうか。

そうです。この関数を無理やり展開していきます。

ここで、ラグランジュ補完を使ってこの関数を求めてもいいですが、私はラグランジュ補完のライブラリを持っていないためwolframalphaを使おうと思います。

と言ったものですが、床関数があって面倒です。偶奇で分けてしまって、最後に足すことにします。

\sum_{k=0}^{n}  \binom{n+5}{5} × \binom{2n-2k+9}{5} と \sum_{k=0}^{n}  \binom{n+5}{5} × \binom{2n-2k+10}{5} を求めます。以下の通りです。

Σ[k=0,n]binomial(k+5,5)*binomial(2*n-2k+9,9) - Wolfram|Alpha

Σ[k=0,n]binomial(k+5,5)*binomial(2*n-2k+10,9) - Wolfram|Alpha

f:id:PCTprobability:20210112222829p:plain

f:id:PCTprobability:20210112222855p:plain

出来ました。後はこれを実装します。数が大きいので打ち間違えないようにしましょう。(経験談)

これを N の偶奇で場合分けをして足し合わせることにより正解出来ます。場合分けと言ってもほとんどしないようなレベルですので、実装はかなり楽です。

提出コード

atcoder.jp

 

感想

ここまで読んでくださりありがとうございます。お疲れさまでした。

本記事では形式的冪級数と二項係数を N 次関数で捕えることがメインでした。

どちらかと言えば後者がメインです。

結構ずるい解法ですね...

変数の数が変わったら使えなくなりますが、ラグランジュ補完の方の実装をすることによりそれを気にしないで出来ると思います。思いますというのは私が試していないからです。早くライブラリ作らないとな~

 

では、改めてここまで読んでくださりありがとうございました!

「みんなのプロコン 2019」 E - Odd Subrectangles 解説

みんなのプロコン E - Odd Subrectangles を解いたのでそれの解説記事です。

始めに

圧倒的数え上げに見えますが、数学ゴリゴリの問題です。ほんっっっっとうにこういう問題大好きなので、ジャンジャン出してほしいです。

問題

NM 列のマス目があります。全てのマスに 0 または 1 の整数が書かれています。

行の部分集合 A と列の部分集合 B の組 2^{N+M} 通りの内、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

AB 両方に属する |A||B| 個のマスに書かれた整数の和が奇数である。

制約

N,M1 以上 300 以下の正整数

解説

以下で総和とは、総和 \bmod 2 の略とします。

なんだかDPな感じがします。けど更新に時間がかかりすぎます。

こういうのは片方を固定するのが定番なので、B を固定して考えてみます。

するとほとんどの場合、総和内、半分が 0 になり、もう半分が 1 となることが分かります。

これは何故かというと B と交わっている 1 の個数が奇数個である列を選ぶか選ばないかにより、それ以外の行の選び方による総和を X とした時、1-X に総和を変更するか、しないかを選ぶことが出来るためです。

 

逆に、全ての行に対して、B との共通部分との総和が 0 になる場合は必ず 0 になることが分かります。

なのでこのようなものの数を求めることを考えます。

選ぶ列を 1、選ばない列を 0 とした行列 S を考えます。入力と S の積の全ての要素が 0 になるような選び方が条件を満たします。

これは、入力の行列の内、カーネルの要素数がいくつかというかということです。

行列に対するカーネルの定義は以下の通りです。

行列 A に対して、AB が零行列になるようなベクトル B の集合

カーネルの要素数は今回は \bmod 2 上での行列なので、カーネルの次元を F と置いた時、2^{F} と求められます。

カーネルの次元に対して Ax×y 実行列とした時、rank A+dim(Ker A)=y

が成り立つため、行列のランクを求めることが出来ればいいです。

これは掃き出し法により求めることが出来るので、解を求めることが出来ました。

 

感想

こういう数学問、解いていて楽しいのでもっと出してほしい~と思っています。DPなどで出来るのでしょうか?私は分かりません。(考えましたが、厳しそうでした)

 

ここまで読んでいただき、ありがとうございました!

AGC047-C Product Modulo

AGC047-C Product Moduloを解きました。これ楽しいね

その感想というか、解説というかを書きます。

 

提出コード

Submission #18992067 - AtCoder Grand Contest 047

実行時間700msなのは、あまりよくないですね...

考察途中に考えていたことを混ぜながら解説をします。

問題

正整数 N と正整数列 A_1,A_2,...,A_N が与えられる。N(N-1)/2 個の全ての非順序対 (A_i,A_j) に対して、\bmod 200003 の和を求めてください。

制約

2 \leqq N \leqq 200000

0 \leqq A_i \leqq 200002

解法

とりあえず、A_i=0 となるような要素は答えに影響しないので取り除いて考える。

見た感じだと、FFTをするように見える。しかし、A_i \times A_j の取る値は、1 以上 200002^2 以下のため、愚直にやっていては間に合わない。

なのでこの方針だと厳しい。

一度方針を変え、A_i \times A_j \bmod 200003 = A_i \times A_j - \lfloor  \frac{A_i \times A_j}{200003} \rfloor であることを利用して、二分探索を適用して解けないか、と考えてみる。しかし、これは二分探索自体を何回もする必要があるため効率が悪い。

一度元の方針に戻ってみる。なぜFFTを使えないのか、それは今回積を取るため、積の値の範囲が大きくなってしまうので使えなかった。

なら和にしてしまえばこの問題は解決する。積を和にする方法は指数化してしまうこと。そうすればFFTを適用できる。具体的には、A_i=2^{B_i} となるような数列 B_1,B_2,...,B_N を導入する。C_j=(B_i=j となるような i の個数となる数列 )と定義されるC_1,C_2,...,C_{200002} を導入する。これに対してFFTを行うことにより、正整数 k に対して、A_i \times A_j=2^{B_i+B_j} =2^kとなるような正整数の組 i,j の個数を求めることが出来る。

後は、C に対してFFTをした数列 D_1,D_2,...,D_{400004} に対して合計を復元すればいい。

また、A_i \times A_i はカウントされないため、これを除き、最後に /2 をすることにより解を求められる。

 

感想

これ楽しかったです。積の範囲が広いので和に変えたい。なので指数法則が条件を満たすのでそれの形に置き換えてFFT

この回のE問題はパズルみたいな感じで面白そうなので考えてみることにします。解けたら多分またブログにします。

AGC解けたらめっちゃ楽しい~~~

JOI2次予選参加記事

JOI2次予選が今日ありました。その参加記事です。

-30分

起床(は????)

いや違うんですマジで眠かったんですよ許して

ここから高速に準備をしてなんとかご飯を食べて12:50分にスタンバイ

この時ようやく緊張感が来ましたね(こいつマジでなんなんだろう)

0分

スタートです。まずはAを見ます。

面倒そう。まぁ仕方ないか...と思って実装をすると案外楽だった。1回バグらせたけど10分くらいでAC

10分

Bを見る。やばそう。なんか適当にやっても貪欲したら駄目なことを手元で確認。うーんと悩んでいたらクエリごとに全ての文字数が同じことを利用したくなった。なのでBFSをしようかな?という気持ちに。コーディング。

50分

一応あったので提出して部分点を獲得。まぁ文字列操作は重いから仕方ないね...などをしていた。ここからmapが重そうなので定数倍高速化としてなんちゃらmapを使うことにする。これでもまだN=13の時10000ms以上かかる。どうしよう。

文字列操作が重いなら3進数にすればいいじゃない!反転もこの方法だとかなり軽い。ということで実装。N=13でなんとか間に合う。提出。得点!

ここまでで90分が経過していてやばい。焦る。

90分

Cを見る。とても焦る。なぜなら他の人はバンバン通しそうで僕が部分点すらわからない問題だったから...

bit全探索で8点取れるけどとりあえず後回しにして、DEを見る。

Dの部分点すぐ取れそう。獲得。(3点)けどK=2のケースはよくわからない...後で考察しよう...

E見る。問題文がなんか複雑。スパイを出来るだけ少なくしたら楽そう...ってこれなんかNP困難みたいな問題になっちゃった...訳わからん...部分点すらも取れない...

 

ここでかなり焦っていました。結構難しくなってるけど3完しないと厳しそう...と思ってCに齧りつく。これがあまりよくなく、Dを考えられなかった。

これから永遠にDPをバグらせて8分前にbit全探索解を提出して終了...

 

結果

画像

とても微妙な結果...非公式順位表では46位ですが書いていない人の成績次第...212点以上の人で書いてない人が少ないことを祈るばかりです…

 

Cで詰まっちゃったのはよくないですがABをしっかりとれて自明部分点も取ることが出来たのでこれで無理なら今年の僕の実力じゃ無理です。また来年。

 

では朗報が来ることを祈って…

 

「追記」(2021/2/3)

無事2次予選を通過できました!本選頑張ります!