10/05(月)
起きたら午後3時だった。昼前に一瞬意識を取り戻してツイッターを確認した覚えがあるが、二度寝に成功したらしい。
昨日のこどふぉのEのhackケースがTLに流れてきた。昨日のツイートだが、誰かのいいねで再度表示されていた。
同じ文字のペアを消すか消さないかは、以前の文字列によって決まる。消すことで後ろからより文字コードの大きい文字が出てくるなら消すべきでないし、逆にそうでないなら消すべきだ。では、後ろにある文字が同じであった場合はどうなるだろうか？
コンテスト中の僕は、この場合一律で消さないべきだと考えていた。消すべきだったら、そもそも後ろに同じ文字があるので、今見ているペアの片方とくっついて消えているはずだという理屈。これは嘘で、実際には"bbzzb"みたいに「消えた結果後ろに同じ文字が現れる」場合が存在する。さらに"bbzzba"だと消したほうが'a'が前に出てきてお得。
これは、後ろから見て「最後に隣り合う文字が異なった個所の文字コードの大小」を持って、それに応じて後ろにある文字が同じ時の処置を決定するようにすれば対応できる。
昨日は放置すると言っていたくせに、ちゃんと解きなおししてしまった。
学食に行って550円の弁当を買うと、レジの人が500円の弁当として会計してしまった。これはレジの人の責任なので500円分の支払いでよいらしい。ちょっとモヤっとするが、プリペイドカードなのでそうやすやすと巻き戻せるわけではなさそうでどうしようもない。
帰ってきてmodintを完成させた。invをどう計算するのか悩んだ。拡張ユークリッドの互除法が速いと思っていたのだが、ACLの実装ではmodが素数の場合はpow(mod-2)している。これはどうしたことだろうか。
実際に試してみると、拡張ユークリッドの互除法をint型で計算するのはpow(mod-2)よりほんの少し速いが、long long型で計算すると大幅に遅くなった。まあ試すといっても、簡単なコンビネーションの計算をする問題に提出しただけなので、詳しいことはわからない。
pow関数の引数に負の数を与えたときはpow(-n).inv()を返すようにした。素数modならpow(n%(mod-1)*(mod-2)%(mod-1))でもいいのかもしれない。大体非素数modで変なことをするなよ、という話だ。まあ使う機会があるとはあんまり思えないし、こればっかりは慣らしてから考えるべき問題だと思う。途中invをpow(mod-2)で実装しているときにpow(-1)を呼んだら無限再帰になってびっくりした。
modintを作ったので、ほかのデータ構造のverifyコードを手直しした。返すmodintを新たに作っていると遅いが、そもそも引数が値渡しなのでそれを書き換える形にしたら速くなった。
次に行列ライブラリを作ろうと思ったのだが、設計に悩んでいる。次元をテンプレート引数で与えるものと、コンストラクタで動的に定めるもの、どちらが良いだろうか。少なくとも正方行列のライブラリについては、例えば2行2列行列をvector<vector<int> >で持つのはぞっとしない話だから、テンプレート引数で与えたい。一方で動的に定めたい問題もいくつか思い浮かぶ。
beetさんやei1333さんのライブラリを参考にすれば、正方行列はテンプレート引数で、普通の行列は動的に定めているらしい。動的な正方行列が欲しくなったら普通の行列のライブラリを使うのだろうか？N行M列行列の構造体にしれっとpow関数が実装されていても、使う側が気を付ければ問題ないか。
明日は講義とその演習がある。演習のほうは直前まで情報が出ていないように見えたのだが、日付が変わったあたりで再度ポータルサイトを確認すると出ていた。ISTUらしい。
ほかの講義はみーんなGoogle classroomで資料を掲載するのに、1つだけISTUでやられると煩雑で困る……と思いながらしぶしぶISTUを確認したら、classroomの授業コードが貼ってあった。OK！
しかし全てclassroomで完結させるのではなく、資料を掲載するのはclassroomだが、レポート提出はISTUで行うという使い分けをするらしい。まあ許せないこともないが、先の学期を思い出してみると、classroomで課題を出すとISTUで提出するので期限までToDoリストに残り続けることになるし、出さなければ気づけないしで困ったものだ。
10/06(火)
起きたら午後4時だった。今日は2限に対面の授業があったけれど、消し飛ばした。
学食に行く。夕方は大学近くの道が死ぬほど混むので、自転車で行く。チェーンがミシミシ言っていて非常に怖い。坂を上るときに強い負荷がかかっていて壊れそう。
帰ってきてから夜までずっとハーメルンを読んでいた。先週月曜日から読んでいた作品が読み終わった。
532話、3,766,229文字。ここ1週間はこれにかかりきりになって全ての予定が崩壊していたが、それだけの価値がある作品。かなり長いが、マジで面白い。ヴォルデモートの最期の場面までは必見。逆にそこのクライマックスが本当に良すぎて（僕は泣いた）、原作終わりからの新しい話の印象がちょっと薄い。
本当はもっといろいろ書くつもりだったんだけど、書きたいことが多すぎてなんともならなかった。
しばらくAtCoderをしていた。ACLが過去問でも使用可能になったらしい。
布団に寝転んで、別のハーメルンをしばらく読んでいたら、急に耐え難い眠気が来た。まだシャワーを浴びていないし、洗濯物もたまっているし、何ならこの日記も書いていなかったが、気にせず寝てしまうことにする。とりあえず歯磨きして顔を洗ったら少し目が覚めたので、またしばらくハーメルンを読んで、今度こそ寝た。この日の日記は水曜日に書いた。
10/07(水)
昼頃起きて、しばらくハーメルンを読んでいた。
昨日の夜中から読み始めた作品は24話なのですぐに読み終わる。とはいえ文字数を見ると204,065文字、これは文庫本1.5~2冊に相当するはずだ。かかった時間はそれに比べれば短いはずだし、やっぱりネット小説は適当に読みがちなんだな。内容は……正直合わなかった。
昨日消し飛ばした対面授業は、資料がclassroomにアップロードされていた。「出席できない人はこれを見て勉強してください」とも書かれていた。最高。もう一生出席しません。
1週間ずっとGame of Vampireを読んでいたわけだが、その間にいくつか新しい作品を見聞きして、タブに保存していた。余裕ができたので読もうと思ったのだが、どうにもそれほど面白くない。上で挙げた作品はジャンルが僕の好みに合っていたから読了できたが、それ以外は非常に厳しい。実際に3つくらい、最初の数話を読んで辞めてしまった。どうやら無意識的にGame of Vampireと比較しているらしい。
この機会に「本好きの下剋上」に手を出すことにした。とりあえず学食に行き、帰ってきてから読み始める。
序盤、まだ成り上がりのきっかけをつかんでいないあたりは非常に辛い。周囲の人からオススメされたことと、高い評価を得ていることを頼りに読み進める。
真夜中からTCOのwildcard roundがあったので、出た。finalに行けるとは全く思っていないが、まあRatedなので出ておくか、といった気持ち。
Easyのみの1完、しかも遅解きだった。どうしようもない。Easyの解法は見た瞬間わかってしかるべきだったのに、しばらく全く別のところをウロウロしていた。Medもよくわからずに立式したらサンプルが一生合わなくて終わってしまった。
まあEasy落ちが結構いたので、僕のコードが落ちなかったことだけはよかった。2246->2222(-24)。ゾロ目である。Rubikunさんが三桁マイナスで一瞬で黄色落ちしていてビビった。
yukicoderをする。ちょっとサボっていた間に有志のコンテストの問題がドバーッと追加されていたので、チマチマ埋める。星2.5以下の問題を再度埋め終わって、現在990AC。あとちょっとで大台に乗りそう。AOJも確かあと30問くらいで1000ACだったはず。Codeforcesは……ナオキです
10/08(木)
起きたら午後3時だった。夜の部が始まる午後4時をめがけて学食に行く。早めに行くと、食べ終わった後も余裕をもって購買で買い物ができる。
サークルからICPCに参加するメンバー全員が、ICPCのアカウント登録まで済ませてくれた。チーム名も決まっているので、メアドと一緒にファイルにまとめてコーチに送る。チームが登録されるのを待って、サークルの人々に情報の追加をしてもらう必要がある。英語のUIなので非常に分かりにくく、一番の難所だと思っている。例年通りならば活動の日に集まってみんなで確認しつつ登録していたが、今年は集まれないので、スクショを共有して参考にしてもらいながらやっていこうと思う。
明日の2限はclassroomに講義資料と動画が数本アップロードされるタイプだが、小テストがあって、授業終了30分後までに提出する必要があるらしい。その時間制限は何？
前日、つまり今日の夜に講義資料がアップロードされたので、とりあえず解いておいた。「授業時間内に動画を視聴し云々」と書いてあるが、本当に意味不明な制約なので、無視して提出した。一応コメントでこれが許されるか確認を取っているが、返信はまだ返ってきていない。
先日作ったmodintについて。2*modintが動かなかった。operatorの定義が問題のようだ。operator+=の実装を用いてoperator+を実装している。
(1) modint operator+(const modint&a){return modint(*this)+=a;} (2) friend modint operator+(const modint&a,const modint&b){return modint(a)+=b;} (3) friend modint operator+(modint a,const modint&b){return a+=b;}
(1)は、左オペランドがintなどで右オペランドがmodintのときに動かない。よって(2)や(3)みたいにfriendで書いておいて、intからコンストラクタ経由で呼び出せるようにしておけばよい。
operator+=を使用する都合上、左オペランドはコピーを取る必要がある。ACLの実装は(2)だが、(3)のほうがシンプルではないか？速度面で違いはあるのだろうか。(2)についている参照渡しのconstは、(3)では値渡しなのだから同様に満たされるはずだと思っている。しかし実測をしていないため確たることは何も言えない。
ライブラリのフォルダ構成を変えることにした。ライブラリをジャンルで大まかに分けた結果、oj-bundleで展開するときにいちいち#include"math/modint.cpp"と書かなければならなくなっていた。これを解消する。
includeフォルダを作って、ここに.hppファイルをずらっと並べることにした。ただしそれぞれのファイルは別のところにあるファイルをincludeするだけにしておく。例えば、include/modint.hppの中身は../math/modint.cppをincludeするだけ、のように。
oj-bundleがファイルを探すパスをincludeフォルダ内にしておけば、modint.hppをincludeするだけでmath/modint.cppが展開される一方、ライブラリ本体はちゃんとフォルダでジャンル分けされたままになるという寸法だ。
同時にverify用のコードも書き換える。これまではverify用のコードがあるフォルダから../math/modint.cppみたいにしてincludeしていた。これはいかにも融通が利かない。ちょっと場所を移しただけですぐにCEになること請け合いだ。
こちらもmodint.hppをincludeするだけにしたい。oj-verifyのconfigファイルをいじって、コンパイルオプションに-I library/includeを渡すようにした。結構紆余曲折あったのだが、最終的にはうまくいってよかった。
デフォルトでは-Wallをつけてコンパイルされたり、clang++も同時にテストされたりする。大体Github Actionsで動かしているのに警告出してもどうしようもないし、clang++は使わないのでテストする必要がない。この2点は前から気になっていたが、configファイルを設定することで両方解決した。最高。
フォルダ構成を大幅にいじって満足したが、実際のところライブラリは1Byteも増えていないのである。
10/09(金)
昨日のmodintのoperator+の話について、日記を書いた後に適当に計測した。modint+intの場合は(2)より(3)のほうがほんの少しだけ速く、modint+modintの場合は(2)と(3)はほとんど同じくらいの速さだった。ここまではよい。
int+modintの場合は、(3)よりも(2)のほうが結構速かった。理由が全然わからない。intのほうはmodintのコンストラクタに渡されるが、(3)ではそこで作成したmodintの、さらにコピーを取っている。これは確かに遅そうだ。const modint&を引数に取っておくと、最適化がかかってくれるのだろうか？
理由はよくわからないが、実際速いのだから(3)に戻して、寝たのだった。
午後3時くらいに起きる。学食に行ったのだが、スマホを忘れてしまい、食事の写真が撮れなかった。同じことをずっと繰り返すことにこだわりがあるので、失敗したのは痛い。
yukicoderをチマチマ埋める。今日もコンテストがあるが、その前に1000ACしようとしていた。999ACなのを確認して1問解いたところなぜか1001ACになっていてよくわからないが、ともかく1000ACは達成できた。やっぱり星の数ではなくsolvedの降順に解くと楽。
サークルのメンバーの1人から、ICPCに関するアレコレについて質問があった。練習についてはAOJ-ICPCのオススメの使い方を紹介した。解答の提出についても、かなりややこしいことを強調して、模擬国内予選で試してくださいと言っておいた。問題は予選で使用する環境だ。毎年碧黴さんに任せっきりでよく理解していなかった。
ライブラリがコンピュータ内のファイルに保存されているのは、これは（あまりよくないが）許容範囲内ではないかと思う。当然コンテスト中に使うのはアウトだが、パソコン内のコード断片を全部探して削除するのは難しいだろう。.vimrcやコードスニペットは削除する必要がある。これを咄嗟に断言できなかったのだが、チームメイトに聞いたところ削除するとのこと。
リクルートの冬のアルバイトについて、オンライン説明会の案内が来た。自分が何をしたいかなど全然考えていないのだが、そうして尻込みし続けているのはよくないだろうということで、試しに参加することにした。今年の夏も、親にインターンに行ってもいいか聞いておきながら何も具体的な行動をしなかったので、ちょっぴり後悔している。
yukicoderに参加する。数学回とのことでちょっと身構えていたが、ふたを開けてみると全然そんなことはなかった。
F問題は橋を検出すれば解けるが、グラフがなもりグラフなので、単純なdfsでもよいらしい。LowLinkは単純なdfsではない。
僕の橋検出ライブラリはグラフが非連結のときにバグる（というか1つの連結成分しか見てくれない）というのは以前にも書いたかもしれない。今回はなもりグラフなのでOKだった。
「N頂点N辺の無向連結グラフ」をなもりグラフと呼ぶの、かなり好き。
しばらくAtCoderをしていた。AOJも1000ACを目指して解き始める。何を埋めようか迷った結果、PCKの過去問を埋めることにした。去年古いものから順番にいくらか埋めていたのの続きで、微妙に穴が開いていたのをふさいでいくことにする。去年飛ばしただけあって難読・面倒のオンパレード。3つ解いたところで寝ることにした。
10/10(土)
起きたら午後1時だった。ちょうどKUPCが始まる時間に目覚ましをかけていた。12時と12時半の目覚ましは黙殺してしまったようだ。
慌てて起きて眼鏡を掛け、パソコンのスリープを解除してA問題を開き、ACするまで2分半だった。
コンテストの結果は5完だった。これはひどい。F問題は制約を読み落としていた。G問題は、かなりいいところまでわかっていたが、末尾に同じ数をくっつける場合の数を最後に計算する方法がわからなかった。それ以外の操作i回と混ぜて並べたときに、どの時点で同じ数をくっつける操作をしてもその場合の数は1通りに定まるので、comb(N,i)みたいな係数でよかった。
次にHHKBコンテストに出た。全完7位。誰が学生か詳しくはわからないが、たぶん学生3位か4位だと思う。3位だったらキーボードがもらえる。4位は虚無がもらえる。
F問題はかなり難しかった。連続的なやつの期待値は積分で求めるのが常道で、それをする。各[L,R]について、x/(R-L)*(min(R',x)-min(L',x))/(R'-L')*...みたいな式をLからRまで積分すると、寄与する期待値が出てくる。
出力する数値の要請から、分母は計算しなくてよい。
minが出てきてかなり困るので、全てのLとRを混ぜて降順に見て計算することにする。L'>=xのときR'>xなのでmin(R',x)-min(L',x)=0。よってLが出現したら計算を打ち切ってよい。そうでない場合、R'<xならばR'-L'になるので別に係数を持っておけば考えなくてよく、R'>=xならばx-L'が被積分関数にかかる。
[L_1,R_1]から[L_N,R_N]まで全部同時に計算することにする。被積分関数が対応する多項式の和になっていればよい。これまで出現した(x-L')*...を別に（other(x)とする）持っておいて、新しく[L,R]を考えるときには、now(x) <- now(x)*(x-L)+other(x)*xとする。これで自分（[L,R]）以外の(x-L')の積×xの総和が得られる。そのあと、other(x) <- other(x)*(x-L)とする。
多項式の積分は簡単。毎回powするのではなく、累積積を持っておくのが速いだろう。まだ出現していない[L,R]に対応する係数を掛けるのを忘れずに。
この事実を利用する方法もあるらしいが、全くわかっていない。
最大値と最小値の分布（一般論と例） | 高校数学の美しい物語
次はこどふぉ。CGR11があるが、その前にtesting roundがあったので、なんとなく出る。10分のテストコンテストで、問題数は2問。1位の人は10分で2問解いたうえで2Hackしていてかなりビビった。A問題で結構落ちているようだ。場合分けでごり押した結果落ちているコードを見つけたが、あんまり読む気にならなかった。
今度こそCGR11。1時間で4完したあと、Eに2時間ぶち込んで解けなかった。椅子に突き刺さって寝たりシャワーを浴びたりしていたのだが、最後の最後でそれっぽい解法が思い浮かんだので実装していた。結局3分くらい間に合わなかったのだが、後から提出したら通った。本来なら悔しがるべきところだが、あんまり現実感がないので特になんとも思っていない。
Nに対して(N^2N)+N^3N^Nはだいたい2になる。2進表現で2つ以上の0が連続する部分があると2にならないようだ。これは実験結果からエスパーしたもの。
この連続する部分をどうにかしてつぶせば2が手に入り、シフトしながら消していくと1を作れる。つぶす方法についてだが、奇数を1から順にかけて((N^2N)+N^3N^N)==2になるのを待つ方法で通った。正当性が全然わからない。
レートは2493->2487(-6)。
AtCoderでbcのAC数が500問になった。bcは文字列が読めないので、入力が数値と文字だけの問題を選んで解いている。あとめちゃくちゃ遅い。総じて、どう考えても競プロ向きの言語ではない。
ライブラリを書く。modintのコンストラクタは、これまで問答無用でlong longにキャストしていたが、テンプレートにした。毎回long longで剰余の計算をするのは遅そう。
行列ライブラリを書く。固定長の正方行列と、動的にサイズを決められる行列の2つ。固定長の正方行列は、例えば2 x 2行列を遅延セグメント木に乗せたり、数列を漸化式で計算したりすることを想定しているので、あまり機能は持たせない。足し算と掛け算とpowのみ。
そういえば単位行列を得るための関数はいろいろあるみたいだけど、僕はOctave由来のeyeにした。別にOctaveだけがeyeというキーワードを使っているわけではないが、僕にとってなじみ深いのはOctave。
普通の行列の方はいろいろ作る。powも作っておいた。縦と横のサイズが違うときにpowするのは意味不明なので、assertも入れておく。これに限らず、行列の計算はサイズが重要なので、いろんなところにassertを入れておいた。昔は自分が書いて自分で使うライブラリにおいてassertなど無駄だと考えていたけど、改宗。
行列式の計算と、ガウスの消去法も実装した。ガウスの消去法について、対角行列ではなく上三角行列で計算を止めると定数倍に結構効くという話もあるが、ライブラリでは対角行列（というか単位行列）まで計算することにした。定数倍高速化がしたければ、その場で書き直す。あとはmodintだったら割り算のかわりにinvを求めておいて掛ける形にするだけでもかなり変わるだろう。それはそうで、log(mod)を落としているから。
ガウスの消去法のverifyとしてyosupo judgeの連立方程式を解く問題に提出したが、ライブラリ以外のところでハマった。拡大係数行列にガウスの消去法を適用して、まずランクを求め、下のほうに非零の数が残っていないか判定するのだが、そもそもこのランクにAx=bのbの部分のみからなる行が含まれている場合があるのに気づかなかった。
10/11(日)
起きたら午後6時だった。えでゅふぉがあるが、確か今日が期限の課題があったはずなので見送る。
レポートを書こうと課題を確認すると、明日までだった。もうえでゅふぉが始まってからしばらく経っているので、今更出る気もないため、この課題を終わらせる。
えでゅふぉが終わったのと同じくらいの時間に書き上げた。提出して布団に入る。まだARCまで数時間あって、少し眠いが、今寝るとどう考えても起きられないので、寝ないように注意してなろうを読む。
午後9時あたりにTLを見たらARCの幻覚を見ている人たちがたくさん「ぞい」ツイートをしていて、ビビる。冷静になってなろうに戻る。
コンテスト10分前に布団を脱出し、ラムネを食べてコンテストに備える。
ARC105が始まる。結果から書くと、5完43位だった。
A問題は何も考えずにbit全探索した。結構いろいろな分け方があると思っていたけど、解説を読むと2通りしかないらしい。確かに。
B問題は実質あまりを取る操作なので操作をするたび最大値が小さくなるからシミュレーションしてもOK、と思っていたらTLEした。バカだから1度目のTLEで懲りず、ほとんど同じコードをもう一回出してもう一回TLEを食らっている。冷静になってとりあえず数列全体のgcdを取るとサンプルが合うので、未証明で投げる。AC。
C問題はNが小さいのでN!全探索を考える。N!の中で牛ゲーをしようと思ったが、今回求めたいのは最も短いときの値だから、逆。（これは符号を反転すればよかった。）
前からdpしてよさそう。今考えると、これはDAG上で牛ゲーをしているだけ。毎回M個の条件をチェックする必要があって、このままだとO(N! N^2 M)。到底間に合わない。
dfsして順に計算していけばNが一つ落ちるんじゃないの！？となって実装。O(N! N M)くらいのコードを投げるとTLEした。アホ。
尺取りみたいにしたらさらにNが消えるんじゃないの！？とO(N! M)くらいのコードを投げると、またTLEした。本当は最初に8!*10^5=~=4e9であることを計算していたので、今投げた2つのコードがTLEすることはわかりきっていたはずだ。なぜ投げてしまったのか。
冷静になると、事前にソートすると毎回判定するべき範囲が2分探索で求まり、累積maxを取っておくと範囲に対する判定が1回で完了するため、オーダーにはMではなくlog Mが出現するようになる。
CでTLEを食らっている間に順位表を確認したら、なんと4桁順位だった。ヤバい。
Dを読む。ゲーム。丹念に場合分けを行う。まずNの偶奇で先手後手両方の戦略が入れ替わる。ここで場合分け。総xorを非ゼロにするのはかなり簡単に見えるので、そちらを考える。なるべく大きな山を作るように操作すれば、めったに総xorは0にならないのでは？となる。具体的に計算すると、だいたい過半数が取れるのでよさそう。コンテスト中は適当に流したが、石全体の過半数が1つの山に集中していれば総xorが0にならないというのは微妙に非自明。
Nが奇数のとき、後手はうまくすれば必ず過半数の山を作れるので、先手が最後に石を山に追加したとき、総xorは非ゼロである。よって後手勝ち。
Nが偶数のときも同じように計算してみたところ、ぴったり半分にしかならない場合があることに気づく。さらに詳しく見ると、同じ個数の石が入った袋が偶数個ずつある場合にこのことが起き、後手勝ち。それ以外は先手勝ち。
これを実装してAC。16分で解いたらしい。
Eを読む。またゲーム。1とNが非連結の状態でどれだけ辺を増やせるか、という問題。その値の偶奇で決まる。
1を含む連結成分のサイズがL、Nを含む連結成分のサイズがRのとき、辺は最大でN(N-1)/2-LR個。最初からM本張られているので、N(N-1)/2-M-LRが奇数<=>先手勝ちだ。
場合分けをしていく。まずL+R==Nなので、Nが奇数のときLRは必ず偶数。よってこの場合は決まり。Nが偶数の場合を考える。
連結成分のサイズの偶奇を変更するためには、1ともNともつながっていないサイズが奇数の連結成分を加えればよい。そのような連結成分を「浮島」と呼称することにする。（僕のコンテスト中のイメージがそれだった。解法を説明するときに頻出するため、名前を付けておく。）浮島が存在しない場合は、現在のLRの偶奇が保たれるので、これも決まる。
浮島が1つしかない場合は、先手がLとRのどちらか好きなほうにくっつけることで浮島がない状態に帰着できるため、先手勝ち。
では、2つ以上は？例えば浮島が2以上の偶数個あった場合、後手は先手の行動に応じてそれを打ち消すように行動できるため、最初のLRによって後手勝ちならばそれが保たれる。具体的には、先手が浮島をLまたはRにくっつけたら、必ず浮島は1つ以上残っているはずなので、それを同じところにくっつける。ほかの行動に対しては浮島どうしをくっつけて「パス」したりすればよい。
先手勝ちならば、先手は最初に浮島どうしをくっつけたあと、上の後手勝ちと同様の戦略をとればよい。以上より、浮島が2以上の偶数個あった場合は、存在しない場合と同様に最初の先手勝ち・後手勝ちが保たれる。
浮島が奇数個の場合が残っている。これは先手が最初に浮島をLかRにくっつけることで、浮島が偶数個の場合に帰着できる。浮島が偶数個の場合は先手勝ち・後手勝ちが保たれるのだったから、この場合の勝ち負けは先手の最初の行動で決まる。先手はLとRどちらにくっつけるかを選ぶことで、必ず先手勝ちの状態に持っていけるため、浮島が奇数個のときは先手勝ち。
以上の場合分けをコードに起こせばよい。26分でAC。
BとCで2個ずつペナを付けたときは心臓が弾け飛んだが、終わってみればパフォーマンスは2774だった。+9というしょっぱい結果だけど、冷えるよりはマシ。でもちゃんと冷静にやっていれば赤パフォが出たということで、やはり悔しくもある。
A問題のコードゴルフについて。条件はA<=B<=C<=DとしてD-C-B==(A or -A)だが、Rakuで(A,-A)X+(B,-B)X+(C,-C)X+(D,-D)を計算して0が含まれるか見てもよい。
このメタ演算子Xは、左右のリストから1つずつ選ぶ全ての場合について演算して、結果をリストで返してくれる偉いヤツ。まあそこそこ短そう。
ところで、Junctionという機能を使っても同じことができる。文にして説明しようとするとかなり厳しいことに気づいたので、リファレンスへのリンクを貼ってお茶を濁しておく。
ともかく、Junctionに対して演算をすると、中の値それぞれに対して計算が行われる。これはXと似たようなことをやっていないか？
ということで、(A&-A)+(B&-B)+(C&-C)+(D&-D)を計算すると、A+B+C+Dから-A-B-C-Dまで16通りの計算結果がallでつながった状態のものが得られた。正確にはallがネストしているのだが、別にanyが混ざっているわけでもないので特に違いはない。
これをbool値として解釈するときは、A+B+C+D&& ... &&-A-B-C-Dが計算される。どこかの項が0になると全体がFalseになるので、これでAからDを足し引きして0が作れるかどうか判定できる。
リスト(A,B,C,D)から((A,-A),(B,-B),(C,-C),(D,-D))というリストのリストを作るのと(A&-A,B&-B,C&-C,D&-D)というJunctionのリストを作るのでは、後者のほうが短くかける。具体的には(1&-1)*AがA&-Aになること、1&-1が1つの要素として解釈されることを利用して1&-1 X*(A,B,C,D)になる。(1,-1)X*(A,B,C,D)はflatされてしまうので、リストのリストにはなれない。
ということで次のようなコードが書けた。
信じられないくらい美しい。
