10/18(月)

先週の週記のページで「が、」を検索すると、なんと70件も存在した。先週は14000文字と少しだったので、実に200文字につき1回のペースでこの接続詞を使っている。文章ごとに読み直した限り、少なくとも自分にとって不自然な言葉遣いにはなっていない一方、全体として見ればあまりにも多すぎる。というわけで、今週の週記はこの接続詞をできるだけ使わないように書いてみたいと思う。逆接なら別の接続詞を採用し、そうでない微妙な用法の場合は、その文章の語順をもう一度推敲するようにしたい。

先週の週記を投稿してからは、Kaggleのチームメイトにもらったスクリプトをぶん回し、ファンの音を感じつつ布団に入った。少しだけハーメルンを読み進めていたら、午前4時過ぎに寝落ちしてしまったようだ。火曜日の同じ時間の空を見る限り、ちゃんと白む前に寝られたはず。

午前8時半くらいに目を覚ます。眠気がかなり残っていたので二度寝できそうな感じだったのに、トイレに立ったついでに回していたスクリプトの様子を見ようとパソコンの前に座った結果、目が冴えてしまった。スクリプトは全然終わっていなかった、どころか、KFoldで5分割したうちの1つすら終わっていないという始末であった。Kaggleなので、ここでどれくらいの実行時間かに言及するくらいはよいだろうと期待している。

atgolferの更新を確認すると、昨日のABC223Cが縮められていた。dcのループ部分に改善があったようだ。そこから入力の1行目もまとめて処理することで-1B、さらにループ部の改善の影響でスタックに2つの値を持つ必要がなくなっており、そのおかげでわざわざ下の値を先に計算しなくてよくなり-4Bと、合計-5Bで取り返した。前者はともかく後者の改善は自力で式を弄ってたどり着いたアルゴリズムだからこそという印象がある。

布団に戻ってからも案の定眠れず、ハーメルンを1作読了した。「レウスはレイアを拒めない」。

レウスはレイアを拒めない - ハーメルン

リオレウスに転生した主人公の視点の話よりも、むしろハンターに転生した別の転生者視点のほうが好みに合った。どこかの話の後書きで言及されていた、狩猟笛使いが主人公のハーメルンを探そうと思い、原作：モンスターハンターで検索して総合評価順に並べてみると、一番上にあったので、次はこれを読もう。しかし総合評価上位はどれも話数少なめなのが気になる。

ちょっとだけ読んで、昼前になったのを見て寝るのを諦めた。大学の昼休みが始まる前に学食に行って、帰ってきてからはしばらくネットサーフィンをしていた。ICPCのチームのコーチから登録情報にエラーがあると言われて自分のものに問題がないことを確認した。チームの画面を見ると、エラーの内容が表示されていたので、先にこれを確認すればよかった。昨日の深夜回し始めたスクリプトは、ようやく5分割のうち1つが終了していた。実に8時間かかっているようで、これを後4回行うのかと思うとめまいがする。

午後1時、今更耐え難い眠気が襲ってきたので布団にダイブ。ちょっとばかりハーメルンを読み進めた後午後2時から午後4時まで昼寝をした。起床後はかなり眠くて、布団の上でしばらくウネウネしていた。

午後4時半からインターン先の定例会。進捗報告のスライドは10分で捻り出したので、話す内容を考えておらず散漫な話題になってしまった。作ったヒストグラムやビジュアライズの結果を見せたので、見栄えはしたのではないか。あとは他の人の発表を聞いて、勉強会に参加して終了。直後にKaggleのチームミーティングが少しだけ行われ、そこで今回しているフルで学習するスクリプトじゃなくても実験はできるということを確認した。データのサイズを減らしたり、KFoldを1回で抜けたり、そういう感じでもモデルや特徴量の相対的な評価は十分に可能。

フォローしていた絵師のアカウントが乗っ取られたことを知った。そのアカウントは現在削除されていて、こちらからフォローを解除したりはできない。絵師のサブアカウントのツイートについていたリプライ曰く、乗っ取った直後は通報されるのを避けてアカウントを削除し、復活期限の30日ギリギリまで待つのではないだろうかとのこと。正直僕はこのことを30日間覚えてはいないだろう。なのでここに書いておいて、もし何かの拍子にこの日の日記を見て思い出したらキチンとフォロー解除しておきたい。

乗っ取られたアカウントは@caburiakiで、新アカウントは@caburibbonである。R18の絵を描く方なので、注意されたい。

ハーメルンを1作読み終えた。今日の昼から読み始めたもので、「笛吹いてたら弟子に推薦された」。

笛吹いてたら弟子に推薦された - ハーメルン

ほぼ再序盤でエタっており、主人公の強さみたいなものは全然描写されていない。錚々たる顔ぶれの古龍と知己を得ているという設定や、強豪ハンターの師匠役であるという設定は好みだった。

CADDIのコードゴルフに挑戦してみた。1、2問目はパーを下回るくらいわけない。3問目はパーが設定されておらず、解ければそれでいいという問題で、こんな感じのブログに乗っている問題なのだから簡単だろうと臨んだのに結局解けなかった。

コードゴルフのキャディをやってみた - CADDi Tech Blog

「科学の力使いまくって隠居生活」の新作が投稿されていた。最近めいさんのはてなブログを読んでおり、ゆっくり実況よりも生身の人間に近づいた感じがしていたところ、逆に動画のゆっくりたちの掛け合いをどことなく冷めた目で見るようになった自分に気づいて愕然とした。僕のインターネット歴としてはそれなりに昔からずっと見ているゆっくり実況者なだけあって、めいさんも現実に存在する人間であるという認識が薄かったのだろうか。

www.youtube.com

最近本を読んでいないことに危機感を覚え、1冊手に取って半分ほど読みつつ、先週金曜日のyukicoderを解いた。とりあえず前4問。

yukicoder contest 318 - yukicoder

Aは非常に面白かった。1回操作すると、そこから別の操作をどれだけ行っても数列は変わらない。よって高々1回操作する場合だけ考えればよい。Bは問題をジャンルごとに分け、各ジャンルで最もクオリティが高い問題のクオリティに $X$ を加算し、あとは貪欲。Cは $0$ の位置が決まり、そこからmexが確定する区間を繋げて伸ばしていけばよい。Dは包除原理などいろいろ悩んでかなり迷走した。最終的には上の桁から見て行って、最小値を作る際に選べる要素数を持ちながらdpして解いた。

布団に入ってハーメルンを読んでいたら、午前6時過ぎに寝落ちした。

10/19(火)

昨夜は学食に行くことを夢見て午後1時に目覚ましをセットしたようだ。一応その時間に目を覚ましたものの、明らかに眠すぎる。結局布団の上で身動きが取れず、うつらうつらとしているうちに学食は閉店してしまった。しかし二度寝できているわけでもない。学食が閉店した後も少しハーメルンを読んだりして、結局午後3時近くになってようやく入眠できた。

午後4時半起床。午後5時からの1on1には余裕を持って起きられて、進捗も産めるだろうと思っていたのに、結局乱れた生活リズムが何もかも吹き飛ばしてしまった。焦りつつデータのビジュアライザを少しだけ改修してみると、少しの時間のコーディングに比べて視覚的な変化がかなり大きく、満足。

1on1。機械学習が上手く行っていないという話になりそうでビクビクしていたところ、モデルのパラメータばかり弄るのではなく、ラーニングレートやその変化のさせ方についても気を配らなければならなかったとメンターさんに教えていただき、ちょっと希望が見えてきた。しかしその周りのことはサンプルコードを写したきりなので、なんにもわからないなあと不安がっていたら、メンターさんも実験してくださるそうなので、後半ではデータセットをAWSにアップロードして共有する作業を指南してもらった。その過程でパスワードやアクセスキーを2回ほど共有・録画していた画面に表示してしまい、そのたびに再発行していただくことになって恐縮しきりだった。

1on1が終わってから学食に行った。注文を迷っていたら後ろから人が来たので譲ったところ、その人が僕が頼もうと思っていた定食を注文して、品切れの予感に震えた。実際は僕が注文したところで品切れになったので、危ないところだったと冷や汗を拭った。

帰宅してしばらくコードゴルフをしていた。Octaveのglpkという線形計画問題を解く関数を使う問題がいくつも縮んだ。glpkはデフォルトで目的関数を最小化するように動く。一方競技プログラミングでは最大化した値を求めることが多く、その場合は最後の引数senseに-1を渡す必要がある。keyword argumentではなくpositional argumentとして渡せるのでまだマシなものの、それでも+3B、またそれ以前の引数がデフォルト値で良かったならばさらに増える。代わりに、目的関数を符号反転することにした。その符号反転で+1B、得られた解をまた符号反転して+1Bで、-3Bと合わせて都合-1Bの短縮であった。

昨日から手を付けていた本を読了。「探偵は教室にいない」。午後の時間は、文章中では「十六時」「十七時」といった24時間表記で書かれ、対してルビはツイートの画像のように「よじ」「ごじ」と振られていたのが特徴的に思われた。確かにこちらのほうが現実に即している。

いいルビ pic.twitter.com/DcqWwed2ul
— こたつがめ (@kotatsugame_t) 2021年10月18日

内容は非常に面白かった。日常の謎としてちょうどいい感じ。設定について、探偵役（とその周りの人）がみんな中学生だというのが気になった。やっていることは高校生でも成立しそうに見えるものの、それでも思考や許される範囲の行動に中学生らしさが伺える。考えてみれば、すでに成人した人間が無理なくイメージできる下限は高校生なのかもしれない。中学生まで下がると、その年代特有の感覚だったり様々な制限が表面化してきそうなものだ。それらもこの作品では描かれていたように思う。

火曜5限のPythonの講義スライドを流し見た。二分探索法が紹介されていて興奮するも、以降特に関係ない話題に移ってしまい残念。Pythonのsetはhash setなのだ……。課題は非線形方程式を解くもので、講義ではニュートン法と、その微分係数の部分を差分で近似した割線法が紹介されていた。課題になっている非線形方程式は微分可能なので、無難にニュートン法を実装した。講義スライドに書かれていたヒントの式が誤っており、しばらく首をひねっていた。ちゃんと自分で考えればわかる。

明日から数日、帰省することにした。その間もインターンの実験コードを回したいと思い、マシンにSSHで接続できるよう設定することを思い立った。とりあえずルーターの設定からIPアドレスを固定して、これで内部ネットワークからのログインは成功。高校生の頃、仮想環境でサーバーを立てたいと思い立ち、ひとしきり唸って諦めたことを思い出すと、かなりの進歩である。現在は仮想環境を作らずともマシンをいくつも持っているのが嬉しいところ。

そのあとノーパソを取り出し、これにテザリングして外部ネットワークからのログインに挑戦しようとした……と、それをする前に、以前からずっと音が出ない状態なのが気になって、これを直そうと3時間弱格闘していた。

ノーパソから音が出ない（スピーカーがダミー出力しか選択できない）ことが発覚。ちょっと格闘してみたが直らなかった
週記（2021/07/19-2021/07/25） - kotatsugameの日記

直った。ちょっと記録を付けておこう。最初はalsamixerが起動しなかったり、/proc/asound/cardsに何もなかったりしていた。lspciではMultimedia audio controllerの存在を確認できる。dmesg|grep sndをしてみると、snd_soc_sklがエラーで落ちているらしい。これはlspci -vから見ることのできる、今現在使われているKernel driverであった。また、そのちょっと下にsnd_hda_intelが見える。もしかして使っているドライバが違うんじゃないかと考え、それからはなんとか使うドライバを変えようと試行錯誤していた。ドライバ名をキーワードに入れていろいろ検索した結果、alsa-base.confにoptions snd-hda-intel dmic_detect=0と書いて再起動したらドライバが代わり、音が出るようになった。感動……！

SSHの話に戻る。そこからさらに3時間ほど格闘したものの、結局ポート開放すらできなかった。ファイアウォールを設定して、ルーターの設定もして、sshdのconfigもちゃんと合わせたはずなのに……。nmap localhostで見てもsshが待機しているという表示が出なかったので、最後はそれを出そうとして、諦めたのだった。

午前7時になってしまった。しばらくなろうの更新を追ってから、帰省の準備を始める。とりあえず時刻表を眺めたところ、親に新幹線駅まで迎えに来てもらおうとすると、かなり急がなければならないことに気づいた。しかもどれもこれも接続が悪く、うまい具合に乗り換えようとすると今から40分後に出発する新幹線に乗るしかないようだ。

ひょっとして間に合うんじゃないか？と思い、急いで着替えて準備をし、家を飛び出した。家から地下鉄駅までを爆走し、朝なので結構頻繁に走っている地下鉄に乗り、仙台駅に到着。地上に上がるエスカレーターも早歩きしたので、残り10分ある。ATMで素早くお金を下ろし、みどりの窓口のテープで区切られた待機列をウネウネ走って、息も絶え絶えになりながら切符を買った。みどりの窓口の時計を見ると残り3分くらいで、焦って改札に駆け込もうとしたところ、その上の電光掲示板でまだ微妙に余裕があることに気づく。もしかしてみどりの窓口は少し時計を早めているのかもしれない。ニクい心遣いだ……。しかし逸る気持ちは抑えられず、売店で朝ご飯を買うのをスキップしてホームまで上がってしまった。

大学生になってから一番走った。みどりの窓口の時計微妙に早められててその気遣いがニクい。帰省します pic.twitter.com/GdVINco9k9
— こたつがめ (@kotatsugame_t) 2021年10月20日

40分前に準備ゼロのパジャマ状態からお金おろして学割で切符買って新幹線乗れるらしい。人体の神秘
— こたつがめ (@kotatsugame_t) 2021年10月20日

代わりに朝ごはんが消滅したな……飲み物も残り少ないし……
— こたつがめ (@kotatsugame_t) 2021年10月20日

飲み物がないのは厳しいので、途中待ち合わせでしばらく停車すると聞き、そこで買うことを思いついた。しかしうっかり先頭車両に乗っていたので、自販機との往復はホームをオタクダッシュする羽目になってしまい、これまた大変だった。

大宮で乗り換え。仙台から乗ってきたやまびこはかなり空いていたので、やはり平日の昼間は人がいないかと思っていたのに、大宮から乗ったはくたかの自由席は1つ飛ばしでほぼ埋まっていた。なんとか空いているC席を見つけて座る。周りが人だらけの中、申し訳なく思いながら売店で購入してきたパンやおにぎりを詰め込み、やっと人心地が付いた。

黒部宇奈月温泉駅からは親の車で自宅に向かう。途中、本屋に寄って帰省中に読む本を4冊購入。全部読めるわけはないものの、これくらいなら自分の手で持ち帰れるだろう。

そういえば買った pic.twitter.com/gdZrFTtbYd
— こたつがめ (@kotatsugame_t) 2021年10月20日

午後2時半、実家のこたつに潜り込んで就寝。

10/20(水)

午後7時半起床。

TwitterのDMでインターン面接についての質問が来ていたので、当時の日記などを読み返しつつ自分語りをした。改めて振り返ってみると、自分がなぜ受かったのかわからない。特に、何度もやりたいことを聞かれていて、その度曖昧な答えしか返せていなかったのが気になる。やはりレートで殴ったということだろうか。

チュウニズムの超大型アップデートの情報が流れてきていた。公式ページを舐めるように読んで内容を確認する。楽曲の削除は恒例行事、LEVEL表記の細分化は驚きの一方で納得もできる。スキルのシステム変更も、これまで通りコラボマップのキャラに対して毎回特別スキルを割り当てているとデータが増えて大変というのは伺える。しかしそれにしたって残すスキルが少なすぎやしないか。個人的にはパニッシュメントが消えてATTACK以下でスキル音を鳴らせなくなったのが辛い。

info-chunithm.sega.jp

あとは、楽曲の削除に伴ってスピソニ称号がいくつか消えることも特別注意しておきたい。1速は一応「見える」のでその場で粘着すれば取れるのに対し、スピソニは入念な研究が必要だろう。消える前に取れるよう頑張る。

「りゅうおうのおしごと！」15巻を読んだ。今回も非常に良かった。シーンとしては序盤に雛鶴あいがYouTuberをやっているのが好みだった。ただ、この巻の主題は当然そこではない。表紙を見ればわかるとおり、一冊通して供御飯万智が九頭竜八一と仲を深めるのを中心に展開しており、序盤はその2人と雛鶴あいが交互に描かれ、ラストで激突して云々……。その後のエピローグも含めて大満足の巻だった。と、良質な読書体験に満足しつつ、巻ごとに最後に付いてくる感想戦を読んでいたら、そこでさらに驚くべき展開が描かれびっくり。作中で九頭竜八一が出した本の反響も含め、次巻がとても楽しみである。

寝る前に、部屋の本棚を探し回って「浅草鬼嫁日記」の1巻を発掘した。最近同作者の別作品「かくりよの宿飯」シリーズを読んだので、こちらを読み返して大旦那様が登場しているシーンを探そうというわけだ。

記憶が新しいうちに同作者の「浅草鬼嫁日記」のほうを読み返して、リンクしている箇所を探してみたいと思う。今は本が実家にあるので、そのうち帰省したらやってみよう。
週記（2021/09/13-2021/09/19） - kotatsugameの日記

実際、見つかった。114-115ページだ。かなり丁寧に描写されているにも関わらず、記憶が正しければこちらの作品で特別な役割を果たしたりはしなかったはず。おそらく当時は何かの伏線だと思い、そのまま忘れてしまったのではなかっただろうか。こういうネタは作者のファンとしては嬉しい一方で、知らない読者を置いてけぼりにしがち。

見つけた後も読み進めて、結局1冊まるごと斜め読みしてしまった。やはり僕が好きな見せ場を作るのが上手い作者であると感じた。2巻以降もチェックするつもりでいたけれど、思ったより時間が経ってしまったし、本棚にバラバラに刺さっているようでそもそもどこにあるのかわからないため、切り上げて寝ることにした。

午前4時半就寝。

10/21(木)

正午起床。今日は帰省の主目的である免許更新と、ついでに参院選の期日前投票に行く。

食事して準備して、さあ出かけようとしていたところに、LINE通話がかかってきた。訝りながら応じると4年ゼミの友人からで、曰く「ゼミ始まってるけど起きてるか？」……ちゃんとゼミの休みを確認して帰省したはず、と慌てて以前送られてきたメールを見返すと、ゼミが休みなのは今週ではなく来週だったらしい。

もうどうしようもない。明日は免許更新できないし、それ以降にずれ込むと生協の弁当配達やコンテストにぶつかって嬉しくない。ということで今日は休むことにして、とりあえず友人から教授に欠席を伝えてもらい、自分も移動中の車内で謝罪メールを作成して送信した。

まず投票。選挙権を得てからすぐ仙台で下宿を始めたので、投票するのはこれが2回目である。投票用紙は特殊な紙でできていて、折り曲げてもすぐ戻る……ということを覚えており、試しに端を折り曲げて感動していた。しかし思いっきり伸ばした状態で投票箱に入れてしまい、横目で見えたらしき母に注意された。

その後免許更新へ。お金を払い、設問に答え、視力を測り、写真を撮る。ところで、僕が3年ほど前に入院したことを覚えている人はいるだろうか？

入院しました
— こたつがめ (@kotatsugame_t) 2018年5月6日

実はこのとき診察中に意識を失ったことがあって、そのことを申告したら別室に連れて行かれてひとしきり問診を受けた。免許を取ったときも同じ理由でちょっと手間取った記憶がある。自分でもなぜ意識を失ったのかよくわかっていないので、曖昧な受け答えしかできなかった。前回も今回も、最終的には許してもらえた。

初回の更新ということで、2時間コースの講習を受ける。講習が始まる直前にJOI一次予選（第2回）の過去問が公開されているのを見つけ、心臓が飛び跳ねた。URL自体は推測できるので、先週日曜日からずっとスマホとパソコンの両方で以下のページを開いており、起きている間は数時間に一度リロードしていたのだった。

JOI 2021/2022 一次予選 (第2回) 過去問 - AtCoder

A、Bはdcでサクッと通す。僕が一番最初に過去問を見つけたようで、ちゃんと最短が取れていた。その後CとDを読み、すぐにはわからなかったので、講習中に考えることにしてその場は放置した。講習中はスマホ禁止である。1時間くらいして休憩時間になり、そそくさとスマホを取り出してコーディング。さらに1時間講習を受けて終了、そこから家に帰る車の中でもまた縮めていた。Cは肯定先読みをgrep -Pで行い、Dは適当にRaku。めちゃくちゃ車酔いしてしまった。

免許証の写真には寝癖が付いていた。

電車に乗って富山駅に出て、夏から会うタイミングを計っていた卵生みらーじゅ（@asakaakasaka）さんと、彼が連れてきてくれたカーニ・カ・ニーカニ998244353世（@kani_kanichann）さんと会った。なんと呼べばいいかわからなかったのでとりあえずTwitterにおける現在のユーザー名を書いておいた。もし別の文言に置き換えたほうが望ましいなら、そのことを教えてほしい。

まずゲーセンに行く。音ゲーが3階から1階に降りてきておりびっくりした。更にチュウニズムの台数も1台減って2台に。カーニ・カ・ニーカニ998244353世さんはプレイしないそうなので、お言葉に甘えまくって卵生みらーじゅさんと3クレくらいプレイした。

その後サイゼリヤに移動。恒例の間違い探しは、最後の1つだけネットで答えを見た2人にヒントをもらってしまった。食事後、やることがないなら……といそいそとソートなぞなぞを布教して、1時間ちょっと遊んだ。今日はかなり素早く答えが出る問題が多かった気がする。これまで飲酒しながらやっていたのはまずかったのかもしれない。

会計は別々に精算するのだとばかり思っていたところ、卵生みらーじゅさんが奢ると言ってくださって、ありがたいやら申し訳ないやらでモゴモゴしているうちに支払いが完了してしまっていた。また機会があったら、次は僕が奢るらしい。望むところだ。電車に乗って帰宅。

帰宅してから、行き帰りの間に読んでいた本を読み切った。「異世界でチート能力を手にした俺は、現実世界をも無双する」9巻。主人公がひたすらインフレし続けて、毎回新たに登場する敵をバッタバッタとなぎ倒している。少し前の巻からあとがきでも「作者でもどうなるかわからない展開」と書かれており、正直もう内容は気にしていない。イラストレーターが好みなのと、たまにある現実世界のシーンが気に入っており、また読むのに負荷が一切かからないこともあって、読み続けている。

さらにもう1冊手を出し、3分の2くらい読んだところで就寝。午前4時半だった。

10/22(金)

午後1時半起床。

食事してちょっと読書してから、高校生のとき通っていた塾に出向いた。帰省時の恒例行事。先生としばらく話した後、1時間くらいプリント採点のバイトをして、雨が降りそうだったので急いで帰った。生徒から「何も見ずに1分計ってみて」と言われ、心の中で数えているうちになんとなく速い気がして心配になり63秒の時点で答えたところ、タイマーでは62秒だったらしくかなり残念な気持ちになった。自分を信じられていない。

TCB41に出た。例によってこの日記が公開される頃にはイベントが終了しているから、ここに各問題の感想を書いておこう。この回は3連覇がかかっていると思ってかなり気合いを入れていたのに、WAを出してしまったし、それでなくとも解くのが遅くて減点されていた。しかし解き終わってから改めて確認してみると、TCB38-40ですでに3連覇を達成していたらしく、安心。

https://techful-programming.com/user/event/2274

6問目まではよい。7問目は、最初 $O(N)$ で解いてから制約をよく見ると間に合わないことに気づいた。焦りつつWolframAlphaに投げると $O(1)$ になってくれた。8問目は3bitのフラグを持って桁dpした。9問目は、重要でない要素のインデックスを引いていくことを考えれば、クエリをソートして遅延セグメント木でゴリゴリすることで計算できる。この問題に時間がかかったのと、尺取り法っぽいことをするときに最後に区間の左端を右まで寄せ切っておらず、1WA。計-18pt。10問目はベクトルの内積の最大化と考えれば、最大値を達成する点は凸包に含まれるため、クエリを偏角ソートして凸包上を回りながら計算できる。

解き終わるとちょうど夕食が完成していた。食事中、テレビにイナガキヤストさんが出ているのを見た。

ご報告。スペシャル放送決定しました！！ https://t.co/q1y1FvkqHJ
— イナガキヤスト (@inagakiyasuto) 2021年10月11日

1冊本を読み切った。「クールな月城さんは俺にだけデレ可愛い」。帯に紙城境介推薦と書いてあり、「文章上手すぎない？」という感想が乗っていたので身構えて読んだものの、僕としては正直期待はずれだった。文章の上手さとはなんなのだ。内容としてもほとんど記憶に残らなかった。読了ツイートにふぁぼん氏からリプライが来て、やっとタイトルに「クー」「デレ」が入っていることに気づいた。ヒロインは主人公に対してほとんどクールな様子を見せず、結果主人公視点が多いこの巻ではクール要素がゼロになっていたと思う。

読み終わった直後からyukicoder 319。全然わからなくて、考えているうちに微妙に意識を飛ばしたりしていた。

yukicoder contest 319 - yukicoder

Aはよい。Bはグリッドを二部グラフと考えると、最初に2人が同じ側の頂点にいれば捕まえられないことがわかる。ではそうでないときは……どうせ捕まえられるだろうと適当に投げたら通った。その後Cを読んでしばらく考え、しかし解けず、Dに移った。山が2つの場合に実験すると、石の個数が同じ場合だけ負けることが分かった。また、片方がコインを取ったらすかさずもう片方もコインを取らなければならないことが分かり、 $N$ が奇数の場合は先手勝ちであることも分かった。この後、僕は残りの山が2つになったときにどうなっているかをずっと考えて解けなかった。2つの時にゲームが決まるわけではないのだ。

どうにも解けないのでEに移った。隣接項の差を $-1,0,+1$ と表して、これがどう変化するかを確認すると、2ステップ後でも非ゼロなのは $-1,-1,+1,+1\rightarrow +1,+1$ とその符号反転のみであることが分かった。つまり、最初の状態が $-1,-1,+1,+1,-1,-1,\dots$ とその符号反転なら $-1$ か $+1$ で、それ以外なら $0$ になる。サンプルを合わせて投げたら通った。残り時間はCに戻って、貪欲でWAを出していた。終了直前に二分探索+最後に使用した要素を持つdpを思いついたものの、遷移を詰める暇もなかった。

CodeChefでSnackDown R1Aが始まっていたので参加した。4問解けば通れそうなsolved数とはいえ、ギリギリで通るのも嫌なので念のため5問解いておいた。

https://www.codechef.com/SNCK1A21

Aはよい。Bは ${\rm lcm}(X,2X)=2X$ と ${\rm lcm}(XK,XK-1)=XK(XK-1)$ を答える。Cは上位 $K$ 人が勝てる回数の総和の最大値を求め、 $K$ で割って2を掛けた。Dは難しかった。片方が1要素しかない場合は別に計算しておく。残りは最小値を含む数列のmaxと最大値を含む数列のminを決め打つとどちらかを増やす・減らすことで一致させることができ、実際には片方を決め打ったらもう片方は二分探索で求めた。Eは連続する1の個数の増減を考えると、 $\pm 2^i$ していく問題に言い換えられる。ところが構築の際は、文字列の外を操作しないように中途半端な位置にクエリを投げる場合があった。そのように操作すると、 $K$ が奇数なら必ず構築可能である。Fはほとんど考えていない。いかにも難しそうであったので早々に諦めた。

明日は仙台に帰るのに、結局朝まで起きていてしまった。日記を書いて午前5時半就寝。

10/23(土)

8時半くらいに親に起こしてもらい起床。今日は仙台の部屋に生協から弁当が配達されるので、午後3時以降のそれに間に合うよう帰ろうとしたら、この時間に家を出なければ間に合わないような新幹線になった。

今日は新幹線の車内で寝てしまうだろうから、乗り過ごし対策にとスマホのアラームをイヤホンからのみ流す方法を調べていた。適当なアプリをインストールして試してみる。確かにイヤホンにしかアラームが流れていないものの音が小さく、音楽を流していたら聞こえない可能性があって困った。

結局、大宮までは十数分ごとに目を覚ますような微妙な寝方をしてしまい、せっかくインストールしたアプリの出番はなかった。大宮で仙台終点のやまびこに乗り換える。これなら乗り過ごす心配はないぞと思っていたのに、こちらではずっとハーメルンを読んでしまい、一睡もしなかった。乗客数については、大宮までは結構いたように思う。大宮からはガラガラだった。

仙台駅に着くと午後2時過ぎで、少しだけ時間があった。ゲーセンに行くのは現在の疲労度を考えれば無意味だったので、駅前でラーメンを食べて素直に帰宅した。

新幹線車内と帰ってきてから少しでハーメルンを1作読了。「龍の恩返し」。

龍の恩返し - ハーメルン

モンハン二次創作。主人公の寿命がめちゃくちゃ長く、話の進みも大胆に数百年飛ばしたりしていて、その辺りはかなり好みだった。ただ主人公と妻のイチャイチャは僕にとって必要ない要素。また、文章がやたら説明的で読みづらかった。

最近3回分でサブモニタがキャプチャされているのに気づき、非常に残念な気持ちになった。以前同じ現象が発生して、ちゃんと直したはずだったのだが……。パソコンを再起動すると元に戻ってしまうとか、そういうことだろうか。
週記（2021/10/11-2021/10/17） - kotatsugameの日記

まだ弁当が届かないので、↑を解決しようと試みていた。ケーブルの差込口を交換するとよいという話を聞いていたので、キャプチャされてしまうモニタとプライマリモニタで交換してみると、驚くべきことに何も変わらなかった。何もというのは言葉通りの意味で、Windowsにおけるメインモニタも移動したりしなかったのだ。モニタの情報がどこかに記録されていて、どんなケーブルで接続しようとモニタの識別には影響しないということだろうか。それっぽい情報はregeditで消してから再起動したはずなのに。

しょうがないので、前回と同様「ケーブルを外してから起動し、ちゃんとプライマリモニタがキャプチャされることを確認してから戻す」方法を取った。直った状態で試しに再起動してみると、やはりサブモニタがキャプチャされるようになったので、本当に再起動すると元に戻ってしまうらしい。

弁当が届いたので、ABCまで昼寝することにした。具体的には午後4時半から午後8時半まで寝ていた。起きてから食事しようとして、結局弁当を食べきれず放置したままABC224。

AtCoder Beginner Contest 224 - AtCoder

Aは出力するべき文字列を取り違えて1WA。sedだった。Bからもう面倒なのでC++、愚直に $O(H^2W^2)$ 。Cも愚直で、通した後ABC181C「Collinearity」と似ていることを思い出し、最短コードをコピペして提出したらTLEしたので放置して次に進んだ。Dはbfs。状態をarray<int,9>で持ったら1secくらいかかった。Eは $a_i$ を降順ソート。FはARC061C「たくさんの数式」と同じ問題設定で、制約が強化されている。ARC061Cの最短コードが線形時間で動作することを覚えていたので、それをコピペしようとした。しかしdcなので実行時間に不安があり、自分の提出を漁っても別の言語で書かれたコードがなく、Pascalで0msを出した時も $O(|S|^2)$ で解いていてどうしようもなかったので、dcのコードを読解してC++に直すことになった。Gは、サイコロを振りなおすときの期待値を変数で置いて立式するとその変数の値を二分探索できるようになったので、それで解いた。

C - Collinearity

C - Many Formulas

コードゴルフ。Aは末尾の文字列が2種類しかないため、sedでも最後の1文字だけ見れば判定できる。またそれ以上にVimでうまいこと文字列を削除するのが強かった。コンテスト中に9Bは達成したものの、同じ長さのコードが開始4分もせずに提出されており、勝てない。Bは解説を読むと $O(N^2)$ だけ調べる方法が書かれていたので、それをOctaveで実装しておいた。Cは、コンテスト中にコピペしてきたコードが複素数の割り算でTLEしていたので、そこを共役な複素数を掛けるコードに直したらギリギリ間に合ってくれた。しかし慌てていたのか典型テクで-1Bできることを見逃していた。Dは手つかず。EはRubyで、文字列の配列を'.map{...'でjoinしてevalするテクからさらに進化し、".sort\n.map{..."でjoinしたあと必要ないsortをコメントアウトするというものが使われており、すごい。

Fは、ARC061Aからコピペしてきた式をRubyに書き直していたら、998244353と119<<23|1が等しいことを利用して縮められてびっくりした。modの値を初期化するのと別の変数を1で初期化するのが同じ場所で行われているので、それをまとめられたようだ。ほかに同様の手法で縮められるものがないかしばらく探してみるも、見つからなかった。その後Haskellの最短コードを見てみると別の漸化式が使われており、Rubyに写すと-1Bできた。最初に使っていた漸化式において、出力する値を直接持つように変数を足して立式すると得られるようだ。Gは二分探索をRubyで書いた。

Hを解説ACした。双対性は昔から超高度典型という感じで捉えていた。解説で紹介されている双対定理のステートメントは見るだに強そうである、しかし証明はあまり読んでいない。とにかく、整数性を外して式変形して、双対定理で書き換えて、整数性を戻すという具合だろうか？解説の通りに実装したら魔法のようにサンプルが合って感動した。

線形計画問題なのでOctaveのglpkが使えないかと思い、試しに提出してみたら通ってしまった。変数の整数性を課していないのに答えが整数になるのは、先に述べた整数性を外せるという条件からだろうか。変数の条件を行列で記述するのがかなり面倒で、最初は2重ループを書いていた。非ゼロ要素のインデックスなら簡単に得られることに気づき、試しにそのインデックスたちからsparse行列を構築して渡してみると、問題なく動いてくれてコードも結構縮んだ。

atcoder.jp

日付が変わったあたりでSnackDown R1Aが終了した。終了数時間前からE問題のACが異常に増えてびっくりしていた。聞くところによると、解説動画がどこかに上がったらしい。終了直前に5完しないといけないことに気づいて焦っている人が何人もいて、昨日気が向くままに5完しておいてよかったと安堵した。

布団に入ってハーメルンを1作読了。「貴方に好きと言いたくて【完結】」。

貴方に好きと言いたくて【完結】 - ハーメルン

またモンハン二次創作。最後まで読み切ってようやく、主人公がなかなかすごい奴だったことが分かった。それまでは、短いので最後まで読み切りはしたものの、よくわからない主人公がウダウダしているのを流し読みしているだけだった。

さらに別のなろうを開いて数話読み、午前7時就寝。

10/24(日)

午後1時半起床。食事して午後2時から模擬国内予選2021。

2021/Practice/模擬国内予選 - ICPC OB/OG の会

7完5位。自分はBDEFGの考察と実装を行った。E問題で微妙に詰まったものの、終わってみればかなり解けたコンテストだった。問題が解けると楽しい。

Bは式を分解すると直ちに求まる。Dは2乗が通るので、Z-algorithmでチェックして遷移するdpを書いたら5secくらいで終わった。冷静になると、manacherみたいな考察を行うことで、遷移先としては最も近いものだけ考えてよいことがわかる。しかしそこから線形にするのはまだわかっていない。

Eは $1$ と $N$ から貪欲に並べていくのが最初に思い浮かんだ。あまりに単純すぎるのでさすがにダメそうだなと思いつつ実装すると、案の定サンプルが合わない。しばらく考えてみると、 $k$ 個先に動かすときにコストが $k+1$ かかることが効いていて、うまくコストへの寄与を分解できないことに気づいた。これは動かさない要素を決め打つことで解消できる。動かさない要素として最後に選んだ要素をキーに持つdpを考えると、更新が区間addで書けたので、それで実家dpしたら通った。コンテスト後に、動かさない要素がLISとなり、残りは転倒数に一致するということを知ってびっくりした。

Fはdpのキーにこれまで作った文字列の長さと1の個数、値にこれまでのコストと文字列を持つと、単純にpairのminで更新できる。解説を読むと後ろから構築と書いてあって、嘘解法だったかと震え上がった。しかし前から構築しても正しい答えが求まることは証明できた。文字列の長さと1の個数が決まっている場合、それを達成する具体的な文字列によらず後ろに追加する文字列のうち最適なものは一意に定まる、ということから言える。

Gは全方位木dpをした。最初、親から来て、子と親を1回往復して、また子のほうに抜けていくという遷移を考慮に入れ忘れていた。これはちゃんとサンプルで落ちてくれるのでありがたい限り。1WA出すも、その後適当に試したケース（3頂点の直線グラフ、x="222"）がHackケースになっていて助かった。サンプルを見て慌てて追加したdpの値の初期値をちゃんと設定できていなかったのが原因だった。Hは $b$ を固定した時の $a$ の区間幅を積分というのを考えて、やりたくなさすぎてクネクネしているうちにコンテストが終了した。

2021/10/26追記：このコンテストの参加記を投稿した。

kotatsugame.hatenablog.com

直後、午後5時から午後10時まで久しぶりのOpenCup。チームで6完で、僕はAとCを解いた。

Aは表の1行目と1列目を取り出し、それぞれ隣接項のdiffを2回取ると、行（または列）における $A$ の和が求まる。それらを反映してもう一度隣接項のdiffを取ると、端の値も求まる。行と列で $A$ の和が等しくなるように両端に値を追加し、さらにこの状態で $A$ を復元した後入力の値と同じになるように左下・右上に値を追加する。それぞれやり損ねて2WA。

Cは辺全てを重みの降順に並べて、同じ重みの辺を同時に処理した後、毎回UFの一致判定ができればよい。UFで扱う代表点を集合のうち最もインデックスが小さい点に定めると、計算量を犠牲に、更新が入った集合における更新前の代表点と更新後の代表点のpairをソートすることでUFの更新の様子を一意に表すことができる。あとはこれを更新が入った各木に対して求め、それらをさらにソートして隣接する要素が等しいか見れば、UFの一致判定に替えることができる。2回目のソートはvector<vector>のソートとはいえ、文字列のソートが文字列長の総和の準線形時間で行えるのと同じ要領で、これも十分高速にソートできる。この一致判定にたどり着くまでに2WA重ねてしまった。

他にチームではEHJKが解かれた。Kについては、僕は実際にグラフを作ってもいいんじゃないかということを指摘し、それ以降のことはコンテスト当時あまりよく考えていなかった。有向グラフの到達可能性を判定することになって、通常はbit並列による定数倍高速化くらいしかできないのでまずそうだった。実際には、作成したグラフは有向完全グラフのような形になるので、必ずハミルトン路が存在し、トポロジカルソート順で前の要素は後の要素に必ずたどり着けることになる。

dcの切り上げで新手を考案し、2つほどコードが縮んだ。割ったあまりが0なら0を、非ゼロなら1を商に足すとき、これまでは~d/++としていた。これはスタックをいくつ消費するかが確定せず、少し使いづらかった。しかし~d~++とすれば、スタックを消費する量が確定する。これを利用して、スタックの下に後々使う要素を積んでおき、変数を使う手間を省いたり、rotateして引き算する手間を省いたりしたのが2つの短縮の正体である。前者のコードのリンクを下に張っておく。

atcoder.jp

久しぶりにインターンの業務を進めようと学習を回してみたら、謎のエラーが出てtorch.cuda.is_available()がFalseになってしまった。エラーで検索してみると、とりあえずnvidia-smiで様子を見るべきらしい。実行してみるも、GPUドライバのバージョンが合わないと怒られてしまった。最近apt updateをしたので、それで何かバージョンが食い違ったのだろうか。よくわからなくなったのでとりあえずPytorchを更新するも、まだ直らない。さらにCUDA Toolkitを更新してみると、同時にGPUドライバのアップデートも行われたようなlogが表示され、見事に直った。

TCB41が終了していた。4位だった。1位は理論値だし、時間の総和でも負けている。しかしWAさえなければ2位になれたのに、と悔しい気持ちが大きい。7問目は数列の平均値が $\frac K 2$ になるらしく、これを使うと僕がWolframAlphaで出した式が直接得られるようだ。9問目の微妙に小さい制約は、Mo's Algorithmが想定されていたらしい。当時少し考えて棄却した覚えがある。今改めて考えなおしてみると、確かにそうだなあという気持ちにしかならない。なぜ思いつかなかったのか……。

午前1時からCodeChef、10月のCook-Offに出た。これで今日のコンテストは合計10時間半になる。それなりに全力投球していた結果頭が回らなくなったらしく、C問題でめちゃくちゃ詰まってペナルティが崩壊した。全完もできず、div.2で3位と残念な結果に。

https://www.codechef.com/COOK134B

ABはよい。Cは斜めにつながってボードを横断（あるいは縦断）しているマスがあるかチェックすればよいと思うも、右と下にしか進めないという制約から、微妙に繋がっていないマスたちによってもたどり着けなくなってしまうのではないかと心配になり、結局「存在できる区間」をvectorで持って更新していった。この区間は高々2つにしか分かれない。

コンテストが始まったときはEの位置にあった気がするDについて（もしかして、こうやって問題の順番が変わるのでみんな問題名で呼んでいるのか）は、 $X$ を聞くと $N\mid X-(X\bmod{N})$ が求まるということで、これを2種類行ってgcdを取ることにした。単純に $X=2\times 10^{18}$ と $X-1$ だと不可能、 $X$ と $X-(X\bmod{N})-1$ ならうまくいくようだ。コンテスト後にTLを見て、 $(X-(X\bmod{N})-1)\bmod{N}=N-1$ から直接出せばgcdを計算する必要がなかったことに気づいた。

Eは適当に左右の警官でそれぞれ偶奇が異なるものが連続している人数を数えて出力したら通った。Fはfunctional graphの閉路を縮約することになって、使用回数が残り1回の頂点を直前の頂点に吸収させるという操作をstackを使って行った。Gは $O(N^2)$ のdpを書いて出力し、OEISに投げるも見つからず、結局解けなかった。どうやら出力結果の比を取るとエスパーできるらしい。

朝方まで日記を書いていた。今週の週記は、過去の週記の引用部分を除き、実際に逆接の「が」を1つも使わず書けたはず。代わりに「しかし」や「～ものの」といった語彙が増えている。思うに、文章を切ろうと思えば切れる箇所でも安穏と「が」を使っていたのがよくなかったのだろう。しかし一方で、文章を切るのが不自然な箇所も存在し、そこにはやはり「が」が入らなければスッキリしないのであった。というわけで、今週の週記には（自分にとって）不自然に文章が切れている箇所がいくつか存在する。来週からはまた「が」も使って書くことにしよう。