週記（2021/02/15-2021/02/21）

02/15(月)

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

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

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

週記（2021/02/01-2021/02/07） - kotatsugameの日記

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

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

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

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

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

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

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

午前10時就寝。

02/16(火)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

午前11時就寝。

02/17(水)

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

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

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

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

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

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

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

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

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

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

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

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

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

午後6時半就寝。

02/18(木)

消えた。

02/19(金)

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

syosetu.org

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

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

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

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

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

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

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

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

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

02/20(土)

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

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

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

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

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

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

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

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

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

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

02/21(日)

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

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

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

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

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

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

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

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

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

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

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