週記(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

週記(2021/03/01-2021/03/07)

03/01(月)

日曜日の31時に週記を投稿してから、寿司打を少しやった。久しぶりに高級コースで+10,000した。手元を撮影しようと思ったがスマホの三脚などないしなあ……で諦めかけたが、ふとWebカメラが使えることに気づく。モニタ上部に設置したまま限界まで下に向けると、いい感じに机の天板だけが映る(後から気づいたが、これは動画編集でどうにでもなることだった)。それで、適当にお手軽コースを撮影して、上下反転して撮影されているのを直してTwitterに投稿した。

動画が終わってから8秒くらい無の時間があって悲しい。聞くところによれば、オブジェクトの最初と最後を切り落として先頭に詰めただけだと、元の長さ分の尺が確保されてしまうのではないかとの話だった。

午前10時半に布団に入ってしばらくハーメルンやなろうを読んでいたが、どうにも腹が減る。仕方なく食事をし、さらに1時間程度なろうを読んで、午後0時半に寝落ちした。

午後8時半くらいに目を覚ました。今週からサークル解説会は春休みなので、思うさま寝ていられた。午前0時半くらいまでそのまま布団でなろうを読んでいたが、メールを確認すると4年セミナーの配属が決定されていたらしいので、確認のために布団を出てパソコンに向かった。

4年次ゼミの割り振りについて、現在僕が第一希望にしているゼミは定員より多い人数が希望しているため、何人かを第二希望以降に回す必要がある。

週記(2021/02/01-2021/02/07) - kotatsugameの日記

こういうことがあって、周りの人の取得単位数など気にもしたことがなかったためアンケートの内容を見て怖がっていたのだが、無事第一希望のゼミに配属された。ホスフィン曰く、僕が希望しているゼミに人が集中しているとはいっても、そこで扱う4冊の教科書のうち僕が希望しているもの以外を目当てにしている人が多いのではないか、とのことであったから、そういうことなのだろうと思っておく。

2月が終わっていたので、また読書冊数の集計をしてツイートしておいた。

午前1時、また布団に戻ってなろうを読み始めたが、午前2時くらいにすぐ寝落ちしたようだ。

03/02(火)

午前7時起床。またなろうを読み続ける。せっかく朝に起きたのだから生協に行って本の受け取りでもしようかと考えたが、どうにも体が動かず、午後7時くらいまでなろうを読み続けた挙句また寝落ちした。

昨日から今日の午前9時半くらいまではこの作品を読んでいた。

https://ncode.syosetu.com/n2296ez/

これは「うちの脳内コンピューターが俺を勝たせようとしてくる」の作者の別作品なのでいずれ読もうとしていたのだが、どうにも設定や内容が肌に合わなかった。知識チートでNAISEIする話、まではよかったのだが、平凡な主人公が曖昧な知識で物事を推し進めようとしているのが合わなかったのだろう。身の丈に合わないことをしている、と感じてしまって、おしまいだった。知識チートもので、Wikipediaか何かのように正確かつ広汎な知識を披露する主人公が揶揄されることもあるようだが、僕はそうやって振り切ってくれたほうが好きである。

そのあとはこの作品を読んでいた。

https://ncode.syosetu.com/n0859fa/

この日記を書いている時点で100話くらいか。本編完結まであと50話もないが、読み終わるとは限らない。しかして今ここでこれまでの感想を書く気もない。

午後7時に寝落ちして、起きたのは午後11時半だった。サークルのバチャを寝坊した……と思ったが、slackを見ても今日開催された形跡がない。さらに今日はECR105があるが、あと5分もないし諦めるかな……と思ったところ、10分こどふぉったという情報が流れてきた。これは何らかの思し召しか。参加を決めて急いで準備した。

ABCD4完で終わり。直前まで寝ていたにせよ、これはあまりにひどすぎる。

Aは全探索。Bもちょっとひねって、四隅の置き方を24通り全探索すればよい。Cは難しいが、押すときはあるスペシャルマスの直前まで押してよい(わざわざ少し離れたところで止めなくてよい)ことが何となくわかるので、それを全探索する。そこまで押したとき、どこの箱まで影響して動くかは尺取り方のように計算できる。それ以降動かない箱のうちいくつがもともとスペシャルマスにあるかというのは、後ろからカウントを累積すればわかる。手元ではサンプルが合ったのに提出すると1ケース目で落ちて首を傾げていたが、custom invocationで実行してみたところ配列外参照していることに気づいた。1ケース目で落ちたのでペナが付かなかったのはいいこと。Dは答えが必ず存在するという制約がなくて微妙に不安だが、答えが存在しなかった場合の処理が書かれていないので大丈夫だろうと適当に提出したら通った。

Eは、サンプルの3つ目の答えを見てループでもOKだと勘違いしてしまい、解けなかった。結局双方向に辺がある頂点ペアが存在しないとNOで、さらにその辺に書かれた文字が一致していなければkが偶数の時NO、それ以外はYESというギャグであった。Fは考えていない。

寝ている間に取られていた最短コードを取り返したりもしていた。

atcoder.jp

布団に入ってから4時間半ほどかけてハーメルンの「輝きたくて」を一気読みした。

syosetu.org

これも「うちの脳内コンピューターが俺を勝たせようとしてくる」の作者の別作品で、今連載中のもの。この作者は毎日更新してくれるのが本当にすごい。今日の朝読んでいた作品は途中で読むのを止めてしまったが、こちらは肌に合ったのか、非常に面白く感じられた。主人公は自己評価低めで、主人公視点でしか語られない序盤は与えられたチートで一転突破みたいな感想を覚えるが、前作同様次第に主人公の生身のスペックも人間辞めてるレベルであることが明らかになってきて僕としては非常に好ましい。Vtuberものも好きなのでさらに良い。

そのあとハーメルンVtuberものを探していた。3つくらい序盤をちょっと確認して、1つ、文章も読みにくくなく良さげなものを見つけたが、8話にしてエタっていそう。僕もちょっとゆっくり実況を作ったが、創作を続けられずエタるのはどうしようもないことが体感できたので、ただただ涙を呑むしかない。

syosetu.org

チュウニズムに「LOVE EAST」が収録されるという告知が流れてきた。最高すぎる。本当に良いので、皆さんも良くなりましょう。

そのあとなろうに移ってさらに別の作品を少し読み、午後3時就寝。

03/03(水)

午後11時半起床。今日もサークルのバチャはなかったようだ。正直な話をすると、昨日の時点で主催者がバチャを忘れているであろうことは何となくわかっていたが、しかし生活リズムの関係上今週は出られそうにない僕が指摘してもなあ……と思ってなんとなくモジモジしているうちに僕も忘れてしまっていた。

食事してすぐ布団に戻り、昨夜(昼?)読んでいたなろうの続きを読む。

ちょっとTLを眺めているとウマ娘ハルウララについての話が流れてきて、読んだだけで感動してすぐに泣いてしまった。涙もろすぎる。

午前4時くらいに寝落ちしたらしい。今日は活動時間4時間半、そのほとんどを布団の上で過ごしており、まさに虚無の具現化とも言うべき1日であった。

03/04(木)

午前8時起床。ちょっと眠いが、起きていることにする。しかし午前中はパソコンの前で固まっているだけだったので、シャワーを浴びて切り替える。今日はチュウニズムのアップデートの日なので、午後はゲームセンターに行くことにする。

いったん生協に寄ってパンと注文していた本を買う。↓のときの本が1冊遅れて発送されていて、まだ受け取っていなかった。

また大学生協で本を注文しておく。前回注文してから新たに発売された新刊と、前回は在庫切れで注文できなかったが今見ると復活していた分、計4冊。

週記(2021/02/15-2021/02/21) - kotatsugameの日記

天気がいいので街までは自転車で移動した。久しぶりに乗ると太ももがパンパンになって、筋力の衰えを感じさせられた。

ゲームセンターには10時間くらい滞在して、55クレ使った。最初5クレほど新曲のAJ埋めをして、そのあと9時間くらいかけて「LOVE EAST」の理論値粘着をした。

120回くらいプレイしたはず。1落ちが4回、2落ちが5回、3落ち以上は数えていない。1日中プレイしてようやく出たが、別に譜面が難しいわけではなく、ただ僕が普段から何でもないところで赤を出してばかりだからである。僕にとってはこれが理論値2譜面目であった。粘着を始めたときはスピード9.5、判定0.0で、そこからいろいろ試して結局スピード10.0、判定-0.2に落ち着いた。昔SDVXで判定を弄ったとき、どれだけ早くしても自分がそれに慣れたらさらに早く押してしまうため全然nearが減らなかったというトラウマがあって、ちょっと腰が引けていたが、まあこの粘着の間だけなら何とかなるだろうと値を変えた。それより効果が大きかったのがスピードを上げたことで、判定は粘着後にもとに戻したが、スピードはこれからもこのままでやっていこうと思う。

本当に好きな曲なので飽きることはないし、譜面も体力を使わないので、立ちっぱなしであることにさえ目をつぶれば疲れはしない。金銭もこの際問題にならない。ただ、これだけの好条件があってすら理論値粘着は辛かった。自分には早いのではないかと思いもしたが、諦めたくなかったので、自分の精神力に寄らず粘着するため「全ランが埋まるか閉店するまでプレイし続ける」ことに決めた。結果として全ラン98人目に滑り込めていいことずくめ。

f:id:kotatsugame:20210309030721p:plain
47小節、51小節

ここで赤を出しまくった。この部分だけ見ても理論値通過できたのは10回くらいではなかっただろうか。このままではいけないと思って、注意深く観察したところ、普段はFASTが多いところこの部分ではLATEが出ているらしい。具体的には、47小節の振り下ろしが遅く、スライド始点で赤が出ていることが分かった。注意深く曲を聞いてみると、確かに僕が思っているのとテンポが少しずれていることに気づいた。かといって単純に早めると今度は手前のタップで赤が出るようになって、本当にどうしようもなかった。

疲れ果てて帰宅。「影の実力者になりたくて!」の更新が2年ぶりくらいに来ていてびっくりした。

https://ncode.syosetu.com/n0611em/

午前3時半就寝。

03/05(金)

午前10時、宅配が届いて起床。ICPC関連グッズだった。その中にチーム紹介ドキュメントも含まれていた。

メイキングは下書きですでに完成しており、あとは投稿するだけだった。夜のほうがいいだろうと思ってしばらく待っていたが、そのままタイミングを逃してしまった。2021/03/09に投稿した。

kotatsugame.hatenablog.com

そのあと少ししてから新春TechFULの商品であるトラックボールマウスが届いた。

最初は使い勝手に戸惑ったが、今はそこそこ慣れてきた。少しだけマインスイーパをやってみたが、3画面を移動するためのマウスポインタの速度とマインスイーパを正確にプレイするマウスポインタの速度は全然両立しない。今使っているキーボードもマウスも、競プロの商品として得たものであることに気づいた。面白い。

午前11時からTSG-KMC合同コードゴルフ大会に外部からの参加者として参加した。以降午前9時までずっとコードゴルフしていた。この日提出したのは次の言語たちであった。かっこで注釈が付けられている問題について、取られたのはこの日ではなくもっと後のことかもしれない。そのあたりの時系列を復元する気力はない。現在の最短コードを更新しないと提出できない仕様のため、手を付けた言語はもっと多かったかもしれないが、もはや記憶が定かではない。ずっとコードゴルフしていたので現実感も薄い。

  • Perl(取られた)
  • Python3(取られた)
  • Go
  • Ruby
  • AWK(取られた)
  • D
  • sed
  • Haskell(チームメイトに短縮された)
  • GolfScript
  • Crystal(取られた)
  • F#(取られた)
  • wake
  • Perl6
  • Ballerina
  • Rail
  • Octave
  • Lua(取られた)
  • Erlang
  • bash(pureのほうは取られた)
  • SQLite3(チームメイトに短縮された)
  • Verilog(取られた)
  • 05AB1E(取られた)
  • gs2(取られた)
  • COBOL
  • Elixir
  • Racket(取られた)
  • Zsh(取られた)
  • Kotlin
  • Vim
  • m4(取られた)
  • Makefile(取られた)

午前9時就寝。

03/06(土)

午後1時起床。

午後2時からDDCC予選に参加した。サンプルがあるのに気づかず提出しWAを生やしてしまったりもしたが、30分前後で全完。やるだけの問題4問用意して何がしたいんだろう。もうどんな問題があったかも覚えていない。

コードゴルフに戻る、が、途中ABC194に参加したのでそれを先に書いておこう。50分全完3WAで66位。

Aは問題を読めず2WA出した。Bも全然題意が把握できず結構時間がかかった。Cは明らか。Dは最初sum N/iではなくprod N/iを求めてしまい1WA。何を考えていたのかわからない。Eはやるだけ。Fは桁DPをもとにして考えた結果、Nより小さくなることが確定した桁で残りの出現パターンも包除原理で数えてしまう実装をし、DPがいらなくなった。代わりに16^2くらいの定数倍がついて1900msだった。

総じて頭が回っていない。コードゴルフに意識を支配されすぎていて、また睡眠時間も減らしてしまったため、非常につらい。明日のAGCが怖すぎる。

ABCのほうのコードゴルフは、ACDを取ってBは取られてEFは手つかずといった感じか。Cは分散のN^2倍なのでOctaveが強いかと考えたのだが、精度の問題だろうか、大きなケースが全然合わなかった。正直あまり考えていないので、すべての問題について縮む余地は大いにある。

さて、DDCC予選とABC以外の時間はずっとコードゴルフをしていた。この日提出したのは次の言語たちであった。昨日提出して今日も提出している言語は、つまり縮めたということである。

午前6時就寝。

03/07(日)

正午起床。午後1時からICPC模擬地区大会があった。これについては参加記を書いた。

kotatsugame.hatenablog.com

コードゴルフ大会は今日の午後9時までであった。ICPC模擬地区大会が終わってから3時間ばかり、最後の仕上げとして取り組んだ。今日提出した言語は次の通り。

  • Jelly

といっても1つしかない。残りの時間は、Makefileと><>(fish)と格闘していた。Makefileのほうは入力を3行ごとに処理する方法が、><>のほうは答えを求めるアルゴリズムが全然違っていて、負け。

終了直後からAGC052があったので出た。ABの2完78分で87位、パフォーマンス2698、レートは2716→2714(-2)。相変わらず頭が回っていなかったものの、崖に助けられた。さらにB問題も最後の解の判定が微妙に足りておらず、yosupoさんのケースで落ちる。

Aは、パズルとして面白くはあるのだろうが、Ratedに出されると泣くしかない問題。45分かかった。0をN個と1をN個と0または1を並べるのだろうな、ということまでは問題を見た瞬間に分かった。そこから文字列の両端は0..00..1と……という風に4パターンあって、このうち3種類しか出現し得ないことを利用するのだと考えていたが、0..01..1が両方出る入力に対する答えを作れなくて苦労した。文字列の形を、末尾に続く0または1の個数という形でもっと詳しく見れば、うまく証明できることに気づいてびっくり。

翻ってBは非常に面白かった。辺に関する条件を頂点に関する条件に言い換えるステップが面白い。この方針が降ってきたとき、直観として正しいと確信した。実際に実験すると頂点の値のswapになっていて、一気に目の前が開けたような心地がした。そこから解のチェックをするステップで、これまで謎に包まれていたNが奇数という条件が突如姿を現して、見事に伏線を回収されたような驚きがあった。詰めが甘かったので、それだけは心残り。完璧に解いておきたかった。

AGC後に、コードゴルフ大会のWriteUpを書いた。以前の大会のものはここから見られる。2021/03/15以降には、今回の大会のものもここから飛べるようになるはずだ。

github.com

さて、僕は最終的に121言語のうち40言語(bashは外部コマンドの実行の可不可で2種類ある)に提出し、21言語の最短コードを保持していた。相変わらず以前に書いた経験のある言語や汎用言語ばっかりだが、まあ数字にしてみればかなり頑張っていたのではないか。その中から5言語、特に面白いと感じたものについて、WriteUpの内容をここにも書いておこう。短縮ポイントを見つけられた場合などはぜひ教えてほしい。

コンテストリンク:Esolang Codegolf Contest #7

問題

入力

  • 入力には 16 個のテストケースが含まれている。
  • 各ケースでは、文字 0, 1 からなる長さ 3 の文字列が 3 個、改行区切りで与えられる。
  • 各ケースの最後には改行が与えられる。

出力

  • 各ケースについて、次の問題を解け。

    入力を 3 行 3 列の将棋盤とみなす。 文字 1 は対応するマスに歩が 1 個あることを、文字 0 は対応するマスに駒がないことを表す。 二歩であるとは、2 個以上の歩が置かれている列が将棋盤に存在することとする。 (3 個の歩が置かれている列でも二歩になることに注意せよ。)

  • 二歩であれば 1 を、そうでなければ 0 を出力せよ。
  • 文字 0, 1 はちょうど 16 個出力せよ。
  • 出力された文字列に含まれる空白文字(改行含む)は無視される。
  • 文字 0, 1 および空白文字以外の文字を出力してはいけない。
  • 提出するプログラムは、入力されうるすべてのテストケースに正しく出力できるものでなければならない。つまり確率解を禁止する。

制約

  • どのテストケースも 1 の個数は 2 以上 4 以下である。
  • 入力されうるテストケースの集合は、1 の個数が 2 以上 4 以下である盤面の集合と一致する。
  • 1 の個数が 1 以下または 5 以上である盤面に対しては、プログラムは正しく動作しなくてもよい。

APL (47B)

{+/'23'∈⍕ω}¨+/16 3⍴⍎⍕⎕ARG[6]
)OFF

数値として足して/2|3/をしている。右から順に

  • ⎕ARG[6]:入力
  • :to_stringのはずだがよくわかっていない。ないと動かない。
  • :eval
  • 16 3⍴:16行3列に成形
  • +/:sum(行ごと)
  • ¨:行ごとに左の関数を適用

{}が無名関数で、引数はωに入る。

  • :to_string
  • '23'∈:elem。[2を含むか 3を含むか]という列が得られる。
  • +/:sum

最終的に01の列になって、変数に入れたりしていないため出力される。

Cubix (21B)

pa^<IIaqbI/biO<@..?:,
  pa
  ^<
IIaqbI/b
iO<@..?:
  ,.
  ..

スタック型の言語だが、ほとんどの演算がスタックの中身を消費しないのは特徴的か。例えば加算をすると、popしたオペランドを再度pushしてから演算結果をさらにpushする。

上のような配置の2x2x2のキューブ上をIPが動いていく。スタートは3行1列目のIで、方向は右向きだ。 3x3x3に詰め込んで満足していたが、ふと2x2x2を考えてみたら詰め込めてしまってびっくりした。

アルゴリズムは、3行を数値として読んで(x&y|(x|y)&z)!=0である。 スタックの中身を消費しないことを利用してIIaqbIapb:,Oと書ける。 x&yを計算してから、いったんqでスタックの底に退避させ、後でpで持ってきている。 !=0の代わりに、:dupして,で切り捨て除算している。実装上0/0は0らしい。

次に、どのようにIPが動くのか見ていこう。

まず3行1列目のIから右方向にIIaqbI/と進む。 /で進行方向が変わる。右方向に進んでいたので、次は上方向になり、立方体上面、1行4列目のaに上から進入する。 上面では<^によってUターンのようなことをしながらapを実行する。1行4列目のpから上に進むと、今度は3行8列目のbに上から進入することになる。 そのままb:と進み、今度は6行3列目に下から進入する。.はnopで、途中<で進行方向を変えつつ,Oと進む。

これでケース1つぶんの入出力が完了した。無限ループになってはいけないので、実行を継続するか判定する必要がある。 iで1文字読んで、改行コードか-1(EOF)かで判定できる。 先ほどの続きから、4行1列目のi、さらに左に行くと今度は4行8列目に回り込んで:?と進む。:dupなので関係ない。?が条件分岐になる。 ?にたどり着いたとき、スタックのトップが0より小さいなら左に、0より大きいなら右に曲がる。 先ほど読んだ文字の文字コードが見られ、改行コードなら右に、EOFなら左に曲がることになる。

左向きに進んでいるので、右に曲がると上方向に進むことになる。また/で反射して右方向に進み、そのまま3行1列目のIに左から進入することになる。確かにループしている。 逆に、左に曲がると下方向に進むことになる。今度は6行4列目に下から進入し、そのまま上がって@にたどり着き、実行が終了する。

コードゴルフとしては、2x2x2に収めたほかにも、下面にnopが多くあらわれるように工夫している。 2x2x6文字に足りない分は勝手にnopで埋められるので、下面の3つのnopはコードに書かなくてもよい。

Jelly (24B->21B)

ƈƈFпOs12µs4PS%9>1)

アルゴリズムは、1ケース12文字(改行を含む)の文字コードを順にabcdefghijklとしたとき(aei+bfj+cgk+dhl)%9>1である。 左から読んでいこう。

  • ƈƈFп:入力を全部読むおまじない。第5回大会のWriteUpから持ってきたものが1B改善できた。元はƈƈ¹Ð¿であるが、この¹はただの恒等関数のくせに2Bも使っている。適当に1Bのmonadを試してみたところ、Fでうまく動いてくれた。Fの意味はリストのFlattenである。
  • O:ord。
  • s12:リストを12個ごとに区切り、リストのリストにする。
  • µ:関数定義を区切る。ここから右は左とは独立した関数になる。

区切られた関数はmonadである。s12で作った12要素のリスト[a,b,c,d,e,f,g,h,i,j,k,l]が引数となることを考えよう。

  • s4:4要素ごとに区切ったリストのリストにする。[[a,b,c,d],[e,f,g,h],[i,j,k,l]]
  • P:総積。積は、リストに対しては内積になるらしい。[aei,bfj,cgk,dhl]
  • S:総和。aei+bfj+cgk+dhl
  • %9:9で割ったあまり。
  • >1:1より大きいか否か。

  • )µ€エイリアス。関数定義を区切り、で左の要素に対してmappingしている。 つまり、先ほどのµより左にあるリストのリストに対して、今見たmonadが要素ごとに適用されている。 )が信じられないくらい偉い。µという2B文字とという3B文字が合わさって1B文字になっていて笑いが止まらない。

ところで、赤チームのコードは見た目的に全然違うものだった。そちらを参考に21Bまで縮めたので、後学のために読んでおこう。

ɠṭɠ,ɠ¤OPS%9>0¢

アルゴリズムは変わっていない。 ɠで1行読み込んでいるが、このとき改行が消えるため、OPS%9したあと>1ではなく>0になっている。

ɠṭɠ,ɠ¤を読もう。先頭のɠniladなので、以下これに対して関数が適用されていく。 は左オペランドを右オペランドにリストとして足す。左オペランドɠだが、右オペランドについて少し注意する必要がある。 順当に読めばすぐ右にあるɠだが、少し先の¤でパーサの挙動が変わり、実際にはɠ,ɠが右オペランドになっている。

¤は、直前にパースしたコマンド列の後ろからいくつか切り取って、niladと1つ以上のlinkが繋がったパターンを1つのniladとしてまとめる役割を持っている。 今回はɠというniladというlinkがまとめられている。複数の切り取り方がある場合は、最も短いものが採用されるので、ここで切られる。

ɠ,ɠは2行読んで2要素のリストにしたniladなので、それに最初のɠが足されて、全体として["efg","ijk","abc"]のようになる。 あとは先ほどと同様OPS%9>0で答えが得られる。

以上で、ɠṭɠ,ɠ¤OPS%9>0が1ケース分の入力を読んで計算するniladであることが分かった。 最後に¢で直前のlinkが(niladとして)参照されている。直前のリンクというものは存在しないため、この場合現在見ているlinkが参照されるようだ。 結果的に、いわばmain再帰のような形のコードとなって無限ループが実現されている。(これは僕の解釈なので、より良い説明があればぜひ教えてほしい。) 最終的にEOFを読んで落ちる。

sed (20B)

N
N
h
G
/1...1/c1
c0

3行を連結し、2倍して/1...1/を探している。

  • N:次の行を読む。2回実行するので、合計で3行、つまりケースごとに以下の処理を行うことになる。
  • h:上書きホールド。以前のホールドスペースの内容を削除し、現在のパターンスペースの内容を入れる。
  • G:ホールドスペースの内容をパターンスペースに追加する。これで文字列が2倍されたことになる。
  • /1...1/c1/1...1/にマッチしたら1を出力して(残りの処理をせず)次の行の処理に進む。
  • c0:前の行のマッチに失敗した場合のみこの行に到達する。0を出力して次の行に進む。

Vim (32B)

qq3JYPJr0/1...1\|\%#
xVpjq15@qZZ

qq..qでマクロを作り、15@qで15回(実行しながら定義するため1回減っている)繰り返す。 以下マクロを詳しく見ていく。処理開始の時点では1ケース3行のうち1行目にいて、処理が終わったら次のケースの1行目にいる、という状態を保つ。

  • 3J:3行連結
  • YPJ:ヤンクして直上に貼り付け、即座に下の行と連結する。これで行が2倍になったことになる。
  • r0:カーソル下の1文字(Jの直後のため、必ず空白文字)を0に置き換える。
  • /1...1\|\%#/1...1/を探す。マッチすれば、カーソルは最初の1の上に動く。マッチしなければ次の\%#だが、これは現在のカーソル位置であるため、カーソルの移動は起こらない。マッチに失敗するとマクロの実行が止まってしまうので、必ず成功させるためのもの。末尾の/は省略できる。

この時点でカーソル直下の文字が出力すべき値になっている。

  • xVp:カーソル直下の1文字を削除しつつレジスタに入れ、ビジュアルモードで1行全体を選択してレジスタの中身で上書きする。
  • j:1行下、つまり次のケースに進む。

最後のjで最終行のさらに下に進もうとすると勝手にマクロが止まるので、qq..q15@qではなくqq..@qq@q再帰のようにしてもよい。これはループ回数が3桁以上になると縮む。 AtCoderVimが追加されてからたった10か月の間に100問以上の最短コードが生まれていて、知見が溜まりまくり。

ICPC模擬地区予選 2020 参加記

2021/03/07に開催された模擬地区予選にチームAobayama_dropoutで参加しました。 メンバーは変わらず碧黴さん・ゆきのんさん・僕です。

模擬国内で使用するユーザ名とパスワードは、各チームに3組ずつ配布されました。直前になって適当に割り当てを決め、コンテスト開始です。

序盤(C問題)

特に何も打ち合わせがないまま、シュッと始まりました。碧黴さんがA、ゆきのんさんがBを読むらしいので、僕はCを読みます。

Cは挿入DPができそうな見た目をしています。同じ値の要素をまとめて、個数を見つつ遷移をしていきます。DP配列としてi<j<kかつa_i>a_k>a_jのうちjだけがある状態、jkがある状態、すべてある状態、の3つを考えます。1つ目は必ず1通りで、3つ目は値が1種類しかありません。2つ目については、条件を満たすjkの組のうちjが最も大きいものを考えることになるため、これだけは配列で持ちます。

これで適当に遷移を書いてみたところ、O(N^3)でした。サンプルを試すと一発で合ったので提出、AC。39分で、2番目のACだったようです。

E問題とB問題

僕がCを通している間に碧黴さんがAを通し、D問題の概要を共有してくれていました。パッと見フローですが、どうにもグラフが想像できなかったので、Eを読みます。明らかに牛ゲーなので、碧黴さんに伝えて実装してもらいます。

ゆきのんさんがB問題で詰まっていたので、これも概要を教えてもらい、priority_queueで中央値を動的に管理する方針を立てて伝えます。これは左右のサイズを注意深く観察しないとすぐバグるイメージなので、ちょっと面倒そうだなと感じて細かい実装までは伝えませんでしたが、ゆきのんさんも同様の解法を見たことがあるらしく、伝わりました。

F問題

Fを読みます。円を左右に分けてCHTっぽくやれば解けると考えましたが、ここで嘘をつきました。実際に式を立てればCHTであることがわかるのですが、僕はそうではなく「曲がっていても直線っぽく扱える」と感じてしまい、スライド最小値で実装してしまいました。

ここで碧黴さんのEがREを出したらしく、コードが共有されてきます。見てバグを指摘したところ、またRE。再度見るとまだバグが残っていて、これを修正してもらうとやっと通りました。

またゆきのんさんがBを通し、Iを読んでいるようで、概要が共有されてきます。そのまま期待値DPをする方針も立ったらしく、掃き出し法をするライブラリを提供しました。

さて、Fですが、実装が間違っているのではないかと疑っていろいろ適当に書き換えた結果4WAくらいしていました。さすがに考察を疑い、結果まずいケースを発見しました。ある円をある円が覆っているとき、その2つがqueueの先頭でずっと比較され続けるのですが、その間に下から別の円が上がってくる可能性があります。

結局一から書き直すことになって、CHTという方針そのものを捨て、円をソートして交点を調べ、最大値が変わる境界を保存して、クエリには二分探索で答えるコードを書きました。提出すると一発AC、185分でした。

G問題

僕がFを通すより先にゆきのんさんのIが通りました。そのまま3人でGを読みます。僕はもう全然頭が回っていませんでしたが、ゆきのんさんが半分全列挙を疑いました。その方針で考えてみたところ、右半分を先に列挙して、左の数が10の何乗倍されるかによって保存するテーブルを分ければ、解けることがわかりました。

僕が実装して提出しますが、RE。コードを共有してみると、すぐにREを出すケースが作成されてきました。

123456789123456789123456789123456789
47

どうやらテーブルのサイズが1足りていなかったようです。増やして提出しなおすとAC!243分でした。

残り時間

最後に全員でKを考えていましたが、全然ダメでした。今振り返ってみれば、全然集中していなかった気もします。

結果

12位でした。全体的にあんまり集中できていなかった気がしますが、これはここ数日コードゴルフ大会にどっぷり浸かっていて、睡眠時間などを削ってしまっていたからだということにしておきます。

実装の分担は結構できていたのではないかと思います。

ICPC2020チーム紹介ドキュメントのメイキング

kotatsugame.hatenablog.com

gist.github.com

https://ideone.com/BrtL8u

今回はQuineのAAコードを作ってみました。

1.AAを用意する

tool-taro.com

前回と同じく、またこのサイトを使ってAAを作ります。元となった画像はガウリールドロップアウトのアニメ公式サイトから拾ってきました。↓のページの4枚目の画像です。著作権は……よくわかりません。

gabdro.com

このままAA変換サイトに投げてもよいのですが、輪郭をちゃんと取り出すために下準備をします。輪郭を認識する……機械学習だな!とはならず、温かみのある手作業です。ペイントで300%くらいに拡大し、マウスを握りしめて縁取りして、内部を白で埋めます。何度か試してみて、つぶれがちだったアホ毛・眉毛・口はちょっと太くしておきました。

f:id:kotatsugame:20210228081646j:plain
微妙に残った元の色が哀愁を誘う

ideoneのフォントでいい感じに見えるように縦横比を調整します(1敗)。ここでいう1敗とは、全ての工程が完了してから縦横比を調整していないことに気づいた、という意味です。

AA変換サイトに投げたものがこれです。サイズは80を指定しました。これはチーム紹介ドキュメントの制約で、幅が半角75文字以内である必要があったからです(1敗)。ここでいう1敗とは、全ての工程が完了してから幅が制限をオーバーしていることに気づいた、という意味です。上の敗北とは別の回です。

f:id:kotatsugame:20210228083245p:plain
第一段階

https://ideone.com/lPnJYs

まず、`を空白に置換し、それ以外すべての文字を#に置換します。また、頭のてっぺんの線を付け足します。そして、幅が半角75文字に収まるように、左右から少しだけ行を削除します。幅を80に指定してAAに変換しましたが、実際は79文字でした。アホ毛を少し縮めて右から-2行、あとは左から-2行しておきます。顔が真ん中に来るようにしました。

さらに後々のため、右目の下2行が9文字・7文字になるようにしておきます。

f:id:kotatsugame:20210228084045p:plain
第二段階

https://ideone.com/2LgmEH

2.ランレングス圧縮する

今回は出力をAAにするにあたって、ランレングス圧縮した数列をもとに構築するアルゴリズムを採用しました。白と黒しかないので、それが交互に出現するようにゼロ埋めしておきます。行の幅をすべて等しくしておけば、改行の出力は75回に1回行うと決め打ってよいです。数列は、各値に65を足したものを文字コードとして見た文字列にして保持します。運よくバックスラッシュが出現しなかったので、特にエスケープなどを考える必要はありません。

次のようなプログラムで文字列を圧縮しました。

ans=[]
while s=gets
  s.chomp!
  a=[]
  t=" #"
  c=0
  75.times{|i|
    t[a.size%2]==s[i] ? c+=1 : (a<<c;c=1)
  }
  a<<c
  a<<0 if a.size%2==1
  ans+=a
end
A=65
puts"WARNING"if ans.include?(92-A)
puts ans.map{|e|(e+A).chr}.join

3.Rubyコードを書く

「あなたの知らない超絶技巧プログラミングの世界」という本を読みます。

https://www.amazon.co.jp/o/ASIN/4774176435/gihyojp-22

4-1-1項(p.137)に、アスキーアートQuineの基本構造が載っています。これを使いました。

eval$s=%w(
s=%(eval$s=%w(#$s))*"";
# 成形して出力
)*""

成形して出力するところさえ考えればよいです。次のようになりました。(一か所(){}が変わっていますが、コードの内容に違いはありません。)

s=%(eval$s=%w{#$s}*"").chars;
a="圧縮された文字列";
t=[32.chr]*897;
l=0;
a.bytes{|c|s,t=t,s;c.downto(66){$><<s.shift;(l+=1)%75==0&&puts}}

どのようなコードを経てこれにたどり着いたかは記録していませんが、最初に書いたコードからかなり変わったことは覚えています。このコードの文字数がちゃんとAAの#の文字数より少なくなるようにコードゴルフしたからです。それでも微妙に収まらなかったので、先ほどのAAから孤立した空白や#をいくつか削除することで、圧縮後の文字列が短くなるようにしました。最終的に、以下のようなAAを使いました。

f:id:kotatsugame:20210228094947p:plain
第三段階

https://ideone.com/KL1HCq

4.AAにする

先ほどのコードをそのまま実行すれば、AAのQuineが手に入ります。つまり、わざわざ手で空白を入れたりして最初の状態を作る必要はないということです(これも「あなたの知らない超絶技巧プログラミングの世界」に書いてあることです)。

ここで、先ほどのコードに少し無意味な変数を足し、順番を入れ替え、圧縮された文字列を2つに分割して、次のようなコードを実行します。

eval$s=%w{
a="圧縮された文字列の先頭";
Aobayama_=t=[32.chr]*897;
l=0;
s=dropout=%(eval$s=%w{#$s}*"").chars;
(a+"圧縮された文字列の末尾").bytes{|c|s,t=t,s;c.downto(66){$><<s.shift;(l+=1)%75==0&&puts}}
}*""

僕が所属するICPCのチーム名はAobayama_dropoutです。これがQuineの中に見えていると、より技巧的に感じられることが期待されます。そこで、Aobayama_dropoutという変数を足しました。最初にAAを作ったとき、右目の下2行が9文字・7文字になるようにしていましたが、そこにちょうどこのAobayama_(9文字)とdropout(7文字)が来れば、全体のだいたい真ん中あたりにチーム名が見えることになります。

試行錯誤の結果、圧縮された文字列の最後3文字だけを分割すれば、ちょうど狙った位置に変数名が来てくれることがわかりました。

5.完成!

f:id:kotatsugame:20210228100549p:plain
実行結果とともに

https://ideone.com/BrtL8u

6.余談

大きな幅で作ってしまったものは、Aobayama_dropoutに加えTOHOKU_UnivもQuineに含めることができました。せっかくなのでそちらも載せておきますが、縦横比を修正する前のため、キャプチャはideoneではなく僕の手元の環境になります。

f:id:kotatsugame:20210228101350p:plain
右目の下半分に注目

https://ideone.com/8bii4H

7.手元に届いてみると……

f:id:kotatsugame:20210305110836j:plain
潰れちゃった

悲しいなあ

週記(2021/02/22-2021/02/28)

02/22(月)

週記を投稿してからしばらく、以前追いついてから更新を放置していたなろうを数作品読んでいた。一度一気読みして追いついただけあって、やはり面白いのだが、どうにも少し溜めると手が伸びなくなってしまうようだ。正午就寝。

午後6時から30分おきに目覚ましをかけていて、午後7時半に起床。サークル解説会は午後8時からで、それの準備をしようと余裕を持たせていたのだが、眠すぎて起きられなかった。残り30分しかないが、何とかARC112-ABの解説スライドを作る。正直公式解説がそこそこ丁寧なので目新しいことは言えない。今日はChanyuhさんがE問題の解説をしてくださるらしいので、なかなかレベルの高い解説会になりそうだ。

何事もなく終了。E問題の解説は公式解説の方法と形式的冪級数の方法2つを紹介してくださった。

2021/02/22 定例会 | puzzleknot 公式サイト

Eは、「まだ動かしていない区間」の両端を持つDPをO(N^2M)で書いてみると、サンプルが合う。

週記(2021/02/08-2020/02/14) - kotatsugameの日記

僕はこのような(解説とほとんど同じ)考察ステップの踏み方をした。ここからだと形式的冪級数にたどり着くのはかなり不自然に見える。どちらにせよ「先頭に置くのも末尾に置くのも(あとからcomb(A+B,A)を掛ければ)同じである」ということに気づく必要があって、その気づきを最初に得るか最後に得るかの違いとも考えられる。

終了して公式サイトの更新やツイートをし、少しAOJ-ICPCを開いたが、眠気に負けてすぐ布団に戻り、寝た。午後9時から午前0時まで寝ていたらしい。本当はこのタイミングでガッと睡眠負債を返済したかったのだが、やはりというべきか、それほど長くは眠れなかった。長く眠るには長く眠るだけの準備とか気合いが必要である。

起きてからまたなろうを読む。午前3時くらいに起き上がり、食事してAOJ-ICPCから1問解いた。500点で、以前チャレンジして解けなかった「The Two Men of the Japanese Alps」。問題概要はまだ覚えていた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5244797#1

ありうる標高をすべて列挙して、直線を分割するのは良い。ここで新たに作成される点の個数をN^2/2以下と評価したのもピッタリ合っていた。問題は、そこから最短経路問題にするときの辺の張り方であった。左右2人とも後ろ向きに移動することはないと思っていたが、実はあるらしい。適当に遷移を増やしたら通ったので最初はよくわかっていなかったが、この遷移がないと答えが無限大になる小さいケースを作成できた。

7
0 0
1 2
2 1
3 4
4 0
5 3
6 0

3 4で出会うことになる。右の人は最初に0→3→0という標高の遷移をしなければならず、左の人は0→2→1→3(→4)を往復してそれに対応する。往復するので、復路において1→2と後退するが、この時右の人は3→0の真っ最中であるため、こちらも後退しなければならなかった。わかってみれば簡単なことだった。

明日は昼からICPCのチーム練がある。午前6時半就寝。

02/23(火)

午前11時起床。弁当を温めて食べるくらいの時間はあった。午前11時半からチーム練。今日はこのセットだった。

https://codeforces.com/contest/1070

ABCDEFGHIJKの11完だった。僕はDKHFAEIBをこの順で解いた。

DKHは自明。Fはやるだけ。Aは最初読んだときSmall Multipleが頭にチラついてうまく考察できなかったが、*10+0から*10+9までを全部書くとただのBFSでも値の昇順に計算することができる。Eは適当にBIT上で二分探索する。Iは結構難しかった。uvを結ぶ辺があったとき、これと同じ会社の辺はuvのどちらか一方にしか存在できない。どちらに存在するかは辺の向き付けに対応して、この言い換えのもとで入次数・出次数が定まるので、フローを流して復元する。Bは気合い。blacklistの区間に対して、whitelistのいかなる区間も含まないような極大なsubnetをとることにしてよい。これは、subnet間の関係として、どちらかがもう片方に完全に含まれるか全く交差しないかの2通りしかなくて、中途半端に重なるようなものが存在しないことからわかる。

最後1時間Lを考えていて、答えが2以下になりそうなことはエスパーできたが、構築ができなかった。Um_nikのコメントを読んでupsolveした。答えが2であるとすると、次数に関する条件は各頂点にZ/2Zの元を割り振る連立方程式の形で書ける。この連立方程式は必ず答えを持つことが示せて、このときbitsetガウスの消去法をするとO(N^3/wordsize)で解ける。

https://codeforces.com/blog/entry/62570?#comment-465420

午後6時からCF #704 Div.2。全完。pretest時点では20位だったが、システスでかなり上がって11位になった。

ABは明らか。Cも明らかだけど実装ミスで1WA。↓これだ。

Dは3回もWAを生やしてしまった。まずB-1<=K<=A+B-2の場合の構築を思いついて、それとA=0B=1を実装して提出した。WA。次にK=0で必ず作れることに思い当たり再度提出。これもWA。K<=Aが作れることに気づき提出するも、さらにWAだった。結局、実は0<=K<=A+B-2の全てが作れることがわかり、A+B-2は理論上最大なので、これで正解。

Eはよくわからない。N<=MN>=Mで処理を分けるやつかと思い、簡単そうなN>=Mから考えていたところ、O(NM^2)っぽいのができる。多分速そうなので出したらpretestを通った。このM^2の項は、第1行のどことどこを変えるかに対応している。しかし実のところ、変えることでこれまでダメだった行がOKになる箇所というのはほとんどないらしい。第1行と4か所異なる行が存在すれば、4C2通りのどれかを選ぶしかない。3か所異なる行が存在すれば、片方は3C1通りで、あとは(だいぶ甘い評価だが)高々M通りである。結局O(NM)なので、これでよかった。計算量解析は日記を書いている今考えたことであって、システス中はTLEしないかとヒヤヒヤしていた。

午後9時からサークルバチャ。今日はCF #542 Div.1。aABCを解いた。

Aはよい。O(N^2)が通る制約でびっくり。ちょっと頑張るともっと速くなりそうな気はするし、解説にも線形時間で解けるとは書いてあるが、考えていない。Bは、正数の項を1つだけ作って残りを-1で埋めることを考えた。このままだとK素数の時などに困るので、-1を一つだけ-1-aにしてみる。項数n-1,...,-1,-1-a,xと並んでいるとすると、Aliceのコードはxを返す。翻って正しい解はn(x-n-a+1)となる。……と思ったが、実際は正しい解がもう少し大きくなる場合があるらしい。区間の幅に対する答えのグラフが上に凸の放物線になって、その頂点が実現可能な値の場合にそのようなことが起こる。n=2000決め打ちでやってみたらWAになったので、n=2..2000で毎回チェックしてみたところ、通った。

Cは題意を取るのにちょっと手間取った。10は4通りのアルファベット列を生成する:"1""0""10""1""0"。文字列Sのある区間から生成されうるアルファベット列の個数、というのを全ての区間に対して計算する。これは、区間に1文字足すことを考えればO(M^2)でできる。次に、以前にまったく同じ区間が出現していないような区間のぶんだけ答えを増加させる。文字列を反転してZ-algorithmを使うと、今の文字列の末尾から何文字までは以前に出現したことがあるのかわかるので、それ以降を足せばよい。わかってみれば簡単。

Dをずっと考えていたが解けなかったので、バチャ後にupsolveした。基本は平方分割で、rをfixしたとき[l,r]における1回しか出現しない値の個数がsum b[l..r]と等しくなるような数列bを構成できるというのも重要。rをインクリメントしたとき、bは高々3か所しか変更されないので、変更のあったブロックを毎回再計算しても間に合う。

https://codeforces.com/contest/1129/submission/108320562

ラノベを1冊読んだ。「ワールド・ティーチャー」14巻。実はキャラクターの名前を忘れてしまっていたらしく、うまく集中できなかった。Nardackさんのイラストが良い。大軍vs大群の戦いだったり、その中での主人公組の無双だったりの上手な描き方とはどのようなものなのだろう。読んでいて戦場の風景をうまく想像できなかったが、これは一般的な城壁のつくりとか兵士の様相を知らない僕に責任がありそう。

午前5時半就寝。

02/24(水)

午後5時半起床。布団でゴロゴロしていたらatgolferの更新が流れてきた。

atcoder.jp

こういうのまだ残っていたのか。そのあとに別の人に同じ方法でもう一つ最短を取られている。

食事をしつつ、AOJ-ICPC 550点の「夕食」を考えていた。これは星もたくさんついているしsolvedも多いが、全然わからずに今まで残っていた。これまでにした自炊の回数だけでなく日付が幸福度の総和に影響を及ぼすので、うまく独立に考えるためにこれをどう解消するかが問題。解消せずとも自炊の回数も持つdpをすれば当然できるが、そのままだと間に合うわけがない。これをデータ構造か何かで改善する方法も考えたが、うまくいかない。

毎日食堂に行くか自炊するかに寄せて、貪欲にずらしていく方法はどうだろう。これは以前にも考えていたが、結局これまでにした自炊の日付も評価に含めなければならないこと、また何らかの極小値にはまりこんで抜け出せないことを予感し、あまり細かく式を立ててはいなかった。これまでにした自炊の日付を評価に含めるのに、区間add・区間maxの遅延セグメント木などは使えないだろうか。評価値を毎回更新していくということだ。とりあえず、この方針で式を立ててみよう。まず最初に、毎日自炊する状態を考える。

毎日自炊する状態からi日目(0-indexed)に食堂に行くことにすると、得られる幸福度の総和はC_i増えてP(Q+i)下がる。またこれとは別に、以後N-i-1日の自炊パワーは2下がるので、さらに2P(N-i-1)下がると考えてもよい。よってC_i-P(Q+i)-2P(N-i-1)、これが初期状態からのi日目の評価値だ。その状態のまま、次にj日目に食堂に行くとどうなるだろう。

まず、j\lt iのとき。このとき、得られる幸福度の総和がC_j増えてP(Q+j)下がるのは変わらない。しかし、以後N-j-1の自炊パワーについては、すでにi日目に自炊しないことが確定しているのだから、下がる値は2P(N-j-2)になる。足してC_j-P(Q+j)-2P(N-j-2)=C_j-P(Q+j)-2P(N-j-1)+2P。よって評価値は+2Pされると考えてよい。

次にj\gt iのときを考えよう。この場合、以後の自炊パワーの下がり幅は2P(N-j-1)で変わらないが、j日目の自炊パワーがi日目に食堂に行った影響で2下がっているので、得られる幸福度の総和の下がり幅はP(Q+j)ではなくP(Q+j-2)となる。よって評価値はC_j-P(Q+j-2)-2P(N-j-1)=C_j-P(Q+j)-2P(N-j-1)+2P。奇しくも先ほどと同じ形をしている。

なんとも驚くべきことに、これで自炊の日付の影響はなくなってしまったようだ。評価値の更新にもセグメント木を持ち出す必要はなく、C_i-P(Q+i)-2P(N-i-1)の降順に並べて都度+2Pの係数を増やせばよくなった。極小値にはまりこむというのも依然として残っているが、これは食堂に行く日を全探索できるので問題ない。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5248766#1

かなりびっくりした。以下の解説ブログでは、もっと直接的に自炊の日付の影響を消している。+1-1+20にする、という部分だけ見れば見覚えがないこともなさそう。

yosupo.hatenablog.com

SRM801に出た。roomに18人いて、そのうち9人が赤だった。EasyとMedを解いて14位。システス前は22位くらいで、Hackが大量に出て一度は26位まで落ちたが、システスで上の人が大量に落ちたようだ。レートは2481→2521(+40)でhighest。いい感じ。

Easyは謎。最初はmapで個数をカウントして、毎回インクリメント・デクリメントしようかと思っていたが、このmap(またはsetを用いても同様)で付くlogは非常に重いらしい。この方針で大量の人が落ちていた。僕は何となくvectorsortして毎回舐める方針に切り替えていたので難を逃れた。

Medも謎。01のように差が1しかない文字同士はswapできないので順番が保たれる。逆にそれ以外はどうとでもなるので、9個の差が1である文字のペアについて、それぞれを抜き出した文字列をarray<string,9>に入れ、これを比較して重複を削除する。見た瞬間解けてよくわからなかった。最悪ケースでは長さ2500の文字列2500個に対し、それぞれ9回ずつ舐める処理をして、その上2500個のarray<string,9>sortするので、不安になって試してみたが、普通に速かった。

Hardはカス。各折れ線は凸包をとって考えてもよくて、どうせ長方形の一辺はどこかの辺に沿う(これは論文があるらしい)ので、それを全探索して頑張ると解けそうである。ここまではすぐわかるのだが、微妙に未証明なので書くのをためらっていて、結果残り20分くらいで書き始めたものがCEのままコーディング時間が終了した。後から書き進めたところ、どうにもデバッグ含めて残り20分くらい必要だったらしいので、すぐ書き始めても間に合わなかったのかもしれない。サンプルを合わせて半信半疑のままシステスを走らせたら一発で通ってびっくり。そもそもSRMは一発で通さなければならないんだよな。

コンテスト後は本を読んだり少しAOJ-ICPCを進めたりしていた。金曜日にまた夕方から遊ぶ予定があるので、生活リズムを少し整えておく必要があると思い、午前7時くらいに布団に入る。

SRMのHardについて、長方形のサイズを1e5x2e5に決め打っても通るらしい。なぜそうなるのか全然わかっていなかったのだが、制約をよく読みなおすと、折れ線の長さが2e5以下であるという文言を見つけた。これが効いているのだろう。辺の長さが1.4e5の正方形、みたいな図形は入力に存在しないということだ。

しばらくハーメルンを読んでから午前10時くらいに寝ようとしたが、眠れなかった。パックご飯を食べ、読んでいた「盤上の向日葵 上」を読み切って、下巻を50ページくらい進めたところでいい感じの眠気が来たと思い、午後0時半就寝。

02/25(木)

午後9時半起床。まずい。

食事をしてから3時間くらいかけて「盤上の向日葵 下」を読み切った。ラストに向けた大きな流れと、その結末に衝撃を受け、しばらく動けなかった。帯の煽り文句にも「しばらく立てないくらい素晴らしかった」とあるが、看板に偽りなしといったところか。

腕は確かだが口も態度も悪い刑事・石破と元奨励会員の巡査・佐野の警察ペアが主となる章と、幼くして母親を亡くし父親から虐待を受けていた、長じて将棋のプロ棋士となる上条桂介が主となる章がそれぞれあり、並行して話が進んでいく。警察ペアの章では現在の視点から過去に起こったことを探り、上条桂介の章では少年時代から現在に至るまでの過程を丹念に描いていく。最初は独立しているように感じられる2つの物語だが、時を経るごとに、あるいは捜査が進むごとにだんだん焦点が明らかになってきて、ついに最終章で2つの物語は完全に一致することになる。上条桂介とその周囲の人々の、どことなく危険で波乱に満ちた生活、また捜査によってその足跡を着実にたどっていく警察ペアの追体験が印象的だった。

このような本を読んだ後は、しばらく次に何を読むか迷うことになる。ラノベでは、何らかの感動を得ようとして読んではいないので、たいてい薄い読書体験になる。そんな中でたまにこうやって一般に高い評価を受けた本を読むと、得られた感情のあまりの違いにこういう本しか読まなくてもよいのではないかと考えてしまうが、しかしラノベを読むのは止められないし止めたくもない。

しばらく呆けていたが、そうもしていられないので、意識的に競技プログラミングに取り掛かる。AOJ-ICPCで昨日開いた問題は幾何だった。幾何の計算について、入力は整数なのだから、許される限り整数の範囲で計算するようなライブラリは作れないだろうかということを以前から考えていた。直線の交点を具体的に求めたりするのは不可能だが、例えば交差・接触判定は可能だろう。今回の問題もそれが使えそうなので、思い切って実装してみることにした。まず現在の幾何ライブラリを複製して、doubleの部分を全部long long(ただしもっと柔軟性を高めるためにusingで適当な型名をつけている)にして、割り算が含まれる計算をなくす。

おおむね書きあがってから問題を解いてみると、しょっぱなから直線の交点を求める計算が必要になってまったく役に立たなかった。残念。せっかく書いたので残しておくが、一切verifyしていないので不安がいっぱいだ。問題自体は、通常の幾何ライブラリで通すことができた。幾何の問題の難易度はよくわからない。円の半径を二分探索するか、直線の極端なケースだけ考えることで通る点の候補を絞るか、この2つの解法のどちらかしか使ったことがない気がする。

AOJ-ICPCで新しく埋めた問題のうち、AtCoderにも収録されているものを探してコピペして提出する作業をした。AC数が7問増えて2777になった。キリが良いように見える。いくつか単純なアルゴリズムの問題があったので、コードゴルフしておいた。

atcoder.jp

最初は124Bで、そこから二分累乗法を普通の累乗にすると115Bになった。さらに別の箇所の計算量を定数倍悪くして105Bのコードを作ったら、150msくらいTLをオーバーした。そこで元に戻すのではなく、二分累乗法に戻してみたら、TLに間に合う111Bになった。

atcoder.jp

昨日解いた「夕食」だ。昨日の解法ではまず毎日自炊する状態の幸福度を計算してから、徐々に食堂に行く日数を増やしていったが、もともとの最短コードを読んでみると、逆になっていた。一旦は昨日の解法で縮めておいて、105Bになったが、もともとの最短コードの解法を使うと88Bまで縮んでびっくり。確かに式の形がシンプルである。

仕送りで来たパスタソースを使ったが、シーズニングタイプのもので、パスタに絡める際にサラダ油か何かが必要なようだった。パッケージを開けてから気づいたが、家には油の類は何一つない。やむなくパスタのゆで汁を用いたが、まあ問題はなかった。

布団に入ってからうっかりなろうを読んでしまい、午後1時就寝。明日起きる気ある?

02/26(金)

午後4時半起床。執念でベッドから身を起こす。今日はホスフィン・たいぺーと3人で今セメスターのお疲れ様会をする。

集合は午後5時45分で、集合場所までは地下鉄で行くことを考えると、30分前には家を出たい。お金も下ろしておく必要があるだろう。準備もそこそこに家を飛び出したところ、午後5時半くらいに集合場所についてしまったが、どうもホスフィンが微妙に遅れているらしいので、近くのゲーセンでチュウニズムを2クレプレイした。

無事合流して、ホスフィンが予約したお好み焼きの店に行く。

午後8時半くらいに出て、少しゲーセンによってマッチングしたあと、先週の金曜日にも行ったバーに再度入店した。

そのあとバーに移動して飲んだ。

週記(2021/02/15-2021/02/21) - kotatsugameの日記

前回はコラボメニューに執着するあまりお酒の好き嫌いを考えなかったが、そもそも僕は苦みのあるお酒らしいお酒が好きではない。この反省を生かし、今日は甘いお酒ばかりを延々頼み続けた。相変わらず腹は下した。今日の注文も以下のリプライツリーにまとめてある。

3人でずっとソートなぞなぞを出題し合って、午後9時から午前3時まで6時間くらい滞在した。見て瞬時にわからないならすぐ出題者にどういったジャンルの言葉か尋ねたりしていたため、どちらかというとなぞなぞに近くなったような問題もあったと記憶している。記録が一切残っていないため、ほとんどの問題は忘れてしまったが、少しだけ覚えている問題を書き記しておこう。

  • えきこさつぬのばろ*1
  • おたちのまやろ*2
  • あぃてでふろー*3
  • かくたっでねのるろー*4
  • ぐせとどまらるん*5
  • おたどはるん*6
  • いいいかかざせっめん*7
  • いいじすせはひゅりんん*8(これはめちゃくちゃ不評だった)
  • おかしたのは*9
  • いきけばん*10

Character Sorter

どういう語をソートすると面白く感じられるのかがよくわからないまま終わった。店を出て深夜の街を歩く。飲み屋街はまだ人がたくさんいた。なか卯でそばを食べ、ドンキに寄って買い物をし、帰宅。しばらく下した腹をなだめすかしながらハーメルンを読み、午前7時就寝。

02/27(土)

中途覚醒を挟みつつ、午後8時起床。あんまり疲れが取れた気はしないが、コンテストがあるので起きなければならない。食事として、昨日ドンキで買ってきたサラダチキンを食べた。あまり好きな味ではないようだ。

ABC193に出る。65分全完、42位。Dに信じられないくらい時間をかけたのと、Fが普通にわからなかった。

Aはよい。解いてからしばらく留まって考え、4分半でdcの10Bコードを作った。11Bのコードは1分半の時点で提出されていたらしいので、速度的には負けていたが、運よく短縮に成功した感じ。B、Cもよい。Dは難しい。真っ先に#を全通り試すコードを書いたはいいものの、最後のサンプルが合わない。これは手札の点数の計算ミス(c_i=0のとき点数に寄与しないとしていた)によるものだが、気づかず、確率計算を間違えているのだと思って必死に考えていた。カードの数字に重複があったりして、適当に確率を考えるとヤバそうな雰囲気が出ているが、実際は全然そんなことはないらしい。結局20分かけた。

Eは見た瞬間atcoder::crtを使う解法を思いつけたが、どうして思いつけたのかの言語化が不可能。Fは見た瞬間フローっぽさを感じてグラフを考え始めたが、どうにも条件が表現できそうにない。ここで市松模様に反転すると便利そうだと気づいたが、そのあと謎の貪欲を考え始めてしまった。しばらくしてようやくフローに戻ってきて再度グラフを考えると、今度は条件が表現できたので、実装してAC。

コードゴルフをする。Aはコンテスト中のものでよさそう。Bはいくつか言語を試したが、AWKの35Bがシンプルかつ強力だった。CもAWKの勝ち。Dはコードゴルフする気がない。E、FはACLを使うのがよさそうで、C++で適当に縮めておく。Eはclimpetさんとバトルして負けてしまった。熨斗袋さんのツイートでYQ通りではなくY+Q-1通りしか考えなくてよいことを知り、これを適用してループを減らしたりもしたが、さらに更新されてしまった。unsigned longを使う発想が非常に美しい。

atcoder.jp

ICPCのチーム紹介ドキュメントは締め切りが28日である。夜中の2時から朝の9時までずっとそれの作成をしていた。昨年は締め切りをほとんど故意に放棄した結果白紙のページになってしまったが、今年もそうなりかけていた。どのようなものを作ったかは、印刷したものが配布されてからのお楽しみである。完成したものをメールで送る前に、チームのSlackに貼って確認してもらう。さらにチーム紹介ドキュメントに関係してブログ記事を1つ作成しておいた。これの公開も、印刷したものが配布されてからである。

2021/03/09追記:公開した。

kotatsugame.hatenablog.com

午後0時半就寝。

02/28(日)

午後9時起床。急いで弁当を温め、食事してyukicoderとCGRに備える。

yukicoderは2完。Aでつまらないペナを生やした。Bはよくわからないが適当に二分探索したら3700msで通ってFAだった。円周上を動く点に、ある特定の位置からスタートして一定の速度Wで動く点が追いつけるのは最短で何秒か?という問題は、一般の場合は簡単には解けないだろうが、Bの制約下においては円周上を動く速度よりWのほうが大きいことから二分探索で解ける。このことはコンテスト後に改めて考えたのであって、コンテスト中は微妙な怪しさを感じていた。Cは頑張ったがわからなかった。数え上げが苦手であることがいよいよ明らかになってきた。

CGR13に出る。ABCDE5完。レートは2633→2658(+25)。

Aはよい。Bは上下の障害物の座標の差を見ればよい。Cは前からやっていいことが直感的に正しく感じられる。ぐっとこらえてしばらく考えたが、どうにもよさそうなので、そのまま実装に入った。実装も、ただシミュレートして間に合うような制約ではあるが、累積和を使う線形時間の実装を思いついたので、そちらに切り替えた。Dは下の桁から貪欲して1WA。下から見た場合はほんの少しだけ自由度があるようだ。上の桁から見るようにしたが、下の桁から見ていた時の文脈を引きずってしまい、サンプルを合わせるのに手間取った。結局、一度すべて忘れて再度問題を捉えなおしたところ、うまくシンプルな問題への言い換えが得られてAC。

Eは全然わからなかったが、雰囲気で書いたコードが通った。部分木の根を飛び越えて葉の方と組み合わせるのがまずいので、順番を保ったままvectorF_kを保持するようにした。ある頂点を見ているときは、その子らのvectorを全部マージして、さらに先頭に親の1頂点を表すF_0=1を付け加える。先頭の2つが足せる限り足して、これを今見ている頂点に関係するvectorとする。同じF_kが2つ連続するまではよい(F_{k-1}が来ると順に足して両方消せる)が、3つ以上連続したり、さらにはsortedな状態が崩れたりした瞬間、できないことが確定する。できないことが確定していない場合は、条件からvectorの長さはそれほど長くならない。

Fは「1つと残り全部」をn回聞くことを考えたが、これはNSの個数の差が1のとき上手くいかない。そこで、先頭から順にii+1..nを聞くことにした。これで非ゼロなiが検出でき、それを用いてi+1..nから-でないものを探せる。nがどうであるかは、これまで見つかった結果とii+1..nを聞いたときの値から復元できるので、これにかかるクエリ数はn-1NSの個数の差が1以下のとき、0..i-1にまだ1個-でないものが残っている可能性があるが、これは二分探索で見つかる。0..i-1-でないものが残っているかどうかを判定するため、さらに1回聞く必要があって、合計でだいたいn-1+1+\lceil\log_2 (n-2)\rceilであるようだ。微妙に回数をオーバーしているのに気付かず投げてしまい、pretestで落ちた。修正できずにコンテスト終了。

問題は、-でないものが残っているかを1回使って判定しなければならないことにある。1..i-1iを聞くことにすれば、非ゼロなiを検出したとき、1..i-1には必ず1つ-でないものがある。これで判定の必要がなくなり、n-1+\lceil\log_2 (n-2)\rceilでACできる。

ラノベを1冊読んだ。「魔王2099」というもの。非常に面白かった。昨今は「長い眠りから目覚めると魔法が退化しており、古代の技術で無双する」系の話が多い中、この作品では眠っている間に高度に発展した社会に翻弄される魔王が描かれる。正直無双を期待して手に取ったので少しストレスがかかったものの、くじけず頑張る魔王のキャラクターが心地よかった。恵まれた容姿を武器に顔出し配信者として活躍するのも面白い。それでいて舞台は練りこまれたSF社会で、物の名前や慣用句まで世界観に合わせて変更する手の込みよう。

昨日のBが縮められていた。AWKで抜き出してsortでソートしてdcで出力・エラー処理をするbashコード。うーん、なるほど。

atcoder.jp

*1:ころばぬさきのつえ(転ばぬ先の杖)

*2:やまたのおろち(八岐大蛇)

*3:あふろでぃーて(アフロディーテ

*4:くろねっかーのでるた(クロネッカーのデルタ)

*5:せんとらるどぐま(セントラルドグマ

*6:はんどたおる(ハンドタオル)

*7:かいめんかっせいざい(界面活性剤)

*8:じゅんすいりせいひはん(純粋理性批判

*9:はかたのしお(伯方の塩

*10:けんばいき(券売機)

週記(2021/02/15-2021/02/21)

02/15(月)

昨日は布団に入ってハーメルンを読んでいたら一瞬で寝落ちしてしまった。午前10時くらいだった。

午後6時、起床。成績を確認してみると、線形代数学Bの単位が出ていた。

現在、幾何学序論Aと代数学概論Cの単位が来ている。先週のツイートと照らし合わせて、残り線形代数学Bの単位が来れば4年生になれるようだ。

週記(2021/02/01-2021/02/07) - kotatsugameの日記

なれた。4年生である。1年次の惨状からよくぞここまで回復できたものだと思う。数学科は単位を集めるだけならかなり楽。正直、コロナウイルスの感染拡大によって講義がすべてオンラインになったことは単位取得にかなり良い効果があったので、その点は(こういうことを言ってはダメなのだろうが)良かった。

ABC191のC問題とE問題の解説スライドを準備して、サークル解説会に臨む。C問題はbitsetを使って頂点を数える解法を紹介した。これは、今朝方格闘していたyukicoderの問題における高速化の1つのアイディアであった。

2021/02/15 定例会 | puzzleknot 公式サイト

Div.3の問題を埋めながらECR104を待ち、出た。まだhackフェーズが終わっていないが、現在A-Fの6完である。

Aはちょっとびっくりしたものの、よい。Bもちょっと面倒に見えたが、実験すると周期的に邪魔されることがわかる。B問題で実験を要求されるのはやっぱり面倒である。Cは難しいが、トーナメント表を書いて埋めてみたらわかった。勝ち負けの矢印でループを作る、という考えは邪魔なだけであった。Dはやるだけ。Eは面倒なだけ。Fは難しくて、上で消しきれなかった数などを持つ桁DPを書いて、その消しきれなかった数の最大値を適当に大きくしたら通った。最初は-100..100で出したが、これは63ケース目で落ちた。テストがしっかりしていてうれしい!しばらく悩んで、-300..300で出しなおしたら通った。実行時間はかなり長め。

Gは後ろ2つ持つDPだと思ったが、もう少し条件が必要らしい。a__a__aみたいなのだけ考えて、常に個数が足りるじゃん!と思っていたが、これは大きな間違いで、aa__aa__aaみたいな置き方をするとまずい。個数をオーバーしうるアルファベットは高々2文字なのを利用して、包除原理で解くらしい。upsolveしていないしあんまりする気もない。

2/11のぶんの日記で6000ACに到達したことを書いたが、そのあとひたすらDiv.3をなぎ倒していたら4日で142問解いていたらしい。Div.3は残り19コンテスト、125問だ。

午前10時就寝。

02/16(火)

午後7時起床。浄水場で問題があったとかで、仙台市が断水するかもしれないという情報が流れてきてビビるが、特に何も対策しなかった。

SRM800で得たTシャツの配送先を伝えるGoogle formがメールで送られてきていたので、回答した。前にも同じ形式のformを記入したが、その時も今回も72時間しか開いておらず、しかもそのことはメールの文面には書かれていない。罠。

サークルのバチャに臨む。CF #534。遅い2完で冷えた。Aはギャグ。Bはしばらく考えてもわからなかったのでCに進んだが、そちらもわからず、順位表を見ると200人くらいに通されていて、慌てて再度考えたところ、解けた。しかし時すでに遅し。そのあとCに戻ってまた考えていたが、結局解けなかった。Bは、まずaの倍数を見つけ、次にそこからいらない素因数を落としていくという方法で解いた。aの倍数を見つけるのは、つまりmod a0になる数を見つけるということで、二分探索でできる。区間の中央と右端でmod aの値を比較しなければならないが、これは実はクエリの形式そのままである。いらない素因数を落とすのには、毎回0と比較するクエリを聞けばよい。

Cは、適当にパスをたくさん作って、どれかがn/k以上の長さであればそれを出力、なければパスがk本以上できるので、それからサイクルを作る、という方針で考えていた。結局頂点の次数が3以上であるという制約がどこに効いてくるのかもよくわからずじまい。

その後、CF Div.3に出た。Fまではそこそこ速かったが、Gでいらないセグ木を持ち出した挙句モノイドの積を間違えていて失速。しかし周りが結構WAを出している中ノーペナ全完ということで、まだopen hacking phaseだが現在3位。open hacking phaseといえば、昨日のECR104は全部通って最初と変わらず19位だった。

問題については特に何も思わなかった。朝方Div.3を埋めていたところ、G問題のクエリなし版を見つけた。Gで二分探索していたところを線形探索してもよいようだ。

https://codeforces.com/contest/1141/problem/E

ラノベを1冊読んだ。「暇人、魔王の姿で異世界へ」12巻。シリーズ完結である。文章中に微妙にネトゲのネタ・用語がちりばめられているようで、微妙にわかりにくさを感じる。あと、「らん豚」のネタもずっと出てきて、僕にはなじみのないものなので(世界観などと比較して)かなり違和感があった。ストーリーは面白いと思う。主人公が最強で楽しい。

日付が変わってからTechFULが始まっていたらしいので、参加する。今回のテーマは「動的計画法」。これは2/17から2/21まで、ということで、この日記が公開される頃にはイベントが終了しているため、ここに解法を書いてもよさそうだ。今回からコード提出履歴が簡単にみられるようになっている。

まず結果から言うと、9問目で少し時間を使ったほか1WAしてしまって-19ptしたが、それ以外は理論値で通せて839ptだった。8問目まではどれも典型問題だが、9、10問目は少し手ごたえがあった気もする。

9問目は、どちらがどれだけ連勝しているかを持つDPになる。ただしまだ足りなくて、それぞれが持つ残高を表現する方法を考える必要がある。これは金銭の移動に関して考察すればよい。勝ったほうは、そのターンに受け取った金額を次の試合でそのまま出すので、結局受け取らないとしても問題はない。負けたほうはさらにお金を支払う必要がある。結局、最初に2人とも1円払い、そのあとは前回負けた人だけが2^t円払っていく感じになる。ここで2進数の桁DPっぽく繰り下がりするかどうかもDPのキーに持てば更新ができる。所持金が足りているかチェックするときのシフト幅を間違えて1WA。

10問目は一瞬で耳DPが見えたので成長を感じた。セグメント木を21本生やそうとして、配列を用意してからそこにコンストラクタを使って作ったセグメント木を代入しようとしたが、自前のセグメント木には代入演算子がないらしく、CE。vectorの初期値のところに書いたら上手くいったが、謎である。

こどふぉのプロフィールページ下部にHeatmapが生えていた。ここ1月で250問くらい解いているらしい。これは昨年の5か月ぶんにもなる。

今日起きた時に流れてきた断水だが、無事回避されたらしい。

市内の断水は回避されました|仙台市

午前11時就寝。

02/17(水)

午後7時半起床。実家から調理済みの野菜のタッパー詰めを含む仕送りが届いていたのでありがたく食べる。これは5個ぶんあったので、順当にいけば5回ぶんの食事に付属することになる。

ところで、野菜を食べるというのは言われ続けた結果意識しており、たまにサラダを買ったりしているが、では肉類はどうやって摂取すればよいのだろう。実は普段食べているものに含まれているので大丈夫である説、たまの外食で食べるラーメンに乗っているチャーシューで十分である説、食べなくても健康に問題ない説。

サークルバチャまで少しだけ時間があるので、また大学生協で本を注文しておく。前回注文してから新たに発売された新刊と、前回は在庫切れで注文できなかったが今見ると復活していた分、計4冊。これは再版がかかったということなのだろう。発売前から目をつけていたが、実際初動が良いらしいのを見ると、何となく取られた気になる。売れるのはいいができることなら僕が初版を手に入れてからにしてほしかった。いやラノベ初版に価値が出ることはそうそうないだろうが。

新刊チェックをしていたら、新妹魔王の契約者13巻が4月に刊行を予定されているのを見つけた。確か11巻がシリーズ本編完結で、もう1冊短編集出ます……とされていながら実際はエピローグが長くなりすぎ、およそ2年前に出た12巻のあとがきで短編集として13巻が出ることが書かれていたが、そのあとは音沙汰なしだった。シリーズ初期から過激なことで名をはせたが、11巻以降はもう完全に官能小説である。

サークルバチャ。時間ギリギリに3完して何とか面目は保たれたか。

Aはよい。こういうのはICPCとかで見たことがあって、合流地点を決め打って3か所それぞれ独立に考えればよい。聞いてみると3点の中央値で合流地点が決め打てるらしい。Bはギャグ。順位表を見ると上位が爆速で通している。考えてみれば、葉に接続されていない辺に重みを割り当てるよりは、それを葉のほうに分けて寄せるほうが直感的に得。n=2のコーナーには気づいていたが、たぶん大丈夫だろうと試さずに投げたら落ちた。

CはずっとWAだった。abのどちらかと初めて違う文字が出現するインデックスは決まっていて、そこでaに寄せるかbに寄せるか(あるいはその間の文字が存在するか)を決め打って2回探索すればよい、と思ったがWA。それまではaより大きいかとbより小さいかのフラグの片方しか持っていなかったが、両方持つようにしたら通った。コンテスト後にしばらく睨んで解決した。

ラノベを読んだ。「シェアハウスで再会した元カノが迫ってくる」。作品リストを見て気づいたが、「お隣さんと始める節約生活」と同じ作者さんだった。なんでかわからないけど読みづらいと感じてしまう。ちょっと言語化しようと考えてみたが、セリフが淡白に感じられるのかもしれない。笑っていても怒っていても、すぐ真顔に戻って別のことを話し始めるような。主人公は出会いを求めてシェアハウスに入居したらしい。この行動原理は理解不能

サークルバチャのDを通した。バチャ中はCに時間を吸われて残り5分しかなかったが、方針は思い浮かび、あとは詰めるだけだと思っていた。実際は方針から間違いだったが、それを書く過程で得られた条件をもうちょっと整理したら解けた。それぞれの手の左・右から見た最初の出現位置を求めて、2番目に現れるものと3番目に現れるものの間の特定の手が勝てない。これは、手が3種類ある場合は左から見た場合と右から見た場合で重複しないので、それぞれ求めることができる。2種類以下の場合は明らか。

今期の講義の感想を書いてツイートした。

Div.3をどんどん埋めていく。途中少しずつ本を読みながら、午後6時くらいまでやっていた。

https://codeforces.com/contest/1006/submission/107759003

眠い中解いた問題。半分全列挙をする。縦NMの盤面を分けるのに、横に真っ二つにすることを選んだが、上のほうの計算結果を持つとMLEした。仕方なく縦にも真っ二つにして、この時左上の部分と右下の部分はそれぞれ持つべきデータ量が少ないため、残り左下と右上を順に計算していって頑張った。3secギリギリになった。解法を読むと、N+Mを半分にすればよかったらしい。これは確か前にも見たことがあるはずで、その時も素晴らしいアイディアだと思っていたのだが、今回も自力ではたどり着けなくてガッカリ。実際に実装してみるとコードも単純になってかなり厳しい気分になった。

午後6時半就寝。

02/18(木)

消えた。

02/19(金)

午前3時くらいに起床。二度寝できずハーメルンを読んだりしていた。

syosetu.org

夏ぐらいに読んで追いついていたのだが、その時点では2年前にエタっていたと判断できる状況だった。その後作者さんのツイッターアカウントができたりして更新されたが、放置していた。今更読了。実は完結していたらしい。ガヴリールドロップアウトは(実は)知らないが、バカテスの雰囲気はいい感じだと思う。

起きて競プロをする。Div.3のF問題で昨日解けずに飛ばしてしまったものを解いたり、JOI本選の問題が公開されていたのを解いたりした。JOI本選はDまで解けた。Aは典型的(僕が出場した第16回JOI本選のA問題も階差をとる問題だった)。Bはあんまり見ない面白い問題な気がする。Cはdpの更新を素早くやるのに結構頭を使った。僕はBITを持ち出したが、解説ではそれなしでO(N^2)で解いていてすごいなあという気持ち。Dはヤバ解法が思いついて、解けることは解けるが……と嫌がりつつ実装してみたらそれが想定解だった。Eは難しいとの前評判を聞いて読んでいない。

前日から読み進めていた本を読み切る。「数学者の夏」。非常に面白かった。数学が得意であると周りから言われ、また自分でもそうであると自負している高校生が、夏、一人で集中するためにホームステイに訪れた山奥の村で事件に巻き込まれる話。序盤の主人公像は、「一つのことに没頭する者」としてかくありたいといった感じの描かれ方をしていて、例えば数学以外のことに興味を持たないようにしていたりなど、ストイックさを前面に押し出している。ところが近頃どうにも数学に行き詰まりを感じていて、序盤は自分の取り組みにうまく集中できないまま村の周りの違和を感じ取っていく。中盤、自分の取り組みを半ば投げ出して調査に乗り出した主人公は、思いがけず自分より数学的センス・知識に優れた人物と出会う。そこから一気に自分の取り組み・村の違和感双方について展望が開けるも、違和感のほうはうまく処置できないうちに事件に膨れ上がりそうになって、それをなんとか収めたことでハッピーエンド。事件の調査・解決を通して、以前は孤独に数学と向き合っていた主人公が、次第に他者との関わりに目を向けるようになる。いわゆる『人間的成長』だろう。

学食に行って食事し、注文していた本を受け取る。水曜日に注文したうち3冊と、前回13冊注文した時に到着日がずれて受け取れなかった2冊。

地下鉄に乗って仙台駅前まで行く。まずトムとジェリー展を見た。前半はトムとジェリーに関する展示で面白かったが、後半は作者コンビの別作品の紹介がメインで、僕みたいなトムとジェリーしか知らない人には少々退屈だった。順路に沿って進んでいく形式で、序盤は前後が詰まっているのでそれほどじっくり見てもいられない。後ろの人に頼んで写真を撮ってもらったが、(スタンプで隠れているものの)実は思いっきり目をつぶっている。せっかく来たのに展示の印象があんまりなくて、名残惜しさからかうっかり物販で1500円の達磨を2個買ってしまった。

そのあとちょっとラノベを買ってゲーセン。新曲を埋めた後少し13+を頑張ったが、鳥寸で終わってしまった。どうにも今日は眠いらしい。水木で無理やり生活リズムを直そうとした影響が抜けきっていない。こういう日はあんまり真剣にやらないのが吉。とはいえ、しっかり5時間くらいプレイしていたようだ。

ホスフィンと一緒に一蘭に行ったが、かなり並んでいたので、別のつけ麺屋に移動。こちらも並んでいたが、入店を決めた。写真を撮ってからすぐ食べ始めたが、そのまま投稿を忘れていたらしい。この日記を書いているときに気づいて投稿しておいた。

そのあとバーに移動して飲んだ。「夜は短し歩けよ乙女」の劇中のバーのモデルになったらしく、コラボメニューが用意されている。入ったときは満員で感染リスクを考え非常に恐怖したが、結構すぐ大きなテーブルが1つ空いて、まあまあ余裕のある配置に収まった。1杯200円均一なので安心してガバガバ頼んでいたが、それはどうにもバーとは言えない飲み方であったように思われる。2人で席料450x2を含めて5000円(税抜)くらいと、ちゃんとアルコールを飲んだ感じの支払いだった。僕はコラボメニューだけ頼み続けて制覇1歩手前であった(1杯ホスフィンに飲んでもらってしまった)。以下のリプライツリーにまとめてある。

途中腹を下してつらかった。帰り、閉店ギリギリのゲーセンに駆け込んでチュウニズムを1クレだけプレイし、ドンキに寄って帰宅した。布団に倒れこむともうほかには何もできず、即座に就寝した。午前2時であった。

02/20(土)

午後1時くらいに起床。まだ眠気はあるが、なんとなくハーメルンを読みだしてしまった。2日酔いの頭痛などはなさそうだ。昨夜も、ただただ疲れていただけで泥酔している感じではなかったように思う。

午後3時くらい、いよいよ眠いが、ここから3時間は生協の弁当配達を受け取るために起きている必要がある。結局午後5時に到着して、それからも眠るタイミングがつかめず、ずっとハーメルンを読んでいた。午後8時半になって食事し、シャワーを浴びてABC192に出た。直前に昨日買ってきたトムとジェリーの達磨を出しておいた。

全完42位。ABでそれぞれペナを生やしてしまった。かなりの人がペナを出していたようで、僕がサンプルを試す手間を取っていれば順位表の1ページ目に入れたみたいだ。

Aはパターンマッチングをすると(100-X%100)%100になるが、実際は100-X%100であった。Bはsedだが、文字列の全体とマッチさせるのを忘れていた。Cは適当にRubyで書いておく。Dはオーバーフローが怖くなった結果Rubyに逃げた。Eはdijkstraで、Fは適当にDPする。

コードゴルフをする。Aは明らかにdc。Bは大文字・小文字の文字集合がそれぞれ\u\lで書けるVimに軍配が上がった。CはPerl。これは後にclimpetさんの更新を受けてさらに縮んだ。DはRubybsearchをする。EFは手つかず。

E問題のdijkstraについてTLに質問が流れてきたので、答えていた。continueしていないことによるバグだったので、その危険性を自分なりに説明してみた。同時に、月曜日にアップロードしたサークル解説会におけるABC191Eの解説の誤りに気付いたので訂正しておいた。continueしないと、ある頂点に辺が集中している場合計算量がO(M^2)になりうる。

TechFULの順位表を確認したら、LayCurseさんが838点で1点差に迫られており非常にびっくりした。

ラノベを1冊読む。「ホラー女優が天才子役に転生しました」2巻。非常に良かった。半年くらい前になろうで追いついた(そのあと放置中だが)ばっかりなので、先の展開を思い返しつつ読んでいくのもまた一興。放置中と書いたが、確認したところ十話も溜まっていなかったので、再度追いついておいた。

もう1冊読んだ。「義妹生活」。キャラクターの行動が論理的であることを重要視しているらしく、いちいち入る理由の説明に微妙にうんざりしてしまう。現時点では特に恋仲になるわけでもなさそうだったが、終盤(僕から見て)唐突にお色気シーンが挟まってびっくりした。

そのあと少しハーメルンを読もうとしたところ、即座に寝落ちした。午前11時半くらいだったらしい。

02/21(日)

目を覚ましたら午後8時だった。目覚ましも特にかけていなかったので、ARCを寝過ごした可能性があるかと思うとゾッとする。ただ、まだ非常に眠いので、30分後まで目覚ましをかけてもう一度目を閉じる。

寝たのか寝ていないのかわからないが、ともかく30分経過したので布団から脱出。弁当をレンジでチンしたところ、できたのが50分過ぎで、そこから全部食べ切る前にコンテストの時間になってしまった。途中で放置し、ふたを被せておいてパソコンの前に戻った。

ARC113は速めのABCDで59位、パフォーマンス2764でレートは2710→2716(+6)。一応highestだ。今回みたいな崖回で詰まらず速解きできたのはよかった。

A問題はABを全探索してもよい。B問題は丁寧に周期を取ってmodpow。C問題は、ちゃんとした証明は難しそうだが直感的には明らかで、粗い証明もすぐ付けられる。つまり、操作できる箇所のうち最も右で操作して損しないことが自分で頷ければよい。D問題はまずmax A≦min Bで、実はこれさえ満たせば全部作れることに気づければよい。N=1またはM=1の場合は別に処理する。ここまでノーペナ21分だった。

Eは、まず気合で場合分けしようとして失敗し、考察の残骸からある程度全探索する方針を探した。b*a*b*の形にできることが分かった。ここからさらにbでflipしたりするかもしれないが、それは場合分けすればよくて、問題はどのようにしてこの形に持っていくかである。先頭と末尾からbを取り除いておくと(この段階で全部取り除かれた場合はそのまま出力する)、残りの文字列はa+(b+a+)*になる。で、このaのブロックのうちどこを中心にして集めるか全探索すればよさそう。babみたいな感じでaが1つだけしかない場合は、それを2つ合わせることで消せるので、ランレングス圧縮して累積和をaa1個だけ、bの3本持てばよい。実装して提出すると3ケースWAが出て、それを修正できないまま終わった。

コンテスト後にストレステストを作って試してみると、"abaaababbb"で落ちているのを見つけた。これは真ん中のaaaに寄せるときに左右にそれぞれa1個だけの部分ができる。ここの2つを組み合わせて消すと、(この文字列では問題ないが、一般の文字列については)その間がflipされて先頭と末尾のbの個数が変わるから、困るなあ……と思っていたが、気にせず出したら通ってしまった。謎だけど、10文字以下の文字列では先に挙げたものでしか落ちなかったことを考えると、このようなケースが問題になるときは必ずbでflipして連結になるから、先頭と末尾それぞれの個数というのは関係ないのかもしれない。

途中考察に詰まったら弁当の残りを食べようと思っていたがそのような機会は終ぞ訪れず、終わってから見たらご飯がカチカチになってしまっていた。

コードゴルフについて。AはAWKが短いらしい。2重ループがあってdcは長め。実は別の方針があるのではないかと思っている。Bはdcの8Byteを見てびっくり。結局4の倍数mであって、全てのテストケースでB^C mod mが0にならないものが存在すれば、わざわざ0の場合を補正しなくても通る。適当に2桁で書ける数を大きいほうから試していたら、F6(つまり156)で通った。7Byte。CはPerl、DはRuby。これらはあんまり頑張っていない。

日付が変わって、TechFULの結果が確定。結局839ptで1位のままゴールイン。

CF Div.3を進める。ラストスパート、4コンテストくらい残っていたのをなぎ倒して、現在の54コンテスト・365問をすべて埋め終わった。次は……そろそろICPCなのでAOJ-ICPCにでも戻ろうか。

ラノベを1冊読んだ。「裏社会最強の男、終末異世界を愉しむ。」。句点まで題名の一部である。実は自分はデスゲーム物が苦手らしい、ということに気づいた。主人公が強いのはいいですね。主人公がヒロインの護衛を勤めている等で自由を制限される設定は少しモヤっとしてしまう。自由でのびのび無双してほしい。バトル終盤、お約束のようにヒロインが狙われてかなり辛かった。

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

02/08(月)

先週の週記を投稿してから、また橙diffを少しやっていた。CFのレート更新が来て、predictorの通り-42であった。布団に入ってからなろうを少し読んで、午前8時就寝。

午後4時起床。幾何学概論Bの教員から「レポートを提出した学生は全員合格しています」というコメントが出ていた。ちょっと喜んだものの、このレポートが何を指しているか明確でないため予断は許されない。講義の途中で挟まれる問題に回答するレポートを指していた場合、半分しか出していない僕はまずいかもしれない。

DDCC2021の予選申し込みが始まっていた。今年はAtCoderから完全に独立してやるらしい。この状況下で30人規模のオンサイトを予定してもいるようだ。ただ、本選が装置実装部門のみになって、コード部門は行われないらしいので、残念。とりあえず申し込みをしておいた。

www.discoverychannel.jp

通販で買い物をする。まずAmazonで500mlペットボトルのお茶24本のケースを買う。注文履歴によれば、1/13にも同じものを注文している。日記には該当する記述がなかった。1月も持たずになくなってしまったので、再度購入した。

次に大学生協のサイトでラノベを探す。最近本屋に全然行けていないので、買っていない新刊がかなりある。リストにまとめてあるので、それを見ながら在庫にあるものをドンドン注文していく。最後に、最近Twitterで流れてきた「数学者の夏」を加えて注文を確定させた。

bookclub.kodansha.co.jp

合計1万円ちょっとで、大学生協で受け取る時に割引が効く。金額だけ見れば常に生協経由で買ったほうが安上がりだが、やはりリアルの本屋で手に取って確認する体験は捨てがたい。

サークル解説会の準備をする。スライドを作成している途中、キーボードが変な感じになった。最近頻発しているので、どういう挙動をするのか動画に撮っておく。今回は半角・全角の切り替えもうまくいっていないことに気づいて、それを直そうと奮闘していたら一緒に直った。

サークル解説会はつつがなく終了。来週もやるが、そろそろ春休み期間なので、どうするか決めなければならない。

また橙diffを進める。計算機の進化によって、ナイーブにやっても間に合うようになってしまった問題があったので、適当にゴルフしておいた。

atcoder.jp

dp配列の初期化は、最初memsetでやっていたが、testestestさんによって「ローカル変数にして宣言と同時に初期化するのを繰り返す」方法が提案された。5000回も3e5要素の配列を宣言するのは脳筋。それで間に合ってしまうのだから面白い。冷静になれば、もともと5000回3e5イテレーションのループを回していたのだから、最悪ケースではほとんど影響がないのか。

1e9+7の埋め込みにも新手が出た。順に59,154,202,7という文字コードの4文字をシングルクォートでくくると、整数型の1e9+7になる。以前は何かint型の変数に代入してから使っており、%=a=1e9+7でmod部分に7Bかかっていたのが、今はシングルクォート含め6B。これを適用して別の問題を2問ほど縮めておいた。

午前3時くらいに眠くなって布団に入る。午前5時くらいまでなろうを読んでいたが、眠気がすごいことになってきたので、就寝ツイートをして寝た。洗濯物を干さなければならなかったのだが、諦めてしまった。

02/09(火)

午後2時くらいに目を覚まし、なろうを読む。再度の眠気が来なさそうなので、午後3時半くらいに起床報告しておいた。さらになろうを読み進め、一作読了。

https://ncode.syosetu.com/n6204l/

これも東方古代スタート。なんと言ったらいいのかわからないが、印象としては江戸時代の町人が使ってそうな感じの言葉遣いをしようとして変なことになった文章で書かれていて微妙に気になる。が、ストーリーは非常に良かった。第一章では幻想入りする前、原作キャラとの絡みを描いて、第二章でいざ幻想入りして久しぶりの再会を描く、その途中でエタっている。

布団から出て、また橙diffを進める。布団に入っている間に解けたはずの問題の実装をするが、全然合わない。ある程度ナイーブにやって解法が正しいか確認しようと提出してみたが、ほとんどのケースでTLEして使い物にならなかった。ここで、ランダムケースを生成してテストすることにした。ランダムケースのジェネレータと全探索のジャッジ解を用意して、ojでケース生成・アウトプット生成・一斉テストをやる。改めてかなり便利であると感じた。実際WAのケースも見つかって、変数の意味に関するミスだったことが発覚。無事ACできた。

別の問題を解き始めて、数回のWAの後にようやく最後のコーナーケースを見つけたあたりでサークルバチャが始まったので、いったん避けておいてバチャのほうに参加する。

今日はCF #559 dvi.1。4完してかなりいい感じ。Aはサンプルの意味が分からなかったので合わないまま提出したところ、当然のようにWAだった。ただサンプル1で落ちたのでペナルティにはならなかった。冷静になると、minが「ちょうど」ある値でなければならないので、全部ひとりでつじつまを合わせようとすると「ちょうど」ではなくなってしまう。これがサンプル1。Bはいったん飛ばしたが、Cを解いてから戻ってきて実験したらすんなり解けた。k=1がコーナー。

Cは、大小関係に関する条件に直してトポロジカルソートすればよい。たくさん辺を張る必要がありそうだが、だいたい同じ形の辺の張り方をしているので、前に張ったやつを再利用すればよい。Dは面白かった。残っている点のうち一番極端なやつ(右に振り切っているか左に振り切っているか)のどちらかをLRに応じて選べばよい。そうすると、次にどの点を選んでも条件が満たせるので、そこで再度一番極端なやつを取る。この「次にどの点を選んでも条件が満たせる」状態を維持して点を減らしていけるので、必ず構成可能。偏角ソートの必要がありそうだが、点は必ず2直角の間に収まってくれるので、外積の符号で判断できる。

Cまで解いてからしばらく、さっきまでやっていた橙diffに戻って通していた。Dは正直解けるとは思っていなかったが、やってみたら解けてうれしい。バチャ中に諦めるという行為はバチャを無意味なものに貶めているので、気を付けたい。

yukicoderで3問ばかり通してsolvedランキングの3位に浮上しておいた。

もうそろそろRating Historyで確認できるsolvedが6000問になりそう。

布団に入って、ハーメルンを読もうとしたが止めてすぐ寝た。午前6時半だった。

02/10(水)

午後2時、起きる。二度寝しようと思ったが、生協に注文した本が届いたらしいので、起きて向かうことにする。閉店は午後3時。学食はすでに閉まっており、また購買のパン類も全滅しているだろうし、どこで食べ物を得るか迷う。今日はAmazonからの荷物も届くらしいので、家にいなきゃならないよなあ……と考えていたが、午前中の間に宅配ボックスに届いていたことを知ったので、家にいなくてもよくなった。ということで、食事は街に出て行うことにした。とりあえず生協で本を受け取る。

13冊注文したはずが11冊しかなくて、よくよくメールを読み直すと、2冊はまだ出荷されていなかったらしい。別々に来るのを知らなかった。ラノベばっかり生協のデスクに並べられて、一つ一つチェックしていたのだが、後ろに人が並んでいて少し恥ずかしかった。精進が足りない。10%引かれて合計で8000円くらいになった。

いったん家に戻って本を置き、軍手などを用意してゲーセンに向かう。地下鉄の駅の広告で、仙台駅前でトムとジェリー展をやっていることを知った。行ってみたい。

www.khb-tv.co.jp

途中の立ち食いそば屋で食事していざゲーム。最近また曲が追加された。同時に古いマップの課題曲が解禁されてもいる。マップを進めるのが遅すぎる。

この後はホスフィンが来てずっとマッチングしていたので、SSSは出ていない。出る前に癖がつきそうで怖い。

午後8時くらいに一緒にラーメン屋に行って食事。そのあと地下鉄に乗って帰宅した。シャワーを浴びて、サークルのバチャに臨む。今日はCF #539 div.1。ABCDが解けた。

AはZero-Sum Ranges。Bは答えが1または2または"Impossible"で、全探索して1の判定をする。Cは遅延セグメント木に区間の幅・区間の変化量・区間内における変化量の最小値の3つを乗せて二分探索する。TLが1.5secで、二分探索にlogを2つつけると落ちそうな制約だが、ACLはちゃんとlog 1つでやってくれるので、本当に実装するだけの問題。これはACLが公開されたことで難易度が大きく下がった問題であると考えられる。1点罠があって、回答クエリに答える前に[l,r)範囲外からスタートして範囲内に入り込んでいるクエリをキャンセルしておかなければならない。これに気付かず2WA。

Dはケイリーの公式で数え上げ。必死に頑張ったら解けて成長を感じる。頂点abを結ぶパスの辺の本数をkとしよう。このkについてループを回し、答えを足し合わせる。以降、kは固定されているものとする。

まず辺の重みについて。abパスに乗る辺の重みは、辺も区別するので単にcomb(m-1,k-1)になる。写像12相における、箱を区別する・ボールを区別しない・各箱に1個以上ボールを入れる、場合の数だ。残りの辺n-k-1本の重みはどうでもよいので、m^(n-k-1)通り。

次に頂点のラベルについて。abパスに乗るab以外の頂点はP(n-2,k-1)通り。で、このabパスを1頂点に圧縮することを考えると、全体はn-k頂点のグラフになるので、ありうるラベル付き木は(n-k)^(n-k-2)通り……とはならない。なぜなら、圧縮した頂点のどこに辺が生えているかは区別されなければならないからだ。これを区別するためには、圧縮した頂点の次数それぞれで計算して和を取ればいい、とも考えたが、これは閉じた式にできなかった。そこで、Wikipediaのケイリーの公式の証明を見る。

ケイリーの公式 - Wikipedia

プリューファーコードを用いた証明の節において、木の葉を削除しつつその親のラベルを記録する、ということが書かれている。このとき、ラベルに関しては圧縮前のものを見ればよいのではないか?つまり、圧縮後の頂点のラベルの代わりに圧縮前のk+1個のラベルのどれかを使うことにして、今考えているようなラベル付き木の集合と1以上n以下の記号n-k-2個の列は一対一対応するのではなかろうか。これは実際そうであった。係数が少し違って、圧縮後の頂点のラベルがn-kであったとすると、圧縮後の頂点はプリューファーコードを作る過程において必ず最後まで残ってくれるが、このとき残る2点のうちもう片方が圧縮前のどこに接続しているかでさらにk+1通りあって、結局全体で(k+1)n^(n-k-2)通りになる。n-k==1のときは特別扱いで1通り。これでサンプルが合い、通った。

考察としてはこのようなステップを踏んだが、今整理しなおせば「圧縮」という操作を考える必要はあまりなかった。プリューファーコードを作る過程でabパスに乗る頂点を残すようすれば、自然と1以上n以下の記号n-k-2個の列ができて、最後に残るk+2頂点のうちabパスに乗っていない頂点がどこから生えているかでk+1掛かる。

D問題のsolvedがC問題に比べてめちゃくちゃ多くてびっくりした。コンテスト後のupsolveで増えたなら理解できるが、コンテスト中からドンドン通されていてびっくり。

また橙diffを進める。

atcoder.jp

桁DPで解いた。復元する代わりに、答えとなる文字列を陽に持っても十分間に合うような制約。更新は、+で繋がれるような新たな数(ループのインデックスによって桁数は確定する)を後ろにつなげるか、あるいはすでにつなげてある数の特定の桁を変更するか。新たに数を後ろにつなげるときは暫定的にゼロ埋めしておいて、そこを変更していく。変更する場所は、数の間に+記号を入れてあるので、そこから数桁後ろに戻るような感じで特定する。難易度的に復元は必要だったのだろう。あるいは、当時は桁DPがそれほど人口に膾炙していなかったのかもしれない。

布団に入ってTLを眺めていると、次の問題がboostの多倍長浮動小数点数で解けたという話が流れてきた。

atcoder.jp

添付されていた提出URLのコードを読んでみると、cpp_dec_float_100を使っている。これは10進数で100桁の精度を持つらしい。似たようなことがdcでもできると思い、100kなどとしてみて数回提出したが、どうにも合わない。おそらく、dcの精度は小数点以下の桁数が固定されるのに対して、boostのそれは有効数字で決まっているからだろう。しかしだ。精度を高くすればACできるわけではない、ということはすでに知っているが、それでも有効数字100桁で計算すると用意された20数個のテストケースに「たまたま」通った、ということは間違いないわけである。

では、小数点以下n桁で計算すればたまたますべて通るような、そんなnは存在するだろうか?

テストケースが公開されていたので、dropboxから落としてくる。これをojで使用できるようにして、プログラムで精度の値を変えながら順番に試していくようなコードを書いた。bashでループを回し、ループ変数の値をdcのコードに埋め込んで、それをoj tで試す。oj tは全ケースに通った時正常終了してくれるようなので、ACの検出はかなり楽である。ACできた精度は、画面に出力してもよいが、念のためファイルにも書き出しておくことにしよう。

そんなコードを回しておいて、午前6時過ぎに就寝した。

02/11(木)

午後3時起床。わくわくしてパソコンのスリープを解除しようとしたところ、キーボードもマウスも認識してくれない。焦る。ぶん回して寝たプログラムが重すぎるのだと思い、パソコンの物理ボタンでいったんシャットダウンした。念のためACできた精度をファイル出力しておいて良かった。しかし、再起動しても認識してくれなかった。

普段はUSBハブを机の上まで出してきて、そこに無線の受信機を入れてキーボードとマウスを接続している。無線の調子が悪いのかと思い、有線キーボードを出してきてUSBハブに差し込んでみたが、これもダメ。パソコンの前面にあるUSB口に入れてみると、認識してくれた。どうやらUSBハブの調子が悪いようだ。よく見てみると、作動ランプがついていないではないか。

今差し込んだ有線キーボードにはいわゆる「乳首」が付いているので、とりあえずパソコンの操作はできる。問題はいったん後回しにして昨夜回したプログラムの結果をチェックすると、なんとたった1つだけACできる精度が発見されていた。879桁であった。どこまで探索したのかはわからないが、いかにも「たまたま全て通りました」といった感じの結果だ。とりあえず提出して最短コードとなった。

atcoder.jp

さて、USBハブの問題を解決しなければならない。Windowsが認識しているデバイスの一覧を表示すると、USBハブらしき項目に「デバイス記述子要求の失敗」と書いてある。これを直せばよさそう。そのままググると、対処法がいくつも書かれたブログ記事が出てきたので、そこにある対処法を上から順に試していく。

……解決しなかった。ノートパソコンを取り出してそちらにUSBハブを差してみると、今度は認識されているようだが、しかしハブにさらに別のUSB機器を差し込んでも認識してくれない。寿命か?そこそこ高かったんだよなあ、と思いつつ、いったんコード類をすべて取り外して再接続してみると、今度は認識してくれた。これまでもコードの抜き差しは繰り返していたが、「いったん全部外す」のが良かったのかもしれない。デスクトップのほうに差しなおしてみると、確かに作動ランプが点灯している。良かった~。

こういう謎の現象が起こった時のために、キーボードやマウスは有線のものを含む2台以上保持しておくのがよいだろう。動作チェックができたので、パソコンが2台あるのもよかった。

成績を確認したところ、新たに1つ講義の評価が出ていた。月曜日に書いていた「レポートを出した学生は全員合格」の講義で、僕もBで浮いていた。うれしい。結局期末レポートが手書きである必要もなかったようだ。

ラノベを読む。まず前日の夜から読んでいた「幼馴染で婚約者なふたりが恋人を目指す話1」。主人公とヒロインがそれぞれ企業経営者の子供であるという設定。自分たちのプライベートな話をクラス全体に話して聞かせているのには結構違和感を覚える。主人公とヒロインが上流階級であるという設定は、婚約者だったり半同棲だったりの理由付けになっているだけで、実際の恋愛模様などは一般人と変わらない感じで描かれる。

主人公が上流階級の人間の話で特別に覚えているのはこれだ。かなり好きなのでリンクを貼る、が、この小説投稿サイトは3月初めで終了してしまうらしい。4年くらい前にも終了するという話があったな、と思って調べたところ、運営を移管して延命したらしい。槻影さんこれどこか別の場所に投稿してくれないかな……。

storie.jp

2021/04/18追記:終了していた。題名も見えないので、ここに書いておく。「天才美少女ストーリーテラー笹宮明と僕の愉快で退屈な日常」というものだった。

2021/12/29追記:復活していた。

次に「日常ではさえないただのおっさん、本当は地上最強の戦神7」。本編読了後あとがきを読むと、どうにもシリーズ完結みたいな雰囲気を出している。慌てて調べたところ、完結だった。どのように読んでもストーリーの途中でぶつ切りになっているようにしか思えない。書き上げてから打ち切りが決まったのかもしれないが、もう少しちゃんとまとめようとは出来なかったのだろうか。なろう版でもちょうど今日最終話が投稿されているようで、そちらを見る限りは本来7巻後も数十話くらい続くようだった。なんとも後味の悪い終わり方。

正直文章も突っ込みどころが多い。似たような立場・設定の人(「八神輝」とか、女性複数人で構成されたパーティーとか)が一気に出てくるシーンが多いが、セリフだけで発話者を区別するのはハナから諦めているらしく、セリフの直前か直後に発話者の名前を書くような感じの文章でかなりテンポが悪い。

もう1冊。「継母の連れ子が元カノだった6」。非常に良かった。ところどころネットのネタやミステリに関するネタが挟まっていて、前者は微妙だが後者はニヤニヤできる。個々のシーンもかなり好みで、ストーリー全体として見ても面白い。良いです。

良すぎて途中途中休憩を挟まないと読めなかった。休憩としてCF Div.3を埋めていた。Contest Maniaというサイトで埋め状況を確認しつつ、最近のコンテストから順に解いている。Div.2とDiv.1に共通する問題でうまく認識してくれないという欠点はあるようだが、Div.3を埋めるにあたっては影響しない。

午前6時くらいに橙diffを埋める作業に戻って、「部屋割り」という問題を開いた。通すのに5時間かかった。

atcoder.jp

最初考えていた場合分けはヤバいケースがあって、それを直すのに非常に苦労した。愚直を書いて、ランダムケースを500個くらい作った。解説を読むとシミュレーションと書いてあって、初手から全然違うんだなあという気持ちに。場合分けにも少しだけ言及されていたが、お勧めはしないと書いてあって涙。

結局通しきることができたので満足。さらにもう1問開いたところ、今度は一瞬で解けてさらに気分がよくなった。続けてCF Div.3からまた少し解き、6000ACに到達した。

午後1時、就寝。

02/12(金)

午後8時起床。yukicoderに出て、4完だった。

Aは数列の総和が与えられていることに気づかず迷走。BはUF。Cは、1倍する区間は一つながりになることを利用して、区間を全探索した。区間を固定した後は、それぞれの端点を調べた後、1倍する区間で三分探索。関数の値を計算するラムダ式を作っておくとかなり簡単に書けた。DはDPのD。包除原理は使わず、ループごとに始点と同じ頂点にいる・いないをキーに持った。

Eはのいみさんのツイートを見てupsolveした。

直後にこどふぉ。全完してシステス後15位。

Aは、bを小さいほうからいくつか試す。Bは真ん中の自由度を累積和で求めて両端は毎回計算した。よく見るとa_r-a_lr-lだけで決まるらしい。Cは非常に難しい。bを固定することを考えると、sqrt(Y)以降は商でまとめるやつをすれば解けることは解ける。実はa%bを固定すればよかったらしい。Dはわからなかったのでいったん飛ばした。

Eは気合い。absのために、ソートして左からの累積と右からの累積を持ったりしたが、実は|a-b|=max(a-b,b-a)を利用すればそんなことしなくてよかったらしい。ソートしたのにソートする前の値を使ったりして2WA生やしてしまった。FはZero-Sum Rangesみたいな感じ、だけ考えて実装を始めたが迷走。ちゃんと紙の上で考えてから解こう!Dに戻って、唐突にLCM(1..16)=720720を確認したところ、解けた。市松模様にして、片方を720720に、もう片方を720720-a^4にすればよい。

さらにCF Div.3埋めを進める。今日は2コンテストぶん+αくらいだった。1コンテストに1時間弱かかるので結構面倒であるようだ。ただ、簡単な問題をなぎ倒すのは楽しい。

午前9時、就寝。

02/13(土)

午後3時くらいに生協の弁当を待ち構えるため目覚ましで覚醒。その後寝たり起きたりを2回くらい繰り返して午後4時になる。寝ているのはマズいと感じたため、スマホを触っていたら午後4時半くらいに弁当が到着した。そのあとも少しスマホを触っていて、午後5時くらいに再度入眠。

ARCを寝過ごさないため、午後7時くらいから30分おきに目覚ましをセットしている。その前の午後6時半あたりでも意識があったような気がするが、結局起きたのは午後7時半だった。生協の弁当を待ち構えるのも含め、細切れの睡眠になってしまった印象があって、どうにも頭がぼやけている。今日のコンテストは寝過ごさなかったが、明日は昼からICPC練習の予定があり、そちらは少しまずいかもしれない。

昨日手を付けたCF Div.3のF問題を通して食事したりしていたらARCの時間になった。今日は5完38位でパフォーマンス2878、レートは2690→2710(+20)で久しぶりに(微妙に)highestを更新した。

Aは頭が回っておらず、最初にCL..Rで全探索するコードを提出したところ、マルチテストケースにやられてTLEした。CFをやっていると、こういう場合はsum R-Lにも制約がついているように見えてしまっておかしなことになる。幸い、よく見たら定数時間で解けるので、すぐ再提出してAC。直後にdcの31Bコードを書いて通しておいたが、これは5完後に30Bに縮んだ。

Bはいくつかの区間が組み合わさった形になる。AでWAを生やし、自分の頭を信頼できなくなったので、区間の重複を省いたりするのには座標圧縮+imos法を用いた。

Cは部分木ごとに再帰的に考えてよいやつ。プレイヤーのスコアはPN-Pになるので、Pの最大化の代わりにP-(N-P)=2P-Nの最大化を考えてもよい。相手は2P-Nをできるだけ小さくしようとしてくる。こうやって差の形にしておくと、部分木ごとに「差の増減」と「先手後手が入れ替わるか」を持ってきて適当に貪欲すればよくなる。これらの考察は書きながら考えていたら整理されていったのであって、最初のあまり整理されていない状態のまま設計したコードで書き上げて無理やりサンプルを合わせてしまった結果、1WA。これはどうしようもない。サンプルがすべてあったコードは、提出しちゃうだろ。

Dは、結局隅からすべてのマスを通れないといけない。最初は隅からBFSして通れないマスが存在する行の個数と列の個数のminを出力したが、これは誤り。実際は1つ地面を増やすことでいくつかの行・列が一気に通れるようになる。これを反映するためにはUFを使うとよい。Eは、「まだ動かしていない区間」の両端を持つDPをO(N^2M)で書いてみると、サンプルが合う。DPをよく見ると区間の幅だけ持っていてもよさそうに見えるが、動かしていない区間として適切でないものを省くのに、結局区間の始点終点が必要に見えてしまう。ここでぐっとこらえて遷移を観察すると、区間の幅を減らすときは左から1個取るか右から1個取るかしかないので、この操作を何回したかの情報(これは区間幅から復元できる)さえあれば、あとは二項係数で区間の始点終点に応じたDPの値が復元できる。これはかなりすんなりACできた。

結局ACDでそれぞれ1WAずつ出してしまった。Cを通したあたりではかなり辛くなっていたが、順位表を見たところ全然通っていなかったので復活し、そのあとも気分よく解いていけた。

コンテストが終わって少し後に地震が来た。かなり大きめであった。机の下にもぐっていると、本棚がグラグラ揺れているのに気づき、思わず押さえに行ってしまった。突っ張り棒は設置してあるものの、多少ゆるみがあったようだ。これは良くない行動であったらしい。

シャワーを浴びて食事をし、SRM800に出た。今日は250-400-550-1000の4問。うち最初の3問を解いて、challengeも1件成功し、16位でレートは2404→2481(+77)、最高値を更新した。記念すべき第800回ということで、いくつかの基準に従ってTシャツが配られるらしい。僕は上位25人という基準をクリアしているので、Tシャツが届くようだ。

250は適当にBFS。400は両端のminもしくはmaxが答えになる。証明も自分なりにつけておいた。小さいケースは手で試すとわかる。より大きなケースでは両端を変えずにサイズを1小さくするのが最適。両端を変えようとすると、小さくしたい人は大きく、大きくしたい人は小さくしかできない。550は二分探索。「a秒までに着手しなければならず、b秒かかる課題」の最適な並べ方はa+bの昇順である。

例えば(a_1,b_1)(a_2,b_2)を並べるとしよう。これまでt秒経過しているとして、t+b_1\le a_2かつt+b_2\gt a_1ならば、(a_1,b_1)(a_2,b_2)より先に来なければならない。変形してa_1-b_2\lt t\le a_2-b_1\Leftrightarrow a_1+b_1\lt a_2+b_2である。つまりa+bの昇順に並べても損しないということ。こういう比較関数ネタは、いちいち覚えてはいられないので、導き方だけ覚えておいて毎回式変形している。

400に再帰全探索のコードが提出されていたのを落とした。TLEなのでジャッジに時間がかかったのだが、その間心拍数がすごいことになっていた。

朝方布団に入り、しばらくハーメルンを読んでから午前9時頃に就寝。

02/14(日)

午後2時少し前に起床。すぐICPCチーム練に突入。今日はこのセットらしい。同じく東北大から横浜大会に進んだ、Aobayama_sugarstepの練習に便乗させてもらっている。

https://codeforces.com/contest/1250

相変わらずこどふぉは人が多いので、solvedが増えてきた問題を順になぎ倒していくのが最も良い戦略となる。今日はチーム参加なので、solved数がmaxの問題はチームメイトに任せて、ちょっと少なめのものから解いていった。結果はABCEFGHJLMNの11完で、僕はそのうちNJCEBMGを、この順で解いた。全体的に解の復元を要求する問題が多くて嫌になった。

Nは気合い。連結成分でBFSするときに、最後に訪れた頂点とそこに行くのに使用した辺を保存しておいて、その終点を変えて別の連結成分につなげればよい。この問題だけはsolved数を見ずに開いたのだが、すんなり解けてちょっと不安になった。Jは二分探索。Cは最初実家DPをしようとして失敗したが、区間の終点を全探索する方針に変えて解けた。累積和のようなものを考えると、更新は区間addで、取得は区間minでできる。

Eは少し難しい。2-SATが見えるが、trueを割り当てる個数の最小化はどうもできそうにない。ここでグラフを出力してよく見ると、a⇒bという辺があるときは常にb⇒a¬a⇒¬b¬a⇒¬bも存在することに気づく。つまり、弱連結成分ならば常に強連結成分となり、各要素の真偽を反転した別の強連結成分と1対1対応するということがわかる。こうなると、この対応する強連結成分2つの組のうちどちらをtrueにするか、を個別に定める問題になるので、真偽の割り当てに応じて小さいほうか大きいほうを選べばよい。

Bはsとしてありうる値をO(K^2)で列挙して、自明に不要なものを除いたり重複を削除したりした後、各候補sについてO(K)rを探索したら1200msで通った。rを全探索するのが正しい解法のようだ。Mは、まず3x3マス置きに埋めて真ん中のブロックを縁取れることに気づき、あとはそれのサイズを倍々(本当は横は縦より長くする)にしていきながら同様に斜めにずらして埋めていくことで作れた。Gは差分とAの累積和を持ちながら尺取り法のようにして更新。これも最初は実家DPを考えていたが、差分が負のときの扱いがうまくいかなかった。冷静になると、更新のために区間からもらってくる必要はなくて、常に区間の一番左端の要素を持ってきてよいので、尺取り法が適用できると分かった。

19時に終了。その後30分程度オンライン通話アプリで感想を言い合って、Div.3を少し埋めていたらyukicoderの時間になった。

今日は3問で、最初の2問を通して終了した。TROCがあったので残り20分あたりで抜けはしたものの、それがなくても3問目は通せなかっただろう。Aは大体何でもできて、BはLCM(1..N)からある素数の指数を1少なくすることしかできなさそうなので、N以下で最大の素数を抜けばよい。N/2..N素数が存在することについては何となくで飛ばしてしまったが、ここにはベルトラン・チェビシェフの定理が使えるようだ。Cは……。

TROC #19に出る。6完4位で2528→2602(+74)。どんどん上がっているが、何気に現在全体ランキングの9位らしい。毎回参加することが重要。今回から制約が問題文の直下に置かれるようになったらしく、非常に便利になった。

Aは書いている途中で常に-1になりそうなことに気付いたが、そのまま書ききった。Bは全体の半分だけ作れる。Cはbitを減らしていく。制約が優しくて、必ず先にKのbitが消える。ちょっと書き間違えて1WA。Dは難しいが、[1,i][i,1]を順に聞いて、その差を見るとわかる。片方だけだと微妙なものが残るが、両方からやるとマズいものはちゃんと消えてくれる。Eはやるだけ。Fは非常に難しいと思っていて、根を決め打ち、子を01任意の3種類に分けて場合分けを頑張ると木DPできる。もっと頑張ると全方位木DPできるので、それで通した。めちゃくちゃ自由度が高いことはわかっていたが、実際にAが全部0のパターンとサンプル2のケース以外はYESらしい。許せないな?Gは諦めた。

DはFAだった。touristと一緒のところに書かれていて非常に誇らしい。touristはCの後Eに進んだようだ。

Gを諦めてからは、今日のyukicoderのC問題と格闘していた。だいたい午後11時にスタートして、ACが午前5時半だったので、コンテスト本番で少しやっていた分も含めれば7時間に及ぶ壮絶な戦いであった。

方針としては、連結成分に番号を振りつつ行ごとに見るDPをする。壁と空きマス(本当はチョコレートだが、ここではこう呼ぶ)は最大でそれぞれ3つずつの連結成分があるので、1マスの情報は6通り、6進数で情報を保持する。よって計算量はO(R 6^C 2^C CN)のようだ。冷静になるとこれで通そうとするのはイカレていた。ちなみに、空きマスの連結成分も考えなければならないことに気づくのに3時間くらいかかった。次のようなケースを数えられていなかった。

#####
#...#
#.#.#
###.#

前の行の情報と現在の行の壁・空きマスの配置から連結成分によって再度壁・空きマスに番号を振り直し、頂点の個数を数えて次の行に更新する。このとき、マスの外側にたどり着けないまま壁にふさがれてしまう空きマスや最後まで連結にならなかった壁の組などを検出して適宜飛ばしておく。連結成分0は必ずマスの外側にたどりつける空きマスにだけ割り振られるようにしておくことで、空きマスがマスの外側にたどり着いたかどうかを判定する。各行の両端が空きマスだった場合はそこを連結成分0に直すことにすると達成できる。

最初にサンプルが合ったとき、最大ケースは手元で19secだった。そこから、途中O(C^2)のループがあったのをなくして12secくらいになった。そのあとは定数倍バトルで、何回も回していたループをまとめたり、不必要な分岐を減らしたり、UFをベタ書きしたり、find関数の戻り値を配列に取って置いたりして計算時間を減らしていった。結局手元で7.5secくらいになったのだが、yukicoder上では相も変わらず10秒オーバーのようであった。最後にCを定数6にしたところ、手元で6secとなり、yukicoder上でも10secギリギリでACできる速度になった。C<=6という小さなループが頻発するので、キャッシュヒットや並列化はあまり考えられない。その代わり、その小さなループを定数回のループに直したことで、ループアンローリングなどができたのではないかと考えている。