ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AGC049 B - Flip Digits

問題
提出コード

解法

できる操作が、

  • 1 をひとつ左に動かす

  • 連続する1 を消す

のどちらかとなっています。
また、右側にある 1 が、一つ左側の 1 を追い越すことはできません(そもそも、追い越したいのであれば、左側の 1 を動かせばよいです)。 そのため、元々Sで与えられた 1 の順序は変化しないまま、左に移動するか、消えるか、その位置のままか、のパターンしかありえないことがわかります。
S_{i}1 のときに左に移動させる(もしくは据え置き)パターンは、それより左側に、まだ位置を確定させていない 1が存在しないが、T_{j} (j \leq i)1 となっているものが存在するパターンです。jが最小となっている箇所に優先的に移動させないといけないため、i-j回の操作が必要になります。
S_{i}1 のときに消すパターンは、上記のようなjが存在しないときです。どこへ移動させてもTと一致することがないので、S_{k}(i \lt k)1 となっている最小のkを見つけ、その 1 と合わせて打ち消します。これにはコストがk-iかかります。
以上のことをシミュレートし、最終的にSTが一致すればよいです。
queueを2つ使い、STでまだ消すべきなのに消してない/ 1にすべきなのにS_{i}1になっていない位置をメモし、消すべき1から優先的に上記の処理を行います。

AGC010 D - Decrementing

問題
提出コード

解法

わかりやすい部分、つまりNが小さい方から考えていきます。

N = 1のとき

1回の操作で必ず1減少するので、明らかに、A_{1}の偶奇で答えが判定できます。
奇数であれば後手勝ち、偶数であれば先手勝ちです。

N = 2のとき

A_{i}のどちらかが1であった場合、先ほどと同様、もう片方の数字の偶奇で判定でき、奇数なら後手勝ち、偶数であれば先手勝ちです。
そうではない場合を考えます。順序は関係ないため、A_{1} \lt A_{2}であると仮定します。
A_{1} = 2のとき、問題の条件より、A_{2}は3以上の奇数になります。
この時、A_{1}を先手が選ぶと、A_{1}が1になり、これ以降はA_{2}を減らすことしか選べなくなります。ここで、A_{2}は開始時点で奇数であることが保証されていたため、結果としては必ず先手が勝つことになります。
A_{1} = 3のときも見てみると、遷移先の勝敗を照らし合わせることで、
(3,4),(3,8),(3,10)は先手勝ち、(3,5),(3,7)は後手勝ちであることがわかります。
この結果を踏まえると、どちらか片方が偶数であれば先手勝ち、奇数であれば後手勝ちであると予想が立てられます。
これが正しいことを証明していきます。
ゲームの最終状態は(1,1)です。よって、両方奇数であれば負け、ということになります。
現在のゲームの状態に偶数が含まれている場合、その偶数を選んで1減らすことで、両方の数字が奇数になります(割り算で偶奇は変化しません)。
逆に、両方奇数である場合、どちらを選んでも、必ず偶数が残ってしまいます。
よって、偶数が含まれた状態でターンが回ってきた場合、相手に必ず両方の数字が奇数である状態を押し付けることができ、逆にそれがおしつけられた場合、相手には偶数が残った状態でターンを渡すことになります。
これにより、N=2のときは、偶数が含まれていれば先手勝ち、そうでなければ後手勝ちであることがわかりました。

N \geq 3のとき

A_{i}に1が含まれている際は、1ずつ減っていくだけなので、これは先ほどまでと同様に答えを求めることができるため省略します。
ここらから状態のパターンが多くなり複雑になっていくので、実験コードを書いて実験をしてみます。すると、Nの偶奇でパターンがわかれていることがわかります。

Nが偶数のとき

A_{i}に含まれる偶数の個数の偶奇で勝敗が決まっていることがわかります。
偶数の個数が奇数であれば先手勝ち、偶数であれば後手勝ちです。
奇数個の状態で回ってきた人は、偶数を選び1減らすことで必ず相手に偶数個の状態でターンを回せます(選んだ偶数が必ず奇数になり、最大公約数が偶数になることはありません)。
逆に、偶数個の状態で回ってきた人は、偶数、奇数どちらを選んで1減らしても、偶数は奇数個になってしまいます。こちらのパターンも、Nが偶数のため、奇数が必ず1つ含まれることになり、最大公約数が偶数になることはありません。
これにより、Nが偶数のときには、A_{i}に含まれる偶数の個数が奇数であれば先手勝ち、偶数であれば後手勝ちであることがわかりました。

Nが奇数のとき

こちらも基本的には偶数パターンと同じ見た目をしています。
偶数の個数がN-1でなければ、上記と同様の作戦をとることで勝敗が決まります。
しかし、偶数の個数がN-1の場合、以下のような例が考えられます:

5
2 4 6 8 11

このようなパターンのとき、先手は11を選んで操作を行うと、

1 2 3 4 5

となります。これは、本来先手から始めた場合に後手が勝つパターンです。1回先手が操作をしているので、上記のケースは結局先手勝ち、ということになります。
つまり、N-1個の偶数があった場合、1つだけある奇数を選んで操作することで、勝敗がひっくりかえることがあります。このパターンのみ、1つの奇数を選んで操作をする、ということをシミュレートし、勝敗がわかるまで繰り返せばよいです。
必ず偶数の最小公倍数になるため、一度の操作で全ての数字は半分以下になります。よって、操作はO(\log A_{i})回で収まり、十分間に合います。

これで勝敗の判定方法がわかったので、まとめます。

  1. Nが1のとき
    A_{1}の偶奇で判定します。

  2. 上記以外で、A_{i} = 1となるようなiが存在
    \sum_{i} (A_{i} - 1)の偶奇で判定します。

  3. 上記以外で、Nが偶数、もしくはA_{i}の偶数の個数がN-1でない
    偶数の個数の偶奇で判定します。

  4. 上記以外(Nが奇数かつ、A_{i}の偶数の個数がN-1
    残った奇数を選び操作をするとしてシミュレートし、上記のパターンに帰着できるまで繰り返します。

という形です。

感想

苦手なゲーム問題で、実験コードを組みつつきちんと通せたので、良かったです。

ICPC2020国内予選 参加記

とまとさん、るぎうさんとの三人で出る。正直、AtCoderで黄色三人のチームは弊学でここだけで、最近は自分の調子も良かったので何もなければ通っていると思っていた。
コンテスト前、大学に来て出ている他の5チーム(?)全部に挨拶してまわる。イケメンだったsuzuken君が眼鏡をかけてさらにイケメンになっていて、気づかなかった。ごめん。

コンテストが始まる。
...
リロードを押す。コンテストが始まる。
...
問題が見えない。びっくりしてコーチの元へ向かうと、他のチームの代表者も来ていた。安心(安心ではない)。
部屋に戻る。るぎうさんに、コンテストサイトは見えた(問題はまだ)と言われ、改めて報告しに行く。何かあったら教えてくださいと言い、戻る。
部屋に戻る。るぎうさんに、問題が見えたと言われ慌てて問題を開く。Aはとりあえず適当に書いてしまえばいいや、と言い書く。AC。

Dを開く。構文解析が見えたので身構える。と同時に、とまとさんから「B問題が読めない><」と言われる。落ち着いてもらうため、僕がBを読み、とまとさんにDを押し付ける。読んだらUnionFindを貼ればいいと書かれていたので、ICPC特別ルールに感謝しながらライブラリをぺたり。AC。

Dへ行く前にC担当のるぎうさんに声をかける。るぎうさんはpython使いで、Cはどうやらc++の方がはやく終わって良い、ということなので僕が実装をする。計算量があんまり計算できなかったけど、まぁ適当に枝刈りをしておけば間に合うだろう、と適当にコードを書く。かなり進みが遅いが、しばらく待つと実行が終わる。AC。
順位表を見ると、弊学TOP3チームが仲良く並んでいて、ここからが勝負だと確信する。

3人がDへ集合する。うんうんうなる。解けない。
Eをチラ見すると、ICPCでは初登場?のMOD数え上げ。チームの数え上げ問題枠だったので、嬉々として取り組む。解けない。
順位表から、EよりDの方がいいと判断し、渋々戻る。
引き続き、3人でうなる。解けない。
途中、僕がEに再び挑んだり、Fが通っていたのでFをとまとさんに読んでもらったりしていた。
気づいたら残り30分ほどになる。
るぎうさんの一言をもとに、正当性に確信を持てない解法が生える。
とまとさんに構文解析の解析パートを書いてもらい、自分が本編を実装する。この時点で説明を端折った結果、僕以外が解法を理解していなかったのがまずかった。
実装が終わるが、サンプルが合わない。焦る。このあたりで、他所から歓声があがる。順位表を見ると、UHISHIROが5完していた。終わった…
解法を疑い、別の変な解法を編み出す。もちろんサンプルが合わない。
とまとさんがこっそりFを実装していたらしく、サンプルがあう。が、実行するとREになったらしい。
Dも振り出しに戻り、そのままコンテスト終了…

終わってからUHISHIROのDを聞く。最初に生えた解法があっていた。なんで…
Fもとまとさんに解法を聞くと、すごくそれっぽい。もっとはやくFを教えてあげられたら…?
EもUHISHIROに聞く。30×30まではできたけど、こんなの思いつかない。数え上げが多少は得意だと思っていたけど引退…
その後も感想戦は続く。
そもそもDをバグらせなければ…?
Dの解法をきちんとるぎうさんに説明していれば…?
あるいは、とまとさんをDに引き戻して一緒にデバッグしていれば…?
この1年何をしていたの…?
競プロなんてやってないで、真面目に学業に取り組むべきだったのでは…?
とまとさんとるぎうさんは最後の年なのに、僕がA~Cやって終わりでいいのか…?
頭の中をいろいろなことがぐるぐる駆け巡る。感想戦の間、ずっと「うー」とか「あー」とか言っていた。

感想戦が長引いたので、UHISHIROメンバーと夜ご飯を食べる。諸事情によりうどんだったので、通過記念に奢ってあげようと思っていたが、すっかり忘れてしまった(今度やる、忘れていたら教えて)。
途中、suta君が「あ、あれを注ぐのか!」と言って急に席を立つ。何かと思えば、温かいうどん用の出汁を注いでなくて、うどんだけで食べていたっぽい。浮かれすぎ?
通過チームと一緒にごはんを食べていて、一人だけお通夜ムードだった。ごめん。


帰り道、1時間電車に揺られる。
ここでも頭の中でいろいろなことが巡る。
自分だけあと2回あるのに、とまとさんとるぎうさんのラストチャンスを奪ってしまったという思いがやっぱり強く、泣きそうになる。最近好きなReoNaさんの曲が、割と悲しめの曲が多いこともあり、イヤホンで聞いていて追い打ちをかけられた。電車なのでなんとか耐える。去年の学生コン予選で落ちた時は友達に電話をかけて泣いてしまったので、少しはメンタルが成長しているかもしれない。
誰か友達にラインをしようかとも悩んだ。そういえば、一緒に出ていた競プロ友達全員大学に居たのに、コンテスト後は誰も会いに来なかった。気を使ってだったのかな、ごめん(最近レートを振りかざして調子に乗っていたのでそれのせいかも、これもごめん)。いろいろ悩んだ結果、最寄り駅あたりでようやく、ICPCの後にラインをくれていた人に話しかけた。ちょっとメンタルが落ち着いた。

家に帰ると、親に順位表を見られていたことを知る。いろいろ話すと、また悔しさがこみあげてきて泣きそうになったので、慌てて自室に逃げてこの参加記を書き始めた。

とはいえ、幸い、悔しさをばねにして頑張ろうって思えるタイプみたいなので、またここから頑張って行こうと思う。ラストチャンスだったとまとさんとるぎうさんの分も、来年リベンジしたい。来年は僕が独りぼっちになってしまうので、まずはチームメイトを探すところから始めなければ…
ところで、競プロに熱中していたせいで学業がピンチらしい。助けて。
(お気持ち成分が多かったので普段と違う口調です。読みづらかったらごめんなさい、読んでいただきありがとうございました。)

ARC106 D - Powers (畳み込み解)

問題
提出コード

解法

まずは式を分解していきます。ループの中、つまり(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に落とし込めるのを既に学習していたのが大きいかもしれません。
逆に、想定解の方法が全然思い浮かびませんでした…

ICPC2020模擬国内 参加記

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

準備

前日はライブラリの印刷をしました。去年は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でグラフを持てば辺も削除できます…)。


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

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

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

結果

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

f:id:emtubasa:20201025235015p:plain

終わり

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

AGC037 D - Sorting a Grid

問題
提出コード

解法

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

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

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

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

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

感想

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

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

問題
提出コード

解法

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

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

  1. ゲーム開始時、もしくは下に移動した直後であり、左右(+下)のどちらも選べる状態

  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回繰り返せばより実装が楽になります。

感想

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