04/04(月)

午前6時半ごろ目を覚ます。僕が寝ている間にTLが盛り上がっていた。

マジでワロタ pic.twitter.com/SfGz6KYV3C
— のいみ (@noimi_kyopro) 2022年4月3日

ACするのに正当性など1mmも必要ではなくて、ただジャッジ対象のすべてのテストケースで正しい答えを出力できればよい
— こたつがめ (@kotatsugame_t) 2019年9月1日

この考えは今も持っていて、つい最近も埋め込みしたという記述を日記に残していた。言い訳じみたことを言っておけば、さすがにこれは虚無すぎたので、これ以来やっていない。この時はFastest 600問から陥落する瀬戸際で、何とか耐えようと遮二無二だった。

今日も6時間程度FastestやShortestを漁っていた。昨日mmapで取ったFastestのうちいくつかが埋め込みで取られていたので、こちらも対抗し、atcoder_testcasesから落としてきた入出力ファイルを食わせると入力の先頭を必要なだけ読んで場合分け＋出力するPascalコードを生成するコードを書いた。これを使ってまたいくつかFastestを取った。
週記（2022/03/14-2022/03/20） - kotatsugameの日記

以下お気持ち表明。正直な話、このアカウントに対する印象は悪い。特にゴルフされていなかった問題で、当時最短の数百Bytesのコードを中途半端に縮めてShortestを取っていたのが強烈に印象に残っているからだ。縮めるならちゃんと1問に数時間費やす勢いで粘着してほしい。当然そのようなコードにはいくらでも縮める余地があったので、AtCoder ProblemsのListで検索して、このアカウントが最短コードを保持している問題を狙い撃ちして縮めていたこともある。最近は上に書いたようにFastestでも似たようなことを行った。

しかしまあ、そのようなことをやるにあたっては僕も既存の最短コードを参考にしていることだし、それ以外にも普段から1Bだけの更新で最短コードを取ることも多い。埋め込みもやってしまったので、完全に同じ穴の狢である。だから、このアカウントの行動を批判するということはできない。ブーメランとなってしまう。ということもあって、これまでは最短コードを奪い取ることで気晴らしをしていたわけなのだが、今TLで晒されているのを見て、本音で言えばちょっと胸がすく思いがした。

ただし、明確に悪とされることは何もやっていないことに注意しなければならない。先ほども述べたように、自分は決して批判できないのだ。そして、ひとたびこのアカウントが明確に悪とされたならば、自分もまたそうなるという危機感がある。

以下のようなツイートを昔したのだが、この言説が受け入れられると個人的には非常に都合がよい。自分の行いをかなりの部分まで正当化できるからだ。本家ゴルフ場であるanarchy golfでは、そのような改善は元になったコードを書いたユーザ名を自分のユーザ名の後に括弧でくくって付け足すという文化がある。anarchyとは言いつつかなり治安が良い。AtCoderにはそのようなリスペクトを示す方法がないので、こんなことになっていると言えなくもないか？自分にそのようなリスペクト精神が育まれているかについては、怪しい。

Shortestについては1文字縮んだらもう改善と呼ぶと思っているな。結局その1文字を削りきれるかどうかの話なので
— こたつがめ (@kotatsugame_t) 2022年3月4日

以上、お気持ち表明。

布団でしばらく淫夢実況を見て時間を溶かした。思ったよりたくさん投稿されており、さすがに3本くらい見たら正気に戻れて切り上げることができた。

www.nicovideo.jp

学食に行って食事。今年度初めてである。まだ入学式も終わっていないのにかなり人がいてびっくりした。大学院生になったという自覚からくる微妙なアウェー感を抱えつつ、普段と変わらないメニューを注文。ご飯の特大も通常通り提供されていて助かった。

その後生協に寄り、注文していたラノベを9冊受け取って帰宅。今日は僕の前後に1人ずつ並んでいたくらいの込み具合だったので良かったが、これから教科書販売が本格化すると考えれば、受け取りのタイミングは考える必要がありそう。

ブラックサンダーも箱買いしてきた。ブラックサンダーの箱に元からついているバーコードはブラックサンダー単品に割り当てられており、これまで箱買いするときには、レジで読み取ったそれを20倍することで対応されていた。最近、箱買いのためのバーコードが新しく用意され、シールとして貼られ始めたらしい。およそ1年半で20箱以上購入した僕のせいだろうか？それとも他に何人も箱買いした人がいたのだろうか？

帰宅してからはずっと先週の週記を書いていた。土日の分を溜めたまま、昨日は寝落ちしてしまった。週末はコンテストが多く文章量が増えがち。

午後4時半からインターン先の定例会。先週の進捗は、すでに出来上がっていたものを微調整してデプロイしただけ。あとは次に書くコードの構想を練っているという感じで発表した。構想を練っているのは嘘ではないが、実際に書き始めてみないことにはどうにも決めきれないと思ってしまったので、そちらもカスみたいな進捗しかない。

勉強会が一段落した頃合いで、書き上げてチェックまで済ませた日記を投稿した。先週はコンテスト8個に加えJOIG春合宿の問題を解いた感想も書いたのでかなり長くなり、普通に書き終わった段階で28000文字を超えていた。せっかくだから30000文字の大台に乗せようということで途中に適当に追記した後、推敲しつつ微調整を加えて、ちょうど30000文字ピッタリにしてある。

食事した後はラノベを読んだりYouTubeを見たりしていた。しばらくして、椅子の上で少し意識を飛ばしてしまったので布団に移動。なおもラノベを読み続けるつもりでいたが、眠気に耐え切れずそのまま就寝。午後10時前だった。

04/05(火)

午前3時半起床。

ラノベを1冊読了した。「Vtuberってめんどくせえ！」。面白かった。女性Vばかりの箱に主人公が男性Vとして一人だけデビューし大炎上してしまうところからスタートする。その描写は正直かなり辛かった。しかしそれにも耐えて活動を続けた結果、ハプニングなども上手く作用して主人公の人柄が知れ渡り、受け入れられていく話。終盤のデマを完全否定する配信のシーンは、主人公の訴えでコメントの流れがどんどん変わっていく様子が劇的で良かった。

このラノベはカクヨム発である。ハーメルンのVtuberモノは結構チェックしていたつもりだったが、カクヨムのほうは全く見向きもしていなかった。探せば他にもいろいろあるだろうし、楽しみである。とりあえずこのラノベの続きも連載分がたくさんあるので、読んでみたいと思っている。

ゴミ出しして、午前7時半からインターン関連のコーディングを始めた。昨日言及していた構想をとりあえず形にしようと書き進めていたら、良さそうなアイディアが浮かんできたので、とりあえず実装してみた。実際の効果のほどは実データで実行してみないことには何とも言えないが、設計的には満足感がある。考えている設計をまとめて、実装できていない部分を洗い出し、また書き進めて……と繰り返していたら興が乗り、正午くらいまでコーディングを続けていた。

設計に悩んだまま50年が経過し、熟練の設計悩み師となった
— こたつがめ (@kotatsugame_t) 2022年4月4日

チュウニズムのバージョンアップ情報が流れてきた。今回は「ロシェの宝物庫」以外にマップも消えないし、削除曲も少なめで、あんまり大きな変更はないなという印象。ただこれに伴って終了するイベントがちょっと問題。

グッズプレゼントキャンペーンというのがあって、デジタルグッズのキャラクター4種類を集めておきたかった。1種類に30ポイント＝30クレが必要なので、キャンペーン期間中に120クレプレイすればよい。さて今はどれくらい溜まっていたかなとチェックしてみると、直近2回スーパーノバに行った分のポイントがないことに気づいた。どうやら開店からキャンペーン終了まであまり間がないこともあって、キャンペーンの参加店舗となっていなかったらしい。ということで現在76ポイントしか溜まっていないため、バージョンアップまでの一週間ちょっとでさらに44クレプレイする必要があるようだ。2日ほど行けばよいだろうか？頑張りたい。

4月14日(木)より『CHUNITHM NEW』がバージョンアップ！『CHUNITHM NEW PLUS(チューニズムニュープラス)』の稼働が決定！明日から新情報をドンドン発表していくので、お楽しみに！！

●ニュースはコチラからどうぞ！https://t.co/oUGuQk09Mq pic.twitter.com/rTDdML2qZQ
— チュウニズム公式@5/12(木)『東方Extra 4』マップ&東方楽曲追加！ (@chunithm) 2022年4月5日

布団に入って、カクヨムで今朝読んだラノベの続きを読み始めた。午後2時くらいに寝落ちして、午後6時半にまた起床。明日は朝から入学式があるので、また早めに寝る必要がある。しかしカクヨムを読むのがやめられず、深夜までダラダラ読み続けてしまった。

電子レンジで4分から5分温めろと書いてある冷凍食品を食べた。万が一にも冷たいままだと困るから5分温めようと思って時間をセットしたら、見事に焦げ付いてしまった。他に同じものが2食あるので、そちらは4分でセットするようにしたい。

午前0時からSRM827があった。Stage3でTCO R4に進出が決定しているのであまり出るつもりはなかったが、せっかく起きているのだしということで参加を決めた。Appletはまだ証明書チェックに失敗していた。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19131

Easyは不快。単純な算数をさせる問題なのに、制約の上限が何もかも $10^{18}$ になっていてオーバーフローにめちゃくちゃ気を遣う必要がある。Pythonに切り替えて解くのが一番楽なのかもしれない。1周期に解く問題数を最初に求める方針を取り、掛け算がオーバーフローしないことを割り算に変形して確かめることで解いた。チャレンジフェーズで見た解法で、まず最初に1周期以内に答えが求まるかどうか調べ、求まらなかったと分かった時初めて1周期に解く問題数を計算する方針は賢い。この場合分けを入れることで問題数がオーバーフローしないことを保証できるし、チェックと実際の答えを求めるプログラムが同じなので関数を再利用できる。

Medは謎。bit全探索した後bool値のdpをして復元するだけで、とても500点とは思えない。行数の制約が列数の制約より極端に小さいことを利用して、そちらでbit全探索を行うというのは、昔のJOIの「おせんべい」という問題で見た印象が強い。

Hardも謎。ROYGBIVを1234560にマッピングしてから実験すると、 $i$ 番目の人は $\sum_{k=0}^S\binom{S}{k}C_{i-k}\bmod 7$ が答えになるとわかる。これは数列 $C$ の母関数に $(1+x)^S$ を掛けていると考えられる。次数 $|C|$ 以上の部分はまた次数 $0$ に戻るように、つまり $\bmod x^{|C|}-1$ で計算してよいので、二分累乗法で計算すれば長さ $|C|$ の列を $O(\log S)$ 回畳み込めればよいことになる。愚直に書いても間に合うだろうと考えていたら微妙に間に合わず慌てた。冷静になると、扱う数の最大値が $6$ なのだから畳み込んだ直後の配列の値も十分小さく、NTTだけで直接計算できる。SRMでは当然ACLのconvolutionは動かないので、かなり久しぶりに自作ライブラリのNTTを引っ張り出してきた。ビットシフトと加減算の優先順位について、いちいち括弧をつけないと警告が出るのが少し癇に障った。

ほかのRoomに比べ、僕がいたRoomはチャレンジでほぼ落ちず平穏だった。そのままシステスも全部通り、全完6位でレートは2613→2655(+42)。highest。今回の上位6人は全員日本人だったらしい。

SRMが終わって午前2時。そこからすぐ寝れば睡眠時間が6時間確保できたのに、再度カクヨムを読み始めてしまった。まだ大丈夫、もうちょっと、と読み進めているうちに午前7時くらいになって、このまま起きていることに決めた。

午前8時前に布団から出る。食事してシャワーを浴びたりちょっと日記を書いたりしていたらいい感じの時間になった。そこからひとしきりネクタイと格闘した結果、予定より少し遅れて午前9時過ぎに出発。地下鉄を乗り継いで会場に向かった。到着したのはギリギリの時間で、運営も急いでいたのかチェックなしでホールに入れてしまい、せっかく用意してきた合格通知書の出番がなかった。

式は30分程度で終了。感染対策も何もあったものじゃないすし詰め状態で座っていた。式の中盤くらいからスマホの回線が不安定になって、終わってホールから出るまでインターネットに接続できずかなり不安になった。外に出て自撮りした。

ハ〜イ pic.twitter.com/DBgLip0Qhf
— こたつがめ (@kotatsugame_t) 2022年4月6日

何とか連絡のついたたいぺーと、その友人と合流。また地下鉄に乗り、仙台駅で降りて駅ビルの地下で食事した。正午ちょっと前という時間帯でしばらく待ったのだが、ウェイティングシートに書いた名前を読み落とされて初っ端から暗雲が漂っていた。その後店に入って出てきたお冷のコップがかなり汚れていたり、ご飯茶碗の底に乾いた米粒がくっついていたり、食事と一緒に持ってくると言われたドリンクが食べ終わって店員に確認するまで出てこなかったり、かなり悪い体験をした。

眠気からゲーセンに行くのを諦め、また地下鉄に乗って帰ってきた。これから研究室に行くらしい2人と別れて帰宅。

人間関係のパスを縮約した（友達の友達と友達になった）
— こたつがめ (@kotatsugame_t) 2022年4月6日

やっと重い腰を上げて担当教員にメールを出した。特に書くことも思いつかなかったので、メールが遅れたお詫びと挨拶しか書いていない。

大学院に合格した後すぐ担当教員にメールを出している人が多く、かなり焦った。
週記（2022/03/21-2022/03/27） - kotatsugameの日記

布団に入ってちょっとカクヨムでも読もうかと思っていたら即座に寝落ちした。午後2時だった。

04/06(水)

午後7時半起床。寝る前に出したメールに返信があった。研究室に伺って自己紹介などをする日程を決める必要があるらしい。

Twitterの通知で、アカウントを作ってから9年が経過したことを知った。

Twitterに登録した日を覚えていますか？#MyTwitterAnniversary pic.twitter.com/pUAUrKR14q
— こたつがめ (@kotatsugame_t) 2022年4月6日

午後8時にまた寝た。

04/07(木)

午前1時半起床、午前10時半までカクヨムを読み続けてまた就寝。

次に午後6時半起床。午後7時、火曜日に読んだラノベ「Vtuberってめんどくせえ！」の続きとして最近ずっと読んでいた作品の最新話に追いついた。500話以上あってかなり時間がかかりそうだと思っていたが、1話1話が短く文字数としては130万文字ちょっとだったので、数日かかり切りになっただけで済んだ。

kakuyomu.jp

ラノベから変わらず面白かった。以降の章もずっと炎上を題材にしていたが、1巻部分とは違い主人公を擁護する側の意見が描写されることも多く、安心して読めた。その意味では主人公が受け入れられていなかった最初が一番辛かったのかもしれない。主人公は問題のある人間ではないので、話が進むにつれだんだん本人が炎上するというより巻き込まれて炎上することが多くなってきていた。

「炎上」それ自体について、初めのころのキツい描写の印象が薄れ、慣れもありなんだか軽く扱っているような感覚を得てしまったものの、実際は非常に重い話なのだと自分を戒めつつ読んでいた。メインの話はそうやって大変なことも多く描かれていた一方、間に挟まれる短編はひたすら安穏としていて、主人公たちの関係性に集中して読むことができた。

起きて担当教員からのメールに返信した。自己紹介の日程について、明日金曜日はガイダンスで山に登る用事があったので、その時ついでにできればなと思っていたのだが、メールを返信するタイミングを逃してしまった結果前日夜となり、さすがに明日の予定を今メールで知らせるのは不味かろうと思って、来週火曜日の午後でお願いした。

メール返信。生活リズムが合わず、1時間で帰ってきた返信に1日かけて返信。クソデカレイテンシ
— こたつがめ (@kotatsugame_t) 2022年4月7日

シャワーを浴びたりして午後8時。夜は天気が悪いらしいのでゲーセンに行くのを諦め、布団に戻って今度は「Vtuberってめんどくせえ！」の没話・零れ話集を読み始めた。午前0時頃寝落ち。

04/08(金)

午前4時起床。

少しして、昨日読み始めたカクヨムを読み終えた。誕生日配信の話が特に気に入った。誕生日という制約から短編を配置できる時期が決まり、しかしその時点での作中における仲としては進みすぎた2人を描いてしまったため没になったらしい。最新話まで読んだ以上その辺りの整合性はあまり気にならず、非常に高い糖度が大変良かった。主人公のタイミングの良さもまさにヒーローという感じで格好いい。

kakuyomu.jp

チュウニズムのバージョンアップに伴う新機能で非常にありがたいものが発表されていたのを知った。キャラクターを育てて手に入るスキルシードが筐体で確認できるというもの。これまで、目的のスキルシードを獲得できるキャラを育てる際は逐一wikiを調べて選択していたのだった。

【『CHUNITHM NEW PLUS』の新機能紹介②】
マップ選択画面にて、カーソルを合わせたエリアの「課題曲」「課題曲のアーティスト」「手に入るキャラクターのスキルシード」が確認できるようになったよ！さらに、キャラクター選択画面でも、育成することでゲットできるスキルシードが確認できるように！ pic.twitter.com/EbKyjEtpKL
— チュウニズム公式@5/12(木)『東方Extra 4』マップ&東方楽曲追加！ (@chunithm) 2022年4月7日

さらにハーメルンを開いて1作読み始めた。30話弱と一口サイズだったので、午前8時半ごろに読了。「魔法科高校の煌黒龍」。

syosetu.org

良かった。クロスオーバーでやってきた主人公アルバトリオンが最強でありつつも、原作主人公の司波達也の出番があまり減っておらず、両立できている感じがする。最初数話を読んだ感じでは原作主人公を放って暴れ回るタイプの話かと思ってしまっていた。アルバトリオンが感情が薄いタイプの男性として描かれているのも良い。

布団から出てシャワーを浴びたり洗濯機を回したりしつつ、日記を少し書いた。午前10時過ぎに家を出る。今日は午後3時までゲーセンにいて、移動して午後4時から山で大学院のガイダンスに出席するという予定。まず生協に寄って食事し、クリーニング屋に卒業式・入学式で着たスーツ一式を預け、正午を少し回ったあたりでゲーセンに到着した。

今日の成果は新曲を埋めただけ。グッズキャンペーンのポイントは16クレ分増えて、92ポイント。Elemental CreationのULTIMAでSSSを出せたのはかなり驚き。低速地帯の前までで0-2出してしまい諦め気味でプレイしていたのだが、終盤は擦りも鍵盤もあり得ないくらい上手くいって耐えた。もっと上のスコアも狙えたということになり、返す返すも前半のミスが惜しい。その後も数回プレイしてみたものの、あれほど上手いプレイはもう出ないだろうということを再確認するだけに終わった。

Elemental Creation ULT SSS！！！
前半で0-2出たけど後半上手かった！ pic.twitter.com/Vrzds5PE7i
— こたつがめ (@kotatsugame_t) 2022年4月8日

一旦帰宅し、自転車から原付に乗り換えて山に登る。前を走るトラックに邪魔されて信号が見えず、黄色信号で交差点に突入してしまった。対面で右折待ちがおり、さらに申し訳ない気持ちになった。途中生協でラノベを受け取りつつ到着し、それからガイダンスの部屋を確認した。普段講義を受けていた数学棟でガイダンスだと思っていたのに、合同棟というちょっとよくわからない建物を指示されていたらしい。原付を停めた場所から少し歩いてようやくたどり着いた。

ガイダンスの間は眠くて目を閉じていた。就活の話をされていた記憶がある。自己紹介タイムが始まったので目が覚めた。僕の番が回ってきたので、学年と専攻分野と担当教員を述べ、あとは趣味の競技プログラミングについて少し触れた。競技プログラミングが趣味で～す、だけだとなんだか物足りなく感じたので、追加で一言考え、「4年生のときにいいところまで行ったのでモチベが消え気味」と述べた。思い返せば、モチベが消えているというよりは、他にやりたいこと（ネット小説漁り）ができたというのが正しい気がする。

ガイダンスが終わってから、自己紹介の時に見つけた僕と同じ担当教員の人に挨拶しに行った。その人は別大学から来られたようで、その関係かこれから研究室に呼び出されているらしいので、試しについて行ってみることにした。数学棟の玄関は既に施錠されており、前で同級生が何人かたむろしていたが、後ろから来ていた先生が通用口を開けてくださった。そのままトントン拍子で話が進み、2人そろって担当教員に挨拶することになった。代わりに、火曜日午後に挨拶に伺うという予定はキャンセルを申し入れた。

1時間ほどかけて、これまで学んできたことを説明したり話を聞いたりした。先生が僕らをどのように指導するかを決めるためらしい。そうすぐに決まるものでもないようで、また来週木曜日に集まって、今度はセミナーを行うことになった。自分が取り組んだことをちょっと準備して説明する。院試の面接のときに取り上げようとしたSliding Window Aggregationについて話そうと思っている。面接のときは僕のまとまっていない話ぶりがまずかったのか、それとも一人にそんな時間をかけていられないからか、かなり最初のほうで制止されてしまったので、リベンジ。

午後7時前に終了。この時間に学食の夜の部が営業していることを覚えていたので、そのまま2人で行った。すると数学科の友人がほかに数人いたので、合流してしばらく駄弁った。そういえば彼らはガイダンスのとき自己紹介していなかったなと思って聞いてみると、盛んに自己紹介していたのは教室の前のほうに座った人間ばかりで、後ろのほうはあんまりそういう雰囲気でもなかったらしい。全員分回していたらかなり時間がかかっていただろうし、それもやむなしか。

午後8時を回って帰宅。即座に布団に入り、就寝報告をする間もなく寝落ちした。午後8時半過ぎだった。

04/09(土)

午前5時頃起床。二度寝できず午前9時半までハーメルンを読んでいた。起き上がり、午前10時からGCJR1Aに出た。

https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5

1問目は文字列の先頭から考えれば、見ている文字とその直後の文字を比較することで2倍するべきか否かがわかるはず。ただ同じ文字だった場合はさらにその後ろを見ることになるので、それなら最初からランレングス圧縮しておけばよい。

2問目は $2^0,2^1,\dots,2^{29}$ を用意しておけばよい。残り何を出力しようと、 $B$ と混ぜて貪欲に選ぶだけで目標値との誤差を $10^9$ 未満にできるので、あとは2べきを適切に当てはめればピッタリに合わせられる。そういう証明はつけていたものの、ビビり、貪欲に選ぶ前に降順ソートした。ローカルテスターを回してみると何も言わず即座に終了してしまったので、何かエラーでもあったのかと思ってしばらくコードを眺めていた。デバッグ出力を挟んだことでちゃんとケースが実行されていることを知り、何も言わずに正常終了するのがACの合図だと気づけた。ちょっと不親切。

3問目は少し難しい。適当に貪欲を書くとサンプルで落ちる。最初から最後までつけたままの重りを取り除いて考えると、機械にセットした重りをすべて取り外すタイミングがどこかで発生する。貪欲に操作した結果のタイミングと最適なタイミングが異なっているらしい。では、そのタイミングを全探索してみるのはどうだろうか？考えてみると、こうやって分割することで元と同じ形をした2つの部分問題に分割できていると分かった。なので区間dpができそう。

適当に書くと、まず区間が $O(E^2)$ 通り、その分割がそれぞれ $O(E)$ 通りで、さらに計算の度に「最初から最後までつけたままの重り」を求めるのに $O(EW)$ かかる。一番最後の共通する重りを求めるループについては、区間を決めたときにやることにしたらよいのではないかと思ったが、そうするとこれまでの分割の様子によってdpの値が変わるので答えが正しく出なかった。遅延セグメント木で $E$ の代わりに $\log E$ を付けてみるも、定数倍の影響かさらに遅くなった。しばらく考えて、分割を決める $O(E)$ のループと共通する重りを求める $O(EW)$ をまとめて行うことにした。累積minを計算する感じ。これで全体 $O(E^3 W)$ になって、定数倍も6分の1くらいつく。手元では十分高速に動作したので、投げた。

1時間半ほどで解き終わり、その後は日記を書いていた。全完123位。1問目について、文字列の後ろから見る $S\leftarrow\min(c+S,c+c+S)$ とする方法をTLで見てびっくりした。この問題の制約ならこれが一番シンプルで簡単そう。3問目は、初めに $O(E^2W)$ かけてすべての区間に対して共通する重りの総数を前計算しておけば、分割を決める $O(E)$ のループだけで計算できるようになる。共通する重りが区間を広げるごとに単調に減少するので、minの差の和とminの和の差が一致するようになったと言える。

また布団に戻り、午後3時頃までハーメルンを読んで就寝。午後7時起床。今日は今年度初めての冷凍弁当が届くと思っていて、1時間おきに目覚ましをかけて深く眠らないようにしていたのだが、受け取った記憶がない。すわ寝過ごしたかと焦ってインターホンを見て、来客がなかったことを確認し、配達が来週開始であることにやっと気づいた。目覚ましのかけ損で眠い。

しばらく布団でハーメルンを読み、起きて日記を書き、午後9時からARC138に出た。

Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138） - AtCoder

Aは、 $i$ と $j$ （ただし $i\le K\lt j$ ）を入れ替えようとしたとき、最初に $i$ を $K$ 番目に持ってくることで合計 $j-i$ 回の操作で達成できる。ここから1要素だけ入れ替えるので十分であるということもわかる。よって、加えて $A_i\gt A_j$ を満たすようなペア $(i,j)$ に対して $j-i$ の最小値を求めればよい。何かデータ構造を使いそうになったが、冷静になれば値でソートして $j$ を舐めつつ $i$ の最大値を管理するので十分。Bは操作を逆から見る。操作Bは行える限り貪欲に行ってもよいことがわかるので、あとはシミュレートするだけ。かなり簡単。

Cは大きいほうから $\frac N 2$ 枚取れそうなことが直感的に分かった。証明できなかったがいかにも正しそうだったので、そのまま書くことにした。取りたいカードを $+1$ と、取りたくないカードを $-1$ としたとき、右からの累積和が常に $-1$ 以上になればよいとわかる。累積和と途中の最小値のペアはセグメント木に乗るので、すべての $k$ に対してチェックできる。

Dは謎。隣接項のXORとしてありうる数を全列挙したあと先頭から全探索するコードを書いて、小さいケースの出力を眺めていた。 $N=1$ のケースを除けば、 $N=K$ または $K$ が偶数の場合明らかにNo。それ以外は構築できそうだ。特に、隣接項のXORを取ってみると1個おきに $2^K-1$ が出現しているので、かなり規則性がある。それらを取り除くとより小さいケースに帰着できそうだったので、何とか法則性を見つけようと格闘していた。残り1時間になったくらいで少し手詰まりになり、順位表を確認すると、もう100人以上に解かれていてひっくり返る。そこでふと、先ほど書いた全探索のコードが一瞬で答えを出してきたのが気になった。試しに大きなケースで試してみると、再帰が深すぎて手元ではセグフォしたものの、コードテストでは相変わらず爆速で終了する。慌てて提出したら50msちょっとで通った。

残り時間はE問題を考えていた。 $1\dots A_{i_1}-1$ の決め方とそれ以降の決め方で分けてdpするのだと思い、前者は $O(N^2)$ になったものの、後者が $O(N^2K)$ から落ちずコンテスト終了。ノーペナ4完で78位だった。Cの証明は、全体の和が $0$ であることを考えると、累積和 $S$ が最小になる点からスタートすることで $S\rightarrow S-\min S\ge 0$ になることからわかる。

A問題だけ適当にRubyでコードゴルフして、午後11時半からECR126に出た。

Dashboard - Educational Codeforces Round 126 (Rated for Div. 2) - Codeforces

Aは直前をswapしたかを持ってdp。Bは $32768=2^{15}$ なので2進数で考えようと思ったが面倒。 $0$ から操作を逆向きに行うBFSができるので、それで最初に全通りの答えを求めて解いた。Cはそろえる高さを $\max h$ と $\max h+1$ 両方試せば十分。高さを揃えるときは、とりあえず貪欲に $2$ を足してみて、あとから回数を調節すればよい。Dは後ろから見れば貪欲に取ってよいとわかる。前からではできない。加算する値とその差分を管理することで、データ構造を持ち出さずともシミュレートが行える。先頭 $k$ 項は直接見て、 $\max\lceil (b_i-a_i)/i\rceil$ を答えに足す。Eはセグ木。区間に対して両端の情報、具体的には端のどのマスとどのマスが連結であるかの情報を持つとマージできる。マージ関数は気合い。迂回して連結になるようなケースを間違いなく処理するためにはUFを持ち出すのが安全。ただマージ関数内でいちいちUFの初期化などしていてもよいかかなり不安だった。何とか600msちょっとで通った。

Fは解けなかった。長さ $l$ の区間をテレポーターで $k$ 個に分割すると、そこを抜けるのに $q=\lfloor l/k\rfloor$ として $q^2\times(l-(l\bmod k))+(q+1)^2\times(l\bmod k)$ だけコストがかかる。 $k$ を動かしてこのコストの変化をみると、 $q$ が一定の間は変化も一定であることに気づいた。そこで、各区間に対して商列挙を行い、変化が大きいところから取っていくようなコードを書いた。しかし35ケース目でMLEやTLEが出てしまい、結局通せなかった。それもそうで、長さ $\sqrt N$ 程度の区間が $\sqrt N$ 個ある場合、全部商列挙すると合計 $O(N^{3/4})$ になってしまう。正解は、コストの変化をどこまで使うかで二分探索することらしい。

5完までは速かったし、Fはあまり解かれなかったので18位。

そこから朝までは淫夢実況を見つつ日記を書いていた。午前8時頃、切り上げて布団に入りカクヨムを読み始めた。途中で今日のARC-Eが解けた気になって、起き上がって実装してみたものの全然計算量が落ちていなかったため、記録としてTLE解を提出しておき、また布団に戻った。午前11時過ぎに寝落ち。

04/10(日)

午後4時半起床。午後5時からOpenCupで、シャワーを浴びていたら数分遅れてしまった。

チームではAJDBCFGをこの順に解いた。僕はADBの考察と実装をした。

最初、少し遅れてAを読み始めた。見た目は厳ついが、よく見ると問題文の状況にかなり制限があって考えやすいことに気づく。適当に考察しつつ順位表を見るとどんどん通されていたので、慌てて書き始めた。一発で通った。次にJが解かれていて、これはチームメイトが考察して書いたもののTLEが出ていた。そこから1時間くらい格闘して通ったらしい。

その間、僕はCを考え、諦め、Dに進んでいた。順位表で大量にペナがついていたので、慎重に考察したつもり。 $n\ge 3$ 頂点の単純グラフであって、頂点 $1\dots k$ は次数がちょうど $1$ 、それ以外は次数が $2$ 以上であり、グラフの直径が $2$ 以下であるようなもののうち辺の数が最小のものを構築せよという問題。 $k\ge 1$ の場合は簡単で、ウニグラフにならざるを得ないので、残りは次数の条件を満たすように置くだけ。 $k=n$ または $k=n-2$ の場合はその条件を満たせないため、作れない。

$k=0$ の場合が難しかった。 $n\le 5$ では大きなループを作るのが最適なので、 $n\ge 6$ でもそこに対角線を張ることで構築するのかなと思った。しかし $n\ge 7$ ではウニグラフに辺を追加する方法が安上がりなようだ。 $n=6$ では辺の数が8本で一致したので、そのあたりで処理を切り替えることにした。しかしこれを投げるとWA。 $n=6$ でしばらくいろいろグラフを作っていると、なんと7本で構築することに成功してしまった。5頂点のループ1-2-3-4-5-1に1-6と3-6を足すというもの。この調子で $n=7$ も減るかと思ったがそんなことはなかったので、とりあえずこのケースだけ対応して投げなおしてみたら、通った。パズル。

次にBを読んだ。頂点数が $n\times 2^m$ で各頂点から辺が高々 $mn+m+2$ 本出ているグラフで、全点対間最短距離を求めるという問題。しかしさすがに辺数はもっと減る。最悪ケースが思いつかないので、PCも空いていることだし実装してしまうことにした。実装して適当なケースを試してみるとそれなりに高速に動く。ここから効きそうな考察が全然わからなかったためとりあえず落ちてから考えようと思って投げてみると、3.3secくらいで通った。

残り時間はFに口出ししたりGを考えたりしていた。あまり良い働きができないまま、午後9時になったのでABC247に出た。

ABCのことを書く前にOpenCupの残りについて書いておこう。Cは僕が離脱する1時間前に通っていた。僕が離脱してから20分ぐらいして、FとGが立て続けに通ったようだ。GはML 16MBという空間計算量が制限された問題だったので、かなり大変そうだった。FもTLEに苦労していたようだ。僕が諦めたC問題だが、 $\max(x_1,x_2,x_3)-\min(x_1,x_2,x_3)=\frac 1 2\left(|x_1-x_2|+|x_2-x_3|+|x_3-x_1|\right)$ という式を使ったらしい。見覚えがないことはない、気がする。

ABC247について。

AtCoder Beginner Contest 247 - AtCoder

AはVim。Bは面倒そうだったので先にCを解いた。Rubyで、配列を足し算していく方法。次にB問題もRubyで解こうとした。文字列の出現回数をカウントしてチェックしようと思っていたのだが、 $s_i=t_i$ のケースに対処できないことに気づいてC++で解くことにした。以降もC++。Dは値と個数をペアにしてqueueに入れる。Eは各 $i$ に対し、直前の $X$ ・ $Y$ ・ $X$ より大きな数・ $Y$ より小さな数の出現位置を記録して、 $R=i$ としたときに可能な $L$ の個数を求めた。これらの出現位置は、dequeにスライド最大値・最小値を求める感じで値とインデックスをpushすることで取得した。後から整理してみれば、変数を用意して書き換えるだけでよかったとわかる。

Fは、同じ数が書かれたカードに辺を張るとグラフ全体が複数のループに分解できる。それぞれのループにおいてどの頂点を選ぶか決める。決めるときは隣接する2頂点のうちどちらかを必ず選ぶという制約があり、これは1点決め打って1周dpする方法で解ける。Gは重みを無視するとマッチング問題になるので、同様にフローで解けないか考えたら解けた。最小費用流を流量を変えて何回も解くことになったので、ACLのslope関数を使って実装した。

Exは転倒数の偶奇など考えていたが、入れ替える2人は隣接している必要がない。このような操作で $1,2,\dots,N$ を $P_1,P_2,\dots,P_N$ に並び替えるのは典型的。 $i$ と $P_i$ を辺で結んだfunctional graphを考えれば、長さ $l$ のループは $l-1$ 回の操作で実現できるとわかる。つまり連結成分ごとに操作回数が $1$ ずつ減るとみなせるので、 $N$ から連結成分数を引いた数が $K$ 以下になればよい。また最初うまく題意を取れていなかったが、入れ替えるときに選ぶ $i$ と $j$ は異なる必要があるようなので、偶奇も一致している必要がある。いずれにせよ、連結成分数ごとに順列の数を数え上げられれば解ける。

連結成分上では $c_i$ が一致する必要があるので、以降は数列 $c$ の頻度配列 $cnt$ だけ扱うことにする。各 $c$ の出現回数 $n=cnt_c$ について独立に考えてよい。長さ $n$ の順列（から作ったfunctional graph）を連結成分数ごとに数え上げたい。挿入dpを考えると、 $0\le i\le n-1$ を列に追加するときは「これまで作ったループのどこかに入れる」のが $i$ 通り、「一人だけでループを作る」のが $1$ 通り。多項式で表現すれば、 $dp\leftarrow dp\times(x+i)$ とわかる。つまり $dp=\prod_{i=0}^{n-1}(x+i)$ である。

それぞれの $c$ についてこのような多項式を作れば、それらの積を取ることで全体の数え上げができる。具体的に書くと $\prod_{c=1}^N\prod_{i=0}^{cnt_c-1}(x+i)$ となり、これは1次式 $N$ 個の積である。そのような積はセグメント木っぽくマージしていくことで全体で $O(N(\log N)^2)$ で計算できるので、解けた。実装は多項式をqueueに詰め、queueのサイズが1になるまで「先頭から2個pop」→「積をpush」を繰り返すのが簡単。

ノーペナ全完3位。

Gで、ACLのslope関数が流量とコストの関係の折れ線グラフを返すという部分に引っかかってWAになっていた人を観測した。すべての流量が出現するわけではないので、手作業で間を補完する必要がある。この実装は最小費用流の実装、つまり「コスト最小のパスに流せるだけ流す」ということを思い浮かべれば自然に感じられると思っている。そうやって流せるだけ流した時の流量はちょうど $1$ とは限らないわけで、そのパスを使い切るまではコストが同じペースで増えていくことになる。折れ線の線分にあたる。

コードゴルフ。Aは最初に提出したVim 7Bが最短。取れてよかった。Bは $s_i$ と $t_i$ を混ぜた多重集合を作り、 $\{s_i,s_i,t_i,t_i\}$ という多重集合を含むかどうかチェックすればよい。RakuのBagを使った。Cは $1,2,\dots,2^N-1$ のlsbに1を足したものを出力すればよく、Rakuで24Bになったのだが、dcで再帰関数を書いたほうが短くなった。DはRubyで負け。EはAWK。残りは手付かず。