週記(2021/03/08-2021/03/14)

03/08(月)

先週日曜日はWriteUpをいくらか書いたら力尽きた。コードゴルフ大会中は週記を書く作業もストップしていたが、溜めてしまったものを書いて投稿する気力もなく、午前7時に就寝。

午後7時に起床。まだ眠かったので再入眠し、結局午後11時半まで寝た。これでもまだ眠い気がする。寝すぎただけかもしれない。

まずWriteUpの残りを書いた。次に、先週の週記を完成させつつ、タイミングを見失っていたICPCチーム紹介ドキュメントに関連する記事を投稿し、模擬地区予選に関する記事も書いて投稿した。

kotatsugame.hatenablog.com

kotatsugame.hatenablog.com

模擬地区予選に関して。実装の分担は常々大事だと思っていて、これは3並列が可能になった今、さらに重要度を増したはずだが、へのkのチームはほとんどへのk一人で解いて実装してしまったらしい。これは本当にすごいことで、並列することの意味みたいなのを考えさせられる。

週記を投稿したらもう外が明るくなってきていた。

コードゴルフ大会中にやろうと思っていたことをする。具体的には、この週末にあったコンテストのコードゴルフである。ABC194BとAGC052Aを縮めた。

yukicoderが今年もエイプリルフールコンテストを開催するらしい。一昨年出題したが、今年も出題しようと思い立つ。1問、以前から何となく考えていた(というほどでもない、星1くらいの)問題を出そうと思って、ストーリーを練っている最中、致命的な間違いに気づいた。はさみ将棋の勝利条件を、コマが相手陣地の最奥まで進むことだと勘違いしていたのだ。ストーリーの文章が完成してから気づいたので、没になってしまった文章はTwitterに放流した。

考えていた問題は、次のようなものだ:盤面に、飛車の動きができる駒が相手と自分のもの1つずつある。相手と自分はそれぞれ盤を挟むように向かい合っているが、このとき、自分の駒を一番向こう、相手側の端まで進めることが勝利条件である。自分と相手の駒が最初にあるマス目がそれぞれ入力されるので、自分が先手としてどちらが勝つか判定せよ。ただしパスはできない。

最初の状態ですでにどちらかが勝利条件を満たしている場合を考えないこととすれば、後は、自分が1手で相手側まで進めるか判定すればよい。1手で相手側まで進めない場合は、横にずれる必要があって、その時相手が勝つ。……嘘である。この場合も、相手駒の目の前まで進むことで、相手はじりじり後退するしかない状況に追い込まれる。これは今書いている最中に気づいた。

結局、自分が初手で1歩でも前に進めることが自分が勝利する必要十分条件になるようだ。

さて、この問題は全然ダメだったが、さらに1問ひねり出すことに成功した。僕は面白いと感じるが、ほかの人がどう思うかはわからない。問題文や想定解をパパッと書いて、%20さんにテスターをお願いするDMを送っておく。

まだ寝る気にならないので、AHC001に手を付ける。初日にコードゴルフのための解を提出してから手つかずだった。この日提出していたのは、最初1x1を割り当てておいて、適当に選んだ長方形を伸ばしたり平行移動したりする解。0→46969906846。

途中ハーメルンを読んでいた。

syosetu.org

寝る前に確認したら早速最短コードが取られていた。ABC194Bである。-1B。

午後8時就寝。

03/09(火)

生活リズムの狭間に飲まれて消えた。

03/10(水)

午前3時半起床。布団でスマホを触っていたが、1時間くらいでまた寝た。午前7時に再度目を覚ました。

ラノベを1冊読んだ。「自称Fランクのお兄さまがゲームで評価される学園の頂点に君臨するそうですよ?」10巻。この巻はお兄さまの活躍があんまりなくて、次巻に向けて力をためているような感じだった。単体としてみると少し消化不良。早く無双してほしい。

なろうの「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」を最後に読んでから3か月くらい経っていた。

https://ncode.syosetu.com/n3297eu/

更新分を読もうとしたのだが、このなろうは後から以前の話の間に差し込むような更新をするため、いちいち題名を見て更新分を探す必要がある(一応、新しいものは〇年〇月〇日投稿と書いてある)。作者曰く、まず大まかに書いてから、以前の分を修正するような書き方をしているそうだ。更新してくれるだけでありがたいのだが、ちょっと面倒だなと思ってしまうのはしょうがない。さかのぼって確認していたら、記憶に残っているシーンなどが出てきて、結局読み返す形になった。

yukicoderの問題は、%20さんがテスターを引き受けてくださるそうなので、リンクを送っておいた。

午前10時くらいにまた寝落ち。今度は午後5時に目を覚ました。

%20さんが問題を解いてフィードバックをくださったので、それを元に問題文を修正する。僕自身微妙だなと思っていた点についてもご意見をいただき、1時間半くらいで完成。yukicoder公式のDMで出題してほしい旨を伝えると、すぐ反映してくださった。これで完成である。

AGC052Aも最短コードを取られていた。こちらは-4Bと大敗を喫した。

今日は早めの時間にCF #706 div.1がある。レジってしばらく「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」を読んでいると、始まった。

Aは、2乗してソートし、大きいもの同士をペアにする。これは未証明で出したが、後から考えてみれば、ペアをつなぐ線分が交差しないようにしていると考えることで明らか。Bは難しい。丹念に考えると、左右の下り坂の長さが等しくかつ偶数で、その2つが全体に存在する下り坂のうちstrictに最大のものである必要がある。strictという条件から答えは0か1になるようだ。Cはギャグ。mod 3で引いて適当につなぐとできる。ここまで解いた時点では3位だった。

Dは、f(i,i)は明らかで、f(i,j)(ただしi!=j)を求めることを考える。まずijを結ぶ最短経路は1通りである必要があって、このとき数え上げる対象のBFS treeはijの最短経路上から木が生えた形をしている。ある頂点kがどこから生えた木に属するかはdist(i,k)-dist(j,k)を見ればわかって、これでグループ分けしたそれぞれの木についてf(i,i)を求める感じで計算すればよい。

Eは、どちらのチームが多くカードを持っているかを見て、カードが少ないほうのチームは全部使い、多いほうのチームは適当に2周してならせばよい。ところがMLEとコーディングミスで2WAしたところでコンテストが終了してしまった。

結果は4完でシステス後27位。レートは2658→2759(+101)でhighestを更新した。Eを後から提出したら通ったので、あと1分あればもっと良い順位が得られたようだ。非常に残念。この点数の問題がこんな簡単なわけないだろと思って、あんまり真剣にコーディングミスを直してはいなかった。もっと急げばよかった。

パスタを食べて、今日も写真をTwitterに投稿したのだが、どうやらうまく保存できていなかったらしく、前回のパスタの写真を再度投稿してしまった。食べている本人も気づかないほど似通った写真なのでどうしようもない。スマホで写真を撮った直後に別のアプリに切り替えるとうまく保存できないことがあるようで、最近は結構写真を撮るのに失敗している。

先週金曜日のyukicoderの問題を解いた。Eは頑張って数え上げる。mod pにおける切り捨て除算が、余りを引いて割ることで行える事実は何となく面白く感じる。Fはループがあったら総xorが0でなければならない、などと考えていたのだが、冷静になるとそのような判定は必要なくて、BFSでもDFSでも適当に決めていけばよい。Gは似たような問題設定なのにFとは全然違う解法になって面白かった。50列ぶんのbitをintで持っているのに気づかず、しばらく首をかしげていた。

今日もマラソンをする。前回の続きから、今日は平行移動する操作をやめ、代わりにほかの長方形を押して伸ばすような操作1本に絞ったうえで焼きなまし法をやってみた。vectorを使っていたのを固定長のグローバル配列に直すと結構ループ回数が増えてよかった。exp関数をテイラー展開して高速化、というのを目にしたので、適当に3次で打ち切ってみたが、あんまり速くはならなかった。1次だとさすがにまずそうで、2次は負の数のexpを取るときにやたら大きな値が出てしまいそう。後は、30分ごとに適当にパラメータをいじって投げると伸びたり伸びなかったりして、それにばっかり夢中になって本質的な改善は一切できていない。46969906846→48039849007。

途中でCF problemsを触っていた。div.4というのが1回だけ開催されているようなので埋めた。

ほかには、DDCC予選を通過したというメールが届いていたので、本選に参加するためにGoogle formに回答したりもしていた。bits/stdc++.hatcoder/をincludeした人たちが落ちていて、面白いコンテストだなあと感じた。交通費の計算について、とりあえず仙台駅からにしておいたが、もしかしたら帰省先の実家から直接東京に行くことになるかもしれない。この場合はどうなるのだろう、富山から東京に行くほうが少し高いようで、別にその分増やしてくれとは言わないから、せめて仙台→東京でないような領収書でも受理してくれないだろうか。

正午、布団に入って「無冠の棋士、幼女に転生する」というなろうを読んでいた。

https://ncode.syosetu.com/n1783ex/

午後3時までかかってちょうど最新話までたどり着いたところで寝落ち。

03/11(木)

生活リズムの狭間に飲まれて消えた。

……火曜日も同じことを書いた気がする。さすがに自分でも違和を感じるので、ここで今週の睡眠を振り返っておこう。便宜上木曜日の欄に書いているだけで、今週一週間分の睡眠を見ている。

時刻 日記において属する日付
先週日曜日
月0700 就寝
月2330 起床
月曜日
火2000 就寝
水0330 起床、1時間で再度就寝
水0700 起床
水曜日
水1000 就寝
水1700 起床
水曜日
木1500 就寝
金0230 起床
金曜日
金1530 就寝
土0030 起床
金曜日
土0930 就寝
土1030 起床
土曜日
日0000 就寝
日0400 起床
日曜日
日0700 就寝
日1300 起床
日曜日

どう考えても水曜日が長すぎる。また、金曜日と土曜日の切れ目がそこじゃないだろみたいなところにある。本来は僕が起きてから寝るまでを1日としていたのだが、今週は寝落ちして変な時間に起きることが続いた結果細切れの睡眠になってしまい、崩壊した。

03/12(金)

午前2時半起床。

寝る前に開いていた話の最後まで目を通して、これで最新話に追いついたことになる。

https://ncode.syosetu.com/n1783ex/

将棋の話だとどうしても「りゅうおうのおしごと!」を比較対象にしてしまいがち。「熱い」というキーワードが出てきたのでそこに注目が行ってしまった。頭を使う対戦ゲームで、プレイヤーを傍から見ているといかにも冷静沈着といった面持ちだが、内心は情熱に燃えている、というような対比を強調して「熱い」という言葉を使うのは別に「りゅうおうのおしごと!」に限った話ではなく、僕がそれしか知らないだけかもしれない。

ラソンをする。前回焼きなましたが、どうしてもいつも目標面積に全然届かない長方形が出てくる。そこで、最初に少しだけ山登り法をして、満足度がある値を下回るような長方形を抜き出し、それだけを対象とした山登り法をしたものを初期解にしてみた。これで2億点くらい伸びた。こりゃいいやと思って、抜き出す長方形は隣り合わないようなものだけにするとか、山登り法じゃなくてここでも焼きなまし法をするとかしてみたが、これらは逆にスコアが悪化してしまった。結局それぞれにかける時間を弄り始めてしまい、そのあとはずっとそれしかしなかった。3回の計算をそれぞれ0.1秒、0.3秒、4.55秒にしたものが一番スコアが高くなった。48039849007→48273067872。

ラノベを読んだ。「りゅうおうのおしごと!」14巻。非常に良い。もう何を言ってもネタバレになりそうなので、何とも言えない。12巻の終わりでも触れられていたが、いよいよ主人公が強くて僕としては嬉しい。

布団でハーメルンを読んでいたら、午後3時半に寝落ちした。

午前0時半起床。

DMでとがさんにコードゴルフのお題を振られていたので、少し考えてやり取りしていた。フォルダ内のファイルを1つずつあるコマンドに渡し、そこの標準エラー出力から特定の文字列を含む行を抜き出し、書かれた数字に対していくつか計算をして総和を取るという問題。もっと具体的に言えば、フォルダ内のmp3ファイルの再生時間の総和を秒単位で求めたいときのシェルスクリプトについて。

最初のコードは、for文でファイル名についてループし、grepで抜き出して(sedでフィールドを区切れるよう空白に置き換え)AWKで計算し、さらにfor文の外側でもう一度AWKを使って総和を求めていた。これらのうち、for文以外のことはすべてAWKでできる。grep/pattern/{}でよいし、フィールドを区切る文字はFS=charで変更できる。さらに、AWKを2回呼び出さずとも総和を持っておいてENDブロックで出力すればよい。

for文をどうにかしたい。コマンドの中には、ファイルを複数一気に処理できるようなものが存在するが、今回使うものはそうではないようだ。まずxargsで書いてみた。空白を含むファイル名を持つファイルが存在するようで、さらにクォートする必要があったが、何とか動いた。ls|xargs -I{} -n1 command "{}" 2&>1 |awk...だ。これだとsedで前後に文字列を入れs///eしたほうが短くなった。さらに2&>1 |awk...というのは|&awk...でよいということをとがさんが調べてきて、これで一旦は完成とした。しばらく後に、xargsのオプションがいくつか無駄であることに気づいた。ls|xargs -I@ command "@"|&awk...として終了。

シャワーを浴びて、深夜のコンビニに行ってみた。弁当とサラダとパンとおにぎりとお菓子を買って帰宅。通行人がいてびっくりした。

溜めていた日記を書いていたら朝になってしまった。また少しマラソンをする。ビームサーチというものがあるらしいので、試してみたが、これが驚くほど効果がなかった。まず試行回数が全然稼げない。さらに、すぐ局所解にハマって身動きができなくなってしまう。初期解を焼きなましで作ってからビームを打つとよいのではないか?とも考えたが、一切スコアが改善されなくてたまげた。コーディングの合間にもパラメータを適当に変えた解を投げ続けていたが、ここでは更新なし。というかシステムテスト形式なので、プレテストのスコアを執拗に気にしているのは良くないのだろうとは自覚している。ただ、バグが発覚したのはよかった。満足度がある値を下回るような長方形を抜き出していたが、ここで1つも抜き出さなかった場合にゼロ除算が発生するようだ。

さて、現在世間的には土曜日で、夜はABCがあるため、いったん寝ておく必要がある。しかし午前10時半からICPCのチーム練がある。起きられるだろうと自分を信じることにして、強気の午前9時半就寝。

03/13(土)

午前10時半起床。ICPCチーム練習の開始と同時に起きても、チーム練習に遅刻することに変わりがないことに改めて気づかされた。急いでバチャにレジって問題を解く。解きながらタイミングを見計らって昨日買ってきたパンやおにぎりを食べていた。

https://codeforces.com/gym/102920

8完。今日は碧黴さんとやっていたが、結局僕が全問書いてしまった。英語問題文を読んで概要を共有してくれる人が1人いるとかなり楽。碧黴さんはE問題をずっとやっていたが、問題文の冒頭、ストーリーに紛れ込んだ本質的な制約を見落としてしまったらしく、その状態で概要を聞いた僕も一緒に考えていたが全然わからなくてびっくりした。これは問題文が悪いよ。

解いた問題は、順番にBCJGHEAL。

Bはやるだけ。Cは、アパートがある頂点を適当に選んで木DFSする。自分を頂点とする部分木がアパートを含むような頂点を数えればよい。Jは\mathbb{F}_2上の掃き出し法。Gは、出力が小数点以下1桁固定であることに気づかず1WA、long longを%dで出力しているのに気づかず2WA(このとき別のバグも直した)、最後にTLEを食らって合計4ペナだった。scanfでlong longを106個読んでいるのが遅いらしく、getcharを使って書き直したら通った。後から聞いたらcin高速化だと問題なく通ったらしい。許せない。

Hはbitset。ここでEの制約見落としに気づき、AC。前から見て場合分け。Aは気合いで実装する。線分の端点が別の線分に乗らない制約で大助かりだった。今いる格子点と今目指している格子点を持つ実装。まず1周回ってみる。1周分の距離が求まったら、進むべき距離をそれで割った余りに置き換えておくと、残り1周未満で答えがわかる。

Lは非常に面白かったので、少しスペースを取って話しておこう。ちなみに、また106要素の入出力なので、今回は先にgetcharを書いておいた。まあ本題はそこではない。

問題概要は次の通り:2\le n\le 10^6要素の数列h、ただし1\le h_i\le 10^6、が与えられる。\displaystyle \max_{1\le i\lt j\le n}(h_i+h_j)(j-i)を求めよ。

例えば、あるペア(i,j)を考えたとき、i'\lt i \land h_{i'}\ge h_iなるi'が存在するなら、明らかにペア(i',j)を考えたほうがよい。こうしてみると、左右から累積maxだけ残した配列だけ考えてよいことになる。このとき、うまく尺取り法のようにして計算できないか考えたのだが、それ自体はうまくいかない。しかしその過程で良い性質を示すことに成功し、それがACにつながった。

i\lt i'\land h_i\lt h_{i'}j\lt j'\land h_j\gt h_{j'}を考える。ii'は左から累積maxだけ残した配列に属し、jj'は右からのそれに属する。ここで、(i,j)の値より(i,j')の値のほうが大きかったとしよう。つまり(h_i+h_j)(j-i)\lt(h_i+h_{j'})(j'-i)だ。このとき、(i',j)の値のほうが(i',j')の値より大きくなる、つまり(h_{i'}+h_j)(j-i')\gt(h_{i'}+h_{j'})(j'-i')となるようなことがあるだろうか?もし大きくなることがあるなら、尺取り法をしようとしても後戻りする可能性があってできない。式変形してみよう。

展開して整理するとh_ij-h_ji-h_ij'+h_{j'}i\lt 0\lt h_{i'}j-h_ji'-h_{i'}j'+h_{j'}i'になる。移項してまとめると(h_i-h_{i'})(j-j')+(h_{j'}-h_j)(i-i')\lt 0になる。ここで登場する4つの項は、最初に置いた時の大小関係からすべて正であることがわかる。つまり左辺は正なので、矛盾。したがって、(i,j)の値より(i,j')の値のほうが大きいとき、必ず(i',j)の値より(i',j')の値のほうが大きい。

勢いあまって尺取り法を書いて2WAくらい出したが、やはりダメであった。各iに対してjを全部舐める必要性はどうしても消えない。ここで天啓が降りる。あるiに対してjを全部舐め、最大となるjを求めたとき、i'\lt iに対してはj'\le jだけ、もう半分も同様に逆の半分のみ調べるだけでよいのではないだろうか。これはiで半分に切っていくことでO(n \log n)になりそうである。書いて提出するとACした。

まったくの別件を経由して後から知ったことだが、これはmonotone minimaそのものであったようだ。名前だけ聞いたことがあって、なんとなく敬遠していたのだが、自力で再発明できたので嬉しい。monotone minima、何するものぞ……。

残り時間はIと格闘していた。明らかに計算量がヤバそうな解を書いてTLEを出しまくるも通らず、このタイミングで参加してきたゆきのんさんに2Dセグ木では?と言われてうしさんのライブラリをコピペしてきたが使い方がよくわからず、提出が数秒間に合わなかった。ちなみにTLEした。コンテスト後もしばらく格闘していたが、ずっとtest 5でTLEしていてつらくなったので通らないまま諦めた。

ICPC練の合間にもまたマラソンで適当にパラメータを変えたものを投げていたら、焼きなましの終了温度を10分の1にしたところで微妙にスコアが更新された。嬉しくないと言ったら嘘になる。48273067872→48275288137。

CF 707 div.1に出た。3完で2759→2744(-15)。

Aはいつぞやの僕が解けなかった300点の、値がdistinctでないもの。distinctでないものは適当に場合分けすることで消せて、結局メインはこの問題とほとんど同じ。出力の順番をミスして1WA。

atcoder.jp

Bは面倒。数列の値がdistinctなので、怒られない日は少ない。簡単のため、n>=mであるとする。まず、0<=i<nに対して、その日からm日間とbm日間を合わせたときに怒られる回数を数えておく。この数列をgcd(n,m)項ごとに見て和をとることで、lcm(n,m)日間で怒られる回数がわかる。これはn/gcd(n,m)ステップでできる。kをその値で割った余りに置き換えて、同様の配列を用いてm日ごとに怒られる回数を見ながら進んでいく。こちらもn/gcd(n,m)ステップ未満となる。最後に、1日ずつ見て細かいところを合わせる。これはmステップ未満となる。

Cはカス。Bを見て操作を逆順にたどる。最後にソートする列は[0,n)がきれいに並んでいる必要があるが、その前の列は、最後の列において等しい値が続いた部分だけでよくなる。ちゃんと並んでいる箇所というのをbitsetで管理しておけば、bitwise andを利用してその列でソートできるかを判定することが可能になる。O(nm2)の64倍高速化……のはずが、TLEした。何がTLEしているのかわからないまま速そうな書き方に直したり判定をもうちょっとちゃんとしたりして、最終的にbitsetであることを使わない解にまで至った(並んでいない箇所を見なくてよくなった時に使う列の候補に追加する)のだが、7ペナ生やして依然TLEのままであった。

ここで、1500x1500の行列をscanfで読み込んでいることに気づく。getcharで書き直したところ、通った。本当に許せない。scanfがいついかなる時も速いと思っていて、CFでは常にscanfを使っているのだが、この日はそれがひたすら裏目に出ている。しかもつい数時間前にキレていた個所で再度キレることになって目も当てられない。この7ペナがなければレートは上がっていたはずだ。

https://codeforces.com/blog/entry/88590?#comment-770387

GNU C++17(64)だとscanfのほうがcin高速化より遅いらしい。本当にキレています。

ABC195に出た。6位。なんの賞も得られない。

Aはよい。Bはよくわからなかったので、個数を1から106まで全探索した。Cもよくわからない。適当に書き、適当にいじってサンプルを合わせたら通った。Dはかなり迷ったものの自分の直感を信じて貪欲に取ったら通った。証明はしていない。Eはメモ化再帰。こういうのを何も考えずに無理やりdpで書き始めるのではなく、メモ化再帰するという選択肢が出るようになったのは成長。手番の人が勝つかを返そうとして混乱していたが、よく見るとターンが交互ではなかったので、素直に高橋君が勝つかを返した。Fはおもむろにraku -e'say +grep &is-prime,^72'と実行すると20と出たのでbitDP。このコードは72未満の素数の個数をカウントするRakuのコード片で、is-primeというのがかなり使い勝手が良くて重宝している。ちなみに105くらいでもう実行時間がとんでもないことになる……と思ったが、手元のRakuをバージョンアップしていたことでかなり高速になったようだ。

コードゴルフはAとBとC。Aは最初のコードが16Bで最短。Bは全完後にちゃんと式変形してfloorceilのO(1)で解いておいた。Cは……謎。全部dcである。

合間合間でラノベを1冊読んだ。「ねえ、もっかい寝よ?」2巻。設定に全然惹かれていないことに気づいてしまったので、かなり適当に読んだ。

ちょうど真夜中ぐらいに、布団に倒れこんで寝た。

03/14(日)

午前4時、目を覚ます。atgolferの更新が流れてきた。新手であるように見えたので、飛び起きて他の最短コードを確認。どうやらほかに影響はなさそうである。いくらかコードゴルフされたものがこれ。

atcoder.jp

これまでのメモ化再帰は、メモ用のHashを用意してh={};f=->x{h[x]||=...のように書いていた。これをHashオブジェクトのnewでやってしまおうという発想が驚き。非常に美しいコードゴルフのテクニックであると感じられる。存在するキーにアクセスした場合は当然メモされた値が返されるが、存在しないキーにアクセスしたときに呼び出されるブロックで、デフォルト値を計算すると見せかけて問題を解いている。これは本当にすごい。

他にもE問題のコードゴルフが行われていたり、C問題が-4Bされていたりしたが、見ても粗はなさそうだった。D問題を縮めて、再度布団に戻る。ハーメルンを読み続けていたが、夜のARCに向けてさすがに寝ないとまずいと感じたので午前7時くらいに再入眠。

今度は午後1時くらいに起きた。午後2時からyukicoderの1時間コンテストに出た。2完。またBのFAを取った。

Bはよくわからないが適当に二分探索したら3700msで通ってFAだった。

週記(2021/02/22-2021/02/28) - kotatsugameの日記

Aはよい。僕は(0,0)(0,1)を聞いた。何を思ったか、(0,0)(0,100)をいったん考えておきながら却下してしまった。ユークリッド距離の2乗が返されると聞いて混乱していたが、冷静になるとsqrtを取ったことにしてよくて、ちゃんと円の交点になる。BはPを降順ソートして、チケットを使う場合は貪欲に使っていく。今何個目の商品を見ていて、どちらのチケットをどれだけ使ったかさえ持っておけば、もう片方の残り枚数もわかるという寸法だ。Cはずっと考えていたがわからなかった。解説を読んで、コードを読んで、ようやく理解した。

僕がコンテスト中にたどり着いた計算は、次のようなもの。おそらく解説でO(HW \min\{H,W\})とされているものであろう(このHWNのことだろう)。

\displaystyle \sum_{0\le h,2N-K-h\le N}\binom{N}{h}\binom{N}{2N-K-h}(-1)^K\sum_{a=0}^h\sum_{b=0}^{2N-K-h}\binom{ab}{M}\binom{h}{a}\binom{2N-K-h}{b}(-1)^{a+b}

この\binom{ab}{M}が厄介で、分解できない。正解は、最初の\sumを分解することだったようだ。

\binom{N}{h}\binom{h}{a}\binom{N}{a}\binom{N-a}{h-a}とする。bも同様に\binom{N}{b}\binom{N-b}{2N-K-h-b}\binom{N-a}{h-a}\binom{N-b}{2N-K-h-b}を考えよう。0\le a,b\le Nを決め打ったときに、a\le hb\le 2N-K-hから0\le h-a\le 2N-K-a-bがわかる。同様に0\le 2N-K-h-b\le 2N-K-a-b。よって\binom{(N-a)+(N-b)}{(h-a)+(2N-K-h-b)}=\binom{2N-a-b}{2N-K-a-b}について、2N-K-a-bN-aN-bからそれぞれいくつずつ持ってこられたかに対応するh-a2N-K-h-bが存在する。したがってhに関する和は\binom{2N-a-b}{2N-K-a-b}という二項係数に吸収される。結局

\displaystyle \sum_{a=0}^N\sum_{b=0}^N\binom{ab}{M}\binom{N}{a}\binom{N}{b}\binom{2N-a-b}{2N-K-a-b}(-1)^{K+a+b}

ただし、2N-K-a-b\lt 0の場合は\binom{2N-a-b}{2N-K-a-b}=0としておく。ab\lt Mのときの\binom{ab}{M}もそうである。

今朝縮めたABC-Dが取られていた。終端なしのrangeを完全に忘れていたのはまずい。reject!を活用するのは上手い。

そのあとはARCまでずっとハーメルンを読み続けていた。もうそろそろ最新話に追いつきそう。

午後8時にAHC001が終了。人々の解法を眺める。焼きなましをやるのはよくて、最初のうちは目標面積を小さく見積もっておくことや、焼きなましの遷移にいったん長方形を破壊するようなものを入れるのが効くらしい。あとは、全体をずらしつつ面積が小さい長方形を引き伸ばす、というのも僕の解法を発展させていったうちの1つと見れるだろう。長方形を分割していく方針の人も結構いたようだが、そちらは正直よくわかっていない。

ARC114に出た。遅い3完で306th、パフォーマンス2102、レートは2714→2665(-49)。ひどい、その一言に尽きる。

Aはよい。昨日も見た。Bもよい。サイクルを数えようとして、ちょっと立ち止まって連結成分の個数でよいことに気づけたのはファインプレー。ここまで7分、6位だったらしい。Cにすべてを破壊された。

最後20分でEに特攻し、脆くも敗れ去った。がりがり式変形している最中、今計算しているのが「ありうるすべての手順における操作回数の和」であることに気づいていたが、何らかの値で割ることで修正可能だと思っていた。不可能だった。

ボロボロのメンタルのまま、直後のTROC20に出た。ABCDFの5完25位でレートは2602→2588(-14)。初めてレートを落とした。

Aはやるだけ。Bは天才パズル1で、必ず2N-3本引けるので答えは2N-3-M。Cは天才パズル2で、0しかない場合はNO、0と1が両方ある場合は(2<=N,Mより)YES、1しかない場合は適当に左上から順に操作してみる。(2021/03/15追記:嘘。本当は常に可能。)Dは天才パズル3で、ランレングス圧縮して3個以下になるかN<=4であることがYESになる必要十分条件。Cはシンプルに難しいし、Dはずっと具体的な形を考えていたせいで0と1が切り替わる場所の個数に着目できなかった。最終的に何かそれっぽい解法を思いついて、とりあえず実装しようとした段階で実質ランレングス圧縮して3個以下になることを判定していると気づいた。ほとんど運試しのように出したが、通って嬉しい。CとDに合わせて1時間かけた。

そのあとEを考えていたが、解けず、Fのほうが解かれていたのでそちらに移った。各頂点についてとりうる値の最大値と最小値を管理する。条件が重なったりして、2つの頂点のうち片方が使えなくなったとき、もう片方の頂点の値が決まる。1つ決まると条件が連鎖するが、そこで決まっていく頂点はBFSで見ることにする。最後に残った条件とそれに関連する頂点たちが問題。一切証明していないが、およそmax-min-max-のように取ることになって、今見ている頂点たちはmax!=minであるから、条件は2部グラフをなしている必要があると考えた。そのように実装するとサンプルが合うので深く考えずに提出。するとREが出た。残り5分だが落ち着くことを意識して見ていくと、条件の番号から頂点の番号を参照するのを忘れて、条件の番号をそのまま使っている個所を発見した。直したが、サンプルを試すのが面倒に感じられたのでそのまま提出。祈るような気持ちでF5を連打した。結果はAC、残り3分だった。

GはOEISにあるらしい。面白いコンテストサイトですね。

ハーメルンを読む。ここ最近読んでいたものの、最新話に追いついた。

syosetu.org

TLで「主人公がVtuberになる」という言及がなされていたのを見つけて読み始めたが、冒頭は全然そんな感じではない。基本は主人公が地球人類の発展を見守り続ける話で、気まぐれにVtuberをやっているだけという話だったようだ。ちょうど現在更新されている部分。それはそうと「主人公が地球人類の発展を見守る」設定は僕の大好物であるため、むさぼるように読んでしまった。むやみやたらにテンプレ無双するだけのシーンが挟まれるが、全体的な流れは非常に良い。ただ文章が非常に残念なことになっているので、おすすめはしにくい。厨二というわけではないのが救いか。250話以上書いて、多少は改善されたような気もするが、相変わらずぶつ切りの文章である。

昨日のICPC練のIは他チームの解答が見れなくて困っていた。ホスフィンにAobayama_sugarstepのコードを教えてもらった。

mine691.hatenablog.com