2021-05-03

週記（2021/04/26-2021/05/02）

04/26(月)

先週の週記を投稿してからの話。ド深夜にAtCoder Problemsのアップデートがあって、現在開催中のコンテスト、具体的にはAPG4bとABSがProblemsに収録されるようになった（ACL Practiceのほうは以前から収録されていた）。コードゴルフの時間である。

ABSは、まあよい。出典と問題idが一致しているので、同じ問題であるという判定がされる。practiceのA問題はここでしか全員の提出を見れないので、その問題だけ新しく最短コードが生まれるが、これももう縮まないだろうという感じはする。一方APG4bは大量に新規問題として登録されるが、ほとんど手付かずだった。AtCoder Problemsに収録されないならば最短コードとしてもカウントされないということなので、どうでもいいやという考えでいたが、いざ収録されるとなるとまずい。

朝方までずっと問題を解いたり現在の最短コードの粗探しをしていた。他のゴルファーも一度縮めてからあまり触れていないようで、比較的最近のテクニックを適用したりして縮められそうなものはいくつか見つけることができた。

今日イチ押しの提出はこれだ。

atcoder.jp

本来ならbc||echo errorと書きたかったのだが、bcはプログラムのエラーに関係なく正常終了するようで、できなかった。Perlから呼び出して、返ってきた標準出力が空文字列だったときに分岐することで似たようなことが行えた。電卓をつくろうという問題ではあるが、bcという電卓があるのでそのまま使っている。

朝方布団に入って少しラノベを読んでいたが、100ページほど進んだあたりで就寝。午前8時だった。

午後3時起床。夢を見た。

夢：一軒家に住んでいる。12/30の夜は大荒れの天気で、ゲーセンに行けなかった。大晦日、両親が来る。冷蔵庫にレモネードのパック飲料が大量にある。これは確か、コンテストの商品だったはずだ。姉も来ているらしい。新しいギネスブックを買いたいと言っていた。
— こたつがめ (@kotatsugame_t) 2021年4月26日

夢をツイートの下書きに記録して二度寝しようかと思ったのだが、先日のJOIG 2021の問題がAtCoderに公開されていたのを発見して飛び起きた。1時間ほど前に公開されたようだ。急いでコードゴルフをし、その後全問解いておいた。

JOIG 2021 過去問 - AtCoder

Aはmax*3-sum。Rakuが良いように見えるが、~~実はdcのほうが短くなる。~~後からRakuの新手が出て、同じ長さになった。似たような問題はほかにもたくさんあって、そこからdcの最短コードを引っ張ってくるのが間違いがなくてよい。まずRakuでmax-sumをしているコードを検索し、その問題の最短コードを見てdcがあるか探す、というステップを踏んだ。

Bは見るからにVimを使ってくださいという問題。とりあえず12Bのコードを書いてから全体の提出を見たら、すでに9Bのものがあった。ボロ負け。CはRubyで書いておいたが、この日記を書いているときに試しにRakuで出してみると~~ギリギリで通った~~コードの短縮と同時に定数倍高速化にもなって、普通に通った。Dは答えを二分探索する問題で、これもRuby。

Eからは普通に解くだけにとどまった。Eは頂点にそこまでたどり着くのに逆転させた辺の本数の情報を付け加える、いわゆる拡張dijkstra。Fは各色について上下左右の端を計算しておくと、ピクセルを隠す領域の端はその中から選ぶことになる。これで縦横1000通りあったのが256通りまで絞られる。まず上と左の端を全探索し、下を広げながら右端をデータ構造で管理する。僕はBITを使って、その位置に右端を置くと何種類の色が隠れるか持ったが、これは $N=\max A=256$ として $O(N^2(N \log W+W))$ かかる。他の提出を見ると、priority_queueで覆いきれなくなった右端を落としていくのが良いらしい。 $O(N^3\log N)$ 。

昨日ゴルフしておいたAPG4bの問題が、さっそくいくつか縮められていた。どれも昨日の自分の正気を疑うようなミスを咎められており、反省。

今日のサークル解説会も外部に公開する。今日は第二回日本最強プログラマー学生選手権の問題を取り扱う。僕はACEの3問題の解説を担当することにした。前回の反省を生かして、今回は競プロに関する予備知識があまりいらないような問題を選んだつもりだ。ほかにsotanishyさんがF問題の解説役に立候補してくれて、合わせて4問題を解説する。

最近、PowerPointのスライド作成時にAlt+セミコロンで数式が入力できることを知り、かなり便利になった。Wordに別のショートカットがあって、そちらはPowerPointで使えなかったので、すっかりないものだと思い込んでいたが、検索してみると見つかった。なぜショートカットキーを変えてしまったのか。

また外部からの参加者も含めて10人ほどが参加してくれた。今回はある程度喋る内容を考えていたはずだったが、今度は僕がひたすら早口になってしまったようだ。また次回気を付けたい。解説会の直後にサークルバチャが控えている。さすがに間が短いだろうということで15分遅らせることになったが、それでも最大限急いでスライドの公開作業やサイトの記事の作成・編集を行った。

2021/04/26 定例会 | puzzleknot 公式サイト

サークルバチャ。今日はCF #573 div.1。問題名に時津風が入っていて、div.2のA問題によればやはり艦これらしい。

https://codeforces.com/contest/1190

Aは、まだ残っている一番近いものがどのページにあるか計算し、同じページにあるものを一気に削除する。Bはおおむね階段状になるはずだが、ソートしたときに隣り合う要素が同じところが2か所以上あるか、1か所しかないがそこを解消しようとすると1つ小さいものに当たってしまうか、あるいは0が2つ以上あるかの3通りで先手の負けが確定する。先手と後手がAlice・Bobやfirst・secondではなく謎の文字列（ユーザー名？）であるような問題は、CFやyukicoderではそこそこ見るものの、正直やめてほしい。

Cは先手と後手が1手ずつプレイして勝ち負けが決まらない場合、相手の操作をそのまま真似ることで勝ちの横取りをしようとする戦略が効いて引き分けになる。先手勝ちの条件は簡単に判定できて、後手勝ちの条件も先手が取りうる手を全探索した上で丁寧に見ていくと計算できる。

Dは、まずX座標が同じ点をグループにする。各グループについて、そのX座標x0が領域の右端となるようなものをカウントする。見ているグループでY座標が最も大きいものをYmaxとしたとき、領域の下はYmax以下である必要がある。領域の下がある値y0であるとき、y0+1との差別化のために、(x,y0)なる点を含んでいる必要がある。そのような点が複数ある場合は、xが最大のものを選んだとしてもよい。このときの選び方は、x==x0のときy0<=yかつx<=x0なる点(x,y)（ただしxに重複があってはいけない）の個数で、これはyに対して個数を持つBITで計算できる。x<x0のときはX座標がxであるグループを見ているときに計算したのと同じ値になるので、毎回x==x0の点だけ更新して、取得はこれにもまたBITを使うことで対応できる。

コンテスト後の反省会で聞いたところによれば、DはY座標が同じ点をグループにして解いた人が多いらしい。ちょっと考えてみたが、確かにそちらのほうが楽な気もする。BITが1本でよいはず。

div.2の問題も解いておいたが、B問題が信じられないくらいカスだった。萬子、筒子、索子のそれぞれ1から9（これらを数牌と呼ぶらしい）、合計108枚のうちから3枚与えられるので、残り何枚引けば面子となりうるか？を答える。艦娘は麻雀しないだろ。

そのあとまたAPG4bを進めていた。昨日見て縮みそうだと思ったが実装が面倒だったものを倒していく。途中Rakuに新手が出た。

atcoder.jp

+<<words~~あたりが新手。これまで$_=hogeとして代入していたのは、ほとんどがhoge~~の形で書ける。これはスマートマッチ演算子~~の右辺がCallableである場合の挙動で、左辺を引数$_にして右辺を実行してくれる。

infix ~~

この更新が適用できる範囲はかなり広い。数えたら17個縮んでいた。ちなみにそのうち自分が最短でなかった問題はたった1つだった。されど1つ、か。

APG4bとJOIG 2021で2900ACに到達した。

逆に何解いてるんだ pic.twitter.com/v291oiWfqW
— こたつがめ (@kotatsugame_t) 2021年4月26日

TCB35の順位が公開されていた。満点3人のうち、回答時間が最も短かった僕が1位になった。37分09秒で、10位までのほかの人と比べてもかなり速い。圧倒的勝利で非常に気分がいい。

今日の典型90問は早いうちにdc 43Bが報告されていた。そのころ僕は53Bで、10Bも差がついていて勝てる気がしなかったが、じわじわ縮めていって、最後に1つブレイクスルーがあって43Bに到達した。一致してしまうとかなり辛い気持ちになるが、ここが踏ん張りどころとさらにコードを睨みつけていたら、42Bになった。コードを公開する気がなく具体的なことは何も言えないため味気ない書き方になったが、43B→42Bには1時間半かかっている。

布団に入ってしばらくハーメルンを漁っていた。午前11時半に寝落ち。

04/27(火)

午後6時、目を覚ます。TLをつらつらと見ていたら、ふとしたことから怖い話のWeb漫画のリンクを踏み、読んでしまった。

ハーメルンで1作読んだ。といってもまだ8話しかない。

syosetu.org

「玄爺」という亀の妖怪が出てくる。旧作の靈夢は玄爺に乗って空を飛んでいたらしい、ということをこの作品経由で知った。玄爺は「東方遺骸王」にも出てくる。読んでいた当時はオリキャラだと思っていたのだが、れっきとした東方キャラでびっくりした。東方遺骸王は本当に徹頭徹尾東方の二次創作なんだなあ、という気持ちになった。

さらに別の作品を読み始めたが、ここらでもう一度寝ておくことにした。しかし起き抜けに読んだ怖い話の印象が強すぎてなかなか眠れない。頑張ってハーメルンに集中しているといい感じの眠気が訪れたので、逃さないよう速やかに意識を落とした。午後9時半だった。

04/28(水)

午前1時、目を覚ます。

Shortest Code㊙情報：トップページに表示されないコンテストの問題はカウントされない
— こたつがめ (@kotatsugame_t) 2021年4月20日

AtCoder Problems をアップデートしました！https://t.co/mu6aGHrWhr
- @nebocco27 さんがリストに無いコンテストもクロールされるようにしました！ pic.twitter.com/Wmsd9hzSJi
— 宇宙ツイッタラーX (@kenkoooo) 2021年4月27日

ンンンンンｗｗｗ

現状、「えびまのお誕生日コンテスト 2021 Day 1」だけがリストに追加されている。まだあるはずなので追加するPRを送ろうとしたが、スマホからだとUNIX時間を知るのがかなり難しいことに気づき、あきらめた。

そのまま布団で昨日から読んでいるハーメルンの続きを読んでいた。ちょくちょく意識を落としつつ、午前2時から午前5時半くらいまでかけて最新話近くまで来た。

午前7時、布団から出る。AtCoder ProblemsにPRを送るため、トップページに表示されないコンテストを探し始めた。Google検索で「site:atcoder.jp/contests」としてみるととんでもない数のヒットがあったので、加えて「お誕生日」とか「有志」のワードで検索した結果、いくつか見つけることができた。

そのうち「ゆらふなセンパイお誕生日コンテスト」は任意の時間にスタートできる形式のコンテストで、現在も参加可能。しかし以下の参加記によれば、問題はすべてAtCoder ProblemsにおけるOther Contestsの過去問であるようだ。

hyoga.hatenablog.com

結局、そういうコンテストは3つ見つけることができた。追加するPRを作成し、送ったところ、すぐにマージされた。

AtCoder Problems を更新しました！https://t.co/XQ7nvyKnYI
- @kotatsugame_t さんがクロール対象のコンテストを追加しました！
— 宇宙ツイッタラーX (@kenkoooo) 2021年4月28日

keymoonさんによれば、さらに次のようなコンテストもあったようだ。コンテストというか、ただジャッジが公開されているだけのページであるので、追加されるべきかどうかは微妙。僕はあってもよいと思うが、自分でPRを作る気はない。

テスト - AtCoder

シャワーを浴びて外出。今日は学食に行って、それからゲーセンで遊ぶつもりだ。そろそろ世間的には連休らしいが、時間の自由がきく身分であるところの僕としてはできるだけ平日に遊ぶようにしておきたい。家から学食までの道の途中に高校があるが、今日はそこで体育大会が行われていた。無観客らしく、フェンスのそばに保護者と思われる人影が数名張り付いておられた。このご時世に体育大会をするというのはかなり挑戦的であるように感じられるが、現在でも高校以下は普通に対面授業をしている、という事実からすれば今更か。

ゲーセンに行く前に本屋に寄って新刊を買った。今月はこれが最初で最後の本屋となりそうだ。財布の中身が心もとなくなったので近場のATMに向かってみると、3月半ばで営業が終了してしまっていた。近くでまだ営業しているATMを案内されるも、未だに土地勘がないためわからない。Google Mapで検索してみると思ったより近かったので、この機会に知ることができてよかった。ゲーセンからの距離を見るならば、おそらく新しく知ったATMのほうが近い。

ゲーセン。今日はアップデートがあって、追加された新曲をプレイしてみたが、縦連が全然追いつかなかった。難しいのでいったん放置することにして、適当に別の曲をプレイしていた。Tidal WaveでAJを出して、そのあとはLv12のスコアを詰めていた。スコア的には全体で1000点以上増えたはずだが、OVER POWERのパーセント表示は微動だにしない。99.50%を目指しているが、数値的にいくつになればよいのかが全然わからない。自分で計算するにしてもLv12の定数表とにらめっこする必要がありそうで面倒。

ウオオオオン pic.twitter.com/lgFVsafup3
— こたつがめ (@kotatsugame_t) 2021年4月28日

かなり眠くなってきたので、いったん離脱してエナジードリンクを飲んでみることにした。今週末にAtCoderでコンテストを開催するところの商品を購入してみた。500mlの缶を持ったまま音ゲーするのは非常に難しい。この日は足元に置いて、上からゴミが入らないよう缶の口をタオルで覆っていた。

エナドリ、4年ぶりくらいか pic.twitter.com/0Rte1qKEFE
— こたつがめ (@kotatsugame_t) 2021年4月28日

2021/02/19以来久しぶりに「《破滅》～ Rhapsody for The End」を連奏して、ついにSSSを達成した。

《破滅》～ Rhapsody for The End SSS pic.twitter.com/t2hkBaiCo3
— こたつがめ (@kotatsugame_t) 2021年4月28日

いろんなところでスコアを落としていたが、ちゃんと譜面を確認したところそこそこ安定させることができて、難所に集中できた。例えばノーツがどういう塊に見えているか確認したり、長い片手トリルについて何分のリズムで何回叩くのか覚えたりなど。以下の2つのうち後者は前から使っていた運指だが、その後ろがよく抜けるのもあって小節全体としての成功率はかなり低い。しかしかなり早い段階でかみ合って、そのままSSSを達成した。たまたまうまくいったとしか思えないが、まあSSSが出たならなんだっていい。

f:id:kotatsugame:20210501181345p:plain — 17-18、21-22小節

f:id:kotatsugame:20210501181413p:plain — 98、102小節

ほかにも13+の未鳥をちょっと触っていたが、Glorious Crownの最後が間に合ったりContrapassoのお前の弁当地帯が繋がったりして、成長を感じる。脱力が少し上手くなっただろうか？

午後8時半くらいにゲーセンを離脱して食事しようとしたが、見渡す限りすべての飲食店が閉店していて非常につらい気持ちになった。仕方なくドン・キホーテに寄ってパンやお菓子などを買った。

家に帰ってきて、今日買った本を写真に撮ってツイートした。

└( ＾ω＾ )┘♪ 買った♪└( ＾ω＾ )┘♪ 買った♪ pic.twitter.com/HSicnxF1bg
— こたつがめ (@kotatsugame_t) 2021年4月28日

今日のぶんの典型90問を解いてコードを少し縮めていたが、眠気がすごいことになっていたのですぐに寝ることにした。午後11時就寝。

04/29(木)

午前6時半起床。月曜日にゴルフしていた典型90問・024が42B→40Bになったらしい。かなり信じられない。勝てない。

午前8時半くらいに身を起こし、ほかに寝ている間に縮められていたコードを確認したり縮めたりしていた。

ラノベを1冊読んだ。「私と一緒に住むってどうかな？」1巻。あんまり好みに合わなかった。主人公とヒロインの2人で古民家をDIYする、という話。あんまりDIYに興味がないし、描写に現実感もなかった。倉庫に材料がたくさんあった、というのは高校生がいろいろ作るという設定上仕方ない部分もあるが、スマホでちょっと調べてちょちょいと木を切ってやすり掛けしたらできましたというのは簡単すぎじゃないだろうか。さらに、ヒロインは過去の出来事から主人公以外をどうでもいいと思っていて、それで衆目の中主人公と過激なスキンシップをとることに抵抗がないという設定だが、このほとんど痴女のような描写も見ていられなかった。

朝、APG4bとウクーニャたんお誕生日コンテスト（非表示のコンテスト）でコードを更新したはずだが、atgolferで流れてこない。これの原因を探っていた。サーバでファイルの更新日を確認したところ、クローラはちゃんと予定通り動いているようだが、問題のコンテストにおいては朝方取得した提出を最後に見に行っていないようだ。結局、原因は以下のようなものだった：

atgolferは高速化のため、AtCoderから直接コンテストリストを取得して見に行く方法と、AtCoder Problemsで最短コードが更新されているか確認してから見に行く方法の2通りでクロールしている。このうちAtCoderに直接見に行くほうでは先に挙げた2つのコンテストを取得できない。よって更新はAtCoder Problems任せになるが、AtCoder Problemsで最短コードが更新されるタイミングは実際の提出があってからかなり後のことになってしまう。それで、6時間経った現在でもAtCoder Problems上では最短コードが更新されていない扱いになっているので、atgolferでも提出を見に行っていないようだ。

原因が分かったところで、atgolferを更新することにした。こちらでも常設中のコンテストを取得し、またさらに非表示のコンテストリストも管理することにした。このコンテストリストはAtCoder Problemsのファイルから引っ張ってくることも考えられたが、APIとして提供された機能でない以上、いつの間にかファイルの場所が変わっていたりしたら対応できない。そこで、僕のやる気が続く限り手動で更新することにした。

1点困ったことがあって、https://atcoder.jp/contests/を読んでもAPG4bとABSが取得できなかった。ここで天啓が降りて、https://atcoder.jp/contests/?lang=jaとしたところ、無事取得することに成功した。この事実はつい最近TLで見たような気がする。それがなければ自力では解決できなかっただろう。確かに英語版が提供されていない以上英語ページからは見えないほうが良いのだろうが、普段日本語ページしか見ない人間にとってそのことに気づくのは非常に難しいことだ。

github.com

ハーメルンを読んだ。かませ犬の描き方が執拗でちょっとイラッとした。

syosetu.org

さらに別のハーメルンを漁ったが、すぐに寝落ちした。午後10時だった。

04/30(金)

午前3時起床。ECR108に参加し損ねた。

1時間半くらい、昨夜から読んでいたなろうを読み続けたが、なんとなく合わなくて読むのをやめた。俺ガイルの二次創作で、八オリ。八オリは一時期Pixivで結構漁っていたはずだが、なぜ今は合わないと感じてしまったのだろう。

syosetu.org

確かこの辺りの時間帯にラノベを1冊読んだはずだ。「この世界、わたしに都合がいいようです！」。これもあんまり面白いとは思わなかった。同じ人物のセリフが連続しているのに、1文1文鍵かっこで分けられているのがかなり気になった。もしかしたら適当に読みすぎて僕が発話者を同定できていなかっただけかもしれない。

ハーメルンの捜索掲示板を漁って作品を探すことにした。いくつかよさそうなものを見繕って、そのうち「竜に生まれまして」というのを読み始めた。

https://ncode.syosetu.com/n5244by/

そのまま読み続けたが、午前8時半から午後1時までまた寝落ちしていた。今日は祝日なので学食が営業していない。食事してコードゴルフしていた。夕方は今日の典型90問のコードゴルフで競っていたが、かなり差をつけたと思ったらあっという間に逆転されて勝てなくなったので諦めてしまった。夜はずっと「竜に生まれまして」を読んでいた。

yukicoderがあったので参加した。4完。

yukicoder contest 293 - yukicoder

Aから難しい。K=3、K=4のときを考えると何となく法則性が見えてくる。縦横2K+1のマス目がだいたい埋まって、下2行が市松模様、それ以外は端までピッタリある行とない行が交互に出現する。適当に計算して通した後、さらに式変形を重ねると、4K^2+2であることが分かった。bashからdcを呼び出すのもRakuも両方13Bだった。

Bはdp。全部持って素直に書くと $O(N^4)$ になる。 $N\le 100$ なので投げたら普通に通った。これが通ることはあんまり直感的ではないように感じられるが、計算すれば当たり前か。CはZero-sum rangesの要領でもらう値を引き算していくdp。WAが出たので適当に全部0のケースを試したら大当たりだった。修正に手間取るも、なんとか2回目で通った。Dは木DP。

Eを見たがよくわからないのでFに進んだ。Fもよくわからないが、こちらのほうがsolvedが多いのでチャンスはありそう。と思ってしばらく考えていたが、そもそも「総和が $A_i$ 以下であるような連続部分列の個数」を答えるクエリを10⁵回処理する方法もわからないので、あきらめてなろうを読んでいた。

コンテストが終了してからFの解説を読んだところ、誤読に気づいた。条件のうち「最小値が $i$ 」を「最小値が $i$ 以下」だと思い込んでいた。「最小値が $i$ 」ならばそのような部分列はかなり限られてきて、その中で上で言ったクエリを解くなら~~短いほうを舐めつつ尺取り法~~短いほうの端点を固定してもう片方を二分探索するので間に合いそうな気もする。実際間に合うらしいことが解説に書いてあるものの、具体的にどう示すのかが非常に簡潔に書かれており、よくわからなかった。

布団に入ってなろうを読んでいたが、午前零時半寝落ち。

05/01(土)

午前5時起床。先々週のコンテストの賞金が来ていた。過去最高額でうれしい。

4月17日に開催された「第二回日本最強プログラマー学生選手権」において優秀な成績を収められましたのでここに賞品を贈呈します。
￥50,000
Amazonギフト券
— こたつがめ (@kotatsugame_t) 2021年4月30日

なろうを読んだ。最近読んでいた「竜に生まれまして」を読了。ついでに主人公の妹竜をメインとした外伝「黄金竜外伝」も読んだ。

https://ncode.syosetu.com/n5244by/

https://ncode.syosetu.com/n9993dp/

良かった。最初は、上位生命体である竜の主人公視点で、幼いころから一緒に過ごしていた女の子がドラゴン使いとなって冒険者として大成するのを見る感じの話かと思っていた。それはそれで素晴らしかったのだが、実際はこの女の子はかなり早い段階で寿命で亡くなり、その後主人公竜が主体となって世界を旅したり戦ったりするのがメインになっていく。これも良い。人間たちの竜に対する無理解などのもどかしさがいい感じ。

別のなろうを漁っていたが、午前9時から午前11時までと午前11時半から午後4時までは再度寝ていた。

起きて、4月分の読書や書籍購入の記録をつけ、ツイートした。今年は全体的にあんまり読めていないが、4月それらに輪をかけて全然読めていない。積読が増えるばかりで非常にまずい。

また今セメスターの時間割が確定しているので、それもツイートしておいた。時間割のツイートをリプライに連ねていくのももう4年目である。

4月の集計
買った：10冊
読んだ：7冊
積読：+3冊
積読（累積）：+35冊
— こたつがめ (@kotatsugame_t) 2021年5月1日

四年春学期さん、対戦よろしくお願いします pic.twitter.com/OVsMcyY7NQ
— こたつがめ (@kotatsugame_t) 2021年5月1日

そのあとは夜までずっと週記を書いていた。溜めすぎ。

午後9時からZONeプロコンに出た。38:58全完2WAで35位、日本人順位だと31位。全然ダメ。

Aはよい。Bもちょっとびっくりするがやるだけ。CとDは点数が逆転しているようだが、かまわずCから解いた。二分探索すると各人のデータは2⁵に圧縮できて、判定にはDPが使える。Dは親の顔より見た。この類の問題はマジで面白くない。Eは $O(R^2 C)$ 本の辺を張ってdijkstraするとTLEしてしまったので反省して頂点倍加した。TLE解を書いている途中に頂点倍加するとよいことに気づいたが、通るだろうと思ってしまった。

Fは適当に基底を取るまではよくて、復元がよくわからなかったので適当にやったら1WAした。ACした僕の方針はこうだ：noshi基底をとる。基底ごとに、それの元となった値を覚えておく。i=1..N-1に対し、xorして0にするために必要な基底のうち最後に並んでいたものの元となった値をuとしてi^u <-> iなる辺を張る。これでよい理由は、i^uが基底のうち今使ったものより前に並んでいるものだけで表現できると言えるからだ。これを繰り返すと最終的に0と辺が張られることになる。

コードゴルフ。Aは最初Perl 22Bを書いていたが、冷静になるとbash 18Bが存在する。ここでZONeではなくONeを数えてもACできるようだが、climpetさんに1分弱負けた。お互い全完後のコードゴルフなのにこんなに僅差になってびっくりした。Bは適当にdc。最近全然書いておらず、累積maxを取るコードは自分が思っていた最短より過去の提出をさらって見つけてきたもののほうが1B短くて冷や汗をかいた。CはRubyで、一度は取ったものの負け。Dは適当にPerl。Eは手つかずで、Fは上で述べた解法より↓の解法のほうがかなり短くなるらしくclimpetさんに取られたが、取り返した。

F のシンプルな O(N) ですhttps://t.co/nCSWqoBwIB
— jell (@jellc_) 2021年5月1日

Submission #22244053 - ZONe Energy Programming Contest

さて、E問題は僕がTLEしてしまった愚直に辺を張る解法でも通るらしい。これについて以下のようなツイートをした。

あ　Eが愚直で通る人と通らない人の違いわかりました
(cost,r,c)を優先度付きキューに入れるとき、(-cost,r,c)にするとTLEで、優先度付きキューにgreater<>を指定するとACです
— こたつがめ (@kotatsugame_t) 2021年5月1日

ちなみにこのツイートにある理由を説明するリプライには間違いがあって、rが「小さい順」で探索することで高速になっている。そのあといろいろな言及があって、「ゴールに到達した瞬間終了する」「costが等しいときはrが小さいものを採用する」「costが等しいときはcの大小で比較する」のいずれかを選択すれば愚直に辺を張って通るらしいことが分かった。まあもともと1ケースしかTLEしなかったのだから、たまたまそのような比較関数に対するテストケースが入っていないのだろうと考えていたが、どうやら遷移の特徴からちゃんとオーダーレベルの削減になっているらしい。証明はわからない。

E問題、タイはrの昇順に取り出せばO(R^2C + RC log RC)になってると思っています。
— ꑄ꒖ꐇꌅꏂ🐈 (@snuke_) 2021年5月1日

ZONeプロコンの2nd Roundに出た。問題があまりにも簡単すぎてびっくりした。僕の環境ではChromeから見えなかったのでMicrosoft Edgeを使う必要があったことや、長めの入力を手で選択してコピペしてくることなどのほうが難しかった。しばらくの間404エラーで先に進めなかったのにもびっくりした。

Crystalのコードゴルフで新手が出た。macroを使う。

04. マクロ | Introducing Crystal Programming Language - Your awesome subtitle

atcoder.jp

CやC++のマクロよりは柔軟らしいが、コードゴルフで使うときは高機能なことはしない。普通にdefで関数定義すればよいじゃないかと思うかもしれないが、例えば上の例では変数名をそろえることで引数に渡すのを省いていたりする。さらなる利点として、上の例では使用されていないが、マクロ展開場所から見える変数を断りなしに使用できるのが効いた。Crystalにグローバル変数がない以上、関数定義の内部で使用したい外部変数はすべて引数として関数内部に持ち込む必要があった。

昨日のyukicoderのFを解いた。計算量解析の理由もちゃんと自分なりに理解できた。あるインデックス $i$ が右側にあるインデックス $r_1\lt r_2\lt r_3$ の計算時に使用されるとき、 $r_2$ から左に進んで $r_1$ に邪魔されず $i$ まで到達することなどから $P_{r_1}\gt P_{r_2}\gt P_{r_3}$ が成り立つ。ここで $r_1$ の左右で $P_{r_1}$ より小さいもののインデックスを探すと、これは左が $i$ 、右が $r\le r_2$ になっていて、このうち左のほうが短いという仮定から $r_1-i\le r-r_1\le r_2-r_1$ となる。同様にして $r_3-r_2\ge r_2-i=r_2-r_1+r_1-i\ge 2(r_1-i)$ がわかるので、間隔が倍々になっていき、 $i$ は左右合わせても都合 $\log$ のオーダーでしか使用されないという寸法だ。

昨日は短いほうを見て長いほうは尺取りすればよいと思っていたが、それは結局長いほうの線形時間がかかることになってよくないらしい。毎回二分探索すると、 $log$ が増えるだけで計算量的にははっきりしている。

布団でラノベを読んでいた。4月から商品の税込総額の表示が義務化されたが、書籍では多くのレーベルで帯に表示することになったようだ。確認できた分では、ガガガ文庫だけがカバーに表示していた。

総額表示義務化
←前　後→ pic.twitter.com/6mgkKcq3NX
— こたつがめ (@kotatsugame_t) 2021年5月1日

午前8時就寝。

05/02(日)

午後3時起床。午後4時半就寝。午後5時半起床、即就寝。午後8時起床、即就寝。二度寝を繰り返しつつネットサーフィンをしていた。

本格的に起床したのは午後11時。今日はCGRがあるので、それに参加するために目覚ましをかけていた。下書きに夢の記録があったのでツイートした。

夢：グーグルのインターンを受験しに行く。実際に社屋に集まって1週間泊まり込み、アイディアだけ出して最終日にプレゼンする。グループごとに合格者が出る。社屋には他にも幼稚園や温泉旅館がある。インターンに採用されるとホテルみたいな部屋に泊まれるが、受験中は5人部屋にグループの人と泊まる。
— こたつがめ (@kotatsugame_t) 2021年5月2日

またこれとは別の夢の記憶もある：皇太子に逆行転生して御幸（調べた限りでは皇太子には使わない単語らしい？）のために駅まで車に乗る。モタモタしていたら周りの人に置いて行かれたので、切符と未来のラノベを掴んで残されていた車に乗り込んだところ、付き添いの人が僕の逆行転生について知らない人だったので、車内でラノベを取り出すことが出来なくなった。道の前のほうを、外国の貴賓を護衛する戦車が走っている。我々も急いでいたため戦車を煽るような形で走ることになってしまったが、急に戦車が速度を落としたかと思うと後ろから数台の車が出てきて我々の前を完全に封鎖してしまった。こちらの車の運転手が車外に走り出て、この車に皇太子が乗っていることを説明すると、道を開けてくれたので、戦車を追い抜かすことができた。

CGR14に出た。7完31位で2743→2821(+78)。かなり良い順位だったが、B問題で詰まって1WA+19分もかけてしまったのが非常に痛い。31位はギリギリTシャツ確定ではなかったようで、さらに悲しくなった。

Aはソートしてヤバいところを後ろとswap。数列の要素がdistinctというのは優しい制約だが、なくても同様に解けるはず。面倒になるだけか。Bは平方数の2倍、または4倍のみがYES。最初は1より大きな2のべき乗のみがYESだと思っていた。今から思えば完全に頭が回っていない。Cは難しいが、priority_queueで一番低い山に積むのを繰り返すとよい。Dは適当に貪欲。

Eは解法ガチャで一発で当たりの $O(N^3)$ を引けた。今いくつ見たかとそのうちいくつを自力でonにするかの2次元DPで、自力でonにするものの連続している区間を一気に遷移して3乗。遷移の係数は、別の区間の石と混ぜて並べる順番のほかに、区間内の順番も考える必要がある。これは、区間の長さ $L$ のうち最初に置く場所を決めるとあとは左右に伸ばしていくしかないことから、どの順で伸ばすかを考えて $\sum_{i=0}^{L-1}\binom{L-1}{i}=2^{L-1}$ となる。この $\sum$ は消さなくても3乗に変わりない。

Fは、まず操作してよい辺を貪欲に操作してよいらしいことが感じ取れる。しばらく考えていたが反例が見つからないので、これは認めてしまうことにした。この反例を考えている過程で、結局アスファルトの量をならしつつ広げていってしまうのだから、適当な全域木を取ってもよいのではないかと考えた。サンプルを試したところよさそうなので、実装してしまうことにした。行きと帰りで操作できるか試すdfsは、1回だとアスファルトを持ち上げて下すケースに対応できないが、2回実行すればよさそう。これでpretestが通った。0ケースもあるので結構安心感がある。実際、システスも通った。

GはまずSCCする。強連結成分内にはたくさんのループがあって、2つのループの長さが互いに素なら1刻みでどのようなメーターの値も取れそう。ループとループをつなぐ余計な辺もまた別のループの一部であるからには、そちらも適当に周回しておけばよい。ループはたくさんあるので、適当にサイクル基底を取り（これはdfs木の後退辺がそれぞれループに対応する）、それぞれ長さを計算して総gcd（ $g$ とおく）を求めておく。 $g=1$ ならどんな $t$ に対してもメーターの値を自由に動かせる。

では1でなければ？このとき $\gcd(g,t)=1$ ならば $\bmod t$ の条件下で値を自由に決められる。さらに $\gcd(g,t)=h\gt 1$ のとき、 $s$ と $t$ を $h$ で割ることで $\gcd=1$ の場合に帰着できる。 $h\nmid s$ ならばNOだ。以上のことは実はすべて $\gcd(g,t)\mid s$ という条件にまとめられる。

ラノベを2冊読んだ。まず「D級冒険者の俺、なぜか勇者パーティーに勧誘されたあげく、王女につきまとわれてる」2巻。軽いセリフ回しが心地よい。それでいて途中かなり重いシーンがあって、落差にびっくりした。主人公がめちゃくちゃ強いのも好み。りいちゅさんの挿絵も非常に良い。

次に「やはり俺の青春ラブコメはまちがっている。」14.5巻。書下ろしストーリーが非常に良かった。これまでの積み重ねみたいなものを感じてエモーショナル。また、比企谷八幡と雪ノ下雪乃がちゃんと付き合っているようで微笑ましい。「い・ろ・は・す」と一色いろはがコラボしたのは記憶に新しい（一色いろはの誕生日である04/16のことだったようだ）が、~~そのコラボ短編も収録されていて非常にびっくりした。~~よくもまあ印刷が間に合ったものだ。折り込みチラシではこの本の表紙は「NOW PRINTING」となっていたが、案外これが原因かもしれない。いや、表紙データだけならすでに上がっているのが普通か？

2021/05/03追記：コラボは2年目だったらしい。収録されたのは2020年度版の短編で、2021年度版も新しい短編があった。以下にリンクを張っておこう。上が2020年度版、書籍に収録されたものだ。

www.i-lohas.jp

2021-04-26

週記（2021/04/19-2021/04/25）

04/19(月)

先週のぶんの週記を投稿してからの話。最後に書いていたARC117Cの最短コードは、エンコードするところでさらに更新できた。ord^5は天才的だが、tr RWB 012をするのでもよくて、ここで'R'はわざわざ置換しなくてもよい。結局tr WB 12になった。

月曜日の夜はサークルの解説会だ。今週からしばらくは新歓イベントのつもりで、MeetのURLを外部に公開する予定になっている。しかし肝心かなめの解説役がまだ1問・1人しかいない！僕も解説をしようと思って、ABC198のE問題を選んだ。ところで、この問題はマージテクで解けないだろうか？map<int,vector<int> >と持ってみて、mapのマージとvectorのマージの両方でマージテクを使うようなコードを書いたら、2ケースTLEしてしまった。テストケースの名前を見ると、スターグラフの時に落ちているらしい。なぜダメなのかわからないのでしばらく考えていたが、そのうちに椅子の上で寝てしまった。

首の痛さで起きる。今は諦めて一旦寝ることにする。布団に入ってから少しだけなろうを読んだ。土曜日に読み始めたと言及した作品だが、今はもう興味が薄れてきてしまっている。これの読了についてはあきらめることにして、ブラウザのタブを閉じてしまった。午前10時就寝。

午後6時と6時半の目覚ましでは起きられず、午後7時にようやく起床。相変わらず解説会用のスライドは手付かずなのに、残り1時間しかない。困った。とりあえずホスフィンに頼み込んで1問担当してもらうことにして何とか体裁を整える。自分はE問題の解説スライドを作る。ところで、マージテクで解くことについてはまだ諦めておらず、寝ている間に新たな方針を思いついていた。multimap<int,int>で持つというもので、こちらだとちゃんとACできた。そこそこ面白いと感じられるので、これもスライドに載せておこう。

なんとか完成して、解説会が始まる。10人以上が参加してくれていて、ありがたい限り。外部の参加者とサークルメンバーが半々くらいか？

まずホスフィンがABC198Cを解説する。直前に無理を言って作ってもらったとは思えない出来。この流れで僕も……！と勢い込んでE問題の解説を始める。まず問題文を読む。

「 $N$ 頂点からなる木が与えられます」

え？

初見の人もいるのに「木」は、ダメだろ。慌てて何とか説明をしようとしたはずだが、正直頭が真っ白になっていて何も覚えていない。サンプルに図がついていなかったのでマウスとペイントで書いたが、書いている間の微妙な時間が耐え難かった。何とかスライドを最後まで読んだものの、1ミリも伝わった気はしない。

最後にsotanishyさんによってF問題の解説が行われた。こちらは計算がゴツいものの、競プロをやっていない人にも伝わるような問題だったし、解説もそうだった。見返してみればD問題もプログラムで覆面算を解くといういかにも面白そうな問題だったから、こちらを解説しておけばよかったものを、なぜE問題というグラフ理論の用語がバリバリに使われた問題を選択してしまったのか……。

ECR16のABを解いて時間をつぶし、CF #716 div.2に出た。4完遅解きでひどい順位だった。

Aは平方数でない数があればYES。BはN^K。Cは難しい。必死に実験すると、gcd(N,i)==1なるiを集めてきて、総積が1にならなかったらN-1を外す、という感じのようだったので実装したら通った。gcd(N,i)==1なるiを集めてくることまでは普通にわかるべきらしくて、このとき総積pはgcd(N,p)==1を満たすから、p!=1のときはpを外す、というのがTLでよく見られた解法だった。pが1またはN-1であることも証明できるらしい。

inamori.hateblo.jp

DはMo's algorithmとSegment treeで書いたら当然のようにTLEしたので乱択。wikipediaからxorshiftをコピペして提出すると通った。そのあとE問題を考えながら30分くらい椅子に突き刺さって寝ていたが、ふと起きるとDがHackされていた。xorshiftが固定シードだったのを狙われたらしい。気づいた瞬間は乱択を落とす暇人にキレていたが、冷静になるとxorshiftの最初の30回くらいの値を見るだけで簡単に落とせることに気づいたので、反省。現在時刻をシードにしたmt19937で出しなおした。速度的にちょっと不安があったが、xorshiftと比べて悪化しているようには見えない。まあ同じループでlogオーダーの処理をしているので、そちらが支配的なだけか。

Eは、（コンテストの時はうろ覚えでここまではっきり名前がわかっていたわけではないが）トーナメントグラフの場合a->bという辺があるかどうかを比較関数にしてソートするだけでハミルトン路が得られる、という話を覚えていたので、その方針で考えてみることにした。これだと1つ目の質問は $n \log n$ 回必要で、 $9n$ と比較してあまり余裕はない。問題を解くにはハミルトン路においてどこまで戻れるかを求めなければならないので、2つ目の質問を $2n$ 回行うだけでそれを知らなければならない。適当に二分探索したら落ちたが、二分探索する前に「そもそも戻る辺があるか」を各頂点で1回かけてチェックしたらpretestに通った。

わくわくしていたらシステムテストで落ちた。解説を読むと、二分探索ではなく尺取り法をすればよかったらしい。これは非常に悔しい。思いつけてもよかったが、そもそも前提となるハミルトン路の作り方さえあいまいなままだったので、自信をもって考察を進めていくことができなかったということだろう。

午前2時くらいに寝落ち。

04/20(火)

午前5時半起床。布団でノクターンノベルズを読んでいた。

https://novel18.syosetu.com/n7518em/

ARC117Cがさらに縮んだ。3つおきに取るのと隣り合う2項を足して符号反転するのを行っていたが、3つおきに取ったとき、さらに隣り合う2項を足して符号反転するところまでやってしまうようにしたところ、コードの大部分を共通化できた。

また布団に戻ってなろうを読んでいたが、午後2時半くらいに寝落ちした。

https://ncode.syosetu.com/n5465fc/

午後9時半起床。競プロ典型90問のコンテストがスタートしていたのと、「えびまのお誕生日コンテスト 2021 Day 1」も始まっていた。

atcoder.jp

お誕生日コンテストの問題を読んでみたところ、どれも普通の問題のように見える。後から気づいたことだが、「お誕生日」の問題はDay 2に隔離されたらしい。言われて初めていつの間にか2日制になっていたことに気づいた。

A問題は解けそうなので布団でスマホコーディングした。答えを最大化しようとしたり、中途半端に修正したり、違う値を出力したりして3WA。Bはよくわからなかったのでまた布団をひっかぶってモゾモゾしていたが、しばらくしてなんとなく実験する気になったのでパソコンの前に移動した。実験するとフラクタルな構造になっているようだ。例えばK=3だと、3で割って2余るものや、9で割って6以上余るもの、27で割って18以上余るもの……等々は消えて、それ以外は残る。適当に実装してみたら一発で合った。解説によるとK進数として見れば示せるらしい。

さらにE問題が解かれていたので、読んだ。前から順に合わせていくことを考えて、バブルソートのように隣り合う要素を交換していくのかとも思ったが、いくらか飛ばして大きなものを後ろに持っていくように交換するとさらにコストが小さくなることに気づいた。それで実装してみるとACした。未証明。TLで見かけた説明だが、このような交換では互いにあるべき相対位置に近づいているので損していない、と考えると納得できそう。

D問題を読んだ。あるkについてA_i-A_j=k(j-i)、つまりA_i+ki=A_j+kjとなるペアを数える問題のようだ。うまくiとjを分離できているので、kを全探索することを考えたいが、これはできない。そこで最初の式に戻ってみると、kがある程度大きいときはj-i（の絶対値）が小さくなることがわかる。よって、平方根のあたりで分割して小さいほうを全探索すれば間に合う。A_i+kiの重複カウントにmapを使ったらTLEしたが、ソートしてランレングス圧縮する方針で書いたら余裕を持って通った。

結局4完。最初から真面目に出ていたらCも解けたのだろうか。解説を見ると、あんまり見たことがない添え字の持ち方をするDPのようだ。

論理学の履修制限について。結局04/16(金)までに履修登録したことが履修する必要十分条件となったらしい。僕はちょうどその金曜日に履修登録していたので、何とか滑り込めた。

競プロ典型90問のコンテストを埋め始めた。

競プロ典型 90 問https://t.co/Tqx135shuf
スレッドでコードゴルフの記録をしていきます。達成したByte数と使用した言語をツイートします。
— こたつがめ (@kotatsugame_t) 2021年4月20日

コードゴルフについては特に言うことがない。そもそも問題が簡単ではないので、適当なスクリプト言語でACして、コードゴルフの定石を手癖で適用していくだけの作業が多い。

004 Cross Sumは4e6個の入力と4e6個の出力を求められて大変だった。スクリプト言語は軒並みTLEして、PyPyで何とか通した。016 Minimum Coinsも想定解が1e8回のループを求めていて大変。こちらもスクリプト言語はTLEしてしまった。

朝方、TCB35の問題を解いていた。今回は念願の理論値を達成することができた。この週記が公開されるころにはイベントが終了しているので、ここに問題の感想を書いておこう。

Aは結構謎。Bはそこそこ難しい、と思っていたが、X座標が1、2、3で固定なので、Y座標も等差数列をなしているかチェックすればよかったのか。Cは全探索。Dは重複チェック。

Eはなもりグラフのループを求める。TechFULは再帰しすぎるとREになるイメージが強かったので再帰を使わないことにし、UFでループの最後の辺u-vを検出して、それ以外の辺を使ってu->vの経路長をBFSで求めた。実は再帰でのREについてはつい最近修正されている。このことを知ってはいたが、今回は安全側に倒したということ。ちなみに後ろのほうの問題では面倒になって問答無用で再帰関数を使っている。

【💡お知らせ💡】#コーディング #プログラミングコンテスト

これまでのTechFULコーディングバトルでお問い合わせの多かった、「深い再帰でRuntime Errorになる仕様」が、新コンパイラによって解消されました。

TechFULは日々皆様のご意見やご要望を受け付けております。^^
— TechFUL (@tech_ful) 2021年4月19日

Fは行ごとに見て列をデータ構造で持つのが思い浮かぶが、実は座圧すれば縦横2000に収まる。Gはグラフを作ってダイクストラ。Hは最大流。IはSCCしてDAGの先頭に来る頂点だけが候補。Jは1e5以下の素数9592個をbitsetで持ってxorしていく。

今日の競プロ典型90問・20問目は、これまでで最も短く書ける問題だった。dcの16Bがほとんど明らかである。これはぜひ最短コードを取りたい。提出先URLはそれまでの問題からの類推でわかるので、ojで提出するのとsleep 15を繰り返すシェルスクリプトを作っておいた。提出に成功するとojの終了ステータスが0になるので、そのときexitする。これを、問題が公開される予定の15時の5分前から動かしておくことにした。ところが、今日は14時53分くらいに問題が公開されてしまったようで、結局僕は2分くらい遅れて提出することになってしまった。

数理統計学のレポートを提出した。その過程で、先週土曜日に提出したレポートの計算が少し違っていることに気づくも、スキャンした原本はすでに捨ててゴミ箱の底にある。PDFファイルに何か書き足すという方法もわからないので、仕方なくもう一度筆記しなおしてスキャンし、再提出した。レポートといっても1ページなので、それくらいなら何とかなる。

午後7時くらいまでパソコンでTwitterを見ていたが、いつの間にか椅子の上で眠ってしまった。30分くらいして目を覚ましたが、これ以上の活動は不可能であると判断して寝た。午後7時半だった。

04/21(水)

消えた。

04/22(木)

午前6時半起床。非常に良い。

人の週記を読んでいて思うが、やはり解いた問題、あるいはコンテスト単位でも、リンクを貼っておくのがよいのだろう。以前の記事を書き直すことはしないが、以降はコンテストリンクを貼るようにしたい。

朝は典型90問のコードゴルフをしていた。寝ている間に、僕がツイートしているコードゴルフのリプライツリーに更新情報がいくつかくっついていたので、それを何とか取り返そうとしていた。更新したものをわざわざ書き込んでくれるのはうれしい。

そのあと、今日の午後からあるゼミのために教科書を読んでいた。発表ではないからと言って気を抜いていたら当日まで手付かずのままになってしまっていた。2冊本があって、そのうち僕がメインで読み進めるほうの本の内容は手元にあり、今日進めるはずの部分まではとりあえず読めた。すでにわからない箇所を発見してしまったので、その部分の発表は入念に聞いておきたい。そのほかの部分は、初回ということもあって難しくない。

しかし、もう1冊の本はそもそもコピーすら手元にない。先々週のゼミの顔合わせの時には教科書を注文しようかとも考えていたが、なんとなく放っておいているうちに2週間が経過してしまった。仕方がないので今日は山に登って数学科の資料室に行くことにしよう。

と思って出かける準備としてシャワーを浴びたりした後、数学科資料室の入室予約をしようとページを開いたら、昼間は職員の休憩のために閉まるらしく、午前中最後の時間帯の入室予約も終了してしまっていた。失敗！出かける準備は万端だが山まで登る必要はなくなったので、川内で食事をして、一応川内の図書館で探してみることにする。

今日は気持ちのよい青空で、気温もちょうどよい。冬と夏の間にある奇跡のような1日だ。

川内に行って食事していると、昼休みに突入したらしく、大学生協の前の広場が人でごった返していた。教科書販売の列もそれなりに伸びていて、かなり危険な感じ。そそくさとその場を後にした。そのまま図書館に行ったが、検索システムがちょうどメンテナンスらしく使えなかったので、数学書の棚を愚直に探索した。ゼータ関数の本がどういうジャンルに分類されるのかもよくわかっていない。結局「有名な関数」だったかのジャンル分けがされている場所にゼータ関数の本が並んでいたが、ゼミで読む本は見つからなかった。

pic.twitter.com/GdLOXpcuqf
— こたつがめ (@kotatsugame_t) 2021年4月22日

ゼミが始まった。手に入らなかったゼータ関数の本はイントロから積分をどっさりしていて、予習なしでは非常につらいものがあった。積分区間に無限が登場しているところの正当性など、何を示せばいいのか自分はよくわかっていないので、このままではいけないんだなあという気持ちになった。もう一方の本はそれに比べるとやはり簡単か。再序盤に1か所あったわからない箇所については発表を聞いてちゃんと解決できた。残りの部分は、今日は一生最大公約数を定義している。

ゼミが終わってからは履修登録の続きをしていた。単位的には今セメ以降何も取らなくてよいらしいが、気になったものをこれまで2つ履修登録しておいた。ほかに、数学科の7セメスターに開講される講義が複数あるので、それぞれチェックしていく。Classroomに一瞬だけ登録して講義資料を覗いたりした結果、「数学基礎論特選」というのを履修登録することにした。モデル理論？やらをするらしい。

3マスしか埋まっていない時間割を見ると動悸が激しくなる。何回も確認したし、卒業単位は十分確保してあるはずだが、やはり1年生で落とした分を必死に取り返した日々の記憶は色濃く残っており、時間割が埋まっていない状態が見慣れない。

今日は木曜日なので、論理学の講義があったらしい。講義動画を視聴してミニットペーパーを提出した。

ECR16のCからFを埋めた。

https://codeforces.com/contest/710

ABは月曜日に解いたが、そこから放置していたわけではなくて、ただただC問題が解けなかった。C問題の問題概要は以下。

奇数 $1\le n\le 49$ が与えられる。 $1$ から $n^2$ を1つずつ $n\times n$ の盤面に並べる方法であって、各行・各列・対角線の和がそれぞれ奇数になるようなものを1つ求めよ。

僕の解法はこのようになる： $1$ から $n^2$ のうち偶数であるものは $\frac{n^2-1}{2}$ 個あるが、これは奇数 $n$ の値によらず4の倍数である。偶数を4つずつ組にして、 $(i,j),\;(i,n-j+1),\;(n-i+1,j),\;(n-i+1,n-j+1)$ に置く。すると関係する行・列には偶数が2個ずつ、対角線と重なるなら対角線にも2個ずつ偶数が置かれる。よって最終的に各行・各列・対角線にある $n$ 個の数のうち偶数個が偶数となるため、総和は奇数である。

非常に難しいと思ったが、ホスフィンによれば魔法陣を作るとそのまま答えになるらしい。これが想定解だったらキレていたところだが、想定解はちゃんと構築しているので許した。

DよりEを先に解いた。たぶん良い。何回かWAを出したが、解法自体は正しかった。逆から見るやつだと思ったが、解説では頑張って順方向にDPしている。

Dは非常に難しい。 $a_1,\;b_1,\;a_2,\;b_2,\;L,\;R$ が与えられるので、 $L\le x=a_1 k+b_1=a_2 l+b_2\le R,\;k,l\ge 0$ なる $x$ の個数を答えよという問題。

まず $b_1\leftarrow b_1-L,\;b_2\leftarrow b_2-L$ として $0\le x=a_1 k+b_1=a_2 l+b_2\le R-L$ と書き直す。 $b_1\le b_2$ としても一般性を失わない。 $x$ についての式を1つにまとめたい。 $g:=\gcd(a_1,a_2)$ と置くと、 $b_2-b_1\not\equiv 0 \pmod{g}$ のとき2つの式が一致することがないことがわかる。そうでないとき、 $a_1 k_0+a_2 l_0=g$ なる $k_0,\;l_0$ を持ってくると、 $a_1 k_0\frac{b_2-b_1}{g}+a_2 l_0\frac{b_2-b_1}{g}=b_2-b_1$ となるため、 $a_1(k\frac{a_2}{g}+k_0\frac{b_2-b_1}{g})+b_1=a_2(k\frac{a_1}{g}-l_0\frac{b_2-b_1}{g})+b_2$ が満たされる。

元の式における $k,l\ge 0$ という条件をギリギリで満たすように、 $k_0\frac{b_2-b_1}{g}$ の値に $\frac{a_2}{g}$ を足すのと $l_0\frac{b_2-b_1}{g}$ の値から $\frac{a_1}{g}$ を引くのを同時に行って少し調整したり戻したりすると、 $x=\frac{a_1a_2}{g}k+b,\;k\ge 0$ となる。これで解けた。

何回か落ちて、テストケースを見ながら解いた。調整するあたりでひたすら失敗していた。

Fは文字数の総和の制約が小さいことに着目して、検索する文字列について部分文字列の先頭を全探索する方法と、線形時間でSuffixArrayを作って検索される文字列集合を全探索する方法のうち計算量が小さいほうを選ぶようにしたら通ってしまった。想定解はAho-Corasick。動的にする方法は、文字列削除については一度削除した文字列が二度と追加されないことを利用し、削除した文字列だけで問題を解いて答えから引くことで達成する。構築は僕としては初めて見るタイプの手法で、2べきのサイズの集合に対してAho-Corasickを作って、追加する際は2⁰、2¹、2²とまとめて2³を作る、みたいな感じにする。2進数の繰り上がりを考えているようなものだろう。文字列が移動する回数がlogで抑えられるというわけだ。クエリ平方分割よりオーダーは良さそう。

今日の典型90問はSCCをするだけの問題だった。C++で書いていたら最短を取られてしまったので、何とかPerlでSCCを実装して取り返したが、そこからさらにドンドン縮められていって、勝てない。そのうえ自分は定数倍バトルもしている。

サークルのバチャに出た。CF #503 div.1。

https://codeforces.com/contest/1019

Aは勝った時の票数を決め売って貪欲。Bは円の向かいの値と組みにして差を見ると、変化が連続（とはいえ-2、0、+2だが）かつ両端の符号が異なるため、関数のゼロ点を求める要領で二分探索できる。ここまで爆速で1位だったが、以降1問も解けなかった。Cは二部グラフのように塗ってみてダメなところを少し修正するもWA。Dは1点決め打って原点に移動させ、もう1点決め打った時に残りの点との外積を見ることを考えていたが、外積のような式の値を検索する方法がわからなかった。

午前零時くらいに布団に入ってなろうを読んでいた。午前2時くらいに寝落ちした。

04/23(金)

午前8時起床。ゴミを出した。布団に戻ってなろうを読みふけっていたら、学食にも行けなかった。

コードゴルフの更新が流れてきた。

atcoder.jp

uniqコマンドのオプション-uを知らなかった、あるいは忘れていた。調べると、ただ1回出現したものだけを抜き出すらしい。まさにドンピシャなオプションのようだ。便利な機能だが、Rakuにはそのようなメソッドはないらしい。uniq -dはrepeatedとしてRakuにも備わっているのだが……。そのこともあって対称差集合という解から抜け出せなかったのだろう。

今日の典型90問は和をgcdで割って3引く。Rakuで書くのがよさそう。dcより10B近く短くなった。

そのようなこともあって、何度かパソコンと布団を往復していたが、午後4時くらいに寝落ちした。本来はゴミを出してからすぐ二度寝する予定だったのに、なろうを読むのがやめられなかったせいで、このような時間に寝ることになってしまった。

04/24(土)

午前3時起床。TC、yukicoder、CFをすべて吹き飛ばしてしまった。TCはunratedだったようだ。

dic.nicovideo.jp

5719757レスに達したらしい。公式からも言及があって、スレが動作や負荷の確認に活用されていたことが明かされている。サービスにおける「普通」を極端に逸脱するようなもので不具合を起こさないか確かめることについては、例えば最近Steamで25000本以上のゲームを所持している人に影響のあるバグが修正されたことが話題になったことが連想される。また僕自身、AtCoderに対してbotに近い回数の提出をしているので、何かのUserScript・ツールの負荷チェックに使われたという話を聞いた気もする。

ついに目標へ到達、感慨深いですね。こちらのスレは運営としても動作や負荷の確認などに活用させていただいてました。12年間、おつかれさまでした。
>>3が理解できることが不幸について語るスレhttps://t.co/sBLFIgtcMN #nicopedia
— ニコニコ大百科 (@nico_nico_pedia) 2021年4月23日

そういえば先週分のyukicoderも解いていない。まとめて埋めることにした。まず今週分から。

yukicoder contest 292 - yukicoder

Aはよい。Bは愚直にやる。タグの「算数」が謎。Cはかなり難しいが、有名な事実ではある。何回かTLに流れてきて、つい最近も話題になっていた気がする。詳しい証明はわからない。Dはナップサック。Eは二項係数で書いてWolfram-Alphaに投げたら閉じた式になった。

$\displaystyle \sum_{h=0}^{H-1}\sum_{w=0}^{W-1}\binom{h+w}{h}=\binom{H+W}{H}-1$

これの求め方には、解説で紹介されている $\sum_{k=0}^m\binom{n+k}{k}=\binom{n+m+1}{m}$ を利用する他にも、考えているマス目を拡張して経路で考える方法もあったはずだ。少し考えてみた。 $H\times W$ のマス目を下に1段拡張してみる。その段に突き抜けてきた経路は、その経路が最後に右に進んだときの、進む前のマスまでの経路と一対一対応する。つまり、それ以降は1マス右に進んで、あとは下に突き進んでいくただ1通りしかないからだ。 $H\times W$ マスのすべてに対してそのような経路を対応させるには、 $W$ 列目からさらに1マス右に進むために右にも1列拡張するべきということになる。

さて、一番下の段に突き抜けてきたというのは、最後の移動が下移動だったということだ。一番下の段のすべてのマスについて総和を取ろうとしたとき、実はその段の一番右のマスに侵入する経路をすべて数え上げればよい。最後の下移動から先は右移動しかないからだ。最後に、 $H+1$ 行 $1$ 列のマスにたどり着く経路に対応するものが存在しないため、 $1$ 引くことになる。よって上記の式が得られる。

FはEに比べれば簡単。二次元累積和で、imos法の分と累積和の分で2回累積和を取るのはあんまり見ない気もする。

続いて先週分。

yukicoder contest 291 - yukicoder

Aから難しいが、ちゃんと考えると解ける。Bは最適っぽい行動が実際に最適になっていることがわかる。Cは、2020/11/30に解いたAOJ-ICPCの問題の系だと思って、かんプリンさんのユーザー解説の方法で解いた。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2336

Dは二部マッチング専用のライブラリを張ると頂点を毎回 $H+W+2$ 個作っても間に合った。 $O((H+W)HW)$ 。Eは超頂点という話を何度も耳にしていたので一瞬。まあこのような問題で超頂点を考えるのはかなり自然であると感じる。Fは解けなかったので解説を読んだが、解説がかなり不親切だった。必死に行間を埋めて、久しぶりに解説記事を投稿した。

kotatsugame.hatenablog.com

昼前に布団に戻り、しばらくなろうを読んでいた。生協の弁当を受け取るため、午後3時には起きている必要がある。午後2時くらいに寝ようとしたが、さすがにあきらめてそのままなろうを読んでいた。

午後3時になって、今日の典型90問のジャッジが公開された。考えていたコードを実装したところTLE。よく見ると $O(HW2^W)$ だった。大体9e9くらいらしいが、TL 8secだし、それ以外はよくわからないので、定数倍バトルをすることにした……と思ったら、値が0のときに遷移をスキップするだけで通った。5700ms。もう少しバトルを続けて、4200msまで落ちた。

これまではマスごとに見ていたが、行ごとに一気に見ることにした。これで計算量から $W$ が落ちるかと思ったら、部分集合全体の和が必要になったので落ちなかった。しかも遷移のスキップができないからか定数倍が悪化したらしく、いろいろいじって縮めつつ7000msくらいになった。そこでコードゴルフはあきらめたのだが、climpetさんによればちゃんとやるとRubyで通るらしい。ちょっと信じられない。

そうしている間に弁当が届いたので受け取り、午後5時に就寝。午後8時半に執念の起床。かなりつらかった。

第六回PASTの問題が公開されていた。ABを解いてちょっとゴルフしていたらABC199が始まった。

AtCoder Beginner Contest 199（Sponsored by Panasonic） - AtCoder

全完12位。EとFでかなり失速した。

Aはよい。FAこそ取れなかったものの、最初の提出が最短。BはRaku。CからはC++を使用した。Cはかなり面倒。本番は何も考えていなかったが、冷静になってみればこれがC問題で出るのはかなりびっくり。Dは1色決め打って残りは二部グラフ。うっかりdfsで最初に訪れる頂点の色を塗り忘れて1WA。Eはしばらく挿入DPが頭にチラついて悩まされたが、ただ先頭から決めるbitDPでよい。Fは行列累乗。

コードゴルフ。Aは先に触れた。Bは、Rakuにおいてはmin-maxとするよりもA-Bを全探索するほうが短く書ける。CはRubyで書いていたが、Perlに負けた。Dは手つかず。EはRubyでTLギリギリ、ほかにコードゴルフしている人がいないためよくわからない。Fも手付かず。

第六回PASTを埋め始める。

第六回アルゴリズム実技検定 - AtCoder

ABCDはよい。Eはひたすら面倒。3個掘り出して2個戻す、みたいなことをしないとならないかとも思ったが、普通にdequeのイテレータでeraseしても十分効率的なようだ。先頭と末尾のうち短いほうを動かしてくれるのだろう。よく考えたらdequeではなくlistでもよさそう、削除に時間をかけるかアクセスに時間をかけるかの違い。Fもよい。

Gは難しい。ある辺を見て、これがいつなら使えるかをセグメント木上の二分探索で求めるコードを書いた。解説は辺をpriority_queueに入れるというもので、かなり頭が良い。Hは2つのうちどちらからいくつ取るかを全探索する。よく見るやつで、面倒。Iはdpするだけ。Jは平均値を見るだけ。これがJにあるのはかなり謎。Kは購入金額 mod 100をdpの添え字にする。

Lは頂点集合を全探索して最小全域木。前のPASTでも見た……と思っていたら、今回はコストの計算がちょっと面倒。微妙な幾何要素。Mは区間をsetで管理して頻度をmapで管理する。かなり面倒だが、どうやら想定らしい。Nは比較関数を考えてソートするやつ。Mは木とそれ以外の辺に分けて、それ以外の辺だけ毎回計算するやつ。

コードゴルフについて。Aはめちゃくちゃ嘘解法が通っていてすごい。BはPerlで、/o/ではなく/ost/までマッチさせることで、インデックスを割り算したときに小数部分が出ないようにできる。CはRubyでArray#&。EはRubyだとTLEしたがCrystalでちゃんとDequeを使うと爆速だった。JはOctave。X-mean(X)はcenter(X)と書ける。

そのほかDFKNはRubyで適当に通してある。ILMはC++で書いたものが最短になっている。また、ABC問題で最速コードを保持している。

この問題追加ラッシュで、Shortest 1500問とFastest 600問を達成できた。

Shortest 1500 && Fastest 600 pic.twitter.com/1S6IilMhv2
— こたつがめ (@kotatsugame_t) 2021年4月24日

朝方はずっと日記を書いていた。溜めがち！

終わってから布団に入って少しなろうを読んでいたが、すぐ眠気が耐えられなくなって寝た。午前10時だった。

04/25(日)

午後4時くらいに目を覚まし、うっかり以前に読んだハーメルンを読み返し始めてしまった。止まらなくなり、そのまま午後6時まで読んでいた。今日は午後7時からAHC002があるので、もう二度寝できる時間ではない。

仕方なく起きて食事した。第六回PASTのE問題が縮められていた。Array#[]?を使った書き方をしたらREが出たので放置していたが、現在の最短コードにはそれが使われている。一体どういうことなのか、Crystalの環境は手元だとサブのノートパソコンにしかないので、引っ張りだしてきて確かめてみると、オーバーフローしているようだった。bytesで得られるのはUInt8型で、その関係だろうか。三項演算子の第二項で型が決まって、第三項がそれにキャストされる……など考えてみたものの、結局よくわからなかった。

atcoder.jp

AHC002が始まった。

AtCoder Heuristic Contest 002 - AtCoder

最初2時間は時間いっぱいdfsする解を投げていた。4近傍のうちポイントが高いマスに行くのは実は全然良くなく、それをするくらいなら4近傍を探索する順番を固定して見ていったほうがスコアが高くなる。時間内に見つかる解というのは、少し探索回数を増やしたくらいではほとんど変化しないことは確認していたが、コンテスト後のTLによれば、この性質を利用して探索時間を短くし、代わりに4近傍を探索する順番を4の階乗通り試すことでもスコアが伸びたらしい。

さて、4近傍を探索する順番を固定すると何がうれしいかというと、探索する場所が固まりやすいことのようだ。目先の利益だけ求めてふらふらさ迷い歩くと、いつの間にか盤面を横断してしまって片方を全然踏めない、ということが起こりうる。

ここで、「固定する」ということにとらわれていたのか、一定の方向に進むのを繰り返すことを考えた。右と決めたら右に、下と決めたら下に、できるだけ移動するようにして、進めない時だけ少しずれるがまた戻るという探索を実装しようとしたが、実はこれはかなり難しい。方向の履歴を見て決めるのはどういう決め方にするかよくわからないし、直前の方向だけ見ているとちょっとずれるつもりがその方向に驀進してしまったりする。dfsを何回かに分けて呼び出して、その時々でどちらに進むか決めるものも書いてみたが、結局制約からまっすぐには進めないので、ずれるときの処理で困っていた。今から考えてみれば、もし実装できたとしてもうっかり盤面を横断してしまいそう。

AHC001で盤面を分割していた人がいたことを思い出したので、その方針で実装してみることにした。これは探索する場所が固まっているのでかなりよさそうだ。先ほど諦めてしまった「一定の方向に進む」ことも、分割した盤面を並べるときに考慮することで実装できる、と考えていたが、結局このことは使わなかったし、実際にあまり一定の方向に進んでいるような感じはない。

適当に10x10マスのブロック5x5個に分割することにした。ブロックの区切りをタイルがまたいでいるとき、そこを経由してブロックを移動することはできない。よって、そうでないマス、つまり経由することでブロックを移動できるようなマスの組を探し、そういうマスが存在するかどうかでブロック間に辺を張ってみた。そうしてできた25頂点のグラフをdfsして、適当にハミルトン路をとる。以降はこれに沿って進んでいくことになる。

1つのブロックの内部は、dfsで全探索しても間に合うようだ。始点を決めて、そこからdfsする。終点としては（結局すべてのマスに対して計算結果を保存するものの）先ほどチェックした次のブロックに移動できるマスを考えている。そのようなマスそれぞれに対して最もスコアが高くなるような経路を探し、それぞれ1歩移動してブロックの境界を越えたものたちを次の始点として扱う。ちょっと変則的だが、ビームサーチしているようなものだと思っている。例えばこれが1通りしか経路を保存していないと、うっかり先に進めなくなってしまったりするのだ。

最後のブロックの終点は、ブロック内のすべてのマスが候補になる。なかなか実装に苦労したが、何とか1時間半弱で書けた。提出すると5e6点を超えた。時間にいくらか余裕がありそうだったので、ブロックの始点の数を制限していた部分を消して提出しなおしてみると、さらに2e5点くらい伸びた。最後のブロックの始点としてこれまでの最大スコアの経路だけ考えていたのを、他のブロックと同様前のブロックから境界を越えてきたものすべてでも計算するようにしてみると、さらに少しだけ伸びた。

分割するサイズもいろいろ変えてみようと思っていたのだが、ちょうど50の約数になっている必要があることもあり、ほかのサイズだとハミルトン路を求めるdfsかブロック内のdfsのどちらかに非常に時間がかかるようになってしまった。10x10はこのどちらもそれなりの時間で終了してくれる、なんともちょうど良い分割サイズだったようだ。

ブロックの始点としては現状1マスにつき1つだけ経路を保存しているが、この制限もなくしてみようと考えて実装した。しかしバグってしまいそのままコンテスト終了。終わった後もしばらく格闘して、なんとかバグは修正できたものの、スコアは逆に下がってしまった。

右下…… pic.twitter.com/IR502idECz
— こたつがめ (@kotatsugame_t) 2021年4月25日

ブロックとしてみれば、右上の始点から下に進み、あとはジグザグに埋めているような感じか。表示してわかることだが、ブロックの境目の取りこぼしがかなり多くて残念。

atcoder.jp

結果は5370372点で22位、パフォーマンス2707、レート794→1783(+989)。非常に良い。

そういえば、ハミルトン路を求めるときはスコアを何も考えられていない。この時、最初にやっていたように、できるだけ一定方向に進むような順序で探索してみると、次の画像のような経路が得られた。周囲をぐるっと一回りした段階で次のマスに進めなくなってしまったようだ。

おもしろ pic.twitter.com/KtBlHfySTT
— こたつがめ (@kotatsugame_t) 2021年4月25日

TCB35が終了した。理論値が僕を含めて3人いたり、賞金ボーダーの点数が理論値-18点だったりと、今回はみんな点数が高い。

2021-04-24

yukicoder No.1481 Rotation ABC

yukicoder.me

解説の行間がデカすぎる！

以下、解説ページを読んだものとします。行間を埋めます。

必要十分条件の証明について

操作が可逆であることに注意します。解説によれば、操作によって文字列 $S$ と $T$ が互いに移り変われることと、次の2つが満たされることは同値です。

文字A、B、Cのどれについても $S$ が含む個数と $T$ が含む個数が等しいこと
$S$ と $T$ のどちらに対しても操作が行えること

このうち、1番は明らかです。1番を満たすような文字列だけを考えたとき、2番が満たされれば文字列 $S$ と $T$ が互いに移り変われることを、 $|S|\;(=|T|)$ についての数学的帰納法を用いて証明します。

$|S|=|T|=3$ の場合は明らかです。 $|S|=|T|=k\;(\ge 3)$ のときに正しいとします。

$|S|=|T|=k+1$ なる $S$ と $T$ を考えます。 $k+1 \ge 4$ より、文字列中には3種類のうちいずれかの文字が2文字以上存在することがわかります。対称性より、そのような文字の1つを文字Aとします。

操作を繰り返すことで、あるインデックスであって $S$ と $T$ のどちらでもその位置の文字がAであるようなインデックスを作り、同時に削除することで文字列長を1減らすのを目標にします。もちろん、残った文字列に対しても変わらず操作が行える必要があります。

さて、まず文字列 $S$ を考えます。 $S$ に対して操作を行えるのですから、 $S$ の部分列としてABC、BCA、CABのいずれかが存在します。その部分列を対象として何回か操作することで、部分列としてABCが存在するようにできます。

文字の位置関係のみが重要なので、今見ている部分列以外のBとCのことをいったん忘れることにします。すると、 $S$ は次のようになります。Aの個数は適当です。

AAAAABAAAAAAACAAAAA

Bの左にあるAのうち、最も右にあるものを選びます。 $S$ は部分列としてABCを含むので、そのようなAは必ず存在します。選んだAと、残したB、Cに対して1回操作します。

AAAABCAAAAAAAAAAAAA

Aについての条件から、操作後のBとCの間にはAは存在しません。

Cの右にはいくつかAが存在します。そのようなAのうち最も左にあるものを選び、BCと組み合わせて2回操作し、BCA→ABCとします。すると、BとCの間にAが存在しないような状態を保ちながらCの右にあるAを1個ずつ減らすことができます。最終的に次のような状態になります。

AAAAAAAAAAAAAAAAABC

文字列 $T$ に対しても同様の操作をします。

さて、 $S$ と $T$ を同時に左から見て行って、初めて文字Aが出現する場所 $i$ を調べます。対称性から、先に $S$ にAが出現したと考えてよいです。 $S_i$ を削除しても、さらに右に部分列ABCが存在するため、変わらず操作できます。

$T$ に対して適当に操作することで、 $T_i$ に文字Aを持ってくることができ、さらに $T_i$ を削除しても変わらず操作できる、ということが示せます。現在の $T_i$ で場合分けします。

Aの場合

そのままでよいです。さらに右にABCという部分列があるため、削除後も操作できます。

Bの場合

さらに右にAABCという部分列があります。組み合わせてBAABCとなります。次のように操作します。

BAABC
BABCA
BABCA
CABAB
CABAB
ABCAB

Aを持ってくることができました。また、Aの削除後もCABが存在するので、操作できます。

Cの場合

上と同様に組み合わせてCAABCとなります。

CAABC
CABCA
CABCA
CACAB
CACAB
AACBC

Aを持ってくることができました。また、Aの削除後もACBが存在するので、操作できます。

以上で $|S|=|T|=k+1$ の場合が $|S|=|T|=k$ の場合に帰着でき、帰納法の仮定より $|S|=|T|=k+1$ でも主張が正しいことが示せました。

余事象の数え上げ

1つ目の条件を満たすが2つ目の条件を満たさないものは $|S|$ 通りです。これについても詳しく見ておきます。

AとBを並べた状態で、Cを新たに置くことを考えます。このとき部分列としてABC、BCA、CABのいずれかを含んではいけません。そのような置き方はどのようなものであるか、観察します。連続する同じ文字を1つにまとめることで、Cを置く前の文字列についてはABABAB...またはBABABA...の形のもののみを考えればよいです。

ABの場合

CAB
ACB
ABC

この場合ACBとするしかありません。つまり、すべてのCをAとBの間に置くことになります。

ABAの場合

CABA
ACBA
ABCA
ABAC

ACBAしか適しません。

ABABの場合

CABAB
ACBAB
ABCAB
ABACB
ABABC

すべて不適です。よってABABA以降も不適であることがわかります。

BAの場合

CBA
BCA
BAC

CBAとBACが適します。組み合わせるとCBACとなります。

BABの場合

CBAB
BCAB
BACB
BABC

BACBのみが適します。

BABAの場合

CBABA
BCABA
BACBA
BABCA
BABAC

すべて不適です。よってBABAB以降も不適であることがわかります。

ACBはACBAの一部である、と考えると、結局ACBA、BACB、CBACのみが適するということがわかりました。これらの形の文字列が何通り存在するかについては、両端の文字をどちらにいくつ割り振るかを考えることで求められます。具体的に、 $S$ に含まれる文字Aの個数を $cnt_A$ のように置くと、それぞれ $cnt_A+1$ 、 $cnt_B+1$ 、 $cnt_C+1$ 通りになります。ただし、ACB、BAC、CBAについては2回ずつ数えられているので、 $3$ だけ引く必要があります。

よって $(cnt_A+1)+(cnt_B+1)+(cnt_C+1)-3=cnt_A+cnt_B+cnt_C=|S|$ 通りになるとわかりました。

2021-04-19

週記（2021/04/12-2021/04/18）

04/12(月)

朝方、先週分の週記を投稿してからの話。この日から今セメスターの履修登録が始まったので、どんな講義が取れるのか一通り確認した。

数理統計学は3セメスターに開講されている講義で、当時は再履修が多すぎて単位取得上限に引っかかって取れなかったもの。今セメスター取ることにした。すべてオンデマンド型の講義なので、まあ負担にもならないだろう。いざとなったら落とせばよくて、取って損はない。

ほかに言語学と論理学もちょっと興味を惹かれる。しかし言語学のほうは毎週課題があって、そのために指定された教科書を買わなければならないようなので、取らないことにした。論理学は人気なので、定員の制限が怖い。水曜2限と木曜1限の2つのうちどちらにするかも含め、後日決めることにしよう。

3月のコードゴルフ大会の問題をJellyfishで解くコードの解説記事が公開されていた。Jellyfishの入門記事としても書かれているようで、非常に面白かった。

Jellyfish(esolang)の紹介

午前11時くらいに布団に入り、なろうを読みふけっていた。

昼頃、仙台レジャーランド一番町店の閉店情報が流れてきた。

俺本格的にwlwやれなくなるぞよ pic.twitter.com/VVHfN7E23z
— wwlww (@Hikaruwlw) 2021年4月12日

かなりびっくりした。日付が変わってもしばらく開店していることや、チュウニズムに台を拭くための濡れタオル（今は使い捨ておしぼりに変わった）が設置されていることなどを理由に、これまで3年間頻繁に利用してきた。僕はチュウニズムしかプレイしないので少し離れたSEGAでもいいが、ボルテや弐寺がメイン機種の人はさらに離れた店舗まで行かなければならなくなりそう。確かに最近たまに行っても全然人がいないという印象だったが、閉店してしまうとは……。

ずっとなろうを読んでいたが、午後4時くらいに寝落ちした。

午後10時起床。またずっとなろうを読み続けていた。ゴミを出さなければならないので、午前4時半くらいに切り上げて布団から出て食事した。

ゴミを出す前にExperimental Educational Roundというのを埋めた。18問あって、競プロを始めてすぐの頃にFだけ解いていたようだ。

4年半？ pic.twitter.com/vJM55dHCGD
— こたつがめ (@kotatsugame_t) 2021年4月12日

Aはよい。Bは誤差が怖いが問題文中の数字をそのまま使って出しても通った。CDもよい。Eは22ケース目でWAしてしまった。入力された点を中心とする六角形が存在するよう、入力に従って座標系が少し変わるらしい。解説についたコメントでもここでハマった人がたくさんいたことが見受けられた。

Gは2つの二項係数を1つの変数で計算しようとするとオーバーフローする。Hはちょっと考え込んだ。Iはよい。Jは「when the next number of sales is divisible by all numbers from 2 to 10」だから2519の時点でボーナスがもらえると思って1WA。KLMNもよい。Oは幾何ライブラリがあればベクトルの回転・足し算で簡単。Pは↓の記事を見て解いた。2018年の記事なのでコンテスト当時はなかったが、まあいいだろう。

つくばサイエンスエッジ2018/文京学院大学女子高校 - 「みらいぶ」高校生サイト

Qは三角錐と四角錐の体積を求めたあと、サンプルを使って五角錐の体積の計算式（係数）を求めた。Rはエスパーで解いたが、解説を見ると相手の真似をする戦略が取れるとあってなるほどという感じ。

このコンテストは全体的に面白くなかった。アルゴリズムを使うような問題がなく、またmodを取らせないことでオーバーフローに気を使わせるだけの問題も多い。

ゴミを出してからECR8を埋めた。Aは題意を把握するのに手間取った。BCはよい。Dは桁DP。Eは優先度付きキューとBITを使って、右上のマスから見たときに左下のマスになれるものを数える。Fは問題タグでフローであることを見てしまったのですんなり解けたが、コンテスト中に出たら解けたかどうか自信がない。

布団に入ってまたなろうを読んだ。午後1時くらいに寝落ちした。

04/13(火)

午後10時起床。またずっとなろうを読み続けていたが、午前2時半に最新話に追いついた。

https://ncode.syosetu.com/n4212eh/

先週からずっと読んでいた「プニキとはじめるリーグ運営　～野球ゲーム？作って運営します～」。非常に面白かった。代表となって会社を大きくしていく系の話として捉えている。

主人公はプログラミングができるわけでも経理や広報に詳しいわけでもないが、それらは会社の代表としての仕事ではないから別の人に任せるので問題ない。会社の方針を決めて責任を取ることや、会社の顔として取材を受けたり会見をすることが仕事であって、その意味で主人公には会社の代表となる才能がある……ということが書かれていた。そういう設定は「羽月莉音の帝国」を読んで以来の好物である。主人公の性格も好みであった。

起きてコードゴルフをした。2つ取られていたが、両方取り返すことができた。片方はdcで、もう片方はPyPyだった。PyPyのほうはRubyやPerlではもっと短くなりそうだったが、TLEしてしまう。ではCrystalならどうだろうと試してみることにしたが、ここで1つの発見があった。これまで入力をすべて読むのにはARGF.gets_to_endを使用していたが、言語アップデートで使えるようになったのか、`dd`で良いようだ。この更新が効くコードを探し、全部縮めておいた。

Rubyでmapを使いto_iを適用するとき、map &:to_iと書ける。しかし例えばto_i(2)を適用しようとしたときにmap &:to_i(2)とは書けない。&はあくまでSymbolをprocにするだけの糖衣構文であって、procにはレシーバと残りの引数を同時に渡す必要があり、procの第2引数だけを部分適用することなどはできないということだ。

一方Crystalではmap &.to_iと書く（コロンだった箇所がピリオドになる）が、to_i(2)の場合もmap &.to_i(2)と書けるらしい。Rubyの構文をCrystalに持ってくる際に新たな記法に変える必要性が生じて、その結果このような書き方が可能になった、ということが↓のページに書いてあった。これもコードゴルフで役に立つ構文である。

to_proc - The Crystal Programming Language

ラノベの新刊チェックをしていたら、「サイレント・ウィッチ」が書籍化することを知った。

kadokawabooks.jp

またなろうを1つ読んだ。逆行転生して株取引で儲ける話。

https://ncode.syosetu.com/n8435gw/

Qiitaで何か記事を書きたいと思い立ってしばらく調べていたところ、Jelly言語でABSを解いた記事を発見した。Jelly言語はTSGのコードゴルフ大会でしか触れたことがなく、日本語資料がほとんど見つからなくて毎回公式ドキュメントを必死に読んで書いていたが、なぜこの記事が見つけられなかったのだろう。かなり内容があって、よくわからない筆頭であったquickについても詳しく説明されているので、もし当時見つけられていれば非常に役立っただろう。

qiita.com

ECR9を埋めた。Aが信じられないくらい難読だった。Bはよい。Cはa+b<b+aという比較関数でソートするもので、何回か見たことがある。DはLCMの最大値が小さいことを利用して調和級数の要領でカウントする。Eは多項式のべき乗を二分累乗法で行う。Fはbitsetを使用したが、想定解では距離行列となることを利用して最小全域木を取っていた。頭が良い。

ECR10を埋めた。Aはまた難読。BCはよい。Dは適当に書いたら全然違うものをカウントしてしまった。Eは二辺連結成分分解。久しぶりに見た気がする。FはAGC013で既出、と思ったらAGC013の方が後のようだ。AGCのほうは解いてあるからそちらからコピペしてきても良かったが、これも練習だと考えて一から書いた。蟻が座標の昇順に並んでいなくてキレそうになった。そういう面倒さはいらない。それにしても問題名まで一緒であるというのはすごいことだ。

Problem - F - Codeforces

C - Ants on a Circle

昼になったので学食に行きがてら原付を点検に出そうと思ったが、家を出た瞬間雨が降り始めたので、原付を点検に持っていくのは止めにした。歩いて学食に行ったところ、学食は午後1時半でいったん閉店するらしく、食べられなかった。前のセメスターは午後2時閉店だったので、あんまり人が来なかったのだろうか。

AtCoder Jobsに登録し、インターンに応募してみた。インターンの募集は4社が掲載されていて、そのうち3社は機械学習の経験が必要だったので、残りの1社であるところのフィックスターズを選択した。プロフィールに書くプログラミング言語の習熟度について、C++とかPerlはもう4年くらい書いているが、それらはすべて趣味の範囲であるから、最低レベルになってしまう。しかし確かに競プロで身に着けた文法というのは限定的であるから仕方ないのかもしれない。ファイルの読み書きもおぼつかないのは言語を使えるとは言えない、と言われたらその通りである。

ECR11を埋めた。ABCはよい。Dは2点を取りその差を計算して重複カウントをする。Eはまあまあ面白かった。二項定理でシグマを1つ消すやつ。FはCHTになったのでうしさんのLiChaoTreeを貼った。LiChaoTreeはそのうち自前で用意する必要があるだろうが、まだアルゴリズムの詳細も知らない。

ECR12を埋めた。Aはよい。Bは難しそうだがシミュレーションしてよい制約。Cは、変える文字数の最小値を出力する問題をAtCoderで見たことがある。実際の構築も適当にやってよい。Dはありったけの1と偶数を1個以下か、偶数と奇数をそれぞれ1個以下、この2通りに絞られる。Eはbinary Trie。Fは10¹¹以下の素数の個数をカウントする問題になって、これはLibrary-Checkerにある。本当はアルゴリズムを学んで自力で実装しようと思ったのだが、かなり難しそうだったので諦めてうしさんのものをコピペした。

Library Checker

直近のECRは2回ともFで未履修のアルゴリズムが出題されており、かなり教育的であると感じられる。

ECR13のAからDまでを埋めた。ABCはよい。Dはこれも二分累乗法の1つである。Eを解こうとしたがWAで、テストケースを見てもよくわからなかったので諦めた。布団に入って少しだけなろうを読み、午後7時半就寝。

04/14(水)

消えた。

04/15(木)

午前4時起床。TROCを逃してしまった。午前7時くらいまでなろうを読んでいた。

kimiyukiさんによってoj-mini.pyが公開された。ojの機能を制限して単一ファイルに収めたものらしい。

github.com

コードを削ったとされているので、気になって読んでみた。可読性を損なわない範囲でさらに行数を減らせるならプルリクを送るべし、と言われているのでちょっと考えていた。1か所、より良い（と僕が思う）書き方ができると感じた所があり、他に2か所ちょっと気になるところがあったので、それらを書き換えたプルリクを送ったところ、マージされた。

Update oj-mini.py by kotatsugame · Pull Request #1 · online-judge-tools/oj-mini.py · GitHub

さらになろうを読み続けて、正午くらいに最新話に追いついた。

https://ncode.syosetu.com/n5295gq/

面白かった。やはり主人公最強は最高。女主人公なのはよいが百合は好きではないので、そのあたりの描写は読み飛ばし気味だった。百合であるという前評判の作品でも、お互いに想い合っている、くらいの軽い描写なら普通の友情との違いが判らずに読み進めるのだが、この作品は結構直接的な行為に及んでいる。

風呂に入ってAtCoder Jobsを確認したところ、応募したインターン先から返信があった。書類選考ということで、Googleフォームに必要事項を記入して送った。開発経験の有無を聞かれたが、全くないのでかなり絶望的。確かに3週間の短期インターンであるから、何も下地がない人間を採用しても碌な成果が出せないのかもしれない。機械学習の知識もない、ないない尽くしなのでもしかしたら面接に進めないかもしれない。

学食に行った。先日の経験を生かし、今日は閉店ギリギリに到着できた。ラーメンを食べた。学食でラーメンを注文するときは、まずレジの列に並んでお金を払い、出来上がるまで別の列で待つことになる。この2つの列は確かにややこしい。人に、その列はどういう列か質問された。新入生だろうか。

学食へは原付で行った。大学を出てガソリンスタンドに行き給油、そのあとバイク屋さんに点検のために預けた。ガソリンスタンドは交通量の多いところにあるので、いつもかなり緊張して走っている。いつもといっても、原付を購入してから18か月経つが、まだ3回しか給油したことがない。それ以外は交通量の少ない山道を走ってばかりなので、3車線ある道路などには全然慣れない。

そのあとはゲーセンに行くつもりだったが、なんとなく眠いこと、また軍手を忘れたことなどを理由にしてすぐ家に帰ってきた。

僕は寝ていて問題すら見ていないが、ECR107のG問題はTL 5secということもあって愚直が通ったらしい。risujirohさんのコードに$50の懸賞金がかかったと話題になっていた。期限は24時間で、結局誰もそのコードを落とせなかったのだが、懸賞金の$50はチャリティー団体に寄付されたようだ。

Hack risujiroh for $50 - Codeforces

布団に入っていくつかなろうを漁っていたが、どうにも文章が合わないと感じるものばかりだった。2時間くらいそのようなことをして、午後5時くらいに寝落ちした。

04/16(金)

04/15 午後11時に起床。自分で設定した日付が実際の日付を追い越したのはこれが初めてのことであるように思う。

ECR13のE問題を考えたが、どうにも解けなかったので解説でDPテーブルの持ち方だけ確認した。自分が優勝した状態から始める逆順のbitDPであったようだ。考えが凝り固まって、そういう発想は一切出せなかった。コンテスト中のsolvedが150人くらいいる問題が解けなくて非常に悔しい思いをした。

F問題を開くと、LiChaoTreeで直線を削除するクエリもある問題だった。「LiChaoTree 削除」で検索したらこの問題そのものの解説記事が出てきてしまった。もういいやと思って記事を読むと、解説ではクエリ平方分割の方針が想定解となっている、との情報が得られた。そちらについては見ている解説記事では触れられていないので、その方針で解くことにする。

しばらく考えていたがわからなかった。布団に入ったら寝落ちした。午前3時だった。

午前8時起床。TCO21のRound2に進出していた。レートが高い人はR1に出なくてよい、というやつらしい。存在を完全に忘れていた。毎年R1はABCよりも簡単な問題しか出ず、そのくせ全員Ratedなので、とんでもないレート変動になってしまう。parallelがあるが、出ないほうがマシ。

ECR13のF問題のクエリ平方分割解がわかった。今見ているブロックで削除される線分については、最初からLiChaoTreeに入れないことにする。今見ているブロックで削除しない線分についてはLiChaoTreeで管理して、いずれ削除される線分は1つずつ愚直に見ていけばよい。クエリ $N$ 個、ブロックサイズを $W$ とすると計算量は $O(\frac N W N\log N+NW)$ になって、これは $W=\sqrt{N\log N}$ のとき最小になる。W=500とかW=1000だとTLEしてしまったが、W=2000にすると通った。log(N)が思ったより効いていたようだ。

うしさんのLiChaoTreeはデストラクタがなく、この状態だとMLEしてしまったので、メモリを開放する操作を入れようとした。しかしポインタを辿ってdeleteするコードもTLEしてしまったので、ACコードではvector<Node>で管理し、しかもvectorは使いまわすようなコードを書いている。

atcoder.jp

AGC053Aが縮められていた。$^Tという特殊変数は、プログラム起動時のUNIX時間を表すらしい。これは現在およそ1.6e9くらいで、しかも書き換え可能なのでmaxの初期値として使用できる。この特殊変数を用いてさらに2問ほど縮めることができた。

月曜日に言及していた論理学の履修登録をしてみた。水曜2限のほうはClassroomで350人以上が受講しており、割り当てられた教室の定員334人をすでにオーバーしているので、何人かは履修登録できないことになるらしい。木曜1限はまだ120人くらいしか受講しておらず、教室の定員174人までまだ余裕があるため、こちらを選んだ。どちらにしてもリアルタイムで受講したり講義室に行かなければならない場合はどうせ単位は取れないので、1限でも問題ない。

4時間くらい週記を書いていた。また溜めっぱなしだった。

Classroomに論理学の講義動画がアップロードされていた。少しだけ聞いたところ、どうやらClassroomではなくISTUを使って資料を配布したりするらしい。そちらを確認したところ、ミニットペーパーの提出をする欄があった。どうやらリアルタイムで受講する必要はなさそうで、一安心。

昨日預けた原付の点検が終了したらしいので、受け取りに行ってきた。午後3時半くらいだった。家に原付を停めて、今度は自転車に乗ってゲーセンに向かう。先ほど原付で走った道路はすでに帰宅ラッシュか何かで込み始めていて、危ないところだった。大学近くの道路は、朝夕信じられないくらい込むので、できるだけ避けて運転するようにしている。

立ち食いそばを食べてゲーセンに入る。店頭に閉店の案内が掲示されているのを自分の目で確認したが、まだこの店が閉まるということに現実感がない。

(｀；ω；´) pic.twitter.com/V5fFg3Wkqi
— こたつがめ (@kotatsugame_t) 2021年4月16日

ゲーセンは03/23に行って以来3週間ぶりのようだ。新曲がいくつも追加されたり解禁されたりしていたので、埋めていた。途中ホスフィンと合流して食事に行ったが、夕方のそばがまだ腹に残っていて注文した分を食べきれなかった。ホスフィンとはその後もチュウニズムで遊んで、フルチェインも出た。

「赤壁、大炎上！！」でSSSを出した。6回くらいだったか、結構すんなり出た。「劉備軍の旗～～～！？」までAJで、あとは一所懸命擦ったり叩いたりしていた。何回かプレイしてみたところ、主に端まで手が届いていなかったり早く離してしまったりで抜けていたようだったので、丁寧に譜面を見ることを意識していた。最後の「勘弁してくださ～～～い！」は1-2くらいだった。これはかなりうまくいった方である。

赤壁、大炎上！！SSS pic.twitter.com/vMbVGm7hy5
— こたつがめ (@kotatsugame_t) 2021年4月16日

ゲーセンにいる間にyukicoderが始まっていたが、問題を見ていない。夜中にCF div.1もあるが、ひたすら眠いので出ないことにした。

ところが何となく眠る気になれなかったので、ECR14を埋めた。ABCはひたすらつまらない。Aは普通の問題に見えて、恣意的なコーナーケースが設定されている。Bはアルファベットの書体が指定されて、与えられた文字列が左右対称になっているか答える問題。Cは与えられた小数を指数表記に直す問題。本当にカス。解く価値は一切ない。Tutorialを見たら青とか緑が出題していた。レートを上げて出直してほしい。DEは典型だが、まあまあ面白い。Fは……よくわからん。全通りの答えを先に求めるという問題を出したかったのか？

ECR15のABを解いた。特に言うことはない。眠気に耐えかねて布団に入り、午前3時就寝。

04/17(土)

午後零時半起床。まだまだ眠いが、大昔に友達に貸した本を受け取るため、この時間に起きておく必要があった。午後2時、無事に受け取れた。

論理学の第一回講義のミニットペーパー提出は今日が期限である。講義資料を見ていたところ、教室の定員を勘違いしていたことに気づいた。確かに満席まで座れば174人だが、このご時世でそんな密な状態が許容されるわけがない。結果定員は大幅に減って90人。履修登録した時点ですでに超過していたようだ。

とはいえ、水曜1限のほうは倍率がもっと高くなっている。なので、このままこの講義を履修登録しておくことにした。ミニットペーパーには履修希望も含めたコメントを書いてください、とあったので、適当に書いておいた。自分のせいで卒業単位を集めている人が履修できないと罪悪感があるので、自分はこの単位が卒業のために必要ではないことも書いておいた。

続いて数理統計学に出ていた課題を終わらせた。初回なのでごく簡単な計算問題。立式後は計算機を使ってもよいらしいが、むしろそのほうが面倒に思えたので、手で書いた。特に問題なく提出完了。この講義の課題の提出期限は一律セメスター終わりなので、↓のようにずっと放置したまま何もせず終了してしまうことを危惧していたが、幸先の良いスタートを切れた。

課題の締め切りはとうに過ぎ去っていたようだ。結局何一つ提出しないまま終わってしまい、評価はDではなくN/A（？）だった。
週記（2021/02/01-2021/02/07） - kotatsugameの日記

今日は第二回日本最強プログラマー学生選手権がある。それまで30分くらい間が空いたので、ECR15のCDEを解いていた。Cは普通。Dはよくわからないが、サンプルが強めのようで、それに通るような場合分けをしたら通った。車に1回だけ乗るか、全力で乗りつぶすか、最後だけ歩くかしか考えなくてよい。Eはダブリングで全部計算できる。

第二回日本最強プログラマー学生選手権が始まった。Aからちょっと難しいが、YZ/X円より真に小さい整数が求まればよい。これはceil(YZ/X)-1==(YZ-1)//Xになる。49秒かかったがFAだった。

Bは対称差集合で、Rakuに専用の演算子⊖、あるいは(^)がある。ところが出力でちょっと躓いた。ただソートするとsetオブジェクト1つのリストのソートになってしまう。これだとsetのキーの順番は変わらず、ちゃんとソートされていない可能性がある。これでWAを出して、keysを付け加えてAC。

Cはちょっと悩むが、答えを全探索してよい。Dはなんだか見覚えがある。そちらは解けなかったが、今日の問題は順番が固定されているのでほとんど明らか。Eは回文のレベルをしっかり理解するのにかなり時間がかかったが、わかってしまえば文字列を半分に折っていくだけ。折る回数はlogのオーダーなので、愚直にやっても十分間に合う。最後に回文を故意に壊さなければならないことにはちゃんと注意しておく。

Fは行と列をそれぞれデータ構造で持つ。クエリを先読みして座圧しておき、個数と和をBITで持てばよい。最初数列の値がすべて0なのは良心か。Gを見てすぐ行列木定理が思い浮かんだのはいいが、必ず使わなければならない辺をどう処理するか悩んだ。これは実は悩む必要などなくて、先にくっつけて頂点を圧縮するだけ。modint、matrix、UnionFindと3つもライブラリを貼ったのでコード長が6000Bを超えた。コンテスト後のTLで、行列木定理を使うAtCoderの過去問が紹介されていたが、実はその問題は解いたことがない。僕が行列木定理を知ったのはPCK本選の過去問だった。

https://onlinejudge.u-aizu.ac.jp/problems/0314

無向グラフの全域木の個数を数え上げる問題に落ちる。これをググると行列木定理というものに行き当たったので実装したら通った。かなりびっくり定理だと感じる。こんなのPCKに出したって検索なしなんだから解けないだろ……。
週記（2020/12/14-2020/12/20） - kotatsugameの日記

Hは非常に面倒だった。まずグラフがN頂点N辺の連結グラフ、いわゆるなもりグラフであることを確認する。これはループ部分とそこから生えている木部分に分解できる。荷物配送は、ループを通るか通らないかで2通りに分けられる。

ループを通らないものについては適当に処理できる。解説ではLCAと木上のimos法を使っているが、僕はマージテクを採用した。LCAはライブラリになっていないし、そもそもたくさん木があってかなり面倒に見える。この選択はよかった。かなり実装が楽だった。

ループを通るものについては、ループ上の2点を連結にする問題になって、これはループのどちらを通るかで各荷物2通りの辺の張り方がある。2-SATやフローを疑ったが全然違う。ここで、どこか1か所を通らないと決め打ったとき、すべての荷物の辺の張り方が決まることに気づいた。ほかに考えるべきこともないので、この方針で突き進んでいくことにする。ループを割り開くと列に対する操作になって、適当なデータ構造を用いることができる。それぞれの辺についてそこを通る荷物の個数を数えることにすると、ある荷物における辺の張り方を変えるというのは、区間に対する足し算になる。通る荷物の個数が非ゼロであるような辺について、その重みの総和を取得したい。

遅延セグメント木で普通にやるとまずい。なぜなら、区間に対して作用した結果、通る荷物の個数がゼロの辺と非ゼロの辺両方が生じる可能性があるからだ。これは区間の更新に失敗したということになる。ところで、「区間の更新に失敗する」という文言には見覚えがある。

rsm9.hatenablog.com

segment tree beatsで実装できるのでは！？↑のページを読むと、区間の更新に失敗する回数が上から抑えられるときに役立つと書いてある。今回の問題では、通る荷物の個数が非ゼロからゼロになるような更新が何回あるかを考えればよさそうだ。~~注目している辺を通る荷物の個数をゼロにしながらループをぐるっと一周するのだから、これは各辺についてちょうど1回である。抑えられた！~~嘘である。初期状態で0-1、2-3、4-5など1つ飛ばしに辺を使用している場合、そのような更新はO(N^2)回ある。

コンテスト中はこのことに気づかず実装に入った。そもそもなもりグラフの前処理から実装が面倒だが、何とか実装しきってサンプルを合わせた。ACLを張り付けているので7000B超え。提出するとゆっくりゆっくり実行が進んでいく。それに合わせて自分の心拍数も天井知らずに上がっていく。ジャッジにはかなり時間がかかったが、一発でACできた。

結果、全完して3位だった。僕を含め上位3人は全員同い年なので、かなりエモい。エキシビションに参加できるらしい。しばらく時間が空いたので、解説を読んだりコードゴルフをしていた。

Hは非ゼロの辺の重みを求めるのではなくゼロの辺の重みを求めることにすれば通常の遅延セグメント木で実装できたらしい。そのようにして提出すると最短コードになった。

コードゴルフについて。Aは最初に提出したdcの7Bが最短。解説にも同じコードが書かれていて面白かった。Bはコンテスト中のコードを少しだけ変えた。この辺りは実行してみながらでないとわからず、コンテスト中にそのようなことをする暇はなかった。CはAWKかと思ったが、普通にdcで書けた。Dはコンテスト中にdc 24Bを出し、さらに数分使って縮まないか試していたが、縮まなかった。

エキシビションは画面をYouTubeで配信しながら参加した。今見返すと、喋ろうと思っていたことの殆どは言葉になっていない。「あ！」とか「ええ〜」みたいな、なんの意味もない音を発するのが精々だったようだ。

heno239さんも配信していた。E869120さんは後日、編集した画面録画をTwitterに公開した。

www.youtube.com

昨日行われた「第二回日本最強プログラマー学生選手権」エキシビションの動画です。皆さん是非ご覧ください。 pic.twitter.com/zamQz8MC4H
— E869120@公開アカウント (@e869120) 2021年4月18日

FAならば点数2倍、というルールをほとんど無視していたのがよくなかった。また一番のプレイミスとしては、B問題のWAを終盤まで放置していたことが挙げられる。これは、問題に対して少し面倒であるという印象を抱いていたため、どこがWAなのかすぐには見つからないだろうと考えていたこと（実際はそうではなかった）、また序盤の問題であるからすでにFAは取られているものと考えていたこと（順位表を見ればまだ解かれていないのは分かっただろうに）の2点が理由であった。唯一解かれなかった問題、Semi Common Multipleは非常に難しい。そもそもこれを15分で解けと言われて解ける人も限られるのではないだろうか？僕は無理だ。考察も覚えていなかった。

コンテストが終了してからはずっとエゴサをしていた。ABC過去問から出題されるのは僕にかなり有利な戦いである、という言説には同意できる。フォロワーが50人以上増えたのにはびっくり。

問題文読んでるの？みたいなコメントが結構あったんですが、まともには読んでいないです。
普段のコンテストだと「問題文を読む→題意を把握する」というステップを踏みますが、ABCの過去問だと問題文の文面から題意を思い出せます。この違いはかなり大きいです。
— こたつがめ (@kotatsugame_t) 2021年4月17日

結構疲れているのでTCOもCSAもサボり、ラノベを読んでいた。まず「超高度かわいい諜報戦」。設定はよい、が、ストーリーはあまり好みではない。主人公の陰キャオタクへの擬態が完璧かつ徹底的すぎてむしろ読んでいてげんなりした。あと誤字や脱字が多い。

次に「精霊幻想記19」。前の巻で主人公が重傷を負い、この巻は代わりにヒロインが頑張る話。ストーリー上必要なのは理解できるが、本能は主人公の無双を求めている。ヒロイン等は敵を圧倒できているわけでもないので、もどかしさがすごい。次の巻からまた主人公のバトルが見られるらしいので、そちらに期待したい。

さらになろうを1作読み始めた。2時間半くらい読んで、午前7時半に寝落ちした。

https://ncode.syosetu.com/n7796fc/

04/18(日)

午後3時、目を覚ます。まだ眠いのだから二度寝すればよいのに、そこから3時間なろうを読んでいた。

途中、昨日のエキシビションのE869120さん視点の動画がアップロードされた。また、昨日のD問題が-1Bされた。やはりO9^7+を2回書くのは長かったようだ。自分でもどうにかしてまとめようとしていたつもりだったが、スタックの一番下に入れておいて必要になるたびに持ってくるだけで-1B。なぜ気づかなかったのだろう。確かスタックの一番下に押し込むコードは書いていた気がするが。

午後6時半くらいになってさすがに眠気がマズいことに気づいたので寝なおした。午後8時半起床。食事してARC117に参加した。

Aは面倒だがまあよい。Bはちょっと難しいがちゃんと考えるとわかる。Cは変換テーブルをどうにかして簡単な式で表せないか考えるのは典型で、ガチャを回して一発で(-a-b)%3が出たのは大当たり。二項係数 mod 3を普通のmodintと同様に計算しようとして0になったのでしばらく悩んでいたが、そういうときの定理があることを思い出した。しかし「二項係数 mod」で検索してもmod 1e9+7しか出ない。最終的に「二項係数偶奇」でLucasの定理にたどり着いた。Dは直感的には直径の端から端まで移動しつつほかの頂点を訪れる感じになる。順位表を見ると結構WAが出ているようだったのでしばらく迷っていたが、ええいままよと提出したら通った。証明：AC。

そのあとEを考えながら念入りに椅子を温めていた。まず全探索するコードを書いてみた。当然TLに間に合わないし埋め込みするのも時間がかかりすぎるようだったので、今度はvalidな移動における累積和のヒストグラムを全探索することを考えた。これもいろいろ場合分けしてすべてのvalidな移動を検出できるようになったが、やはり間に合わないようだ。残り10分くらいになってFを読んで牛ゲーだと思ってちょっと考えていたが、やっぱりダメだった。

結果は4完速解きで28位、パフォーマンス3033、レートは2670→2712(+42)。ずっと同じレート帯をウロウロしている。

ここ最近のレート変動です pic.twitter.com/czHUjT59ik
— こたつがめ (@kotatsugame_t) 2021年4月18日

コードゴルフ。A問題は、1..A * sum(1..B)と1..B * -sum(1..A)を出力するのがかなり頭がよい解法。B問題はPerl。sort{$a-$b}glob`dd`が`dc -e?f|sort -n`になるようで-3Bされた。CはN=3k+1のとき0番目、3番目、……、N番目を取り出したN=k+1の列と同一視してよいということを利用したコードを目にして、それを縮めた。これはなぜかというと、comb(3k,1)≡comb(3k,2)≡comb(3k,4)≡comb(3k,5)≡……≡0 (mod 3)だから。適当にPerlで書いていたらBWRを012のどれかにエンコードするところで更新された。

2021-04-12

週記（2021/04/05-2021/04/11）

04/05(月)

午前9時半起床。

二度寝するべきだとは思っていたが、寝落ちする前に読んでいたノクターンノベルズの続きを読み始めてしまい、そのまま止まらなかった。正午、読了。

https://novel18.syosetu.com/n7640gf/

主人公とハーレムメンバーのバランスのとり方とか、主人公の優しさが良さげに描かれていて良かった。

そのまま他の作品を漁って、2つ読んだ。こちらは完全にエロに振り切っていてストーリーなどないようなものなので、特に感想もない。題名も書かないので気になる人はリンク先（R18サイト）に飛んでほしい。

https://novel18.syosetu.com/n6275gw/

https://novel18.syosetu.com/n8082gs/

午後1時半ごろ寝落ちして、午後8時ごろに目を覚ました。ツイートを確認すると午後6時頃に少しだけ覚醒していたようだが、特に何もせずまた寝たようだった。

食事して週記を書いた。また数日分溜めていたので、午後9時から作業に入って投稿したのが午後11時半だった。

ECR2を埋めた。Aは不快。BCは普通。

Dは幾何で、2円の共通部分の面積を求めよという問題だった。ライブラリになっていなかったので、この機会に作っておくことにした。2円の交点を求めるライブラリはあったが、その点から角度などを復元するよりは処理自体をコピーしてきたほうがよさそう。それぞれの円に対し、2円の交点と円の中心からなる扇形の中心角が求まれば、そこから扇形の面積と三角形の面積が計算できて……というやつだ。

ところが落ちてしまった。テストケースを見ると、ほんの少しだけ重なるときに誤差で落ちているようだ。そこで、以前は角度を求めるのにacosを使用していたところを、asinで求めることにした。asinのほうが精度が良い、という話を最近のICPCで聞いた気がする（が、実際のところはよくわかっていない）。ほんの少しだけ重なっているという仮定、より一般にacosで求めたい角度が直角より小さいことが分かっていれば、3辺の長さから求めた三角形の面積（仮定から、角度を使用して求める符号付き面積と一致する）を使用することでsinの値がわかる。これで試してみると、確かに少しだけ誤差は減ったようだが、まだACにはならない。

最終的にdoubleをlong doubleにしたらacosのままで通った。つまらない。今回はdoubleをlong doubleに置換したが、より汎用的にするべく幾何ライブラリにusing Real=doubleと書いてdoubleだった箇所をすべてRealにしておいた。今回のような場合はusing Real=long doubleに書き直すことになる。

Eはマージテクで、Fは解けなかったので解説を読んで通した。二部グラフであることを巧妙に使っていて面白かった。

そういえば、汎用的なグラフ構造体というのはいつか作りたいと思っていたライブラリの一つである。これの設計に関して考えていた。メンバ変数の名前が決まっていて、ほかに必要な情報も持てるようなedge構造体だけ毎回書いて、グラフ構造体自体は常にvector<vector<edge>>で持つ、というものを考えたが、kimiyukiさんによればこれは汎用的なグラフ構造体とはならないらしい。具体的には、辺を陰に持ちたかったり、隣接行列で持ちたかったりする場合に困るようだ。それはそう。

上の設計ではedgeについて抽象化していたが、ここをvector<edge>について抽象化する（隣接リストを舐めるイテレータを作る）というのが良さげならしい。そういう方針で作成されたグラフ構造体についての議論は以前TLで見たことがある気がする。

ECR3を埋めた。ABCDは普通。Eは見た瞬間最小全域木+オイラーツアー+LCA+RMQの解法が思い浮かぶが、実装が嫌でしばらく逃避していた。RMQ以外はライブラリになっていない。そういったことをツイートすると、第2回PASTのO問題ではないかという指摘が来た。見てみると全く同じ問題だったので、コピペしてAC。並列二分探索による解法は当時感動していた気がするが、時が経ち、すっかり忘れ去っていた。Fはセグメント木上で二分探索。

Problem - E - Codeforces

O - Variable Spanning Trees

ECR4のAからEまでを解いた。ABは普通。Cはかっこの対応が一意に定まる。Dは幅0の区間をわざわざ削除してしまい1WA。Eはどこかで見たことがある。

Fを開いて、解法自体はすぐわかるものの、復元があって実装が辛そうだったので今日は止めておくことにした。布団に入ってまたノクターンノベルズを読んでいたが、午前11時ごろ寝落ちした。

04/06(火)

午後4時半起床。そのまま夜まで布団でノクターンノベルズを読み続けていた。

https://novel18.syosetu.com/n9485dy/

↑これはたこノすけさんにオススメされたものだが、50話くらい読んで放棄してしまった。

https://novel18.syosetu.com/n8462gt/

サークルのバチャに出た。CF #516 div.1。途中30分くらいこどふぉが落ちていて非常に厳しい気持ちになった。問題はvjudgeから見られるが、実装まで済ませた問題が提出できないのは辛かった。

Aはギャグ。未証明で通した。バチャ後の反省会で知ったが、回文の両端の文字が等しいことに着目すれば証明できる。文字列の文字をソートしたものが答えだが、これは回文の両端の文字になりうるペアすべてが、実際に回文の両端の文字になっているので、最大。

Bは左右の移動が打ち消しあった回数を持っておけば、どちらにどれだけ余分に移動しているかはスタート地点と現在地の座標の差から計算できる。打ち消しあった回数で01BFSをした。ほかの人は左右に移動した回数の和で01BFSしていたようだ。min(L,R)*2+abs(y-sy)=L+Rが成り立つから、L+Rで01BFSしようとmin(L,R)で01BFSしようと変わらない、ということだろう。他にも、LとRでそれぞれ01BFSした人もいた。変に遠回りすることでLを増やしてRを減らす、なんてことはできないから、これも正しい。

Cは二分探索っぽくやる。2^29<10^9<2^30なので、最初の1点だけは一番端に固定する。また、X軸から少しだけ浮かせておくことで、座標が1しか離れていない2点の間を通るような直線が簡単に引けた。

コンテスト後にDをupsolveした。答えとなる値を決め打つと、それがminとかmaxの1つの引数になるので、探索する区間を適当に分割してminやmaxを消し、あとは頑張る……というようなことを考えていたが、どうにもならなかった。特に単調性があるわけでもないし、割り算が出てくるのでその商ごとにまとめて見ることでさらに区間に分割しようとしたが、floorはともかくceilのほうがよくわからなかった。解説はかなり頭が良い。O(min(n^2,k/n))だが、僕の実装だとO(k/n)のほうにlogがついてしまった。k/n<1e7という場合分けだとTLEして、n>2e4にしたらACした。

このlogは、(d+1)a+db=1なるaとbを1組見つけるために使った拡張ユークリッドの互除法によるものだが、冷静になれば(d+1)-d=1なのでa=1とb=-1が必ず解である。これでちゃんと線形になって、試してみるとk/n<1e7の場合分けでも通った。サボりすぎ。

最近はレトルトカレーを食べている。実家でよく母がやっていたように、カレーの皿を洗う前にはティッシュで汚れをある程度拭き取っている。実家では不要になった肌着などを使っていたが、そんなものは保管していない。カレーに限らず、汚れが多い皿は拭き取ってから洗う、というのは重要な典型テク。

またノクターンノベルズを読んだ。

https://novel18.syosetu.com/n5258gt/

昨日放置したECR4のFを実装した。そもそもの実装がつらかったのと、さらに円周上をどちらに移動するかの符号を合わせるのに苦労したが、サンプルが通ったものがそのまま一発ACだった。

ECR5を埋めた。ABCは普通。Dは尺取り法。Eは商ごとにまとめて見るやつ。Fは文字列を'$'などを間に挟んですべて連結した文字列を作り、それの接尾辞配列と高さ配列を計算して、高い順に要素をマージしていく感じでできる。ただこれだと全体で2回以上出現する文字列に関してしか計算できないので、1回だけ出現する文字列に関しては別に計算する必要がある。ここの計算を間違えて2WA。

ECR6のAからEまでを解いた。ABCは普通。Dはオーバーフローで1WA。10⁹を4倍してしまった。2倍して2倍する、という形で書かれていたので気づけなかった。Eはオイラーツアーして区間set区間bitwise ORの遅延セグメント木。

せっかくなのでオイラーツアーのライブラリを作っておくことにした。今回必要なのは辺属性ではなく頂点属性。昨日考えていたグラフ構造体をいよいよ実装して、それを使って作ろうかと思ったが、何回もクエリに答えるため構造体が必要で、結局ほかのライブラリと同様オイラーツアー構造体にadd_edgeを作ってグラフを作る形になった。

library/euler_tour_vertex.cpp at master · kotatsugame/library · GitHub

Fは解けない。布団に入ってノクターンノベルズを読んでいたら午前7時半ごろ寝落ちした。

https://novel18.syosetu.com/n8141gc/

04/07(水)

午後2時半起床。寝落ちする前に読んでいたものをそのまま読み続けて、読了した。

https://novel18.syosetu.com/n8141gc/

かなり歪んでいて、心情的には理解できないが、そういうものに触れてみるという点では良かった。

他の作品をいくつか漁ったが、だいたいは少し読んで投げ出してしまった。1作だけ読了。

https://novel18.syosetu.com/n9412dj/

そうこうしているうちに夜になったので、サークルバチャに参加した。CF #511 div.1。

Aは誤読して1WA。削除しなかった要素のgcdが、削除した要素のどれよりも大きくなる必要がある、という風に読んだ。正しくは、削除しなかった要素のgcdが最初の全要素のgcdよりも大きくなること。こちらだと、最初に全体をgcdで割ることで、総gcdが1でないような部分集合のうちサイズが最大のものを計算する問題になる。もっと言えば素数pで割り切れる数列の要素の個数をpそれぞれに求められればよく（p|gcdとなるような部分集合のサイズとなる）、これはエラトステネスの篩の要領で各数に対して素因数を1つ求める前計算をし、O(log A)で素因数分解すればカウントできる。なんとなく怖かったので同じ値の要素をまとめて計算したが、別にそのような必要はない。

Bは気合いで場合分け。1x6が必ず埋められるので、縦横をmod 6で考えることにした。2x5や3x4が埋められるのは結構非自明な構成だが、運よく手で作れた。他には、2x2は1つも入れられないが2x8だと埋められるとか、2x3は2マス空くが8x3や2x9だと埋められる、1x2も7x2も2マス空くが13x2だと埋められるなどの処理が面倒だった。書いていて発見したが、僕のコードは7x8で落ちるようだ。7x2と同様に2マス空くと思っていた。

Cは頑張る。グループのvalueの和がpであるような分割（pによる分割と言うことにする）が可能であることの必要十分条件は、分割の仕方が一意であることに気づくと、全体のvalueの和（sumとおく）がpで割り切れて、かつ部分木のvalueの和がpで割り切れるような頂点の個数がsum/pに等しいことだとわかる。このとき直ちに、pによる分割とq|pによる分割があった場合、pを経由してqの分割が作れることがわかる。

あとはpを全探索。ただ毎回チェックすると間に合わないので、sumを素因数分解して、素因数ごとにbitsetでチェック結果を持っておき、具体的なpに対してはpを素因数分解してテーブルをbitwise ANDすることにした。すべての倍数に対して遷移するDPを書こうとしたが、よくわからなかったので、pとしてありうるものを列挙した後2乗かけた。これはsumが高度合成数のとき最大で26880²ステップくらいになりそうだったが、通った。

解説は頭がよく、コードも簡潔ですごかった。sum/pに着目する。s_uを、uを頂点とする部分木のvalueの和とすると、p|s_uとsum/gcd(sum,s_u)|sum/pは同値になる。sum/p<=nなのでsum/gcd(sum,s_u)<=nとなるような頂点だけ考えればよく、個数のカウントやDPの遷移も添え字がnまでなので調和級数の要領でできるというもの。

またノクターンノベルズを読んだ。

https://novel18.syosetu.com/n7438gs/

溜めていた日記を書いていたら午前5時くらいになった。広義明日は午前10時から学科ガイダンスがあるので起きなければならない。まだ途中までしか書けていなかったが切り上げて布団に入った。しかしそれからもしばらくなろうを読んでしまい、結局寝たのは午前7時頃だった。

04/08(木)

午前10時起床。学科ガイダンスに参加する。

4年目ということもあって特に目新しいことは言っていない気がする。院試の日程とか、インターンとかに触れられていた。資料もアップロードされるので、無理やり起きて出る必要性は感じられなかったが、出なかったら出なかったで自分の知らない情報があるのではないかと心配になるはずだから、出ておくべき。

途中で昨日の分の日記を書いていたら、バチャのB問題が落ちることに気づいた。自分でHackしておこうと思ったが、コンテストが終了したのでそのような機能はないらしい。とりあえず修正したものを投げておいた。

ガイダンスは時間が少し余ったので近況報告をしようという話になり、数人喋っていた。僕も何を話そうか考えていたが、結局すぐ解散になった。謎。こういう交流イベントは心臓に負担がかかるが、それでも今は久しぶりに（カメラ越しに）顔を見た同級生が懐かしいという思いが強い。僕はカメラオフだったので、一方的に観察していたことになる。

午後1時から4年次ゼミの初回、初顔合わせがある。それまで2時間くらいあるから寝ておこうかとも考えて布団に入ったが、万が一寝坊すると大変なので、なろうを読みつつ起きておくことにした。

ゼミが始まった。自己紹介のタイミングで皆カメラをオンにしていたので僕もオンにしたが、パジャマだし洗濯物を片していないしでもう大変。自己紹介については、競技プログラミングから数論に興味を持った……ということを言った。プログラムで問題を解くとは何をするのか？ということを聞かれた。これはよくある質問だが、いまだに何を喋ればいいのかわからなくなる。今回は「AのB乗を普通にB-1回掛け算するより高速に求められる方法がある」という話をした。といっても二分累乗法の説明をしたわけではなくて、そうやってプログラムをアルゴリズムの力で高速化する競技である、とだけ言う感じ。

今年読んでいく本を決める。「Introduction to Analytic Number Theory」と「Multiple Zeta Functions, Multiple Polylogarithms and Their Special Values」の2冊の候補があって、それぞれグループを作る。前者を希望したところすんなり通ったので、それをやっていくことになった。3人チームで順番に発表を担当し、僕はその3番目だ。ゼミ生同士の連絡手段をどうするかという話になって、博士課程の人の主導でLINEグループが作られた。SlackとかDiscordを提案しようとしたが、そういうところで目立つのもどうかと思い止めておいた。

読む本を手に入れなければならない。僕が読む本についてはネットにPDFが落ちていると言われ、探してみると確かにあった。しかしこれは……いいのか？あんまり触れちゃいけない話題なのかもしれない。もう1冊はないようなので、また後日入手方法が知らされるか、あるいは自分でコピーしてくるかしなければならないだろう。

library--/Introduction to Analytic Number Theory (1976) - Apostol.pdf at master · isislovecruft/library-- · GitHub

ゼミが終了したので即座に布団に入り、午後3時から午後8時まで寝た。起きたらりんごさんの配信が始まっていて、TLでその話題がたくさん流れてきた。

布団でなろうを読んだ。「金で買えないスキルはない　～『外資系投資銀行に勤める俺が、異世界転生して金の力でチートする』～」。

https://ncode.syosetu.com/n7340da/

かなりテンポよく進んでいった。意図的にリーマンショックを引き起こすのは面白かった。ところで、美醜の基準が違うのでヒロインは異世界ではとんでもない醜女だとされている、という設定はいらないと思う。周りの反応が読んでいて不快だった。

続いてもう1作。「スゴいカードを拾ったので株式投資で資産家目指します」。

https://ncode.syosetu.com/n6412fu/

面白かったが、自分がこれを面白いと感じてしまうことがちょっと信じられなかった。お金が無限に使えるようになったので株を買い漁って財閥（コングロマリット）を作る、という話。経営の話は一切出てこなくて、主人公が社会的地位を得たり有名になったりお金を使ったりするシーンが延々続くが、それでも面白いと感じた。

前々から「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」が好きだという話をしているが、その流れで会社を経営したり投資したりする話に興味を持ち、それで検索して読んだ作品だった。ほぼ無限にお金を使える設定のものは他に書籍化したものを読んだことがあるが、そちらは全然合わなかったので、自分は「どうやって稼いだか」ということに興味があるのだとばかり考えていたが、この作品を面白く感じてしまった以上、結局主人公が社会的地位を得るのを一番面白がっているということが明らかになった。

布団から出て食事し、火曜日解けなかったECR6-Fと向き合ったが、やはりわからない。適当に提出したらTLEしてしまった。手元で試行錯誤した結果26secが23secになったが、TLは10secなので焼け石に水。ふてくされて布団で丸まっていたら寝てしまった。午前2時だった。

04/09(金)

午前5時半起床。うつらうつらしていたら神崎さんのなろう読了ツイートが流れてきて、それを読み始めたら止まらなくなった。「転生したら皇帝でした～生まれながらの皇帝はこの先生き残れるか～」。

https://ncode.syosetu.com/n6066gi/

午前11時までかけて一気読みした。非常に面白かった。傀儡を演じるため思うように動けない主人公のもどかしさや、そんな中で少しずつ自分の味方を増やしていく緊張感が良い。

読み止しにしていたノクターンノベルズを読んだ。

https://novel18.syosetu.com/n0019fz/

正午にまた意識を落とし、途中一瞬の覚醒を挟んで午後8時まで寝た。食事してyukicoderに出た。全完。

AはPerlで置換したが、制約をよく読むと文字数が5e6だった。よく間に合ったものだ。22Bで、これ以外ないと思っていたが、tailsさんが同じくPerlで16Bを出していてびっくり。コンテスト後に見るとy/a-z//s（の短い書き方）を使用していた。オプションsは同じ英子文字が連続している箇所を1文字にまとめてくれる。なるほど。このオプションはBashのtrでも使えるので、tr -cs _を提出して8Bとなった。

B、Cはよい。Dはよくわからなかったので飛ばし、先にEを解いた。Eも特になし。Dに戻って、9が連続すると考えて提出したがWA。ここでようやく実験コードを書いてみると、どうやら最初に1文字8が入るらしい。実装してAC。

Fは面白かった。ある人に配られたPの個数をX、qの個数をYとすると、Y=0であるか1<=Y<=S<LかつX>=L-Yである必要がある。このときY>0であるような人数とそのYの総和が分かれば絶対に使わなければならないPの個数が求められ、残りのPは自由に配ってよいことになる。人数と総和をキーにするDPが計算できるので、余ったPの配り方をさらにかけ合わせれば解ける。

ECR6-Fがどうにも解けないので解説を読むことにした。Mo's algorithmのようだ。僕も考えたが、削除ができないと思い諦めた。しかし今回の問題では削除が必要ないらしい。

長さNの数列aに対してクエリ[l,r)が飛んでくるので、数列のl番目からr-1番目までの要素から2つ（u<=v）選んだときのu^(u+1)^...^vの値の最大値を答えるという問題。まずMo's algorithmの前提の話をしよう。f(x)=0^1^...^xと置けばf(u-1)^f(v)の最大値を答える問題になり、Trie木が使える。Trie木は2本用意し、f(u-1)を入れるTrie木の各ノードにはその値を達成する最小のuを持つ。これで、ただ^f(v)した最大値を答えるのではなく、u<=vなるuによって達成され得る最大値が求まる。f(v)を入れるTrie木も同様にする。これでuとvのどちらからも相方を探せるようになったので、Mo's algorithmにおける区間の伸長ができることが分かった。

削除不要とはどういうことなのか。区間から2点選んで計算する形式の時にそうできるようだ。ブロックサイズをB=sqrt(N)とし、クエリ[l,r)であってl/B（切り捨てとする）が等しいものを集める。ここでmid=l/B*B+Bとおき、[l,r)を[l,mid)と[mid,r)に分ける（空になる区間は今は考えない）。区間から2点選ぶというのは、どちらかの区間から2つとも選ぶか、1つずつ選ぶかの3通りに分けられる。rで昇順ソートすると、[mid,r)から2点選ぶ方法に関しては区間は伸びる一方なので削除の必要がない（①）。あるクエリに対して[mid,r)を処理したとき、いったんストップして、[l,mid)を考えることにする。挿入せずにペアの相方を探すだけにすると、Trie木を変更せずに2つの区間から1つずつ選ぶ場合が計算できる（②）。最後に、クエリそれぞれに対してTrie木を初期化して、[l,mid)から2つ選ぶ方法を計算する（③）。

計算量を考えよう。Trie木のlogは一旦無視して、区間の伸長だけ考える。 $B=\sqrt N$ であった。①は $\frac N B$ 個のブロックに対して $O(N)$ なので $O(\frac{N^2}B)=O(N\sqrt N)$ 。②はクエリの個数 $Q$ に対してそれぞれ $O(B)$ なので $O(Q \sqrt N)$ 。③もクエリごとに $O(B)$ なので同じく $O(Q \sqrt N)$ 。合わせると確かに $O((N+Q)\sqrt N)$ である。

この問題ではN<=5e4、Q<=5e3だった。計算量は $O( (N+Q)\sqrt N \log \max a)$ である。解説には $O(N^2+Q)$ で通されたと書かれていた。TLが10secということもあり、なるほど確かに $O(N^2)$ が通りそうだ。 $N\gg Q$ であることに気を取られて、区間を全探索できることに気づいていなかった。Trie木だと $\log \max a$ がつくからどうするのだろうと思ってtouristのコードを読んだら、シンプルな $O(N(N+Q))$ で解いていた。ペアの一方を決め打ってもう一方をそこからインデックス順に試しつつ累積maxを取り、決め打った項を含むようなクエリに対してクエリの右端rでの累積maxで更新する。

ECR7を埋めた。慎重にコーディングした結果全部1発ACだった。AtCoderではコードゴルフに関係する再提出がたくさんあり自分の提出一覧が汚くなりがちだが、CFではそんなことはないため、全部ACで揃わないかとちょっと気にしていた。div.3を埋めているときは何度も発生した状況だが、ECRはやはり難しく、これが初めてであった。

ABCはよい。Dは必ず0にできる。Eは簡単なバージョンを2018年のICPC横浜大会で見たので、それの解説を参考に解いた。

Fは $\sum_{i=1}^n i^k$ を $1\le n\le 10^9$ 、 $1\le k\le 10^6$ で求める問題。 $k$ がもっと小さな制約の問題を2019年のICPC バンコク大会で見て、当時解けなかったのを覚えている。多項式補完が思い浮かぶが確か漸化式でも解けたはずで……と当時のやり取りをSlackで漁ったが、 $O(k^2)$ だったので今回は使えなかった。いい機会だと多項式補完を実装することにした。

多項式補完というとxには相異なるという制約しかないはずだが、例えばうしさんのライブラリを見るとx=0,1,...,N-1と決め打ちされているようだ。この制約は何だろうと思っていたが、アルゴリズムを見れば当たり前だった。より一般にxが等差数列であれば、1点とその他の点の差の積を求めるのが簡単。というか逆にxが等差数列でない場合の処理がO(N log N)でできるのがびっくり。

適当に書いて実験したらよさそうだったので提出、AC。ライブラリにもしておいた。求める値xは最初modintで与えられることを想定していて、この時大小比較ができないのですでに計算された値であっても知らないふりをする必要があった。後から必ずlong longで与えられるように修正した。

library/lagrange_interpolation.cpp at master · kotatsugame/library · GitHub

ライブラリのverifyにはyukicderの「貯金箱の溜息」を使用した。これはうしさんやbeetさんのライブラリのverifyを真似している。しかしこれが多項式補完になるというのはにわかには信じがたい。解説をいくつか読んで議論は追ったものの、狐につままれた印象。maspyさんの解説を読むと、累積和を6回取るので5次式であるということが式から見て取れるので、少しだけ理解できた気持ちになる。

ついでにコンビネーション類の計算をするライブラリも作った。毎回fac[]とinvfac[]を作って前計算していたが、さすがに面倒になった。以前はmodpowも毎回書いていたのだが、今から考えるとちょっと信じられない。

library/combination.cpp at master · kotatsugame/library · GitHub

ライブラリの設計に関する議論だけは済んでいた。これはLayCurseさんに教えていただいたものだったと思う。

mod上の逆元リストを必要に応じて生成する方法についての議論があった。前から作成する方法は、オーダーだけ見ればO(N)だが、実際は変数による除算や連続的でない配列アクセスなどがある。その点、後ろまで作ってから1回だけ逆元を計算する方法は、O(N+log mod)と変なのがついていても、定数による除算しか行わなかったりシーケンシャルアクセスが保たれたりと良いこと尽くめ。必要に応じて生成する場合も、倍々に増やしていくことで対応できる。これに関しては、呼び出しごとにif文による分岐が入るのが気になっていたが、分岐予測がかなり効くだろう、という話を聞いた。
週記（2021/02/01-2021/02/07） - kotatsugameの日記

ノクターンノベルズを読んだ。

https://novel18.syosetu.com/n6343gw/

午前10時からGCJ R1Aなので寝なければならない。午前6時、布団に入るも寝られない。なろうに手を出したところ午前10時直前まで読んでしまった。そのまま食事も摂らずコンテスト。

Abcで646位、何とか通過した。Aは愚直にやってよい。これを通したときは6位くらいだったのでびっくりしたが、両方Visibleなので確かに正しい答えを出力できたのだろう。

Bはわからない。とりあえず積を全探索する愚直なコードを書いてVisible 2つを取った。しばらく考えてもわからなかったので次に進むことにした。

Cは難しい。まず値がとても大きくなるようだったので言語をRubyに切り替えた。問題ごとにそれがT（もしくはF）だったときの場合の数を数える。これはどの問題で計算しても和が等しくなるはずで、場合の数が大きい方を選択すればよい。場合の数を数えるのは計算量的にちょっと大変かもしれないが、N人の回答は2^N通りしかなく、それぞれの個数を数えてメモ化することでQ回ではなくO(2^N)回しか計算しなくてよくなる。ここまで考えて細かい解析をせずコーディングした。小さいサンプルは合ったが、N=3、Q=120がどれだけたっても終わらない。とりあえず2つ取ることを目的に提出しておいた。

しばらくRubyで高速化して、大きなサンプルも3secくらいで通るようになったが、あるとき値が大きくなるとは言っても2^120をちょっと超えるくらいであることに感づく。そこでC++の__int128_tを使うことにして書き直した。大きなサンプルが0.15secくらいになったので時間ギリギリに提出したが、WA。ここでコンテストが終了した。

Bは積ではなくそれに使った数の和を全探索すればよかったらしい。xの素因数の和をf(x)とおいたときx+f(x)=sumだな～とは思っていたが、f(x)の値が全探索できるとは一瞬たりとも考えなかった。知ってしまった今では逆になんで考えられなかったのかわからない。CのWAの原因は分かった（Rubyで高速化しているときに嘘になったらしい）が、出しても結局TLEのままだった。N=2のときはどちらかの人のコピペをするか逆張りをするかで4通り試せばよかったらしい。

さらに1時間くらいなろうを読んで、午後2時就寝。AGCがあるので非常にまずい。

04/10(土)

午後3時、新年度1回目の弁当配達を寝過ごさないための目覚ましで起床。ここからうすぼんやり意識を保てればよかったのだが、思いっきり寝てしまった。午後5時半くらいに弁当が来て、何とか受け取れた。またすぐ寝ればいいのになろうを読んでしまう。午後6時半に再度就寝。

午後8時半起床。眠すぎて動けないが、食事だけでも摂っておく必要があったので、さっそく弁当を温めた。焦りながら食べてAGC053に臨む。

2完3WA、136位、パフォーマンス2447でレートは2692→2670(-22)。崖がデカすぎる。

Aは各項をできるだけ小さくした数列を引く方針で2WA。たくさん引いておいたほうが良い項もありうると気づく。隣合う項の差の最小値だと感じて、とりあえず最小値を取る2項を構築しようと思い立つ。極端に偏らせると別の項にしわ寄せがいくことがわかり、できるだけ均して置くことを思いつく。実は全ての項でできるだけ均したほうが良いのではないか？と思い考えたところ、証明がなんとなくつけられたので、提出してAC。

Bは大きいものから貪欲に取ることを考えた。setで管理するコードを書いている間に考えが整理され、中央の2i項のうちi項までしか保持してはいけないという条件になることに気づく。これはBITで計算できる……としたらWA。大きいものから貪欲というのはただの直感であったから、ちゃんと考え直し、priority_queueに2個入れて1個出す方針を生やしてACした。

Cはまず列が与えられたときの答えを考える。解説の2段落目の考察はかなり早い段階でできていた。そのあと、2Nがある山を固定して、挿入DPっぽくすることを考えていた。しかしmaxをうまく管理できなかった。maxについての数え上げで、maxの値を掛け算するのだから、p(x)を「答えがx以上になる場合の数」とおくとsum pになる。この方針を生やして、答えがx以上になる原因となりうるペア（他の場所に答えがもっと大きくなるペアがあるかもしれないが、一旦無視する）を配置し、数え上げてみたところ、全然答えが合わない。そのまま2時間念入りに椅子を温め続けてコンテストが終了した。

Cの解説を少し読んだが、p(x)を「答えがx以下になる場合の数」とおいている。これだけの違いかと思うとちょっと残念。しかしどうやって計算できるのかはまだよくわからないため、別に惜しくもなんともないのかもしれない。

AGCと少し被っていたCF #713 div.3に出て全完した。ABCはよい。Dは1個削除したときの最大値を見る。Eは大きいほうから貪欲に当てはめてよい。Fはどこで立ち止まるか全探索。Gは前計算。input validationが壊れていたらしく、AがHackされて嫌な気分になった。

AGCのコードゴルフをする。Aは、均すとき、今何個目の数列を作っているか見るのではなく毎回Aの値をインクリメントすることでも実現できるらしい。a//k+(i<a%k)みたいな式を使っていたが、a++//kでよくなる、ということ。BはPythonでheappushpop。Cythonによるループ部の改善があって負けたかと思ったが、n>i>=0を~n<i<0にして-1Bできたので再度奪取。

朝方布団に入ってからもずっとなろうを読んでいて、寝たのは午後1時だった。最近読んでいるなろうはこれだ。

https://ncode.syosetu.com/n4212eh/

04/11(日)

午後8時半起床。なろうが面白すぎて布団からの脱出に失敗しそうになるが、食事のため何とか這い出た。ABC198に参加する。今日はスクリーンキャプチャを録画しようと思ったが、なぜか録画が始まらなかった。原因を探している時間もないので、今回はあきらめた。

44分1WA全完で3位。Fが解けたのはかなり運がよかったと感じる。

AはABCで既出。こういう問題で既出かどうかを考えるのは無駄だということはわかっている。

atcoder.jp

Bはよくわからなかったので素直に書いた。Cはコーナーケースで1WA。D、Eはよい。

Fは、面に書く数の重複度を調べる。ある重複度についての回転して一致しないような書き込み方の個数は、最初は手で全通り生成しようと思ったが、さすがに正気に戻ってプログラムで書くことにした。さいころのありうる状態をすべて列挙するのに自信がなかったので、さいころライブラリを検索して拾ってきた。初期状態で面に配置する数を6!通り全探索して、それぞれに対しハッシュ値を計算する。ハッシュ値は、さいころの面の数値を6桁の6進数として読んだ時の値として、さいころを回転させて最も小さかったハッシュ値をもとに一致判定した。いくつか試すと手で計算した値と同じなのでよさそう。

重複度の列挙は再帰関数でよい。重複度の昇順・降順ではなく、実際に重複している値の昇順に列挙することにした。これを適当に組み替えると、a+2b+3c+4d+5e+6f=Sとなる正整数a..fの組み合わせの数を数える問題になる。係数のいくつかは使わないかもしれない。

これはつい最近見たことがある。金曜日に作った多項式補完のverify用問題、yukicderの「貯金箱の溜息」とほとんど一緒だ。貯金箱のため息では硬貨の額面という設定上1|5、5|10など係数の間に約数・倍数の関係があるが、答えが多項式補完で求まることの証明にはあまり関係がない。結局LCM(1,5,10,50,100,500)=500だったのがLCM(1,2,3,4,5,6)=60になるだけ。というわけでいそいそと多項式補完のライブラリを貼り付けてみたところ、サンプルが見事に合った。提出してAC。

コンテスト後のTLを見ていて気付いたが、Fの最後のステップは素直に考えれば行列累乗だった。

コードゴルフをする。Aの3B解もまた既出であるから、27秒ACで82位だったのを見て絶望していたが、蓋を開けてみれば僕が最短だった。Bは末尾の0を正規表現による置換で削除して云々、と考えていたが、reverseして数値として解釈すると勝手に消えることに気づいた。+0とすると括弧が必要になるので、負号をつけて判定する。Cはdcで、sqrt((X^2+Y^2)/R^2)を考えていたが、sqrt(X^2+Y^2)/Rのほうがよい。sqrtだけ精度を高く設定して計算する。コーナーケースの場合分けはいろいろ試したが、切り上げしてしまうとちょうど1歩でたどり着ける場合と区別がつかないので、切り上げする前に答えが1未満かどうかを見ることにした。Eは適当にPerl。他は手付かず。

CF #714 div.2に出た。ABCDFの5完。どうせ全完できるだろと思ってEを飛ばしたが、Fが大炎上した。

Aはよい。Bは適当に書いて合わせる。Cはsum Mにも制約がついていると思ってO(TM)で解いたらTLEした。行列累乗でO(T log M)でもまたTLE。結局行列累乗したものを前計算することで解いたが、850msとギリギリだった。前計算することさえ思いついていればDPっぽく書けたと思うが、行列累乗のコードを流用することばかり考えていた。Dはaの昇順にどこまで辺を張れるか見る。見るのはgcdのセグメント木で二分探索する。

Fはつらい。差分を計算する。swapする2数を $a_1,b_1,a_2,b_2$ とすると、 $a_1\lt a_2 \land a_1\le b_1 \land b_2\le a_2$ というものしか考えなくてよい。 $a$ の昇順にペアを見て、 $a_1,b_1$ の管理にデータ構造を使おう。 $-(a_2-b_2)-(b_1-a_1)+|b_2-a_1|+|b_1-a_2|=2\max(a_1,b_2)-2\min(a_2,b_1)$ なので、まず $a_1$ と $b_2$ の大小で場合分け。

$a_1\le b_2$ の場合は $2b_2-2\min(a_2,b_1)$ になる。セグメント木で $a_1$ に対する $b_1$ の最大値を管理しておけばよい（当然座圧が必要になる）。

$a_1\ge b_2$ の場合は $2a_1-2\min(a_2,b_1)$ になる。この $a_1$ が曲者。 $a_1$ の最小値と $a_1-b_1$ の最小値の両方を見ておく必要があったので、とりあえず $a_1$ の最小値を管理するセグメント木に入れて、 $b_1\lt a_2$ となったものから順に $a_1-b_1$ を管理するセグメント木に移し替えた。 $a$ の昇順に見ているので、これでよい。インデックスに対して値を複数持たせるといけないので、座圧の際は複数の要素を1つのインデックスに割り当てないよう $a$ と $b$ のペアでソートしておく必要がある。

Fを通した時には残り9分しかなかった。Eに適当に2回提出したが合わず、これだ！と思ったコードの提出は数秒間に合わなかった。直後にTLでそのコードも間違っていたことを知る。upsolveしておいた。

午前3時くらいから溜めていた日記を書き始めた。木曜日から4日分！いまここを書いている時点で4時間半経過して、12000文字書いたらしい。

2021-04-05

週記（2021/03/29-2021/04/04）

03/29(月)

正午、起床。昨日のDDCCのアンケートが来ていたので回答した。

ABC158-Dが縮められていた。

atcoder.jp

非常に面白い。リダイレクトという機能があることを知っているつもりだったが、それがコードゴルフに役立つとは一瞬たりとも考えたことがなかった。これはprintからシェルにリダイレクトしているが、逆にシェルからgetlineにリダイレクトする記法もある。こちらは本当にコードゴルフには役に立たないだろう。getlineが長過ぎるためシェルの方で操作するべきで、その時役立つであろうsystem関数を使用するコードゴルフにはすでに前例がある。

ARC116-Fをupsolveした。

偶数長の列の真ん中2つだけ見る、というのが嘘だったらしい。先頭を削るか末尾を削るかで、奇数長の列に帰着できる。奇数長の列に最初に操作する側が必ず損する（しかもそれで手番が入れ替わるわけでもない）から、奇数長の列を考えるのが後回しになる。このことから、どちらが奇数長の列に対して最初に操作する役割になるか？が定まって、このとき、それぞれの奇数長の列の最終的な値を、先週書いたように真ん中3項を見ることで計算できる。これは、先週の週記に書いた「先頭と末尾のどちらかを削ることによる利得がプレイヤーによらず定まる」ことに対応している。

例えば、全ての数列の長さが2以下だったら楽だろう。長さ2の数列のどちらを選択するか？ということのように、先頭と末尾のどちらかを削ることによる利得がプレイヤーによらず定まって、高橋君はその大きな方を、青木君は小さな方を選択するというようにできないだろうか？
週記（2021/03/22-2021/03/28） - kotatsugameの日記

コンテスト中の大胆な予想というのはあんまり外れていなくて、このもとで考察を進めた後に最初に考えていたことに立ち返れば良かったのだろうか。しかし、解説を読み解く過程でいくつか大きなギャップを感じていて、正直、そのうちの1つがわかっていたとしても、それ以外がわかったかというと自信がない。

昨日は先週ぶんの週記を投稿できずに寝てしまったので、その作業をする。数日溜めてしまっていたので、これにはかなり長い時間がかかった。ずっと文章を書いていた。日曜日のDDCCについてはオンサイトであるから、別に参加記の記事を作った。

kotatsugame.hatenablog.com

DDCCの参加記を書くにあたって、自分の装置実装の模様を撮影した動画をTwitterにアップロードした。ブログ記事に動画を挿入するためだったが、これをきっかけに他にも数名アップロードした人がいるようで、僕は当時失意のズンドコにいてあまり他へ注意を払っていられなかったこともあり、改めて他の人の様子を見られて楽しい。

ただ、僕の動画には微妙に顔が映っている人が2名ほどいるようだったので、正直ちょっと危なさはある。

ARC116-Aのコードゴルフが進んだ。もともと僕のdcが最短で、今日、ループ部を改善して-1Bされていたのに気づいた。そこで改めて最短コードに近い長さの他のコードを眺めていると、Perl 39Bを見つけた。これは普通に三項演算子で書いているだけ。よく考えれば当たり前で、1行に1つしか数値がない上に出力もただの場合分けであるから、dcの利点というのはほとんどない。そこで改めてRakuで書いてみると、さらに-2Bできてしまった。最近はdcでバトルすることが多かったように感じるが、それで視野狭窄に陥っていたのか。

夜、CF #711 div.2に出た。全完8位。

Aは2|gcdとなる場合を考えようと思うと、桁上がりが起こるたびにパリティが変わって良さそうだな、という気分になる。桁上がりが連鎖する場合はともかく、そうでない場合はだいたい20個くらい試したら見つかるだろう。それで書いたら通った。正直全探索で正解だろうと確信していたので、桁上がりが連鎖する場合についてはあまり考えていなかったが、冷静になれば連鎖したらさらに20回くらい調べるのでよい。

Bは二分探索して上のbitから見る。Wが2^29くらいのbitを持ちうることを忘れて2^19から見始めたため、1WA。これに気づくのに結構時間を使ってしまった。Cはややこしいことが書いてあるが、愚直に実装して毎回何個あるかカウントすれば通る。Dもちょっと悩んだが、数は必ず大きくなるし、クエリごとに全ての数を見ても間に合うので、小さい方から順に見ていく。操作回数の上限については、「その数を作るために現在のクエリで操作した回数の最小値」を持つdpで考慮に入れられる。kxのオーバーフローで1WA。

Eはk_u<=k_vなるu,vについて? v uを聞いて、Yesだったらuとvは互いに到達可能。よってk_v-k_uが大きいものから順に聞いていけばよい。これは（正直それ以外の方針で解ける気がしないため、というエスパーでもいいが）証明も付けられる。uからvへ到達可能であることを言えばよくて、u->vという辺があれば当然よい。以下、ない場合（u<-vである場合）を考える。uでもvでもない頂点はN-2個あり、そのうちN-1-k_u個にはuからの辺が存在し、またk_v個はvへの辺が存在する。ここでN-1-k_u+k_v>=N-1>N-2のため、鳩の巣原理よりuからの辺とvへの辺を両方持つ頂点が存在し、それを経由してuからvへ到達できる。

Fはk==1でGrundy数を計算するコードを書き、しばらく実験しているとわかってきた。深さはmod 2kで同一視してよく、kから2k-1までのそれぞれの深さに対して、その深さの頂点に対するaの総xorのxorが非ゼロなら先手勝ち。ほとんどエスパーみたいなものだが、一定の確からしさは感じられる。全方位木DPを書いたら一発で通った。

その後しばらく本を読んでいたが、読みきれないまま午前3時半就寝。

03/30(火)

正午起床。

本来は明日本屋に行く予定であったが、明日は昼にyukicoderでコンテストがあることに気づく。4月頭に発売される本を購入することを考えると、03/31はともかく03/30だとちょっと不安感があるが、しばらく迷った結果、今日本屋に行くことにした。

母に車を出してもらい、ちょっと足を伸ばして県内でも大きめの本屋に行った。結局4月頭どころか03/30発売予定の本もなかったが、ともかくそこで5冊買い、さらに古本屋にも行って18冊買った。

└( ＾ω＾ )┘♪ 買った♪└( ＾ω＾ )┘♪ 買った♪ pic.twitter.com/fbcGpVrT7w
— こたつがめ (@kotatsugame_t) 2021年3月30日

この古本屋に前回行ったのは、昨年の8月のようだ。

昼食を食べて古本屋に行く。仙台でも駅前のブックオフにはよく行っていたのだが、最近はご無沙汰。僕が最後に行ったときのものと比較すると、富山で僕が行く古本屋はラノベがよく揃っているように思う。
週記（2020/08/17-2020/08/23） - kotatsugameの日記

半年ぶりということで、本棚のレイアウトこそ様変わりしていないものの、内容にはいくらかの入れ替わりが見られた。まあ店側の商品が何も変わっていなかったとしても、その時々でどのようなタイトルの本に興味を惹かれるか、どの位置の背表紙に目を留めるか、というのはちゃんと時とともに移り変わっていくから、古本の購入は常に行える。

この古本屋、もといブックオフでは、他の店舗と同様トレカの売買も行っている。デュエルマスターズの高額カードを眺めていたが、今や売られているほとんどのカードは左上のコストが丸で囲まれた新しいデザインのものになっていた。そんな中で1枚だけ、僕にとって見慣れたデザインのカードがあった。あの「超新星アポロヌス・ドラゲリオン」……と同じパックで登場した「ザ・ユニバース・ゲート」だ。

《ザ・ユニバース・ゲート》 - デュエル・マスターズ Wiki

このパックは（子供のお小遣い程度ではあるが）かなり買った覚えがある。当然このカードも何枚か当たって、しかし実際にデッキに組み込むことはなかった。そもそもフェニックスなんてほとんど持っていなかったためである。効果のド派手さに惹かれるものはあったのだが……。それが今こうして値段が付いているというのは、なんとも面白く感じられる。ちょっと調べてみたが、別に信じられないような使い方をするわけではなくて、普通にフェニックスを捲ってターンを追加するらしい。

デュエルマスターズの漫画においては、エスメラルダがこのカードを使ってザキラ相手に3ターン追加し、シールドを14枚に増やしていた。そもそもシールドを増やすためのカードをそんなに使えたこと（そのころは墓地から回収して使いまわすなんてのもほとんど知らなかった）、また結局そのシールドがアポロヌス・ドラゲリオンのワールド・ブレイカーで1発で割られてしまったことなど、目まぐるしい展開に気を取られていたが、そもそも3ターン追加したのに殴り勝つ・あるいは究極銀河ユニバースによるエクストラウィンをしなかったことがかなり謎らしい。

ハーメルンの「輝きたくて」が完結した。

syosetu.org

この作者の前作「うちの脳内コンピュータが俺を勝たせようとしてくる」は、作者自身があとがきで指摘しているように終盤かなり駆け足だったが、今度は駆け足どころではなく、個人的には打ち切りと変わらないくらいの唐突さで終わったように感じられた。最近10話くらいかけて描かれたイベントが終わっていたので、書きたいことを全て書いたからこその完結なのかもしれない。考えてみれば、特に山も落ちもない話を延々続けるのは良くないという考え方も存在するだろうし、その点においてはすっぱり完結させてしまうのが一番良いのかも。唐突に終わったと言ったが、では唐突ではない終わり方とはなんなのか？僕がリアルのVtuber界を全然知らないため、最後の山場を感じられなかっただけではないか？

「文字渦」を読んだ。面白かったが、かなり疲れた。自分としてはそれぞれの短編をそれなりに読めていると感じていたのだが、文庫本の巻末の解説を読んでみると、さらに丁寧な解釈がされていて、自分が全然読みこなせていなかったことに気付かされ、愕然。どの短編も全くの無から生まれてきたわけではなくて、ちゃんとモチーフになる事物が存在したらしい。

モチーフ、つまり現実と、そこから小説にするにあたっての創作の境目を見極めるのには、固有名詞の創作か否かの判別が鍵となるだろう。よくわからない語彙が出てきたときに、適当にスルーするか、それとも検索してみるか。全部検索にかけているといくら時間があっても足りないので、自分の嗅覚である程度判別しなければならず、僕は普段SFを読まないためにそのような嗅覚が備わっていない。

そういえば、短編のモチーフについては1つだけ明確にわかったものがあった。「ハングル大移動」と言われて、言語ごとにまとめられた文字の話をしているから、これはと思ってUnicode関連で検索したらあたりだった。Unicodeにおけるハングル文字の配列が変更されたことと、より一般にUnicodeにおける言語の文字領域の話だった。最初からそのつもりで読んだので、この短編についてはかなり読めた方に入るのではないだろうか。

検索している途中に面白い話を見つけた。

北朝鮮の文字コード(KPS 9566)には「金日成」と「金正日」専用領域が確保されているのだけど、2001年にUnicodeに追加のプロポーザルを提出していたらしい（残念ながら却下されたようだ） https://t.co/ePlXqdz7zI pic.twitter.com/xETOX8IAwh
— rls (@quolc) 2017年1月10日

現代の避諱。他のサイトでは、こうやって別の文字コードを割り振ることによって、この文字だけ装飾を付けたりすることが簡単にできると書いてあって、うまいなあと思った。

「時々ボソッとロシア語でデレる隣のアーリャさん」を読んだ。ふぁぼん氏がロシア語という部分に反応して言及していたラノベ。イラストが良いので、そういう言及がなくとも購入リストには挙がっていただろう。僕が引きこもっている間に売り切れてしまい、再版を待たなければならなかった。

ヒロインの出身国をたまたまフランスでもイタリアでも中国でもなくロシアにしてしまったせいでこんな異常オタクに目をつけられてしまった作者さん、かわいそうすぎる寄り添った
— ふぁぼん(Фабон Ильич Фаворский) (@syobon_hinata) 2021年3月4日

非常に良かった。ロシア語要素はかなり限定的で、それよりも主人公の過去だとか、それから始まり本編を経ての心境の変化だとかに興味を惹かれた。設定されたキャラ同士の関係も良いしストーリーも良い。おまけに絵も良い。ラブコメとしても面白かった。次の巻が楽しみ。

さらに別の本を読み始めたが、途中で切り上げ、午前4時就寝。

03/31(水)

午後2時半起床。

せっかく本屋に行く日を前倒しにしたのに、当日起きてみたらコンテスト（yukicoderの新入生プログラミングコンテスト 2021（昼の部））が始まっていて絶望。しょうがないので遅れて参加し、途中昼食を挟んで解いた。全完。

Aはよい。Bはちょっと考えたが、たとえばハンバーグだとN+1品あればランチが1つできる、と考えられる。Cは幾何ライブラリを整備したことがあればすぐわかる、というより思い出せるだろう。Dでちょっと式を書いていたら昼食が用意されたため、Dを含めて残り5問を覚えてパソコンの前を離れた。昼食を食べながら全て解き、帰ってきて簡単なものから実装した。

HはA^Bを全探索すればよい。A^Bの各bitがどちらに割り振られるかについては、A<=Bという条件から最上位bitだけ確定し、あとは自由。FはMを全探索すればよい。Dは式を見ると4項ごとに-4倍されているようだったので、N%4とN/4%2で場合分けして実装。Eは拡張ダイクストラ。Gは正直何をやっても解けると思っていたが、実装しようと思ったら実は適当にやっても解けないことがわかった。冷静になると後ろから見ればOK。

夜、外食に行き、帰りに本屋に寄った。昨日行った本屋とは違い、こちらはそれより小さな家の近くの本屋だが、ラノベの品揃えは結構充実しており、4月頭に発売される本や昨日探してもなかった03/30発売予定の本を購入することができた。

また本を買ったぜ！ pic.twitter.com/ZPMnqiBVYx
— こたつがめ (@kotatsugame_t) 2021年3月31日

夜9時からまたyukicoder。今度は新入生プログラミングコンテスト 2021（夜の部）。最後の1問が解けなかった。

Aは、ややこしいが、制約から愚直にやって解ける。FA。Bは適当に貪欲。Cはちょっと面倒な実装。Dはさすがに親の顔より見た。EはBのコードを拾ってきて、後は平均Zを、各要素からZ引くことで総和=0に言い換えるやつ。Gはよくわからなかったが、Rubyで愚直に実装してそれなりに大きそうなケースを試すと爆速だったので提出。変数名を間違えていたりC++に提出してしまったりで、正答まで4回の提出がかかってしまった。C++に間違えて提出したほうはCEになるので、ペナ的には1WA。Gは二分探索の判定問題を考えるとX(X+1)/2>=Nなる最小の整数Xが答え。

Hは、ちょうどこの日きたまさ法の話題を目にしていたので、それをずっと考えていた。しかしかなり経ってから線形性が全然ないのでどうあがいても不可能であることに気づく。きたまさ法について、漸化式の左辺の添字を2倍するときに右辺で添字が変わる変数を勘違いしていて、線形性がなくても行けると盲信してしまっていた。後から適当に行列累乗など生やしてみるもTLEでコンテスト終了。答えを二分探索することでbit列の問題に言い換え、更に高速化できるらしい。

ところで、Gは（問題文は違えども）答えが同じになる問題がAtCoderに存在する。その問題の最短コードがこれだ。

atcoder.jp

$\frac{X(X+1)}{2}\ge N$ を満たす最小の整数 $X$ は $\left\lfloor\sqrt{2N+\left\lfloor\sqrt{2N}\right\rfloor}\right\rfloor$ 。このコードはコードゴルフの配信中に見つけたことを覚えている。

改めて手元で調べてみたが、この式は少なくとも $1\le N\le 10^9$ では正しい値になるようだ。どのようにして見つけたのだったか、再現してみよう。

まず、 $\frac{X(X+1)}{2}=N$ を解くと $X=\frac{-1+\sqrt{8N+1}}{2}=\sqrt{2N+\frac 1 4}-\frac 1 2$ になる。 $X$ は整数なので天井関数を適用するが、その中身に $1-eps$ を足すことで床関数に直せると考えると $X=\left\lceil\sqrt{2N+\frac 1 4}-\frac 1 2\right\rceil=\left\lfloor\sqrt{2N+\frac 1 4}+\frac 1 2-eps\right\rfloor$ 。ここで根号の中の $\frac 1 4$ と $eps$ が打ち消しあうとすれば $X=\left\lfloor\sqrt{2N}+\frac 1 2\right\rfloor$ が得られる。昔はこの式によるコードが最短だった。

ここで $X=\sqrt{2N}+\frac 1 2$ として両辺を2乗してみると、 $X^2=2N+\sqrt{2N}+\frac 1 4$ 。大胆にも $\frac 1 4$ を無視すれば $X=\sqrt{2N+\sqrt{2N}}$ が得られ、さらに根号を取るにあたって毎回floorしても答えが合ったというわけだ。

SRMを見送ってラノベを読んだ。「僕が答える君の謎解き明神凛音は間違えない」。最近「継母の連れ子が元カノだった」で売れている紙城境介さんの新作ということで、本屋で見かけて即決で購入した。非常に面白かった。ラブコメも面白いし、それでいてちゃんとミステリーしている。

ヒロインは、推理に必要な材料が集まった瞬間直ちに真相がわかる特殊能力の持ち主。これで犯人を指摘することはできるが、一方でそれを証明するための推理の流れは自分でもわからない。そこで主人公が、「ヒロインがどのようにして推理し結論にたどり着いたのか」を推理し直すという話である。これはつまり、一見それとはわからない形でストーリー中に「読者への挑戦状」を組み込んでいるとみなすことができて、後期クイーン問題に対する1つの回答である。

また、主人公が最初にたどり着いた推理の道筋が、ヒロインの当時の振る舞いと合わない（証拠を集めながら推理しているのに、集めた順番が違う等）ことがあって、さらに別パターンの推理の道筋を示すなど、多段階の謎解きになっている話もあって、巧みだなあと感じた。

さらに別のラノベを読み始めたが、半分くらいで切り上げた。午前5時半就寝。

04/01(木)

正午起床。

TechFULからAmazonギフト券が5000円ぶん届いていた。いつだかのTCBで1位を獲得した商品。回を重ねるごとにどんどん強い人が進出してきたので、今後1位を取れるかは微妙である。直近のセットなど理論値達成者がいたので、もはやそういう世界の勝負である。

このはてなブログを開設してからこれで3年らしい。RUPCの参加記を書こうと思って開設したはずだ。初期には解いた問題の解説記事を作ったりもしたが、2つ書いただけで終わっていて、それからしばらくは読書記録を更新するのとオンサイトイベントの参加記だけが積み重なっていき、最近（といってももう8ヶ月前か）になって日記を書き始めた。

ブログを開設する前、2017/03の時点から読書記録自体はメモ用紙で付けていたので、そのぶんも記事を立てたときに入れておいた。

チュウニズムのアップデートが行われていた。ノーツ数が4208の譜面が追加されていてびっくりした。これでもエイプリルフール限定ではなく通常の譜面のようだ。これまでの最多ノーツ数はKattobi KEIKYU Riderの3600ノーツだったので、一気に増えたなあという感想。

ABC197-Dが縮められていた。tauと書くと $2\pi$ になるのだが、これは素直にギリシャ文字でτと書くと2Bになるようで、-1B。piとπはどちらも2Bなのでどちらを選ぶかは好みであり、僕はいつもpiと書くが、それに引きずられてtauと書いたままにしていた。悔しいのでしばらく睨んでいたらZ*を使って入力に係数を掛ける書き方を思いつき、縮めることができた。さらに-1B。

atcoder.jp

夕方は本を読んでいて、夜からyukicoderでエイプリルフールコンテストに出場した。今年は自分も1問出している。

yukicoderが今年もエイプリルフールコンテストを開催するらしい。一昨年出題したが、今年も出題しようと思い立つ。
週記（2021/03/08-2021/03/14） - kotatsugameの日記

僕が出したI問題を除いて、コンテスト中にはBDEFKが解けた。

Bはシンプルで、必ずYesになる。Dは公式が存在する事実が有名。Eはなんとなくページのソースを確認したら解けた。FもBと同様エスパー要素のないシンプルな問題。Kは普通に難しくて、Y-12年とY+1年がそれぞれうるう年であるか判定して場合分けした。念入りに考えてコーディングしたところ1発ACできて気分がいい。

挑戦して解けなかった問題について。Aは質問タブを見れば良かったらしい。これは秋分コンテストでも見たもの。Cは最短コードがbash 10Bであるのを見て、tr A-Z a-zとかその逆を試していた。Text(cat)が最短でない以上入力を読む必要があると考えていたが、スペシャルジャッジで弾いていただけらしい。やられた！Hはどうしようもない。Jはfactordbで素因数分解するまでは良かったが、問題名の「除け者」という言葉に囚われて、指数が1であるような素因数だけ抜き出して連結したり掛け合わせたりしていた。特に、連結した文字列の長さは最短コードであるText(cat)の12Bと等しくなったので、これが答えであると確信したのだが……。

さて、僕が出したI問題についての話をしよう。この日記を書いている時点でFavが10個も来ていてありがたい。

yukicoder.me

最初は入力文字列に数字・空白や改行を入れてQコマンド以外も使おうと考えていたのだが、これはちょっと難しいというか面倒であることに気づいた。そこで今のような、英大文字小文字のアルファベット列を出力するソースコードを作成させる問題に簡略化した。

Esolang wikiを探してもまともな処理系はなさそうだったので、安心してオレオレルールを定めることにした。例えば作者のページではqqqqというソースコードがqqqq_qqqq_qqqq_qqqq_（_は改行）を出力するような書き方がされていたが、いちいち改行されてはたまらないため、改行を自動付加せずソースコードだけを出力するような処理系を書いた。これで改行なしのソースコードを食わせれば望んだように、先の例で言うならqqqqqqqqqqqqqqqqが出力されることになる。

しかしこの状態では、問題の回答となるソースコードは改行なしの文字列になってしまうため、出力の最後に改行を付けてくださいという注意書きが推奨される状況においてはあまりよろしくない。そこで、半ば無理やりであるが、処理系自身で1行だけ読んで末尾の改行を取り払うようにしておいた。

このとき2行目以降に適当な文字列を付け加えても無視されるので、そうやって2行以上に渡るソースコードを書いて、実行すると1行目だけ読まれて正しい文字列が出力されるので正しい回答です、とも言える。そんなのは困るため、さらに回答は1行だけにせよとの制約も付けた。1行だと回答は一意に定まるため、これでちゃんとスペシャルジャッジを用いずとも判定できる。まあスペシャルジャッジを書いても良かったのだが、面倒……。

以上のようなことを考えていたので、問題文では「改行」や「1行」という言葉を多用して、なんとか曖昧さをなくそうとすることになった。結果、どことなく怪しげな、何かありそうな問題文になってしまった。

H、Q、9、+以外の文字の扱いに関する質問がいくつか来た。それらは僕の書いた処理系ではnopになるが、WikipediaのHQ9+の記事だけ見ていてはわからないことだっただろう。そのあたりもカバーするつもりで「以下の処理系を使用します」と書いたものの、実際に僕が意図していたことは「以下の処理系を言語仕様の定義であるとします」であったことに気付かされた。

「新謎解きはディナーのあとで」を読んだ。最近東川篤哉さんの手になる本を全く読んでいなかったので、久しぶりに触れることになった。記憶にあるよりもずっとギャグ調でびっくりしたが、それはそれで面白い。このシリーズの以前の本を読んだのはもう覚えていないくらい昔のことだから、キャラクターなどわからないのではないかとビクビクしながら読み始めたが、すぐ「ああ、こういうキャラだったな」というのが蘇ってきてスムーズに読めた。それほど特徴的なキャラクターたちだったのだろう。

3月が終わっていたので、3月に買った本・読んだ本の集計をした。

3月の集計
買った：48冊
読んだ：14冊
積読：+34冊
積読（累積）：+32冊
— こたつがめ (@kotatsugame_t) 2021年4月1日

来月から頑張りたい。

夜中、溜めていた日記を書いていたが、全然終わらない。月曜日から水曜日のぶんまで書いて、今日のは後回しにしてしまった。布団に入って少しラノベを読んだが、流石に夜が明けそうだったので就寝。午前6時だった。

04/02(金)

午後1時起床。

「新妹魔王の契約者」13巻を読んだ。シリーズ完結。12巻が発売されたのは2018/04だったので、丸3年開いたのか。これまで書かれてきた店舗特典等の短編集なので、これまで12巻のストーリーを総復習している感じで、以前の巻を参照しながら読んでみると面白かった。かなり重要なことを話している短編もあるように見えたが、確認してみると、確かにそのシーンは本編では飛ばされていたようだ。短編にたまに入る挿絵は当時描かれたものが使われているため、最近のラノベと比較するとそこまで過激すぎるということはなさそうだが、その分描き下ろしの絵はすごかった。これが全年齢対象というのは信じがたい奇跡。

「異世界で美少女になった俺、地球に戻れたので裏垢やってみる。」という作品が完結した。

https://ncode.syosetu.com/n6063gu/

1作、面白いと感じるものを見つけて読了した。「異世界で美少女になった俺、地球に戻れたので裏垢やってみる。」。
週記（2021/03/15-2021/03/21） - kotatsugameの日記

この日に読み始めた。読了したと書いているが、実際には「最新話に追いついた」という意味合いであった。

主人公の友人が高校に入学したこととか、話のネタになりそうな展開はあったものの、あまり触れられずに完結してしまった。番外編で触れられるかもしれないので楽しみに待つつもりだ。

yukicoderのコンテストに出た。6完。コンテストタイトルに〇〇's Birthday Contestと書いてあって、あまり注意していなかったが、本当にお誕生日コンテスト（原義）だった。

Aの問題文を読んでまずびっくり。この時点ではお誕生日コンであることに気づいていなくて、まともな問題を出す気がないのかとキレかけていた。

Bは3進数で桁和を取って、1引くときに繰り下がりが起きてもパリティは変化しないことを確かめた。これでも解けることは解けるが、そもそも取れる石が必ず奇数個なので、そのままNのパリティを見ればよかったらしい。解説を見て気づいた。

Cは多倍長整数が必要そうだったのでRubyで書いた。DはRubyのto_rで一発。pで出力すると(1/2)のように括弧が付くことに気づかず1WA。

Eは逆から見て/2と-3に言い換えた上、NからBFSした。実は4->1以外は/2できるなら貪欲にして良いことが示せるらしい。mod 3に着目すればよいと聞いたので考えてみた。まずmod 3=0のとき、-3しても/2してもずっとmod 3=0であるから、必ず不可能。mod 3!=0のときは-3しても/2してもずっとmod 3!=0なので、値がどんどん小さくなっていって最終的に必ず4->1か2->1ができる。当然減少スピードが速いほうが良いため、/2を優先的に選択するべきである。この方針だと2回に1回は/2することになるため、操作回数はlogのオーダーになる。

Fを見てTwitterでキレたところ、お誕生日コンであるとの指摘を受け、ここでようやく気づいた。この問題はだいぶ壊れていて、定数を確定させた後の式が何度も更新されることになった。僕は4!P(4n,4n-4)と書かれた時点でイコール(4n)!であると早とちりして、実際その解釈でACしてしまったが、実はn=0のことを考えると両者は一致しない。この点も考慮しつつPで書き表すのは不可能に見えていて、式はその後も何度も修正されていたが、Writerがやりたいこととそれが不可能であることがわかっているだけにもどかしい思いをした。今思えば質問タブでちゃんと指摘すれば良かった。

Gは普通に難しい。解説を読んでもよくわからなかった。

「氷の令嬢の溶かし方」2巻を読んだ。2人が自身の恋心を自覚して両片思い状態になった。これは健康に良い。身も蓋もない話だが、ちゃんと作中でそうであることが明言されているので安心感がある。列車の窓から黒い羊が見えたとき、その羊の少なくともこちら側半分が黒いことしか保証されず、他の羊に関しては何も言えないのと同様に、作中で明言されない限り、ヒロインは主人公が好きなのではなく、今でもただ主人公とお友達になりたいだけである、という可能性を否定しきれない。

なんにせよ、1巻はまだ馴れ初めといった感じなので、続刊が出るよう祈っている。
週記（2020/10/19-2020/10/25） - kotatsugameの日記

とりあえず続刊が出てよかった。さらに帯には何らかの賞を受賞したと書いてあったので、かなり売れているのだと思っていたが、どうやら打ち切り間近らしい。そういうことをかなりオープンにしている作者さんというのは珍しい気がする。それともこのラノベの出版元であるモンスター文庫特有なのか？僕はモンスター文庫を少し避けている節があるのでよくわからない。ともかくも2人が両思いになる様は読みたいので、売れてほしい。03/30に発売してから1週間が勝負……！

初めまして、デビュー作が半年で打ち切られそうなラノベ作家です。
売れ行き次第では続刊可能ですが、ここままでは…といった状況です。

1人でも多くの方に作品を知ってほしいので、RTで拡散してくださると助かります🙏 pic.twitter.com/A4b1PvHYym
— 高峰翔@打ち切り間近の作家 (@kakeru_takamine) 2021年4月2日

また週記を書く。明日は仙台に戻るつもりなので、読んだ本の感想などを実物を参照しながら書こうと思うと今日中に書いておく必要があった。午前5時くらいにこの日のぶんまで追いついたので、就寝。

04/03(土)

午前11時半起床。

バナナを1本食べて車に乗り、両親とともに仙台へ向かう。普段は来た時と同じように新幹線に乗って帰っているが、たまに両親の旅行がてら車で送ってもらうことがあり、初めてではない。非常にありがたいことである。車で移動することのありがたみというのは、主には荷物を自分の目が届く場所で運べることにあると考えている。

途中で三春滝桜を観光した。

三春滝桜 | Find！三春【みはる観光協会～福島県三春町】

pic.twitter.com/RrX9qydwiI
— こたつがめ (@kotatsugame_t) 2021年4月3日

ぐるっと一回りして写真を撮ったが、その中から1枚だけ選んでツイートした。うまい文章が思いつかなかったので、位置情報だけ付けている。何回か写真を見返しているが、やはり綺麗であったと感じられる。せっかくなので、日記では他の写真も投稿しておこう。

f:id:kotatsugame:20210405232725j:plain

f:id:kotatsugame:20210405232858j:plain

f:id:kotatsugame:20210405233021j:plain

f:id:kotatsugame:20210405233036j:plain

f:id:kotatsugame:20210405233040j:plain

夜になって仙台に近づいてきた。仙台は最近新型コロナウイルス感染症の感染が急拡大しているため、市街地で食事をするのは憚られた。よってサービスエリアのフードコートで食事をした。両親はレストランがあるサービスエリアを探していたようだったが、どれも一時休業中であった。

食事 pic.twitter.com/06MaWT89qH
— こたつがめ (@kotatsugame_t) 2021年4月3日

仙台の部屋にたどり着いたのは午後9時手前であった。一緒に運んでもらった仕送りの食糧や本を部屋に入れ、代わりに読み終わった本を持ち帰ってもらう。読了済みだけど読み返したいので手元に置いておきたい本というのはいくつかあって、特に「りゅうおうのおしごと！」なんかは全巻部屋に保管していたのだが、いよいよ本棚の空きスペースがなくなってきたので、今回ついに持ち帰ってもらうことにした。非常にまずいが、本を売るというのは考えられないので、頑張って読むか、本棚を増やすか……。実家の本棚も埋まりつつある。

両親は部屋にしばらく滞在して、持ってきた食糧を棚に詰めたり、僕が放置していた水回りを掃除（！）してくれたりした後、帰っていった。今日は仙台で一泊して、明日富山に帰るらしい。調べると、富山に帰るのは「帰富（きふう）」と呼ぶのがよさそうだった。確かに「帰山」であると、該当しうる県は多数あるようだ。

しばらく放置してしまっていた競プロサークルの公式メールアドレスを確認すると、さっそく入部希望のメールが来ていた。入部届の準備をしなければならない。早速取り掛かろうとしたが、こどふぉがあったので出ることにした。

CF #712 div.1。4完して31位だった。レートは2649→2743(+94)。いい感じ。

A問題は、最初片方を(((...()...)))の形にしてもよいという大嘘をついたが、サンプルで落ちたので気づけた。s_i='0'なるインデックスの個数が偶数でなければならず、かつ先頭と末尾を含んではならない。これらが満たされているとき、s_i='0'なるインデックスだけを取り出すと()()()と)()()(になるように配置して、残りを先ほどの(((...()...)))で埋めるとよさそう。

Bは最初(i+j)%3で分けることを考えたが、ダメそうだった。そこでなんとなく(i+j)%2を考えるとうまくいった。そうやって市松模様で埋めると、2種類の色のうちどちらかは必ず使用できる。それでどちらかの色を使い切ったら、残りのマスはすべて隣り合っていないので、例えば色2を使い切って色1が余っていたら、色1のぶんを色1と色3の使用できる方で埋めていける。気づけたので面白い。

Cは、遷移コストの式を見ると、aの値が小さくなる方向の遷移はいくらでもできるので気にしなくて良さそう。ここで、まずaが大きくなるほうに移動して……と考えたが、スタートがa最小とは決まっていないためちょっと戸惑った。しかしよく考えてみれば、結局ぐるっと一回りするわけだから、a最小の頂点をスタート地点とみなしてもよい。あとはDPっぽく計算する。DPの値はpriority_queueで管理して、a+cが今見ているaより小さいか大きいかで管理するキューを分け、適当に移し替えながら計算した。コンテスト後のTLによれば、これはa+cの最大値を管理しつつはみ出した分を足すだけでよかったようだ。

Dはいくつか切れ目があって、分割したそれぞれのブロックについては配置が2種類しかありえない。またブロック同士は関係しないので、それぞれ貪欲に取れる。実装にしばらく悩んだ。サンプルも弱かったが、度胸試しとばかりに提出したら通ってびっくり。Eは全然わからなかった。

入部届（と継続届）の準備をする。どちらもGoogle formで作成している。継続届のほうは去年のものをコピーしてきて、いくつか質問を追加するだけで完成。追加した質問というのは、個人とSlackのアカウントとAtCoderアカウントを対応付けるための質問で、これは昨年度のICPC準備の際にうまく対応が取れずちょっと苦労した思い出から。

入部届のほうはそううまくはいかない。弊サークルの入部届は、formの回答を送信すると記入したメールアドレス宛にメールが届き、そこに記載されたSlackの招待リンクやサークルで使っているGoogle ドライブへの招待を通じて活動に参加するという形になっている。どうやら去年のものをコピーしてきただけの入部届ではうまく動いていないようだった。そもそもどういうシステムでそのような連携が可能になっているのかわからなかったので碧黴さんに確認して、返信を待つことにした。

まだなんとなく眠る気になれなかったので、第1回えでゅふぉを開いて全問通したが、かなり大変だった。

ABDEはよい。Cは10⁵個の点が与えられて、偏角の差が最も小さいペアを出力せよという問題。偏角の差というのは時計回りと反時計回りどちらか小さいほうであって、必ずπ以下になる。制約から点の座標の絶対値は10⁴以下であったから、atan2でソートしていけるかと思ったが、WA。

この問題の制約ならatan2を使用してもソートできるらしい。誤差の評価についてはmaspyさんが教えてくださった。
週記（2021/02/01-2021/02/07） - kotatsugameの日記

この部分に続いて引用されたツイートによれば、今回の入力では偏角に1e-8くらいの差があるなので、偏角ソートは良さそう。角度を比較するところがダメだったらしいが、それに気づいたのはこの日記を書いているときであって、当時は偏角ソートすら怪しんだ結果整数の範囲で偏角ソートするライブラリを持ち出した。

さて、角度を比較しなければならない。今回は偏角の差であるから、内積を取ってからcosだけ取り出したものの大小比較でよさそう。そのままだと分母にユークリッド距離のsqrtが出てくるが、ここで分母を払って2乗し、改めて符号をつけなおすことで、ちゃんと整数範囲で比較できる。ただし値の大きさが8乗オーダーになるので、__int128を使わなければならなかったが、通った。

みさわさんに別の方法を教えてもらった。あるベクトルを回転させてX軸上にそろえて、角を構成するもう一つのベクトルも同様に回転させ、その位置を外積によって比較することを考える。回転は、以下のツイートのような考え方を用いれば、整数の範囲で行える。

とりあえず複素平面と思っておきます。複素数の掛け算は(極座標表示を思い浮かべれば)回転拡大です。
共役との積は実数なので、p の複素共役を掛け算する操作は、p を実軸に持っていく回転拡大になります。
— みさわ (@Mi_Sawa) 2021年4月3日

これは回転行列のabs倍をしているとも考えられるが、そちらだと整数になることがあまり直感的ではないように感じられるので、上の説明が一番わかりやすかった。これだと移動後の座標の値は2乗オーダーで、外積でさらに掛け合わせても4乗、よって64bit整数に収まってくれる。Y座標を0以上に直すことで、偏角の差がちゃんとπ以下になる。

Fは幾何。自己交差のない、（凸とは限らない）多角形があって、クエリごとに与えられる直線との共通線分の長さを答える問題。かなり苦労した。基本的には直線と多角形の外周との交点を列挙し、ソートして2個ずつ見る。多角形の頂点が直線上にある場合は、その直前の頂点と直後の頂点を結んでできる線分が直線と交差するか見て、交差しなければその点は考えないことにする。

多角形の辺が直線上にある場合が一番つらい。適当に前処理して、そのような辺が2つ連続することがないように、もっと一般には内角が2直角の頂点がないようにしておく。先ほどと同様に直前の頂点と直後の頂点を結んでできる線分が直線と交差するか見て、交差すれば、交点の代わりに辺を区間として見て両端を持っておく。交差しなければ辺の両端をそれぞれ持ち、処理後にその間が答えに足されていないようなら改めて足すことにしたら通った。

布団に入ってなろうを読み、午前7時半就寝。

04/04(日)

午後1時半、目を覚ます。

昨夜碧黴さんに送ったメッセージに返信があった。Google formの回答を集めるスプレッドシートからスクリプトを動かしているらしかった。formをコピーしただけでは動かないのも当然のことだが、幸いスクリプトや設定をコピーしてくるとちゃんと動いた。

まず継続届のリンクをサークルのSlackに貼って、記入をお願いする。同時に活動する曜日に関するアンケートを取った。新入部員が出そろうまでの仮の日程で、またゴールデンウィークを目途にアンケートを取りなおす予定だ。さらに入部届を公開する。とりあえず入部希望のメールを送ってくれた人に送って、さらにサークルの公式サイトに2021年の新歓ページを作って載せてもらった。サイトのほうは記法などよくわからないことが多かったのでホスフィンに丸投げした。ありがとう……。

2021年度新歓情報 | puzzleknot 公式サイト

ホスフィンはさらにSlackに自己紹介用のチャンネルも作ってくれた。

布団に倒れこむ。眠いが、昨夜読んでいたなろうの続きが気になるので、ずっと読んでいた。途中のこどふぉも微妙な眠気を言い訳にサボり、驚くべきことに午前4時半まで読み続けていたようだ。そのまま寝落ちした。

なろうと書いていたが、正確には「ノクターンノベルズ」というなろうの男性向けR18版サイトだ。「放課後インスタントセックス」という作品。この日の時点ではまだ最新話に追い付いていないので、特に感想などは書かない。

https://novel18.syosetu.com/n7640gf/

2021-03-29

週記（2021/03/22-2021/03/28）

03/22(月)

週記を投稿してからはすぐ布団に入った。ハーメルンを開いて少し読み進めただけで寝落ちしてしまった。午前7時半だったようだ。

午後1時起床。布団の中でもぞもぞしていたら学食の営業時間が終了してしまったが、それはそうと床屋に行っておかなければならないため、何とか身を起こす。

購買でパンを買って食べ、床屋で髪の毛を切った。今日担当してくれた人は、体を覆うカバー（散髪ケープというらしい）の首回りをゆるゆるにしたり、使っているバリカンから信じられない音が出ていたりとかなり不安を感じたが、結果的には普通だった。

明日、帰省を予定している。行く機会が極端に減るだろうから、今日はゲーセンに行くことにした。ラーメンで腹ごしらえしてチュウニズムをプレイ。今日はしっかりカウントしていて、5時間半で25クレ使ったようだ。

Blackmagik BlazingでSSSを出せた。

出た！今日一発！
Blackmagik Blazing SSS！ pic.twitter.com/44KcWjjHCL
— こたつがめ (@kotatsugame_t) 2021年3月22日

最近追加された新曲の「Blackmagik Blazing」をプレイしたが、手が間に合わなくてお話にならなかった。
週記（2020/11/09-2020/11/15） - kotatsugameの日記

1日に何度もやるような譜面ではないため、今日最初のプレイで決まってよかった。いまだに今回のプレイがなぜうまくいったのか分かっていないが、とりあえず手は間に合っていた。いい感じに力が抜けていたのだろうか。また、以前何連奏かした時の経験から、後半で出てくる斜め3つのタップを擦ったのもよかったと思う。押そうとするとテンポが崩されたり、直後のノーツを押すのが間に合わなかったりして苦労していた。

さらに、前の木曜日のアプデで追加された13+の両方でもSSSを出せた。事前に譜面動画を見ており、速い連打だったり微妙にテンポの違う交互だったりが難しそうだなと思っていたが、実際にプレイしてみるとそれらは誤魔化せるものであった。

レメゲトン鳥〜 pic.twitter.com/8NZHGd5NIn
— こたつがめ (@kotatsugame_t) 2021年3月22日

伸びた〜 pic.twitter.com/3BEBO9eM23
— こたつがめ (@kotatsugame_t) 2021年3月22日

午後11時、帰宅。明日新幹線の切符を買うときにお金を下ろすだろうと考えて、今日はATMに寄らなかったのだが、そのくせ所持金をギリギリまで使ってしまったので夕食を食べられなかった。

布団に入って少しハーメルンを読んだが、すぐ寝た。午前5時。

03/23(火)

午前11時起床。帰省の準備をする。とはいっても別に着替えなどを用意する必要はないので、例えばノーパソのOSのアップデートをしておくとか、必要になりそうなデータをクラウドに上げておくとかである。

出掛けにLINEが起動しなくなって焦ったが、調べてみるとこれは僕だけの不具合ではないようだ。対策についてもすでに広まっていて、「AndroidシステムのWebView」というアプリを一旦アンインストールすると良いらしい。試してみると確かに起動するようになった。アンインストールすると、環境によってはChromeが使えなくなったりもしたようだが、僕の方はそういうこともなくて嬉しい。

リュックサック1つを持って午後1時に家を出た。仙台駅に向かい、まずお金を下ろして切符を購入する。すぐ新幹線に乗るわけではなく、しばらく駅前で遊ぶことにする。

まず昼食として、最近できた一蘭に行った。僕が並んだときは先に10人くらい並んでいたように見えたが、帰りは誰一人並んでいなかった。ちょうどピークとぶつかってしまったようだ。

この一滴を最高の喜びと定めたとき、与えられた形状の器に含まれる喜びの送料をmod998244353で求めてください。 pic.twitter.com/n5TKoDJZKp
— こたつがめ (@kotatsugame_t) 2021年3月23日

次にゲームセンターに行った。駅前のゲーセンには、手元撮影用のスマホアームを設置している店舗がある。そこに行って、運良くスマホアームが設置された台に入れたので、1時間と少しプレイしていた。かなり調子が良くて、それぞれ1回プレイしただけで13+のスコアをどんどん更新できた。

BUCHiGiRE Berserker 0-1 pic.twitter.com/7FAY1IhWxf
— こたつがめ (@kotatsugame_t) 2021年3月23日

folern 19-2-0 pic.twitter.com/sgi2vKTeCC
— こたつがめ (@kotatsugame_t) 2021年3月23日

folern 19-2-0はマジでビビった。13+でこんなに精度が良かったのは初めてである。ただ、今回アタックが出た箇所はかなりどうしようもないと感じているので、AJは遠そう。

時刻表を見て、タイミングを見計らって駅に戻った。地震の影響で臨時ダイヤになっていて少し戸惑ったが、ずれたおかげかやまびこ（東北新幹線の自由席がある列車）とはくたか（北陸新幹線）がちょうどうまく接続しているものを見つけたので、それに乗ることにした。

やまびこは上りだからかかなり混み合っていた。大宮の1つか2つ前でたくさん乗ってきて、このご時世では信じられないことに、2人がけの席に2人で座ることになってしまった。降りるときに気づいたが、どうやら立ち乗りも出ていたようだ。それに対して、はくたかはかなりスカスカで安心だった。

車内ではラノベを読んでいたが、残り2、3ページだったのに駅についてしまって残念。駅から父の車で実家まで行く。途中で2軒の本屋に寄り、本を10冊購入した。

└( ＾ω＾ )┘♪ 買った♪└( ＾ω＾ )┘♪ 買った♪ pic.twitter.com/6mSR10MIUc
— こたつがめ (@kotatsugame_t) 2021年3月23日

実家のWi-Fiで、今日撮影した手元動画をTwitterにアップした。以下のリプライツリーにまとめてある。先頭のものが、先に言及したfolern 19-2-0の手元である。

folern 19-2-0 手元 pic.twitter.com/fNIMKx0Y4G
— こたつがめ (@kotatsugame_t) 2021年3月23日

手袋をしたほうがプレイしやすいと感じるが、それを撮影するとどうにも不格好に思えてしまう。

「AndroidシステムのWebView」の不具合修正のアップデートが来たようなので再インストールした。

新幹線で読みさしにしていたラノベを読了。「最強魔法師の隠遁計画12」。この巻からしばらくは、Web版で僕が一番辛かったところであるような記憶がある。書籍化にあたってショックな展開はいくぶん削減されている気もするので、ドンと構えて読んでいきたい。書籍版オリジナルヒロインの影響でストーリーも変わるらしいが、そもそも元のストーリーをすでに忘れ去っていて悲しい。

別の本を読み始めたが、かなり眠くなったので素直に寝ることにした。特にネット小説を読むようなこともなく、午前2時半就寝。

03/24(水)

午前8時半起床。ちょっと目を覚ましてスマホを触ったら、それから二度と眠れなかった。起きると食事を用意してくれそうなので、起きた。

朝ご飯を食べて読書。それから昼食を挟んで午後5時までかけ、「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変2」を読んだ。

今巻も非常に面白い。Web版だといろいろな話がぐちゃぐちゃに入り乱れているという印象を受ける（もちろん、書いている本人には一貫した流れというものがあるのだろうが……）が、書籍になる際に統廃合されてかなり読みやすくなっている。

また政治経済の話は、Web版ではほとんど読み飛ばしてしまっていたが、しっかり読み込むとまた一層面白さが増すことがわかった（このせいで読了にかなり時間がかかった）。もちろん細かい話にはあまりついていけないが、少なくとも人の名前と陣営をちゃんと記憶するだけでも良さそう。

帯には、1巻発売直後からSNSで話題沸騰とある。3巻の予告も巻末についていた。次は夏らしい。好きな作品が書籍化されて、売れ行きが好調である、ということほど良いことはない。

次に「お隣の天使様にいつの間にか駄目人間にされていた件4」を読んだ。最高。Web版を読んでいる人には伝わるだろうが、今巻の最後の方は体育祭である（これは目次からわかる情報なのでネタバレにはならないだろう）。この作品の体育祭の部分は最高であることが知られている。その少しあとの部分も好きなのだが、そちらはこの巻には収録されていなかった。おそらく5巻の冒頭に入るはず。非常に楽しみである。

DDCCの移動に関して考えていた。朝は12時半集合だとわかったので、当日出発することにしても朝は十分余裕がありそう。問題は帰りである。

コンテスト終了は午後6時半で、このご時世なので懇親会などは存在しない。しかし、この時間から帰っても家にたどり着く前にARCが始まってしまうのだ。ARCの前に家に帰れないなら、ARCの後に帰るしかない。

後泊をするのが最も良いはずだが、それは流石にもったいないような感じがして尻込みした。改めて時刻表を確認していると、2012東京駅-2257富山駅という新幹線を発見。これに乗って車内からARCに出場するのは不可能ではないだろう。後ろ3分（降車準備を含めると8分くらい）コーディングできないのはちょっと怖いが、うまく2100-2300を含むような列車は存在しないのでしょうがない。また、2104-2315という列車もあるが、コンテスト開始直後に乗車するようなスケジュールよりも、コンテスト終了直前に降車するほうが幾分マシだろう。他にも、富山駅の1つ前で降りることで駅のホームでのコーディングにも10分程度のまとまった時間を取る、ということも考えられたが、これは迷った結果富山駅まで行くことにした。この決定を後悔することがないようなコンテストでありますように。

深夜、コードゴルフで新手が出ていくつか最短コードを取られた。

atcoder.jp

入力をシェルコマンドで加工してdcに渡すとき、わざわざ?で読んでいたが、<<<でdcコードに直接埋め込んで渡すと短くなるものがあるらしい。?を2回以上呼ぶものと、逆順ソートして上から数行読むもの。逆順ソートは、埋め込むことにすると下から数行が簡単に取れるので通常のソート順で良くなる。

この更新には粗が存在しなさそうなのでどうしようもない。ただのdcで無理やり解ける問題があったので、それで1つだけ取り返したのが精一杯であった。

午前1時就寝。

03/25(木)

午後1時起床。最近うまく眠れなかったぶんを取り返そうとでもしているのだろうか。

食事して、最寄りのみどりの窓口まで行って切符を購入する。昨日決めたとおりの日帰りの乗車券と特急券だ。22950円だった。DDCC運営には仙台駅から乗ると言ったのに、富山駅から乗って行くことになってしまったので、ちゃんと交通費を出してくれるか不安な部分もある。念の為メールで確認しておくことにした。

帰ってきてから読書。「公女殿下の家庭教師8」を読んだ。この巻で一区切りついたようだ。Web版からの加筆で、まだWeb版の方でも明かされていなかったはずの設定が出てきてびっくり。

帯にシリーズ20万部突破と書いてある。こちらは8巻で20万部、「お隣の天使様にいつの間にか駄目人間にされていた件」は4巻で30万部らしい。うーむ、ここまで差がつくのか。しかし書店では「公女殿下の家庭教師」も結構プッシュされているような印象を受けるから、天使様が圧倒的なだけで売れているほうなのだろう。

最近スマホのTwitterクライアントが頻繁に固まって落ちるので、昨日、ちょっと調べてキャッシュとストレージを消した。合わせて800MBくらいあった。それ以来一度も固まっていないので、かなり効果があったようだ。

もう1冊ラノベを読んでいたが、こどふぉがあったので出た。CF #710 div.3。40分で全完、Dでペナを出して11位。

Aはよい。Bは文字列を直接見ていく実装を頑張ったが、先に'*'だけ取り出してしまうと楽だったようだ。Cはやるだけ。Dもやるだけに見えたが、nが奇数のときに必ず1つ残ることを見落として1WA。非常に難しい。

Eは自由になる要素をqueueで管理するかstackで管理するかで最小・最大を分けることができる。面白い。Fはビビるが、グラフの形がシンプルなのでできる。入力が不親切。制約の文言も不親切。Gは'z'から・'a'から決めるとか謎の方針を産んでしまったが、結局は冷静になってやるだけ。

読んでいたラノベを読了。「暗殺者である俺のステータスが勇者よりも明らかに強いのだが4」。前の巻の刊行から2年が経過しており、内容やキャラクターをかなり忘れてしまっていたが、それは出版側もわかっていたのか冒頭にキャラ紹介やあらすじが付いていて助かる。細かいことを忘れてしまっていても面白かったので、すごいなあという気分になった。

文章に何かしらの特徴を感じたのでちょっと考えてみたが、どうやら会話文が極端に少ないようだ。大半は視点キャラの独白で進行する。このあたり、ちょっとした仕草から読み取らなくても独白で心境などを事細かに描いてくれるので、頭を使わずに読める、かもしれない。

この本の帯にも出版部数が書いてあった。シリーズ4巻（+漫画化3巻？）で驚きの80万部だ。先に挙げた2シリーズを大きく引き離している。そこまで人気だとは思えないのだが……。

1巻が出版されてから3年経っている、という理由かとも思ったが、とはいえ1巻は最初の1年で6刷されているので、最初から売れているらしい。

この作家は僕と同い年のようで、大学受験の直前の11月と直後の3月にそれぞれ本を出版している。流石にヤバすぎる。3月に出した本には、無事大学生になれたとのことが書いてあった。

午前3時半就寝。

03/26(金)

正午、起床。UTPCのため、起床時間を昨日より遅くするわけにはいかなかった。

食事してラノベを読む。「転校先の清楚可憐な美少女が、昔男子と思って一緒に遊んだ幼馴染だった件」。最近こういう「男友達のような距離感の女友達（美少女）」をヒロインに据えたラノベをよく見る気がする。これも同じ系列の作品に思えて、ラブコメとしてはまあ……普通だという感想。ちょっとしたお色気シーンで、男友達の感覚だったヒロインが見せる女らしさに主人公がドギマギするというのもテンプレートだと考えて良い。1点、主人公とヒロインの関係を学校ではひた隠しにしている、というのは結構僕の好みの設定だと思う。

さらにもう一冊。「幼馴染の妹の家庭教師をはじめたら3」を読んだ。前の巻でヒロインと主人公がくっついて、作者もそこで一区切りだと考えていたようだが、続刊を出せたので出したらしい。新ヒロイン登場。主人公は彼女ができた余裕が現れてモテ始めているらしい。これは好きな設定。ネタバレになってしまうが、新ヒロインはこの巻の最後で告白するところまで行く。それをバッサリと断ってしまうあたり、態度がハッキリしていて現実的には好印象だろうが、ラノベ的には大丈夫か？と心配になってしまう。

昨年のICPCの写真が公開された。これは僕（灰色のパーカー）が企業賞をもらって両手を挙げて回っているところ。

pic.twitter.com/Kh1EuV9Oe7
— こたつがめ (@kotatsugame_t) 2021年3月26日

yukicoderに参加した。Cで詰まって、Fもかなり難しく、結局Gが間に合わなかった。

Aは値の小さいものから貪欲に取って損しない。Bは食い違うindexをsetで管理する。Cはコンテスト後に解説を読んでupsolveした。N==Kのとき（だけ）が難しいと考えていたのは正しくて、全員がなるべく均一に誤答するというのも正しかったようだ。そこからAを使って穴埋めするのが間違っていた。Dは頑張ると解ける。添字を1ずらしたりしそうだったので丁寧に書いていたが、結局そういうことはなくて綺麗な式になった。

Eは難しかった。最初は使う航空会社を決め打って、頂点をマージしてからグラフ上の最短経路に帰着すると思っていたが、できるグラフが木ではないことにLCAを書いてから気づいて絶望。改めて考え直し、航空会社の間に辺を張って最短経路問題を解くと良いことがわかった。せっかく書いたLCAが無駄にならなくて良かった。

Fは値0だけ特別扱いして、ほかはmod 2^10でまとめてカウントする。Gも同じ要領で解けて、今度は値0と1を特別扱いして頑張る。A_i==0なる値が出現して以降は常に0になることに注意。

夜、ラノベを読みつつGCJ qualに出た。30点取れば良いらしい。

Aは愚直に計算する。Bは最後の1文字を持つDP。Cは逆順に値を埋めつつ適当な区間をreverseしていくと上手くいった。これはほとんど直感で導き出した答えだったのでびっくり。Dは要素を2つ選んでpartitionとするようなクイックソートができる。再帰的に適用して、2段階目以降は呼び出し元のpartitionと比較することで2つ選んだ要素の大小もちゃんと判定できる。Eは諦めた。

溜めていた日記を書いて、午前4時就寝。

03/27(土)

午前12時半起床。急いで食事をし、UTPCに備える。

AGHの満点とDEの部分点を取った。いろいろ手を出しては見たものの、あまり解けなかった。

Aはよい。二分探索しかないと思っていたが、線形時間でも解けるらしくてすごい。Hもまあよい。Gは、最初ある2行を選んでflipしていたが、このとき対角成分の符号を変えないようにするとずれる。正解は対角線上で交わる行と列を同時にflipすること。

Dは、Mがdistinctだとすると、選ぶ人で最もMの値が小さい人を決め打って、それより大きなMの値を持つ人からK-1人選ぶ全ての場合について1/Mの積の和が求まればよい。これはMをソートすると前からdpで計算することでO(NK)で部分点が得られる。distinctでない場合もソートで順序付けしたと考えれば良い。満点は、上の式を多項式の積と和に言い換え、積と和をペアにして持つことでセグ木のようにマージしていけるというもの。多項式の積に言い換えるのはわかったが、そこから適当に係数をいじることで積のまま和を求めようとして失敗した。結局多項式の1点しか見ないので、全体を和で持つという発想がなかった。

Eは、ある区間をまとめてソートするとしたとき、どの2つの区間に分けてソートしても同じ結果にならないときだけ遷移できる。区間を決め打ったときにそれがvalidかを計算するのはどうとでもなるはずで、これはO(N^2)。部分点。

Jをupsolveした。Aをマージしようとすると、x,x,x+1があったときに2xと2x+1のどちらを作るべきか一意に定まらない。Bを分割するとよいようだ。これは全然考えなかった。さらに、Aより先にBを使い切るのもダメだということを見逃していくらかWAを重ねた。

Aをdcで、GをOctaveでコードゴルフしておいた。Gは普通のbit全探索をOctave風味に直したコードで書いたが、bitを並べた行列は対称性があるため、hadamard行列のように名前が付いていて関数で一発で生成できるかもしれない。

夜、外食して帰りに本屋に寄った。本を10冊買った。

└( ＾ω＾ )┘♪ 買った♪└( ＾ω＾ )┘♪ 買った♪ pic.twitter.com/wiuhNhoFUq
— こたつがめ (@kotatsugame_t) 2021年3月27日

「時々ボソッとロシア語でデレる隣のアーリャさん」は、前回本屋に行ったときは在庫切れで、重版の予定も出ていなかった。本屋に行く前にネットで確認すると、依然「取扱不可」の表示で諦めていたが、念の為探してみるとしれっと入荷していた。奥付を確認すると再版だったので、無事重版してくれたのだろう。

帰宅してABC197に出た。24分全完で2位。Eで勘違いしてしばらく詰まっていたのが痛い。

Aはよい。Bは面倒。Cもよい。Dは面倒。Eは区間の両端さえ考えればよくて、これは前にCFで見た。バチャだったかもしれない。Fはパスの両端を持って縮めていく。

Aの最短はVim。明らかな5B解が存在して、1秒差で負けた。

pic.twitter.com/7F27jIRfdn
— こたつがめ (@kotatsugame_t) 2021年3月27日

Bは、最初はスタートから順に置換するのを連鎖させる方法でPerl 140Bを作ったが、マッチした文字列の長さを見ると良いようだ。横はともかく縦が面倒で、transposeを使ったり、行の幅で割ったりしている。CはRubyで再帰する。再帰の呼び出しに入力をそのまま埋め込んでevalすることで縮められて、このとき先頭の1要素だけ初期値に抜き出すのが簡単にできる、ということで抜き返した。DはRakuで複素数を使う。

EFは手付かず。Fは嘘解法が通るということで書いてみたが、TLEしたし、そもそも提出する前にafter_contestが追加されていた。

UTPC-Aの最短が取られていた。線形時間で計算する方法にも2種類、前から見るものと後ろから見るものがある。僕は前から見ていたが、dcはスタックの言語なので後ろから見るのも比較的簡単に書ける。これでループ部が改善することもあって-2B。

「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました3」を読んだ。清々しいまでのチートもの。まあ主人公が強いのは良いことなので、よし。キャラクターをほとんど忘れていたので、最初のほう男だと思って読んでいたキャラクターが女でびっくりしたりもした。剣聖と言われると何もなければ男キャラクターをイメージしてしまう。

夜寝る前、ARCの配点が出た。345588。全完チャンスか……？最近の800は難しいので、なんとも言えない。ただ4問目までで詰まると人生が終了することは確かか。

午前2時就寝。

03/28(日)

午前7時半起床。昨日今日と朝に検温している。これはDDCCからのメールに書いてあったこと。寒い中で計ったのが良くなかったのか、36.3℃と36.1℃だった。流石に平熱がこれであるということはないだろうが、とりあえず発熱はない。

GCJが終了したので結果を見た。Bのhiddenが落ちていた。なぜ落ちたのかわからないのでTLで聞いてみたところ、バグを教えてもらった。

その DP はよくて、初期値の与え方によっては一文字目を置いた時に不正にマイナスポイントを獲得しうると思ったんですがそこじゃないですか？
— ふっぴー (@fuppy_kyopro) 2021年3月28日

点数的には69点なので、無事Round 1に進めた。

食事してノーパソやノート・筆記用具などを持ち、富山駅まで送ってもらった。午前9時の新幹線に乗って一路東京へ。車中では円城塔「文字渦」を読んでいた。ちなみにこの日記を書いている時点でまだ読み終わっていない。

ここから先の話は、別に参加記を書いた。

kotatsugame.hatenablog.com

帰りに新幹線から出場したARC116について。開始直前にスマホの電波が不調になるなど大変焦ったが、なんとかスムーズに問題を見ることができて助かった。

ぞいぞいしてきた pic.twitter.com/Puk0LfI7Ec
— こたつがめ (@kotatsugame_t) 2021年3月28日

結果はEまでの速解きで28位、パフォーマンス2937、レートは2662→2692(+30)。

A問題は明らか。この明らかさはむしろコーナーケースへの疑いが強くなるが、自分を信じて提出した。B問題は適当に書く。C問題は比に言い換えると総積がM以下となる。2e5以下の素数を列挙して、それぞれどこに割り振るか決める再帰全探索を、ちょっとした枝刈り付きで書いてみたところ、サンプルの最大ケースでも速かったので提出した。計算量はよくわからない。Dを開いたらまた数え上げで笑ってしまったが、こちらは1桁ごとに見るDP。瞬殺。

Eはパッと見二分探索+DFSだが、正当性がよくわからなかったので、一旦順位表を確認。そこそこ良い位置についていて安心するが、すでにSSRSさんが5完していて目を剥く。こんなに速いんだから、どうやらさっき考えた適当なDFSで良さそうだと見当を付けて実装した。再帰関数が返す値を上手くイメージしておらずちょっと戸惑いつつもサンプルがあったので提出。すると1ケースだけ落ちてしまった。しかし幸運にも適当に試したケースがWAのケースだったので、すぐに修正できてAC。ちなみに落ちたのは、根に直接情報を伝達する必要があるかの判定ミスだった。

Fもよくわからないので、とりあえずA問題とB問題のコードゴルフをした。Fに戻って考えてみる。例えば、全ての数列の長さが2以下だったら楽だろう。長さ2の数列のどちらを選択するか？ということのように、先頭と末尾のどちらかを削ることによる利得がプレイヤーによらず定まって、高橋君はその大きな方を、青木君は小さな方を選択するというようにできないだろうか？結果的に言えばこれは正解の方針だが、コンテスト中の僕は利得をプレイヤーによらず定めるところで躓いてしまった。

ここでサンプル2を眺めつつ、大胆に予想を打ち立てる。数列の真ん中の方の値しか関係ないのではないだろうか？これは、自分が真ん中からずらそうとして削っても、相手は反対側を削ることでそれをキャンセルできる、ということからわかる。この考察には既視感があった。奇数長の列の真ん中を取り、偶数長の列は真ん中2つだけ見ることで、全ての数列の長さが2以下の場合に帰着できた。

しかしこれは合わない。奇数長の列の真ん中を取るのではなく、真ん中3つを見て適当に定めると良さそう。このとき、場合分けして計算した結果から、自分から選択すると相手に邪魔されるので、どうしても損してしまうことがわかる。つまり奇数長の列を考えるのは後回しになりそう。実際にどちらが選択することになるのかは、偶数長の列の個数の偶奇で定まる。これを実装するとサンプルが合うが、WA。そのまま修正できずコンテストが終了した。

終了 pic.twitter.com/DkFAd5Kc3q
— こたつがめ (@kotatsugame_t) 2021年3月28日

終了前の数分を争うような状況にならなくて良かった、という思いもあるものの、全完していない以上、半ば諦めてしまっていた自分の弱さも感じてしまう。

コードゴルフについては、Aをdcで、BはRubyで書いただけ。dcはRで出力文字列を持ってくる関係上|コマンドを使うのが定石だが、TLEしてしまったのでおとなしく4%1+Rとした。Bは適当に書いて同値な変形を繰り返す。modの値を変数に入れるとき、そのまま和の変数を初期化しても良い、つまりsum,mod=0,998244353とsum=mod=998244353が本質的に同じであるというのはよく使う面白いテク。

帰宅する。風呂に入った後は眠すぎたのですぐに寝た。午前1時半だった。