週記（2020/10/12-2020/10/18）

10/12(月)

午後7時くらいに起きた。生活リズムが一周しかけている。時間で見れば、一周するにはあと12時間ずらす必要があるが、週末夜のコンテストに参加するためには必ずどちらかにずらしておかねばならず、後ろにずらすことを選択した場合は週の半ばあたりで無理やり一気にずらすことになる。そうしなければずらすのが間に合わず、夜眠くて戦えなくなってしまう。

今年のICPC国内予選のルール（仮）が公開されていた。チーム全員が同時にマシンでコーディングしてよくなったらしい。

なんとも言えない。ただ今年は4完だと厳しいかもしれないので、きちんと5完以上を目指しておきたい。可能なはずだ。なんてったって去年の国内予選よりレートが400上がっているのだから。あとはちゃんとICPCの過去問を埋めること。

コーチによって、ICPCのサイトでチームが編成された。サークルメンバーに情報の登録をやってもらう必要があるが、それを伝えるにはちょっと時間が遅いかなと思う。朝になってからSlackで周知する。

ずっと布団でごろごろしてなろうを読んでいた。日付が変わったあたりで布団から出るが、微妙な眠気があって何にもやる気にならない。

とりあえず、昨日シャワーを浴びずに寝たので、今浴びる。ついでに食事の用意（レンチン）もしておく。

PCKの過去問を進める。ICPC練習は？

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0247/review/4908275/kotatsugame/C++14

dx[4]={1,0,0,-1},dy[4]={0,1,-1,0}という順番で探索しているが、これは移動直後に後ろを向かないような条件を簡単にするためだ。連続する移動の方向（0,1,2,3）を足して3になったら、後ろを向く移動をしていることになる。

そのあと、訪れたことがあるマスに印をつけることにしたので、後ろを向く判定はいらなくなったが、探索の順番を変え忘れていた。

ちょっと気になるなと思って、普段何気なく書くようにdx[4]={0,1,0,-1},dy[4]={1,0,-1,0}に直して提出したところ、TLEした。どうやら探索の順番がたまたま上手くはまって、解が爆速で見つかっているだけだったらしい。かなりびっくり。

ググって解説ブログを見たところ、IDA*をしていた。A*やIDA*は、僕の競プロ歴の最初期に螺旋本で触れたっきりだったので、まったく覚えていなかった。見積もりコストを使って枝刈りをする方法は覚えていたが、それがA*のことだと勝手に思い込んでいたらしい。

もういくつか問題を解いて、AOJも1000ACを達成した。うれしい。こどふぉはコンテストでしか問題を解かないので、いまだに500ACちょっとしかない。逆に一切バーチャルコンテストをせずに500ACということは、単純計算でコンテストに100回近く出ているということになって、結構びっくり。unratedのコンテストに出ても履歴に残らないので把握できない。

ICPCアカウントに情報を登録する。僕の分をまず完成させて、Slackに貼って参考にしてもらうつもりだ。

去年の分でほとんど埋まっていて、今年新しく増えたらしい項目に「Number of Full-Time STEM Semesters Completed」というのがあった。何を答えればよいのかわからない。

STEMとはScience、Technology、Engineering、Mathematicsのことで、それに関連する学科を指しているのか？とりあえず、僕は数学科で2年半、つまり5セメスター過ごしてきたため、5と書いておいた。

2021/10/09追記：2021年横浜大会公式ページのQ&Aによれば、この項目は初期値である0のままで問題ないそうだ。

アカウント登録 | ICPC 2021 Asia Yokohama Regional

aiueo700のwikiを読んだり動画を見たりしていたら昼になってしまった。ICPCアカウントに情報を追加するようサークルSlackに書き込んで、寝る。

10/13(火)

起きたら午後9時だった。いつもなら生活リズムを後ろにずらすことを選択するのだが、今週は水曜日の夜にリクルートのインターンのオンライン説明会があるため、それはできない。

このオンライン説明会についてメールが来ていた。オンラインだし人の話を聴くだけだろうなと安易に考えていたのだが、カメラとマイクの確認を求められた。どうやらこちらからも何か発信する必要があるらしい。3000円ぶんのギフトチケットが配られて、それで飲み物と食事を各自で用意して、歓談をしましょうと書いてある。

「自由な服装で参加ください（スーツである必要はありません）」とも書いてある。衝撃を受けた。確かにこの説明会は僕が申し込んで参加しているため、プログラミングコンテストに引っ付いているオフィスツアーとは違い、より真剣な態度で臨まなければならない（いやプログラミングコンテストに引っ付いていても真剣な態度で臨む必要があるが）。その点僕は意識が低かった。スーツを着る可能性があるなどとは全く考えていなかった。というか今は実家にある。

脱衣所に敷くバスマットは、実のところ1年以上交換していない。さすがに洗濯しようと思ってはがしたところ、ペリペリと音を立てた。バスマットに黒色の斑点があり、床には何らかの跡が残っている。カビである。

とりあえずバスマットを洗濯機にぶち込み、回している間に床を掃除する。インターネットで調べると重曹が効くとか書かれているが、そんなものはないし使い方もよくわからないため、素直に歯ブラシやスポンジの堅い面でしこたま擦る。歯ブラシは何の役にも立たなかったが、スポンジのほうはいくらか改善がみられたように思う。そもそもうまく角度をつけないと見えない跡なのでよくわからない。

20分くらいして諦めた。別のバスマットを敷く。本当は2交代で使用するはずが、片方をずっと敷きっぱなしだったせいで延々待機していたもの。

洗濯機から出てきたバスマットは、まだ微妙に黒い斑点が残っているが、まあこれも気にしないことにする。

カメラとマイクの確認をしていないことに気づいたので、する。Webカメラなど持っていないと思っていたが、ノーパソについていた。OSをUbuntuに入れ替えたが、問題なく認識してくれてうれしい。

テストのために、デスクトップとノーパソからMeetに接続して試してみた。500円のマイクを使っているからかはわからないが、環境音？ノイズ？がちょっとある気もする。

今日もいくらかPCKを進めた（だからICPC練習は？）。今日見た中では2問くらいわからない問題があって、昨日はググったりして解いていたけど、今日は飛ばすことにした。

解いていない問題の解説を見るのには抵抗がある。これはAtCoderの良質な問題を大切に解くための考え方だが、PCKの過去問くらいなら別にいくらでも解説を見ていいんじゃないの？とも考えられる。解けない問題は解けないので、どこかであきらめて解説を見ないと成長できない。そもそも成長するだけの精進をしていないので、今は関係ないが。AtCoderの問題だってARC-CDとか埋めるべきなのに、放置している。

ラノベを1冊読んだ。主人公とヒロインが読書家なので、いろいろ出てきて面白い。十角館の殺人とかハルヒシリーズ、古典部シリーズなどの有名作品に交じって、裏染天馬シリーズの名前が登場してびっくりした。

ブックマークフォルダに、覚えておきたいコードゴルフのテクニックが使用された提出や、言語リファレンスの特定のページなどを集めている。500件近くなっているそれが、なくなっていた。操作ミスで削除したのか？別のフォルダに紛れ込んでいる可能性も考えてブックマークマネージャを開くも、見つからない。本当に心臓が止まるかと思った。

インターネットの接続を切った状態で別のパソコンを起動して、そこのChromeから復元することを思いつく。でもとりあえずは、とスマホのChromeから確認したところ、フォルダ内フォルダの中に移動していることを発見した。ブックマークマネージャでは、フォルダ内フォルダは展開されないので見えていなかったらしい。

こんな思いはもうこりごりなので、ブックマークをエクスポートしようとしたところ、どうやら1月前にもエクスポートしていたらしいので、そこまで焦ることではなかったかな。

もう昼になってしまうので寝る。明日はしっかり起きたい。説明会に参加登録して3000円ぶんのチケットをもらうだけもらって本番に参加しないような恥知らずにはなりたくない。

10/14(水)

頑張った結果、午後6時に起きた。7時間弱しか寝ていない。快挙。

まだいくらか時間があるので、学食に行っておく。しばらく意識しないうちに、もう日が落ちるのがかなり早くなっていてびっくりする。夏至が6月の終わりごろにあるのはかなり非自明。9月あたりまではそんな日が落ちるのが早くなったなんて全然意識しないが、7月から9月にかけても昼の時間は着実に狭義単調減少している。

数学科の友人と会った。彼は1年生のころから取得する単位を厳密に計算しており、毎学期必要かつ十分なだけ取っている。そんな彼の今期の時間割はスッカスカ。僕も1年生の頃の負債をおおむね完済しているため、やろうと思えば演習を全部消し飛ばしてスカスカにできないこともないが、落とすことを考えるとかなり怖い。

午後7時に帰宅した。迷惑メールが来ていたのでスクショをツイートする。

リクルートの説明会は午後7時半からなので、少し余裕がある。ノートパソコンの電源をつけたままなろうを読んでいたら、リクルートの人から電話がかかってきた。なんだ？と思って出たところ、「参加されていないようですが、どうされたのかと思ってお電話しました」……？

午後7時からだった。アホくさ。本当に社会性がない。当事者意識がない。おまけに記憶力もない。

急いでミーティングに参加しようとしたところ、Zoomが起動しない。Ubuntuなので何か変なことがあるんじゃなかろうかとググってみると、手動でZoomアプリをインストールする方法が紹介されていたので、急いで行う。無事開けたのでOK。

自己紹介の途中だった。そっと入室して自分をミュートする。司会の方が僕に自己紹介をするよう促してきた。マイクをつないでいない！何もOKではなかったんだが？

急いでデスクトップからマイクを取りに行くが、コードが机の後ろを通っていて手間取った。さすがにまずいだろうということでいったんノーパソのカメラに映る場所に戻って、チャットで自己紹介することにする。

適当に書いた後、改めてマイクを取り外し、ノーパソにつないだ。スピーカーから音が出なくなった。え？

ヘッドセットの端子しかないので、マイクをつなぐと音声の出力も吸われてしまっているのか？いちいち調べている時間もないため、マイクなしで乗り切ることにする。

急に発言を求められたらどうしようかと少し気が散っていたが、特に業務における競プロっぽいところの話は聞いていてためになった。あとてぃーいけのアルバイト体験談など。

かなり応募してみたい気持ちになったが、この説明会で遅刻をかましてしまったので腰が引けている。

終わった後、コンビニに行く。最近0時から6時まで閉まっていたのだが、10月からは24時間営業に戻っているらしい。うれしい。

クーリッシュのマスカット味というのを見つけて衝動買いした。帰ってきて食べたところ、超うまい。

「うちの脳内コンピューターが俺を勝たせようとしてくる」という、ハーメルンでランキングにも載った「りゅうおうのおしごと！」のオリ主二次創作がある。かなり好きな作品だったので毎日更新を楽しみにしていたが、最近完結した。これが非公開になっていることに気付いて愕然とする。

週記（2020/08/24-2020/08/30） - kotatsugameの日記

これが再度公開されていた。最高にうれしい。またリンクを貼っておく。

syosetu.org

午後1時くらいに布団に転がったところ、寝落ちした。

10/15(木)

午前7時前に起きる。しばらく布団で「うちの脳内コンピューターが俺を勝たせようとしてくる」の好きなシーンを拾い読みした後、パソコンの前に移動して別のなろうを読む。昨日オススメされて数話読んだものの続きに取り掛かる。

デブオタと追慕という名の歌姫（ニセ梶原康弘） - カクヨム

引き込まれた。話数も少ないので一気読み。

以前にアイドルもののなろう小説を探した際、これもあらすじだけは読んでいたが、本編を開いてみてはいなかった。やっぱりあらすじで判断するのは難しい。オススメされたのは非常に良い機会だった。

午前9時くらいから読んでいたはずなのに、気づいたら午後1時で学食が閉まりかけていた。慌てて家を出て学食に行った。

帰ってきて少しパソコンを触った後、眠気に身を任せて布団に入る。上のなろうをオススメしてくれた人は、読んだものをツイートのリプライツリーにまとめてくれているので、そこから読んだことのないものを漁った。

https://twitter.com/kapt0nH/status/1294841739539124224

これを読んでみよう。逆行転生はかなり好きだ。

https://ncode.syosetu.com/n8920ex/

しばらく読んでいたところ、午後6時前に非常に強力な眠気が襲ってきたので耐え切れず意識を手放し、気づいたら午後11時だった。昨日の迷惑メールと同じアドレスからさらに1通来ていた。

またなろうを読み進める。午前3時くらいに寝落ち。なろうを読んでいる間はかなり現実感を失って時間間隔もあやふやになるが、履歴から時間を復元できることに気づいた。

10/16(金)

午前9時、起きる。また寝落ちしていたのか……。メールを確認したところ、急に12時半までのレポートが生えている。

明日の2限はclassroomに講義資料と動画が数本アップロードされるタイプだが、小テストがあって、授業終了30分後までに提出する必要があるらしい。その時間制限は何？

週記（2020/10/05-2020/10/11） - kotatsugameの日記

先週は前日のうちに講義資料が投稿されていたが、今週は当日午前9時に投稿されている。本当に意味不明。オンラインのくせに講義時間を守ろうとするのは一体何を考えているんだ？オンラインのいいところをぶち壊しにしている。生徒が全員日本標準時で生活しているとでも思いこんでいるのか。

ぐちぐち言ってはいるが、今週はたまたま起きていたのでセーフ。急いで書き上げて提出。ちなみに先週「課題を授業開始前に提出してもよいですか？」とコメントを送ったが、返信はない。

まだ3週目なので、実は今週だけ投稿が遅れました、という可能性もある。動向を注視していきたい。それにしても12時半までという時間制限は意味不明。

AOJ-ICPCを1問解こうとしたらうっかり定数倍高速化ゲーが始まってしまい、また学食が閉まりかけた。最近改めて覚えなおしたA*を使ったが、普通に情報を全部DPのキーとして持てたらしい。

学食に行って、帰ってきて、家でしばらくAtCoderをした後ゲーセンに行く。10月に入ってから初めてらしい。

そもそも外出の機会がほとんどないため、わざわざ繁華街まで行く際には必ず本屋さんに寄る。久しぶりに本を買うにも関わらず、あまり新刊が多くない。買っていないものをリストにまとめているが、そのリストが短い。

やっと買えた。1冊だけ棚にズドンと並んでいた。もう平積みされてないのか……。他にラノベの新刊を6冊買った。

音ゲーは全然ダメ。どうにもぼんやりしていてLATEまみれになっている。普段はFASTが多いので、真逆。こういう日は素直に帰って日を改めるべきだが、せっかく外出したんだし……と意固地になってプレイを続ける。終盤は微妙に調子を取り戻した気もする。

そういえばプレイ中に迷惑メールがまた1通来ていたが、さすがにもう面倒なので特にスクショを撮ったりせず報告・削除した。

帰ってきて本の写真を撮ってツイートした後、布団に寝っ転がったらそのまま寝落ちしてしまった。

10/17(土)

午前11時に起きる。前から楽しみにしていたたこノすけのハーメルンおすすめまとめが投稿されていた。めっちゃ催促してごめんね。

taconosuke.hatenablog.com

とりあえずこれを読み始める。

syosetu.org

なんだか結構な数のなろうを立て続けに読み始めてしまったが、まあラノベでは数十並列など珍しいことでもないので、耐えられるだろう。でも読むの途中で止めちゃうかもしれないな。

パソコンの前に移動してプログラミングしたり、布団に戻ってハーメルンを読んだりしていると、ABCの時間になった。今日は他のコンテストとの兼ね合いで午後8時から。

ABC180。E問題まで10分もかけずに通した後、F問題で55分使った。

Aは13秒でFA、それがそのままShortestになった。4Bytesなのでさすがに縮まないだろう。

E問題は頂点間の移動の際に別の頂点を経由しても短くならないことが重要だが、完全に見落としていた。

Fは取り出す連結成分のサイズでループを回した結果、調和級数みたいになった。実際はサイズに関する条件はf(L)-f(L-1)をして消すべきだった。同じサイズの連結成分を区別しないために、サイズごとにループを回す必要があると思っていたが、結局それでどうやって区別をなくしているかというと「選ぶ頂点集合の中から1つ固定する」だけなので、普通にループしてもできる。

ただ、連結成分のサイズでループしたところf(L)-f(L-1)のように定数倍が2掛からなくなったのが効いているのか、この記事を書いている現在は49msでFastestだ。

かなり眠いが、こどふぉにも出る。6完。D問題でちょっと詰まり、E問題でドハマりした結果ペナルティがとんでもないことになって-17。

F問題は、区間の左端を固定して右端全部を1度に足すことを考えると、左端をずらして1が出現するたびに「連続する1の部分列の長さの最大値」が更新される場所の手前まで、足す値が+1されることがわかる。

この更新される場所というのは、現在1が続いている個数を初めて超える場所なのだが、+1しかされないことを考えるとstackで持って上から削除していけばO(1)で求められる。全体でO(N)。コードはかなりシンプルになった。

E問題でハマり続けて、Eより先にFを通したのだが、Fは見てから10分くらいでACできた。そのあとしばらくしてEも通ったが、これは-(A+B)を-A+Bと書いてしまうミスによるものだった。

生活リズムが合っていないため、眠気で本格的に頭がボンヤリしてきた。SRMもあるが、出ないことにする。

10/18(日)

昨日は眠気があるとか書いておきながら、布団に入ってから6時間程度ハーメルンを読んでいた。結局寝たのは午前11時くらいだった。

ABCのD問題の僕の解法が嘘だらけであることにも気づいた。XとYの最大値が1e18ではなく1e9だと思い込んでいたのでオーバーフロー対策を何もしていないし、X*A<X+BではなくX<Bを判定している。両方合わさるとたまたま通ったらしい。この方針でコードゴルフもしてしまった。まあコードゴルフに関しては、テストケースが弱ければその隙を突くのは当然なので問題なし。

午後8時に起きる。午後7時半から午後9時まで30分おきに目覚ましをかけていたが、その最初のもので起きて、しばらく布団でモゾモゾしていた。

理論的にはあと30分×2回くらい寝られるはずだが、そんなに心臓が強くないので、この時間から寝るのは不可能。

AtCoder Problemsを確認すると、RPSが400000を超えていた。毎週2100ずつ増えていく謎の指標という感じだ。

AGC048はABCの3完75位で、パフォーマンス2795、レートは2696→2706と上がった。2700を超え、いよいよ赤が見えてきた。でもこんな微増だと収束してしまう。

A問題は1発で通った。コンテスト中はペナのにおいを感じ取ってそこそこ丁寧に提出した。いくつか頭の中で場合分けをして、それぞれに対して最適性を確かめていたはずだ。7分。

B問題は最初途方に暮れていた。AかBかではなく0かB-Aかを考えればよいことをひらめく。片方だけのvalidなかっこ列であって、もう片方もちゃんと埋められるようなものにはどのような特徴があるか？を考えると、ペアになるものの間に偶数個の文字があればよいことが感じ取れる。

ここでいったん何か%2をキーに持つDPを考えて書き上げ、サンプルも合わせるが、提出の直前で意識を取り戻し、よくよく考えると違うことがわかる。

正解は、インデックスの偶奇で分けてそれぞれペアにすること。実装してAC。30分。

C問題はややこしくてよくわからない。中途半端なところに石を持っていくことはできないので、どこかの石を固定して、そこにくっつけていくしか調節する方法はなさそう。また、最適な移動において右に行った後左に行くような（逆もしかり）石は存在しないということを感じる。頭の中で適当に説明をつける。いったん右に行く必要があるなら、より左にある石も同じく右に来るはずだが、そうするとそれらをどかさなければ自分が左に動けなくなる。

このあたりでいったんO(N^2)を書く。左に移動する石iは、自分より左の石j（j<i）であって都合の良い位置にあるものを探し、そこまで1つずつ動かしていくことになる。つまりA_j+(i-j)==B_i or B_j+(i-j)==B_iなるj（j<i）のうち最も大きなものを探して、ans+=i-jをする。

右に移動する場合はiに対してj（i<j）であってA_j-(j-i)==B_i or B_j-(j-i)==B_iなるjのうち最も小さなものを探して、ans+=j-i。

この2つはどちらもA_j-j==B_i-i or B_j-j==B_i-iとなるので、まとめられる……わけではない。1WA。

iとjの大小関係をすっかり忘れてしまっていた。例えばL=114514、A={3,4}、B={4,5}のときに互いに互いを頼りに動けると判断してしまうコードを書いていた。

自分より左にあるものと右にあるものを分けて管理し、iを進めるごとに1つずつ移すように書くとAC。30分。

D問題は、気合で4つの山に対する勝敗判定を計算し、5つの山を前にして投げ出してしまった。ゲーム系の問題は場合分けを投げ出さないことが基本だと以前書いたのに……。

でも本当は、この勝敗判定から端の山の石の個数に対する単調性を感じ取ればよかったらしい。1つ取るか全部取るかしかないことを頼りに、遷移をスキップするDPを書こうとして実装が爆発していた。

久しぶりのコードゴルフ。Octaveに新手が出た、というかバージョンアップでよくわからない変更が入っていた。

Octaveの数値は全部doubleなので、ある程度大きな数を出力しようとすると指数表記になったりして困っていた。

最初期の解決策はdisp(int64(ans))。これは非負整数を出力するときに、先頭の空白をつけないようにする効果もある。

これは、dlmwrite(1,ans)とすることで1B縮む。1はstdoutのことだ。C言語でおなじみ。

ここまではOctave 4.0.2の話。現在のOctave 5.2.0では、disp(ans)でもちゃんと出力してくれるらしい。なんと驚異の-6Bだ。探し回って縮めた。

もう1つある。入力を読む関数にdlmread(0)がある。0はstdinのことだ。この関数は特に横に長い行を読むのが非常に遅く、10^5要素あるとTLEしてしまう、と思い込んでいた。

実際には、列数が異なる行を読むときに特別遅くなっているだけで、10^5要素の行だけを読み込むならちゃんとまともな時間で動いてくれるようだ。以前までは、例えば1行目に入力される要素数Nもまとめて読み込んでいたので気づかなかった。これをすると1要素の行とN要素の行で列数が異なるため時間がかかる。ちなみに、足りない分は0埋めされる。

リクルートのアルバイトに応募するためのエントリーシートはどんなものか見てみたら、これまでに最も成果を出した取り組みを聞かれていた。僕の取り組みといえば競プロだが、特に目に見える成果があるわけではない。なるほどこれは厳しい。AtCoder Jobsでレーティングが就活に使えるのがかなりありがたいことなのだと気づいた。