週記（2020/11/02-2020/11/08）

11/02(月)

寝落ちしていて、午前9時に起きる。そこから2時間くらい二度寝しようと布団でもぞもぞしていたが、結局そのまま起きることにした。この時点で午前11時。

昨日は日記を書かず寝落ちしてしまったので、その分を書いて、投稿した。なんとなく興が乗って4000文字くらい書いたところ、この週の週記の文字数が14000文字となり、2000文字/日を達成した。実際にはリンクを貼ったりした分でいくらかかさましされている。

投稿した後ふと思い立って、ABC181のC問題のコードゴルフをもう少し考えてみる。2次元平面上の点を扱うなら、複素数で持つのが定石だったことを思い出した。原点と点x、yをそれぞれ結ぶ直線が平行であることの条件は、x=a+bi、y=c+diとしてad-bc==0を判定したいのだから、x*y.conjの虚部が0かどうか判定すればよい。y.conjはyの共役な複素数を表す。

これでcombination(3)したほうが短くなった。rescueも消えた。

atcoder.jp

食事をした後、AOJ-ICPCを埋める。無証明でテストケース見ながらごり押しするのは練習としては最悪なんだけど、やってしまう。解説ブログを読んだら枝刈りで計算量がよくわからないタイプの問題だった。止めよう！

そういえば、AOJにもレーティングが存在して、例えば問題の提出一覧を見るときなどこの値の降順にコードが並ぶが、最近更新されていない。結構気にしているので、また更新が再開されることを願う。

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

このくらいの構文解析の問題はかなり楽しい。時間をあまり気にしていないので、設計をしばらく頭の中で練ってから実装した。

https://onlinejudge.u-aizu.ac.jp/status/users/kotatsugame/submissions/2/1233/judge/4962252/C++14

多項式を表現する必要がある。各項の次元を表す構造体Strと、それの線形結合である多項式を表す構造体expを作った。名前は適当。

Strでは、関係する変数を次数のぶんだけ並べて保持することにした。x3 y2だと"xxxyy"のような感じ。正直これはstringを掛け算する関数だけ作るのでもよかった。実装上の要請からいくつかメソッドを用意したが、ほとんどは元のstring型のメソッドを呼び出している。変数は文字コード順に並ぶようにしているが、これは毎回ソートしなくてもマージソートの要領で並べればよい。ただ実装上の手間を考えると毎回ソートしたほうがいいのかもしれなかった。

expは、map<Str,int>で各項の係数を持つ。ただ、係数が0の要素が残っていると比較の時にちょっとまずいことになるので、毎回係数が0になった要素を消している。足し算や引き算はそのまま足しこめばよくて、掛け算はStrの掛け算を呼び出して行う。

構文解析は普通に書けばよいのだが、スペース交じりの文字列なので、そこをどう扱うか少し悩んだ。多分関数内で適宜読み飛ばししてもよいのだろうが、いろんなところで読み飛ばしのコードを挟み込むとちょっとつらそう。なので、入力のstringをまずトークンに分解して、vector<string>に対して構文解析を行うことにした。数値は纏めるが、それ以外は全部1文字ずつに分解する。

そんな感じでゴリゴリ書いたところ、30分くらいかかった。クーリッシュを机に出していたことを完全に忘れており、解き終わってから見るとグズグズに溶けてしまっていた。食べごろを逃している。

メールをチェックすると、リクルートの冬アルバイトの書類選考を通過していた。

もし向こうが競プロerに興味があるなら、僕をエントリーシートで落とす理由はないと思う。

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

尊大な自尊心である。羞恥心が臆病かどうかは知らない。

面接日程を決める必要があるが、近くならないと自分の生活リズムがわからないので、しばらく放っておく。スキルチェックをやってみる。これどこまで情報を書いてもいいのかわかんねえな。問題を盗んで公開しているらしいLeetCodeはカス。

まずアルゴリズム関連の問題を選んで解いてみる。競プロチックな問題に見える。using namespace stdしないで書いたが、信じられないくらい読みにくくなった。

問題なくコードを書き上げて、別の問題を開いてみるが、もうわからなくなってきた。一応自分用に書いたコードで使用したことのある技術なので、まったくとっかかりがつかめないわけではない。必死にググり散らかしながら書いたが、半分もいかないうちに嫌になってきて布団にダイブし、そのまま寝落ちしてしまった。

11/03(火)

午前8時くらいに起きた。だんだん早起きになってきている。

寝落ちしてしまった昨日の分の日記を書いた。昨日1冊本を読んだはずなのだが、どの時間帯に読んだかさっぱりわからない。いっそのこと今日の部分に書いてしまおう。

「御執事様の仰せのままに」という本。貧乏大学生が実は日本一の金持ちの直系で、急に跡取り候補になって上流階級の生活に戸惑う……みたいな話だ。

内容はさておき、「上流階級の話」ということでちょっと考えていることがある。作者は別に上流階級の人間ではないそうだが（あとがきより）、描かれた描写はどれくらい現実味があるのだろう？この本で描かれた上流階級の話はほかのなろう小説とかで読むものとあまり変わりがないので、現実にどうなっているかはともかく、そういう共同幻想があって、それに沿って話が作られていると考えられる。

大富豪とか会社の社長とか芸能人といった人たちを主人公にしたなろう小説をよく読むが、各ジャンルの作品群にもたいてい共通する描写の要素はある。しかし読みながら現実ではどうなっているか気になってしまう。というか会社の社長って何をするんだろう？どれくらい忙しいんだろうか？

勝手な想像だが、極端な話アメリカ合衆国の大統領とかは1日のスケジュールが秒単位で決まってそうだと思っている。でも調べて出てくるようなインターネットの記事を見る限りだと全然そういうことはなくて、朝起きてからしばらく運動のために時間を使っていたり、ちゃんと毎日プライベートな時間があったりする。忙しい日は忙しいのだろうが、記録を1つ読んでみた結果、分単位のスケジュールがあるわけではなくて行動の描写の解像度が高いだけという感想になった。廊下を移動するのはスケジュールに入りますか？常に行動しているので、そういう点では忙しいだろうが、僕の想像が極端すぎた。

昨日から引き続きコーディングテストを進める。サンプルのデータが弱すぎるのでかなり心配になる。ジャッジしてくれても、正常に終了してファイルが出力されているかどうかしか教えてくれず、出力が要件を満たしているかは教えてくれない。それらの点数は提出を確定させて初めて知ることになる。

競プロで攻めていこうとしていたが、そんな狭い範囲の職業は存在しておらず、データを加工するポジション一般にカテゴライズされている。それについてのコーディングテストなので、例えばネットワークだったりSQLだったりの知識を求められていて、それらに対して競プロは何の役にも立たない。

多分どの設問もそのドメインの知識を持っている人にとってはやるだけの問題なんだろう。何も知らないような人をはじく目的か？

いやになってきたのでAOJ-ICPCを進める。

幾何ライブラリを設計した時の自分、何を考えていたんだ……。ちなみに以前、これで2時間くらいハマったことがある。その時は二度と間違えないという決意を抱いただけで済ませてしまったが、今日またハマりかけたので直した。元あったintersectをcount_tangentという関数名に変更して、新しいintersectは1<=count_tangent<=3を判定する。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1242

これかなりfloor_sumだと思って喜び勇んで実装したんだけど、実際は微妙なスキマを正しくカウントするのがどうしてもできなくてダメだった。ACコードでは辺に重なるマス目を愚直に列挙して、完全に含まれるマス目は平面走査でカウントする。

情報理学IIのレポート提出期限が明日に迫ってきているので、する。フーリエ級数とかの問題で重めの積分計算を要求される。計算が必要な個所は途中計算も書くこと、と書いてある。

グラフのプロットには計算機を使っていいらしいので安心。

かなり眠くなってきたので布団に近づいたところ、一瞬で吸い込まれてしまい、無事寝落ちした。

11/04(水)

午前5時半に目を覚ます。寝落ちしたことに気づいて絶望する。レポートが終わっていない。

いつもなら二度寝するのだが、今日は起きることにして、レポートを進める。面倒な計算をしたりWolframAlphaに投げたりして、とりあえず手で書くパートは終わる。あとはグラフのプロットをいくつかする。

グラフィカルなことは何もわからないけど、とりあえずJupyter notebookってやつを使えばよさそう。適当にググってコピペしながら書くと、グラフがプロットできた。凡例をグラフの外に表示したりとかも調べれば簡単にできて、うれしい気分になった。これを印刷する必要がある。

まず、ブラウザを拡大してスクリーンキャプチャしてみる。キャプチャしたものをWordに貼り付けて印刷すると、ぼやけてしまいなんとも悲しいグラフになってしまった。

TLに質問を投げつつちょっと調べてみたところ、画像としてダウンロードできるらしい。今度はこれを貼り付けて印刷したが、まったく同じぼやけ方をしていた。人からそれっぽい方法のリプライが来ていたのだが、僕はちょうどこのあたりであきらめてしまい、結局ぼやけたままのグラフを提出することにした。

そんなことをやっている間にちょっとサークルのSlackを確認すると、公欠届1人分をお願いし忘れていたことに気づいた。冷汗が出た。

幸い、11/05までにもらえればよいとのことだったので、まだ1日時間がある。今日顧問の先生にお願いして、今日の夜か明日の朝に返ってきてすぐ渡せばギリギリ間に合いそうだ。急いでファイルを作成し、先生にSlackで送ろうとしたが、まだ午前7時台だったので通知がOFFになっているらしい。このような場合、通知がONになったときに一気に送られるのだろうか？ちょっと自信が持てなかったので、通知がONになるのを待ってから送ることにする。

これまでは公欠届が出来上がってから各人にチェックしてもらっていた。学籍番号や氏名などがもし間違っていた場合は、署名と押印をもらうところからやり直しなのだが、それくらいの時間の余裕はあった。（今考えると、先生に負担を押し付けていることになってあまりよくなかった。）

今回はもう間違っていたら間に合わないので、同時にチェックしてもらうことにする。8時を過ぎて、先生の通知がONになったので、メンション付きでファイルを送った。送った後すぐにチェックしてもらった人からレスポンスがきて、間違いはなかったらしい。まさかこんな朝早くにレスポンスがあるとは思っていなかったので、チェックの結果を待たなかったのはしょうがない。

ともかく、これであとは先生からファイルが返ってくるのを待つだけ。先生がどれくらい忙しいのか全然想像がつかないのだが、結果だけ言えば午前9時半に返ってきた。こういう小さな用事は見た瞬間に済ませることにしているのかも。

ともかく、これで僕のミスのカバーが完了した。サークル運営にかかわることでミスをすると他人に迷惑がかかるので、ちゃんとToDoリストを整備しておく必要がある。今回のミスは、公欠届申し込みの締め切りを設定したあとにそのことを別の場所にメモしていなかったことが原因。誓約書まで書き終えて安心して、サークルSlackを放置していた。

レポートを提出する。山の上の研究室まで行って提出しなければならないらしい。このオンラインのご時世に物理的なレポートを求める必要性はどこにあるのか？まあ求められたものはしょうがないので出しに行く。思い返してみれば、前期は結局山の上に行っていないはずだから、都合8か月ぶりの青葉山なのか。

数学系研究棟の近くの駐輪場に原付を停めて、研究室まで歩く。目的の研究室は理学研究科合同C棟という少し離れた建物に入っている。道路沿いに進めばすぐ着けるのだが、洒落っ気を出して大学の中、建物の間を縫って歩いて行こうとした。

迷子になった。

思ったより移動できない段差が多い。あと工事をしていていくつか道が通れなかった。とりあえず大きな道路に出たい。方向だけ定めて深さ優先探索（もしくは右手法）をしたところ、うっかり研究室の建物を大きく超えてもっと先にある地下鉄の駅の出口まで歩いてしまった。このあたりの話は青葉山キャンパスマップを見るとわかる。

たいぺーと待ち合わせていて、合流した。提出は間に合った。本当はもっと余裕があったはずなのだが……。

同じ建物にレストランが入っていたので、そこで昼食を食べようとしたが、なんだかミールカードが使えなさそう。あきらめていつもと同じ原付を停めたところの学食に行く。食べ終わって生協でけんちょんさんの本を買った。

帰ってきてハーメルンを読みつつAOJ-ICPCを埋めた。少しだけAtCoderもした。

bcでリアクティブ問題を解いてみたところ、特に出力回りをいじらなくともACできた。バッファリングは行われていないようだ。よく考えてみればbcは対話型の言語なので、当たり前の話かもしれない。

午後8時を回ったあたりで眠気が強くなる。うっかり椅子の上で意識を飛ばしてしまった。半ば寝落ちを覚悟して、午後9時半くらいに布団にダイブし、当然のように寝落ちした。これもう普通に寝てるだけじゃないの？と思いそうになるが、忘れてはいけない、寝る前にするべきルーティンを一切こなさずに寝ているからこその寝落ちなのだ。あと電気とかエアコンとかつけっぱなし。

11/05(木)

午前4時半、起きる。異常。どうしようもないので、今日はどこかでお昼寝をすることに決める。

今日は何もないし明日はICPC国内予選なので、ずっとAOJ-ICPCを埋めることにする。これまでも埋めてはいたのだが、日記に書こうとしても特に書くことはないため、文章にはあまり出現しない。今日もずっと埋めてたけど本当に書くことがない。

www.youtube.com

このサムネイルの画像がなんのゲームか探している、とのツイートがTLに流れてきた。僕はつなこさんの絵が好きなので見た瞬間にわかるのだが、これはつなこさんの絵。pixivにはなくて、サイトにもなかったので、「つなこ」で画像検索すると、似たキャラクターの画像が引っかかる。詳細を見ると、フェアリーフェンサーエフというゲームだった。公式サイトを見ると確かにこのキャラクターが登場している。

探していた人に教えたはいいものの、そもそもこの動画の詳細の部分にPicture : Fairy Fencer Fと書いてあったらしい。目がついていないことで有名。

つなこさんはデート・ア・ライブのイラストを担当しているイラストレーター。ラノベのイラストレーターなら少しはわかる。たいていは同じ人が同時期にいくつも担当していて、すごい。

ASCII Expressionに挑戦してみた。領域の上下左右だけ持てば余裕だろうと高をくくっていたのだが、そんなことはない。普段の構文解析と同様にするためには、問題文にあるbaseを調べておき、左端を参照で持って縮めていく必要がある。あとスペースの入り方を考えて関数からreturnする前に一つずらしたりなども普段とは違うところ。

結局80分かかった。しかも1WAしたあとテストケースを見ているので、実際にコンテストで出たらどれくらいかかるかは分かったものではない。まあミスは大したことない場所1か所なので、自力で見つけることが不可能ということはないだろう。べき乗の時に領域の外を見る可能性があったのだが、そこには基本'.'しかないだろうと思ったら文字列をはみ出して'\0'を見ていた。

そんなことをしていたらお昼寝のタイミングを逃しそうになった。午後8時、布団に入ってお昼寝する。午後11時に頭の痒みで起きた。無意識に頭皮をかきむしっていたらしく、枕カバーに抜け毛が大量についていた。確かに昨日からシャワーを浴びていないが、1日でここまで耐えがたい痒みに襲われるのはちょっと尋常ではない。眠気も少しあるが、それよりなにより頭が痒くて仕方ないので、急いでシャワーを浴びた。

Lowlinkのライブラリは、グラフが連結である場合にしか対応していなかったみたいだ。

週記（2020/09/14-2020/09/20） - kotatsugameの日記

僕の橋検出ライブラリはグラフが非連結のときにバグる（というか1つの連結成分しか見てくれない）というのは以前にも書いたかもしれない。

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

これを直す。引用するために過去の週記を漁ったのだが、こんなに昔の話だったのか。とりあえず螺旋本を読んでLowlinkの気持ちになる。直し方については、まあどう考えても最初のdfsのスタート頂点を0固定ではなくループを回して探すようにすればよい。dfsの時にカウンタ変数を参照渡ししていて、これの値をどう扱うかでちょっと考える必要があると思っていたが、別にそんなことはなかった。毎回リセットしてもよいだろうし、しなくても動く。

Library Checkerの二辺連結成分分解にACして、verify完了。多重辺と逆辺（無向グラフなので）の区別をどうするかちょっと困ったが、隣接リストを舐めるときに親が2回以上出現したら多重辺であると考えて問題はない。

親の顔より見た親の顔。

今日だけで550点を中心に16問も解いた。洗濯物を干したり日記を書いていたらいつの間にか午前4時半になっていた。この部分を書いている最中にFHCのTシャツに関してメールが来ているのを見つけたが、さすがにもう寝ないと明日が怖い。

11/06(金)

昼前に起きる。本当はもっとしっかり寝ておくつもりだったが、二度寝に失敗して起きる。金曜日なので課題が出ていた。

メールを確認したところ、急に12時半までのレポートが生えている。 週記（2020/10/12-2020/10/18） - kotatsugameの日記 これに関して、先週の金曜日は特に何も書かなかったが、2限の講義ではレポートが出なかった。今日はどうなるだろう、まだ出ていないが……と待ち構えていたのだが、どうやら今日は学祭の日で休講らしい。

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

これ。なんだかんだ言ってまだ3回目くらいのようだ。今日の課題は午前10時に投稿されていて、提出期限は17時だった。問題自体は自明も自明なものだったので、期限が延びているのはよくわからない。これからずっと17時期限なら、少しは許せる。いややっぱり当日に課題投稿するの許せないな。

あまりに自明だったので、問題が隠されていないかとか誤読をしていないかのチェックに少し時間を使った。

スキャンして提出し、学食に行く。学食と同じキャンパスの建物からICPC国内予選に出る予定。味噌汁が好きなので毎食味噌汁を注文するようにしているのだが、信じられないくらいしょっぱい。あまり客が来なくて、蒸発した結果濃縮されていると予想している。耐えられないので、生協の一言カードで苦情を入れた。

生協でお菓子と飲み物を買いつつ、マルチメディア棟の演習室に行った。数人人がいるが、サークルメンバーかどうかはわからない。オンラインなのでメンバーの顔を知らないまま活動している。昨日寝ながら考えていた500点問題を1問通しつつ、リハーサルもこなして、チームの集合を待つ。

これ以降コンテスト中の話に関しては参加記を書いたので、そちらを参照されたい。

kotatsugame.hatenablog.com

打ち上げの後の話は、文章量が多くなりすぎたので別の記事に分割した。

kotatsugame.hatenablog.com

部屋に戻ってしばらくはパソコンの前でボンヤリしていたが、午前9時くらいに寝た。

11/07(土)

午後5時くらいに起きる。HTTF予選が始まっていた。とりあえず1Byteの解と自明な解を投げる。すぐには方針が浮かばなかったし、ほかにやりたいこともいくつかあったので、HTTF予選に関してはこれで終わりということにする。

AOJ-ICPCが更新されていた。つい先日解いたばかりの問題が容赦なく除外問題に行っており、感慨深い。

昨日からずっと考えていたコードが1Byte縮んだ。

atcoder.jp

4^8全探索をするのだが、数値を4進数に変換するときに他の変数との兼ね合いでわざわざ4を掛けている。つまり、a桁目を見たいのだが、aが1-indexedなのでi/4^a%4とはできず、i/4^(a-1)%4あるいはi*4/4^a%4としなければならなくなっている。

このことは、4^9全探索をすることにすれば解消できるが、どれだけ試してみても時間制限に引っかかってしまう。内部のループを減らしたりもしてみたが、どうにもコードテストで2200msくらいかかってしまう。なんとも絶妙なところだ。

この問題では、以前まで僕のPerlが最短だったのを、ある人と僕によって都合6回Bashによる更新が行われた。上のコードはその6回目だ。5回目の更新を見て、もうだいぶ短縮合戦をしたのでこれは勝てないと思い、しばらくは別言語で縮まないか考えていた。結果そこそこ早い段階でRuby129Bのコードが完成し、さらにずっと時間を使って考えていたのだが、そこからはついぞ縮めることはできなかった。

このコードもいずれまた取り返されるのかもしれない。他の人のコードを縮めることより、自分のコードを縮めるのはよっぽど難しい。僕もこれ以上縮まないことを十分確認したつもりだが、やはり感覚としてチャレンジャー側で考えているのと防衛側で考えているのは違う。

yukicoderが2週間ぶんたまっていたので、ほどほどに解いておく。数学コンテストを銘打っているほうは問題のレベルが高いのであんまり解いていない。昨日行われたコンテストのほうは全問解けた。最後の問題はbitDPで解いて、面白かった。C問題は何となくそれっぽい解法をひねり出したけど、解説で1手交代のはずのお互いの行動をそれぞれ別々に考えているのが納得いっていない。あとはまあ、自明かな……。

ICPC国内予選の参加記を書いた。後ろのほうにお気持ち表明パートを付け加えようとしたけど、書きたいことがまとまらないうちに頭の中でどんどん話がずれていって、そのことに気づいた瞬間に書くのを諦めた。コンテスト終了直後は気が立っているのもあっていろいろ強い言葉を使いそうになったけど、1日置いた今、そこまでの熱意はない。ただ何も書かないのも腹ふくるるわざ、ということでツイートをする。

AOJ-ICPCに追加された問題を埋めようとした。最近の問題なので、コンテスト会場で読んだ覚えのある問題がたくさん並んでいる。ちょっと詰まってしまったので布団に寝転んだところ、寝落ちした。午前5時半くらいだった。

11/08(日)

正午、起きる。結構鮮明に夢を覚えていたので、文章にまとめてツイートする。覚えているうちに、と頑張ってガーッと書いたら8連投ぶんにもなってしまった。

昨日の続きでAOJ-ICPCを解いた。とりあえず400点問題までは再度埋めた。

明日月曜日の講義開始前までが期限のレポートがある。コンピュータグラフィックスという講義だ。普段の小テストとか演習は存在しないので、これまでノータッチだった。そろそろ始めないと間に合わなさそうだと感じてレポート問題を見ると、アフィン変換の行列を作ったり移動をシミュレートしたりするだけの簡単な問題が少し並んでいるだけだった。拍子抜けしたが、別に頭の中で三次元のアフィン変換をシミュレートできるわけではないので、ちゃんと検算もしておく。僕の好きなOctaveを使うと便利！と思っていたが、入力が面倒だった。

書き上げて提出する。夜のABCまで結構時間がある。ただし、眠いからと言ってお昼寝をするほどの時間はない。昨日と一昨日の分の日記を書くことにした。寝落ちとかでバタバタしていて書いていなかった。

日記の木曜日の部分を読んで、FHCのTシャツに関するメールをその後確認していなかったことに気づいた。慌てて確認したところ、「第三者からのメールが来週末までに届くので」と書いてあって安心。まだ届いていない。

午後6時、第4回PASTの受験期間が終了した。直後に問題が過去問として公開されるものだと思って、AtCoderのトップページをしばらく更新したりして見ていたが、全然公開されないので、あきらめて日記を書くことに専念した。

午後8時ごろにPASTの問題が公開されたので、解き始める。相変わらずコードゴルフには向かない問題だらけ。Iまで一息で解いたが、中央値ではなく最大値を求めていたり、答えのmodを取り忘れたり、グリッドの横幅のところで縦幅を使っていたりといくつかWAが出た。Jを読んで少し詰まったのでシャワーを浴びることにした。冷静になると明らかだったので、解く。そのあとKも解いて、ABC182が始まった。

全完4位だった。E問題で同じ処理が2回出現したときにコピペしたのだが、1か所HにすべきところをWのままにしていた。そもそもこういう問題ではH!=Wのサンプルも用意しておいてほしい。ただ、このペナルティがなくても2位のようだ。

全完した後コードゴルフをしていたのだが、A問題が1Byte縮んでかなり残念な気持ちになった。一応最初に解いてから少し時間を取って確認したはずだったのだが。さすがに30分経過しているし誰かが先に出しているだろうと思ったが、終わってふたを開けてみれば単独で最短コードが取れていた。

B問題なんかは、C++を使うべきではなさそう。Rubyのmax_byメソッドを使うべきシーンでは、ほかの言語で書くと少し面倒になりがち。比較のための値と、出力する値の2つを保持して計算する必要があるからだ。

Fはいつもの繰り上がりフラグを持つDPだと思って、それっぽい遷移を書いたらサンプルがあってそのままACしたので、あまりよく考えていない。解説を読むと、問題の言いかえだったり探索範囲の絞りこみだったりをしていて、かなり難しそうに見える。

ひとしきりコードゴルフをしているとコンテストが終了したので、一応各問題の最短コードを確認した後、PASTに戻った。残り4問。M問題の計算量をよく考えないまま通したこと以外は、ほとんど詰まることなく駆け抜けた。かなり簡単なように感じた。

M問題の解説を読んだところ、計算のスキップする部分でUFを使っていた。僕のコードに照らし合わせると、どうやらUFで経路圧縮をしない場合だと考えることができそうで、十分間に合う計算量であることが分かった。

最近睡眠が下手くそで、寝落ちした挙句早い時間に起きて二度寝できないことが多い。今も結構眠いので、とりあえず週記だけ早めに投稿しておくことにした。毎週月曜日の昼頃になって投稿しているのはあまりよくない。

ICPC国内予選 2020 参加記

2020/11/06に開催された国内予選にチームAobayama_dropoutで参加しました。メンバーはいつもの碧黴さん・ゆきのんさん・僕です。

例年はサークル顧問の先生の研究室に集まって出場しているのですが、今年はコロナの影響で全員は集まれないとのこと、急遽マルチメディア棟の演習室を借りてもらったので、そこから参加します。

このあたりの事情を含めて、サークル運営としてのICPC参加記も書きたいと思います書きました。社会性をたくさん消費しました。

kotatsugame.hatenablog.com

コンテスト前

ノーパソのキーボードはストロークが浅すぎて慣れないので、今年はキーボードを別に持っていくことにしました。

今回も戦略としては僕が最初にDを読んで、その間に他の2人でABCを通す感じです。模擬国内の後にこれに関して少し話し合ったのですが、結論はうやむやになりました。

コンテスト中

しばらくページが見れない状態が続いていました。緊急事態だと思って同じ部屋から出場しているチームにも確認したところ、全員繋がっていないうえ、ポケットWi-Fiで接続している人も同じく繋がっていないので、向こうの問題だと確信し、待つことにしました。しばらくチームメイトと談笑していると、ヌルッとコンテストが始まりました。

D問題

読みましたが、全然わかりません。しかし僕がDを解かないというのはあり得ないので、あきらめずに考え続けます。とりあえずbit系の解法を考えることにしましたが、bitDPはどうにも情報が足りないので使えません。

もうしばらく考えていると、文字をグループ分けするとよさそうなことがわかります。具体的には、文字集合を2つに分割して片方がもう片方より必ず大きいとし、この状態で構文解析すると、文字列の評価値がどちらのグループに属するかわかります。このとき、評価値にならないほうのグループはどのように並んでいても関係ないこともわかります。

つまり、毎回サイズを半分にしながら同様の問題を解いていけばよさそうです。comb(16,8)*comb(8,4)*...を計算するとかなり小さかったので、この方針で実装します。

mapに正か負の値を入れて、各文字の評価値とします。このとき値の絶対値を2**文字集合のサイズとして再帰の階層ごとにユニークにしておきます。本当は±1でよいのですが、念のため意図しない値が評価値となったときに検出できるようにしておきたかったからです。

残りは最も簡単なレベルの構文解析なので、特に問題はありません。ただ対象となる文字列が2つあります。一瞬、関数を2つ用意しようかとも考えましたが、string::iteratorを渡しておけば1つの関数で対応できます。

テクニックとして、例えば今回の問題では</>とmin/maxのどれがどれか考える必要はないです。結局順序を全通り試しているからです。

D問題が通ったのは40分過ぎで、その間に他の2人はABCを通してE問題を読み始めていました。

E問題

E問題を読むと全然わからないので、F問題をチラ見します。直感的に後ろからUFで連結成分を管理しつつ最大連結成分を持っておけばよさそうだと思ったので、その方針で実装してしまうことにしました。チームメイトに伝えて実装し、サンプルが一発で合ったので提出しましたがWA。よく見ると考察していたことが全然実装できていないことに気づいたので、コードを書き足して、出力が変化したことを確認して再度投げましたがこれもWAでした。

Fを書いている途中にゆきのんさんがE問題の解法を生やしていました。縦横を逆にしたら2^(60/4)になるというものです。どう考えても天才の解法で、明らかに合っています。遷移が2^15になりそうですが、適切に畳み込めばよいです。太鼓判を押すだけ押して実装をしてもらっていましたが、どうにも行き詰っているようで、僕自身FがなぜWAなのかもわかっていないので、改めてE問題を書くことにしました。

bit列と行番号を対応付けるのがかなり難しいですが、この辺りは4通りしかないので2人にそれぞれ求めてもらうことにして、遷移の部分を書きます。かなり時間がかかりましたが、とりあえず書けて、サンプルを試します。何一つ答えが合いませんでした。このあたりでコンテスト開始2時間くらいです。

しばらく格闘していると、遷移に関係する縦のマス目の個数とスタート地点が違うことに気づきました。直すとサンプル1と2が合いますが、3番目は合いません。

入念にコードをにらみつけていましたが、どうにも実装におけるミスが見つからないので、考えたことが間違っているのではないかと疑います。これは当たりで、畳み込みが全然できていませんでした。適当に書き直すとサンプル3も合ったので、提出。WAでした。残り30分です。

サンプルが合って通らない絶望感がヤバいです。相変わらず実装におけるミスはなさそうでした。さっき書き直した畳み込みを疑って、もう少し大きなケースでどういう遷移をしているか想像してみると、明らかに変な挙動をしていそうなことに気づきます。縦の長さが4分の1になるので、そこそこ大きな入力でないと影響が出なかったようです。

間違っていることはわかりましたが、正しい畳み込みが思い出せません。ゆきのんさんがローカルに落としておいた数人の競プロerのライブラリから探してみると言っていましたが、何変換か名前がわからないので見つからないようです。

しばらく唸っていると、何となく「j⊃iなるjに対してdp[j]+=dp[i]」をO(N 2^N)で行うコードっぽいものを思い浮かべることができたので、書いてみます。ちなみにこれまでの実装では⊃ではなく⊂だったので、毎回bit反転します。

サンプルを試すと通り、また先ほどのコードから出力が変化していたので、提出しました。ACでした。コンテスト終了10分前です。このAC自体はかなり遅いのですが、Dまでがそこそこ速かったので、5完内の順位は結構上がりました。

そのあとはF問題の先ほどのコードを少し変えて提出してみましたが、相変わらずWAでした。終了直前に、そもそも途中でセグフォして答えが出力できていないことに気づきましたが、提出はできませんでした。

コンテスト後

セグフォに気づかなかったショックでまともに受け答えができなかったのですが、気づいたら同じ部屋のチームはすでに帰宅していました。この演習室ももう閉めるということで出ます。

チームで打ち上げをしました。

帰宅して、上がっていたFのACコードと出力を突き合せたところ、めちゃくちゃdiffが出たので気が楽になりました。

Dは2分割じゃなくて3分割すると、文字列の評価値を決め打ちして解けるようです。評価値決め打ちはちょっと考えたのですが、文字集合の分割を思いつく前でした。

振り返り

Fは完全にカスでした。一人で勝手に読み始めてふんわりした考察で実装して投げてWAを出すというのはチーム戦においては最悪です。まだ何が違っているのかも分かっていません。

毎年D問題もそんな感じで僕が一人で抱え込んでるんですが、そっちは戦略です。とりあえず僕が最初にDを解いておけばまともなペナルティで四完ができて、東北大学から出場しているなら国内予選を通過します。3並列である今年はまた違った戦略を取る余地もあったかもしれませんが、マシンが1台だと実力を鑑みてこれが最適です。必要なのは何が来てもDを通すという自信・自負・実力と、AからCを任せられるチームメイトです。

週記（2020/10/26-2020/11/01）

10/26(月)

先週の週記を投稿した後布団に入り、そのまま6時間ハーメルンを読んでいた。

魔法の世界のアリス - ハーメルン

かなり面白い。面白いんだけど、あからさまな謎を残したままエタっていて精神が持たない。ダリアの歌わない魔法のエタり方よりはマシだけど、つらい。

ハリポタの原作を読んだのは相当昔の話なので、もう全然覚えておらず、二次創作から補完してしまっている。前半の出来事はたいていそのまま描かれるが、後半になってからオリ主の介入だったり性格改変だったりで全然違う枝分かれをする。まあそれを求めるのが二次創作といえばそうなのだが。この作品はもう全然分霊箱が見つからなくてびっくりした。原作もこんなもんだっけ……？大抵の二次創作ではあっさり見つかってるので、原作もそんなものだったと錯覚していたが、よく考えたらハリーは7年生の時はずっと探しっぱなしだったかもしれない。少なくともこの作品ではそういう描かれ方をしていて、そういえばそうだったかもといった気持ちになっている。

別の作品を読み始める。

東方project × ONE PIECE ～狂気の吸血鬼と鮮血の記憶～ - ハーメルン

20話ほど読んだところで眠気に耐え切れなくなり、寝落ちしたらしい。閲覧履歴から時刻を復元したところ、午前11時だった。

起きたら午後9時だったらしい。10/26は（すでに日時の感覚を失っている）AtCoderをプレイしていないので、スマホからちまちま提出する。その後再度ハーメルンに戻る。なろうの更新を確認して読んだりしていると、日付が変わった。

atgolferを確認したら久しぶりにやられたという感じの最短コード更新があったので、載せる。

atcoder.jp

NとMが与えられる。M<=Nである。1以上N以下の数であって、Mでないものを1つ出力せよという問題。Mから1ずらすことを考えると、M%N+1という式が得られる。以前まではこれが最短だった。

普段は1を出力することにして、M==1の時だけ別の数を出力する、ということを考える。これはdcのRコマンドを用いると非常に簡潔に書くことができるようだ。スタックに1 Nと積んでおいて、MでRすると、M>1のときは一番下の1が先頭に来る。M==1の時だけ一番下まで遡らずNが先頭に来る。これで、先ほど述べた場合分けができている。

1?Rpだ。シンプル。僕が達成していたら文句なく美しいと褒めちぎっていたが、僕のコードではないため嫉妬で言葉が出ない。

10/27の13時でリクルートの冬アルバイトのエントリーシート締め切りだ。あと10時間しかないが、1文字も書いていない。

もし向こうが競プロerに興味があるなら、僕をエントリーシートで落とす理由はないと思う。自尊心。

「自分がこれまでしてきた取り組みのうち最も成果を挙げたもの」には何を書くか、ということは最初にエントリーシートを確認した時から考えていた。結局TLのある人のツイートを受けてコードゴルフについてを書くことにする。実際に書くのは明日に回す。

昨日読み始めたハーメルンを読み終えた。いわゆる超古代スタートで、そこそこイベントを書きながら50話弱かけてようやく原作キャラが出現し始めたところでエタっている。儚い。

ほかのハーメルンをいくつか漁りつつ、5時半くらいに寝落ちしたようだ。Webページの閲覧履歴から復元。

10/27(火)

午前8時、起きる。全然寝てない。が、エントリーシートの締め切りが迫っているため、起きる。書き始める。

似たようなページに入力したときの経験から、エントリーシートのページを開いてから送信するまでに時間制限があることが予想されるため、いったん長文回答の設問を抜き出してメモ帳で推敲する。

ところでデータを扱う知識・経験の有無を問われていたが、一切ないことに気づいた。この辺りは僕の自己肯定感に結構効いてきて、いやな気持になった。開き直って全部なしと書いたら少し楽になった。

おおむねこんな感じのツイートをしていたところ、助言をもらった。

こう書かれるとコードゴルフってすごいなとなる。個人的な印象としてはかなり的確で、大体間違っていないと思う。

寝ても覚めてもコードゴルフやってるんだし、これくらい自分のことを褒めちぎってもいいかなという気持ちになった。かけた時間だけその技術に対する信頼が生まれる。根拠のある自信に思えて、心強い。

書きはじめた頃は結構微妙な気分になって出すかどうか迷っていたのだが、以前にも書いたように、こういうのは一度やってみないことには何も始まらないと思っており、このことを強く念じることで、文面を完成させることができた。

午前11時ごろ、リクルートの方からSMSが来て、期限間近であることをお知らせされた。入力の最中であると返信を送る。説明会に参加した人全員に送っているのだろうが、なんとなく気が楽になる。ちょろい人間である。

いくらか文字数をオーバーしてしまったが、なんとか削減し、提出した。すぐにコーディングテストがあると思っていたが、これは別のコースに応募する場合の話だった。僕が応募したコースは、面接に進んだ人のみがテストを受ける。

beetさんのなろうオススメまとめ、かなり参考になるんだけど、普段読んでるものから厳選してるんだろうなと感じたので、ブックマークが全部見たいとツイートした。学食に行って帰ってきたら、はてなブログに投稿されていた。

beet-aizu.hatenablog.com

僕もやる。

kotatsugame.hatenablog.com

JavaScriptを調べながら書いたのでかなり疲れた。布団に入ってゴロゴロしていたが、20時くらいに寝落ちしてしまった。

10/28(水)

深夜、起きる。また寝落ちしてしまったことに絶望しつつ、ハーメルンを読む。午前4時半くらいにまた寝落ちしてしまう。次に起きたのは午前9時のようだ。

スマホアプリのGmailのアイコンが新しいものに変わっていた。目新しくて面白い。目新しくなくなった場合どうなるかは知らない。ほかのアプリと並べたときの視認性が悪いというツイートはよく見る。

細切れで微妙な睡眠しかしていないため、布団から起き上がる気力がわかない。しかし競技プログラミングはしたいため、布団でノーパソを開いた。

AOJ-ICPCから「論理式圧縮機」と「リボンたたみ」を解いた。論理式圧縮機は解法っぽいものは一瞬で見えたが計算量がちょっとヤバそう。多分2^16*2^16くらいのステップ数があると思うのだが、実装してみたところ手元実行でも6secだったので提出した。

リボンたたみは、確か昨年の国内予選の直前に肩慣らしとして解こうとしてあきらめた問題だ。今見たら結構すんなり解けた。与えられた情報から素直に計算できるものを元に考察したところ、上手くいった。

まず、上から何番目にあるか？という情報から、i回目の折り畳みで印をつけた部分が持ち上げられるか否かがわかる。

折りたたむ前に印をつけた部分が左半分にあるか、右半分にあるか、というのは、その部分が持ち上げられるか否かに応じてLRを割り振ると決めることができる。最初にどこにあるかは入力で与えられているので、これを順に適用しながら場所を計算していくと、答えが得られる。

そろそろAOJ-ICPCの450点を埋めきろう。最後の1つ、「浮動小数点数」である。これは一昨年の国内予選で解けないまま今までずっと残っていたものだ。

他の人のツイートから結構ヒントは知っていて、覚えていた。それをもとに考えて、何となくわかってきたところで学食が閉まりかけたので、中断。

学食の味噌汁は最近非常にしょっぱい。人が来ないから水分が飛んでしまっているのかも。

生協で「扇物語」を見つけた。新刊なので買っておく。このシリーズは結構前の巻で読むのがストップしている。買い始めたころは中学生で、確か終物語が刊行されたくらいだったと思うが、そこから今まで一度も最新刊に追いついたことがない。

帰ってきて実装し、AC。これでAOJ-ICPCの450点以下はすべて埋まった。今解いてみたら割とあっさり解けたなと感じるが、まっさらな状態から考察を始めたわけではないので何とも言えない。

布団に転がってハーメルンを読んだりラノベを読んだりしていたら、ついにICPC国内予選の誓約書の情報が公式ページに書かれた。締め切りは……11/02！？あと6日しかない。助けてくれ。

誓約書はメールで来るようだが、僕のところには来ていない。TLを見ているとコーチに来ているらしいので、急いでSlackで連絡を取った。すぐに返信があって、誓約書となるGoogle formのリンクを共有してもらう。サークルのSlackに貼り付けて参加メンバーにメンションを飛ばした。

ICPC予選出場に関する誓約書をGoogle formで提出してください。締め切りは11/2(月)です。期限がかなり短いので、このメッセージを見たらすぐに提出してください。終わったらACのリアクションをしてください。

結構強めの言葉でお願いしたところ、すぐにいくつかリアクションがあった。うれしい。この日記を書いている今、すでに残り4名のところまで来ている。

AOJ-ICPCの500点問題をさらに1問解いて、120000ポイントを達成した。

10/29(木)

7時間半睡眠。完璧。王の睡眠。学校で学ぶちょうどよい睡眠時間は大体これくらいの気がするが、本当は足りないと思う。ちゃんと毎日9時間寝たい。別に予定があるとかではなくて、うっかり寝床でスマホを触ってしまい二度寝できなくなるのが原因。

朝、1冊本を読んだ。創元推理文庫「ヴァン・ショーをあなたに」。

途中で本を1冊読んだ。創元推理文庫「タルト・タタンの夢」で流し読み気味だが面白かった。シリーズもので続編があるらしく、把握していなかったので、とりあえず古本サイトで探してお気に入りに登録しておく。今度古本を注文する機会があれば一緒に買うだろう。

週記（2020/07/20-2020/07/26） - kotatsugameの日記

実は8/20に新刊で買っている。シリーズの3巻がちょうど文庫になったらしく、一緒に1・2巻も平積みされていたので、うっかり手に取って購入した。そのあと古本屋に行ったら2巻が安く売られていたのでちょっと残念な気持ちになった。（ここで嫌な気持ちになるのは、本読みとして良くなさそう。）

相変わらず流し読み気味だったし、相変わらず面白かった。ただ即座に3巻を読むかというと微妙。

12時くらいに学食に行く。普段より1時間早く、ちょうどお昼休みの時間帯だからか、びっくりするくらい人がたくさんいた。

多分AOJ-ICPCを埋めつつ布団に倒れこんでいたりしたと思う。途中でチラチラハーメルンを読んだりもした。特に何かを決めてずっとやっていたわけではないので、何とも書きにくい。

昨日Slackに投稿したICPCに関する誓約書は全員が回答したらしいので、そのことをコーチに報告した。1時間くらいして返信が帰ってきて、どうやらあるチームのうち1人が回答していないようだ。いや、回答していないのに投稿にACのリアクションをつけるのは意味不明だから、何か間違いがあったのだろうか。ともかく、チームの誰が間違っているかはわからないので、とりあえず3人にメンションを飛ばして確認をお願いしておく。

vector aとvector bのswapについて。a.swap(b)と書くとO(1)になることは知っているが、swap(a,b)と書いたときにどうかを断言できない。ライブラリでswap(a,b)と書いてある箇所があったので、念のためa.swap(b)に直しておく。

了解！

うっかり午後8時に寝落ちしてしまい、起きたら午後11時半だった。TLを眺めているとまたすぐ寝落ちしたらしく、次に目が覚めると3時半だった。本当はもう一回二度寝するつもりだったが、結局しなかったので、ここで日記の日付も変わったことにしておく。

10/30(金)

朝から本を読んでいく。まず「わたしの幸せな結婚 四」。表紙イラストがいい。中身に関しては、かなり適当に読んでしまい、何も覚えていない。

次に「境界探偵モンストルム2」。昔イラストレーターの晩杯あきらさんが好きで、その人がイラストを担当したラノベを少し集めていたうちの1冊。シリーズ2巻だが、1巻はいつ読んだのかと読書記録を探ると、2018年3月だった。さすがに何も覚えていない。タイトルに探偵とあるが、ミステリ要素があるわけではない。足と人脈で情報を集めるタイプの探偵と言えばいいのか。

シリーズが続きそうな終わり方をしているが、シリーズ3巻は出ていない。そもそもこれを出版したノベルゼロというレーベル自体、1年半新刊が出ていない。ただまあシリーズ3巻が出るならその時間は十分にあったはずなので、やはり打ち切りだろう。

メールを確認したところ、急に12時半までのレポートが生えている。

週記（2020/10/12-2020/10/18） - kotatsugameの日記

これに関して、先週の金曜日は特に何も書かなかったが、2限の講義ではレポートが出なかった。今日はどうなるだろう、まだ出ていないが……と待ち構えていたのだが、どうやら今日は学祭の日で休講らしい。コロナウイルスで学祭も消えたので、虚無の日。別にコロナウイルスがなくても虚無の日だったと思う。

読んでいる最中、ついにHHKBが届いた。

とりあえず箱を開いて、机に放置して学食に行く。休講なので営業時間がちょっと短い。

帰ってきてキーボードを使おうとするが、どうにもデスクトップPCとペアリングができない。調べてみたところ、PCにBluetoothの部品がついていないらしい。そう……。

とりあえずはUSBケーブルで接続するが、本当は別の用途で使うはずのケーブルなので、キーボード用に何かを買いたい。具体的にはUSB接続のBluetoothアダプタを買いたい。

6月あたりにAtCoderの何かのコンテストで手に入れたAmazonギフト券がまるまる残っているので、これを使おう。よくわからないけど1000円ぽっちのアダプタを買うだけで送料が無料になったので、余計なものを買おうとせず即座にレジに進み、購入。

キーボードの使い心地を試すため、つい先ほど追加された先日の模擬国内予選の問題を解いてみる。まずCtrlとShiftの位置がこれまで使っていたものと逆になっており、かなり違和感がある。

プログラミングには関係ないが、半角／全角キーに相当するボタンが左下にあるのも結構つらい。キーを連打するときの感覚も微妙に違い（キーストロークが深くなった影響だろう）、cin>Aを連発してしまった。

まあせっかくお高いキーボードを手に入れたので、慣れるまで頑張ってみようと思う。寿司打をやってみたが、特に速くも遅くもならなかった。

もう1冊本を読んだ。「ブックマートの金狼」。これも前のものと同じノベルゼロというレーベルから出版された本で、しかもレーベルが創刊したときの1冊。だから何だという話だが。

著者は杉井光。この方の作品は「神様のメモ帳」と「生徒会探偵キリカ」を読んだことがあり、両方とても好き。この本も設定が好きなので買った。

「神様のメモ帳」も似た理由で好き。ほかには「池袋ウエストゲートパーク」というシリーズがある。そういえばIWGPはアニメ化している最中らしい。

今は「ブックマートの金狼」の話をしよう。確認してびっくりしたのだが、この本は表紙以外イラストがない。あとがきで「締め切りが過ぎてからプロットを作った」と書いてあったので、多分イラストを描いている時間がなかったのだろう。ほんとにラノベレーベルか？

ノベルゼロで画像検索するとわかるが、このレーベルは高めの年齢層をターゲットにしていたらしく、ラノベレーベルとしては異色の装丁がされていた。カバーは単色でかなり紙っぽく、大きめの帯が付属していて、表紙イラストはそこに印刷された。全部過去形。今はもうない。

読み終わってしばらくツイッターをしていたら、うっかり寝落ちして7時間も眠っていた。yukicoderに参加できなかった。

起きると、ICPCの誓約書を確認してもらうようメンションを飛ばしていた3人から確認したとの返答があった。僕もコーチからチームIDを教えてもらっていたのでチェックしたが、まだ直っていないようだ。考えられる原因としては、誰かがアカウント作成に使用したのと別のメールアドレスを書いているとかか。すでに深夜なので、この時間に返信するわけにはいかない。朝を待とう。

AOJ-ICPCを進める。550点を埋めていて、英語問題を優先的に解いている。英語問題は日本語問題より読解が面倒なので、先に手を付けておこうという魂胆だ。

サークルのメールをチェックすると、入部希望の方が2名いた。入部するのはいつでも大歓迎なのだが、最大のイベントであるICPCはちょうど参加登録を締め切ってしまったので、何ともタイミングが悪い。

朝を待って、誓約書に関することと入部のメール2件に返信した。

10/31(土)

昨日（というか今日の朝方）に布団に入ってから、ハーメルンを1作読んだ。

魔法省大臣は人使いが荒い - ハーメルン

そんなことをしていたら昼ぐらいになってしまう。ICPCの誓約書は無事に全員が提出したことを確認できた。夕方に荷物が来る予定があるので、その時間に起きている必要がある。急いで寝ようとして、あんまり眠れずにTLを眺めていたら、ICPC国内予選のルールが大幅に変更されたらしく祭りになっていた。コピペ解禁！！！

かなり衝撃的。まあライブラリペタリすると解けてしまう、いわゆるやるだけ問題なんて出ないだろうし、ルール変更の前に問題は決定しているだろうから、問題の難易度的にはあんまり変わらないかな。

普段使いしているマクロをそのまま使用可能になったのも大きいだろう。それで大きく速度が変わるとは思っていないが。

午後1時に寝た。午後4時に目覚ましで起きる。午後4時から6時の間に荷物が到着する予定なので、うっすら意識を保っておきたい、と考えていたらすぐに来た。無事受け取れたので、安心して眠ることができる。ARCがあるので、それまで4時間くらいか？細切れの睡眠になってしまって辛い。

午後7時半に起きた。頑張って眠気を覚ます。部屋がとんでもなく寒い。今冬初めてエアコンを入れる。食事を摂る。コンテスト前にシャワーを浴びるか迷ったが、何となく止めておいた。別にジンクスとかはない。

ARC107が始まって、終わった。4完。Eの解説を読んだら、実験をしましょうと書いてあって、本当に絶望した。最近実験していない。

レートは17下がって2666→2649。明暗を分けたE問題の解法が実験エスパーだったので、精神がひどく傷ついた。放心状態で1時間くらい椅子に座っていた。

1と2をまとめて考えるとNANDになるので、その方向で頑張っていた。丁寧に観察した結果、おおむね0と1 or 2は交互に現れるが、たまに1 or 2が2連続する箇所があって、右下にずれていくことまでわかっていた。何のことはない、斜めに同じ数が出現していただけなのだ。

おおむね交互という点から、だいたい半分が0でもう半分が1となって、2は先ほど述べた1 or 2が2連続する箇所にしか現れないので、その分を引いておく、というような解法を投げていたが、全然通らなかった。冷静になるとそれはそうで、0と1は全然半々ではない。各行にどれだけ2が現れるかカウントして、あとは0と1のどちらが先に出現するかなど考えればできないこともなさそうだが、そこまで深く考える時間はなかった。

月曜日の講義のレポートを書いた。前回提出した課題からしばらく新しいものが出ておらず放置していたが、いつの間にかかなり進んでいてびっくりした。再履じゃなかったら死んでいた。

できるだけミスしないように打ってみたら、初めて20000円を超えた。

ARCの問題を少しコードゴルフしていたら朝になってしまった。日曜日はチーム練をしたいのだが、まだ何も決まっていない。とりあえず練習できる時間に起床しなければ話にならない。

11/01(日)

昨日は布団に入ってからハーメルンをしっかり読んでしまって、寝たのは11時だった。日曜日の午後にチーム練をする予定だったが、何も決めずに寝た。

午後2時くらいに執念で起きる。チームメイトは僕がとんでもない時間に就寝しているのを見てゲームセンターに行っていたし、僕自身意識を保つのがつらいので、練習の時間を（ABCにかぶらないように）できるだけ後ろにずらすことにする。具体的には、午後5時から3時間ということにして、それまであと3時間眠る。

午後4時45分、起きる。30分の目覚ましでいったん意識を取り戻したが、二度寝しそうになったので、慌てて15分単位の目覚ましを再度かけなおした。

食事をしつつ練習内容を決める。今日は2017年の模擬国内のセットを解く。D以降を解いていなかったので、ちょうどよい。

ABCDFの5完だった。E問題は嫌だったので、手を付けていない。

僕はまずDを読んだ。よくわからないが、たぶん単調性があるので二分探索をする。Xがある値以下のとき条件を満たす、とするとWAだった。実際にはX=s_1がありうる最小値で、これを下回ると敵が倒せなくて行動不能になるが、この部分は単調性から外れてしまう。二分探索の下限を修正してAC。

Cが難航しているようなので、先に僕もそれを読む。できるだけ速く4完を確保するための行動。特に問題なく通る。画面共有してコーディングを眺めていたのだけど、そこまではせずとも解法を伝えた段階で次の問題にとりかかってよかったかもしれない。

Eは嫌なのでFを読む。DAGをパスに分解して、最大の重みを調べる。チームメイト2人も合流して一緒に考える。ゆきのんさんがフローと言ったので、その方針で考える。ちょっと迷走したが、頂点を倍加して流量1、コストを-体積とする方針で考えることにする。

とりあえずそんな感じで実装する。最小費用流のコストに負も許すためには、内部のダイクストラを最初の一回だけベルマンフォードなどの負辺を許すアルゴリズムにすればよい。修正のしやすさを考えると、priority_queueをqueueに書き換えればよさそう。僕はこれがSPFAだと思っていたが、実はキューに2回要素を入れないなどの高速化もするらしい。

まだうまくいかない。答えが小さくなっている。答えを小さくするには、倍加した頂点を通る必要があるが、流量はちゃんと1に設定しているので、どこかで通ってはいけないのに通ってしまっている。冷静になって考えると、パスの始点でありながらパスの中継点にもなってしまう可能性があるようだ。中継点になるためには倍加した頂点を通る必要があるので、こちらは必ず1回以下だが、パスの始点になるのには特に制限を設けていなかった。修正する。

計算量もってくれよ！頂点3倍界王拳だっ！！！

さっき倍加した頂点からさらにもう一つ伸ばして、そこの流量を1にする。パスの始点となるときも中継点となるときもそこを通ることになるため、これでどちらか1方しか選べなくなる。

あとはここにいくらかフローを流して最小のコストを求める。流す流量は1からNなので、流量を変えつつ毎回グラフを作り直して流しまくればよい。AC。

午後8時になったのでチーム練を終了する。Fにみんなで取り組んでACできたのはよかった。Eの幾何は……ナオキです

こどふぉが始まっている。ABCと被っているので、そちらを優先するため元から出る気はない。

10/30に注文したBluetoothアダプタが届いた。ケーブルが消えてかなりうれしい。ただ、パソコンをスリープから復帰させたときはキーボードの電源ボタンを押さないとキー入力ができないので、ちょっと不便に感じる。これまで使っていたキーボードは、キー操作をすると自動で電源が入っていた。持ち運びとか考えると、それはあまり嬉しくないのかな。

キーボードのキー配列を操作するスイッチのうち、SW2だけONにした。これで左FnキーがCtrlキーになり、Ctrlキーが英数キーになる。

まずCtrlとShiftの位置がこれまで使っていたものと逆になっており、かなり違和感がある。 プログラミングには関係ないが、半角／全角キーに相当するボタンが左下にあるのも結構つらい。

10/30にこのようなことを書いていたが、両方解決された。半角／全角キーの代わりに英数キーを使っている。

ただ、今度はFnキーが右下にしかなくなったのがちょっと不便に感じられてきた。DelとかEndとか、あとF5とかはかなり使用頻度の高いキーなので、簡単に押せるようにしておきたい。まあこの辺りはスイッチで解決しようとせずにキー配列を変更するソフトウェアを使うべきだろう。そもそもFnキーとのコンビネーション自体全然慣れていないので、しばらく様子を見たい。

3000円コースと5000円コースもやってみたが、一発で倍のスコアが出た。うれしい。

ABC181が始まった。3位だった。

C問題は、最初N<=1000と勘違いしていて、3乗が微妙に間に合わないと思ったので傾きをsetに入れて重複を調べることにした。O(N^2 log N)。書き始めたところでN<=100に気づいてちょっと残念な気分になったが、3点が同一直線状にあることをチェックする数式がパッと思い浮かばなかったので、そのまま実装する。傾きをdoubleで管理する必要はなくて、pair<int,int>を適切に正規化すればよい。gcdで割って、xを正にして、x==0のときはyを正にする。最近のABCで似たようなことをやったな、その時はもうちょっと複雑だったような……と思っていたが、それは90度回転も許していたから。

F問題は、直感的に「釘と直線をグラフの頂点として、ユークリッド距離をコストにして辺を貼り、パスのコストを「通る辺のコストの最大値」としたときに直線から直線への最短距離÷2」が答えだと感じたので、それをダイクストラで実装したら通った。（辺の数がO(N^2)なので、毎回全点に対して更新することにするとpriority_queueが必要なくなってlogが落ちるらしい。）

この値より大きな半径だと左から右へ抜けられないのはわかるが、この値以下であれば抜けられることを示せない。サンプルが合ったので提出しただけ。解説を読んでも右手法がどこで使えるのかわからず困惑していたが、kyopro_friendsさんのツイートで納得できた。

これすごい。似たような問題がいくつかあるらしい。

コードゴルフをする。A問題はそもそも最初の提出が最短。B問題はRubyやRakuでrangeの総和がO(1)になることを利用すると短いかと思ったが、dcで普通に計算したほうが短かった。

C問題は、combination(3)するよりも、1点固定して残りの頂点と結んだ直線の傾きに重複があるか調べたほうが短かった。点(a,b)を固定して、(x,y)に対して(y-b)/(x-a)を列挙する。x==aのときは代わりにy!=bを値とすればよい。(a,b)==(x,y)のとき、同じ頂点を2回カウントしていることになるので除外する必要があるが、true/falseで分けることで達成できる。

最初は三項演算子を使っていたが、(y-b)/(x-a)rescue y!=bのほうが短くなった。ゼロ除算の例外をキャッチしている。コードゴルフにおいて初めてrescueを使った気がする。

AOJ-ICPCを埋めようとしたが、眠すぎて動けない。椅子に突き刺さって寝てしまう。意識を取り戻してとりあえず週記を書き上げようとしたが、できず、布団に倒れこんでまた眠ってしまった。

なろうのブックマーク一覧

追記：2021/06/16

beet_aizuさんのブログが非公開になってしまい、スクリプトが行方不明に……。

冷静になると、僕はブックマークを公開しているので、そちらへのリンクを貼ればよかったですね。

小説家になろう

https://mypage.syosetu.com/mypagefavnovelmain/list/userid/866106/

ノクターンノベルズ等（18禁）

https://xmypage.syosetu.com/mypagefavnovelmain18/list/xid/470719/?nowcategory=1

カクヨム

フォローしている小説（こたつがめ） - カクヨム

ハーメルン

こたつがめのお気に入り小説一覧

これは何

beet-aizu.hatenablog.com

ハーメルンはこんな感じでできました。

let str=$("h3").toArray().map(function(x){
    let title=x.getElementsByTagName('a')[0].outerHTML;
    let auther=x.textContent.match(/（作者：(.*)）$/)[1];
    return title+" （"+auther+"）\n";
}).join('\n');
copy(str);

カクヨムはまごころを込めて手打ちしました。

ほんへ

小説を読もう！（小説家になろう）

戦え、崩陣拳！ （魔人ボルボックス）

陰の実力者になりたくて！【web版】 （逢沢大介）

逆行転生したおじさん、性別も逆転したけどバーチャルYouTuberの親分をめざす！ （ブーブママ）

薬屋のひとりごと （日向夏）

異世界国家アルキマイラ　―最弱の王と無双の軍勢― （蒼乃暁）

異世界シヴィライゼーション ～長命種だからデキる未来にきらめく文明改革～ （さきばめ）

現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変 （二日市とふろう (旧名:北部九州在住)）

【書籍発売中】氷の令嬢の溶かし方　～クールで素っ気ないお隣さんがデレるとめちゃくちゃ可愛い件～ （高峰 翔）

次元の裂け目に落ちた転移の先で （四つ目）

本好きの下剋上　～司書になるためには手段を選んでいられません～ （香月　美夜）

最強カップルのイチャイチャＶＲＭＭＯライフ （紙城境介）

打撃系鬼っ娘が征く配信道！ （箱入蛇猫）

平凡な俺と非凡な彼ら　 （灰原　悠）

天才最弱魔物使いは帰還したい　～最強の従者と引き離されて、見知らぬ地に飛ばされました～ （槻影）

大魔王様の街づくり～魔法と科学と魔物が創る理想の街～ （月夜　涙（るい））

嘆きの亡霊は引退したい　〜最弱ハンターは英雄の夢を見る〜【Web版】 （槻影）

俺は星間国家の悪徳領主！ （三嶋　与夢）

俺が美少女Vtuberとして高みを目指す理由 （２５５）

世界最高の暗殺者、異世界貴族に転生する （月夜　涙（るい））

世界で一番『可愛い』雨宮さん、二番目は俺。 （編乃肌）

ホラー女優が天才子役に転生しました　～今度こそハリウッドを目指します！～ （鉄箱）

ティアムーン帝国物語　～断頭台から始まる、姫の転生逆転ストーリー～ （餅月望）

ちっちゃ可愛い竜だから！　～ルート・ミレニアム～ （佐野ケンジ）

だから俺は〇〇なんかじゃない！～高嶺の花をナンパから助けたら正体がばれました～ （NaHCO3）

ここではありふれた物語 （越智 翔）

お隣の天使様にいつの間にか駄目人間にされていた件 （佐伯さん）

クラスで陰キャの俺が実は大人気バンドのボーカルな件 （夜桜ユノ）

Recordless future （宮下龍美）

Magica Technica　～剣鬼羅刹のVRMMO戦刀録～ （Ａｌｌｅｎ）

21世紀TS少女による未来世紀VRゲーム実況配信！ （Leni）

魔王様の街づくり！～最強のダンジョンは近代都市～ （月夜　涙（るい））

転移先、２０００００年前。　帰還先、復讐。 （佐野ケンジ）

素人おっさん、転生サッカーライフを満喫する(書籍化作) （ハーーナ殿下@コミック戦鬼1巻《祝重版》）

目指せ樹高634m！　〜杉に転生した俺は歴史を眺めて育つ〜 （石化）

異世界クイズ王　～妖精世界と七王の宴～ （ＭＵＭＵ）

玉葱とクラリオン （水月一人）

無職転生　- 異世界行ったら本気だす - （理不尽な孫の手）

滅竜山くんの一生　～46億歳、全ての生命と魔の祖～ （黒留ハガネ）

死神を食べた少女 （七沢またり）

杜人記－ゆるゆる土着神－ （オーヘム）

村人ですが何か？（ウェブ版） （白石新）

怠惰なドラゴンは働き者 （不健康優良児）

堕落の王【Web版】 （槻影）

地味な剣聖はそれでも最強です （明石六郎）

善人おっさん、生まれ変わったらＳＳＳランク人生が確定した （三木なずな）

二度目の人生を異世界で （まいん）

予言の経済学　～巫女姫と転生商人の異世界災害対策～ （のらふくろう）

不倶戴天の許嫁：ファンタジー世界から千年後、宿敵だったオレたちは許嫁に転生した （紙城境介）

メリゼル魔法学園の日常 （低系）

双翼の舞う世界　～魔法界からの帰還者～ （低系）

ノーライフ・ライフ （黒留ハガネ）

チート魔術で運命をねじ伏せる （月夜　涙（るい））

アビス・コーリング〜元廃課金ゲーマーが最低最悪のソシャゲ異世界に召喚されたら〜【Web版】 （槻影）

アイリッシュ・スナイパー （鰤／牙）

「「神と呼ばれ、魔王と呼ばれても」」 （しまもん（なろう版））

VRMMOをカネの力で無双する　サブアカウント （鰤／牙）

VRMMOをカネの力で無双する （鰤／牙）

VRMMOで攻略とスローライフの両方を手に入れる方法　エキストラ （陽乃優一）

VRMMOで攻略とスローライフの両方を手に入れる方法 （陽乃優一）

HP9999999999の最強なる覇王様 （ダイヤモンド）

異世界チート魔術師（マジシャン） （内田健）

異世界はスマートフォンとともに。 （冬原パトラ）

最強魔法師の隠遁計画 （イズシロ）

【web版】奴隷商人しか選択肢がないですよ？　～ハーレム？　なにそれおいしいの？～ （カラユミ）

デスマーチからはじまる異世界狂想曲（ web版 ） （愛七ひろ）

黒の星眷使い ～世界最強の魔法使いの弟子～ （左リュウ）

剣士を目指して入学したのに魔法適性9999なんですけど！？ （年中麦茶太郎@ZZT231）

私、能力は平均値でって言ったよね！ （FUNA）

ラスボスの向こう側～最強の裏ボス＝邪神に転生したけど、１０００年誰も来ないから学園に通うことにした～ （天音のわる）

Tamer's Mythology （槻影）

神居村へ、初めての夏を （ヒダカ　カケル）

カクヨム

誰にでもできる影から助ける魔王討伐 （槻影）

公女殿下の家庭教師 （七野りく）

始まりの魔法使い （石之宮カント）

モブの方の桶川君。～じつはスゴいんです～ （芹澤しゅいろ）

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

美少女モデルのAliceは今日も片想い （芹澤しゅいろ）

【番外編】美少女モデルのAliceは今日も片想い （芹澤しゅいろ）

ハーメルン

東方遺骸王 （ジェームズ・リッチマン）

アイドルの世界に転生したようです。 （朝霞リョウマ）

Game of Vampire （のみみず）

元おっさんの幼馴染育成計画 （みずがめ）

美少女になってちやほやされて人生イージーモードで生きたい！ （煉瓦）

転生して電子生命体になったのでヴァーチャル配信者になります （田舎犬派）

ダンブルドアは自由に生きられるか （藤猫）

霊晶石物語 （蟹アンテナ）

バカと天使とドロップアウト （フルゥチヱ）

異世界で 上前はねて 生きていく （詠み人知らず） （岸若まみず）

指し貫け誰よりも速く （samusara）

腕振って、飛車振って、 （うさみん1121）

まほうつかいのおしごと！ （未銘）

このすば*Elona （hasebe）

この〇〇のない世界で （ぱちぱち）

うちの脳内コンピューターが俺を勝たせようとしてくる （インスタント脳味噌汁大好き）

やはり俺の大学生活は間違っている。 （おめがじょん）

ブラック企業社員がアイドルになりました （kuzunoha）

死に目に魂貰いに来るタイプのロリババア （Pool Suibom / 至高存在）

気付いたら赤木しげるの娘だったんですが、 （空兎81）

青空よりアイドルへ （桐型枠）

我輩はレッドである。 （黒雛）

ダリアの歌わない魔法 （あんぬ）

東方project　×　ONE PIECE　～狂気の吸血鬼と鮮血の記憶～ （すずひら）

【完結】ハーマイオニーと天才の魔法式 （藍多）

比企谷八幡　「・・・もう一度会いたかった」 （TOAST）

ポケモン世界に来て適当に(ry （kuro）

紅く偉大な私が世界 （へっくすん165e83）

私の世界は硬く冷たい （へっくすん165e83）

魔法の世界のアリス （マジッＱ）

元RTA実況者がSAOをプレイしたら （Yuupon）

東方先代録 （パイマン）

ハリー・ポッターと野望の少女 （ウルトラ長男）

週記（2020/10/19-2020/10/25）

10/19(月)

日曜日の分までの週記を投稿した後布団に入り、ずっとごろごろしていた結果、寝たのが17時過ぎになった。日付が変わる前に起きてハーメルンを読んだ。読み終わってから起床報告をした。

私の世界は硬く冷たい - ハーメルン

紅魔館組とハリー・ポッターのクロスオーバー作品。作品間のキャラクターの関係性だけ見ればかなり「Game of Vampire」を彷彿とさせる。実はこれは逆で、「Game of Vampire」の連載がスタートしたのは上の作品が完結してから2年後のこと。

ただ、登場人物たちのキャラクターが全然違っている。こちらは何というか、人を人とも思わない認識が紅魔館組に通底している。この点で微妙に人を選びそうな気もする。

50話くらいで完結しているが、1話1話がそこそこ長いので、文字数的には771,065文字と結構ある。こんなのを集中して読んでいたので生活リズムが大崩壊している。

日付が変わってから、起きる。しばらくAtCoderをしていた。そろそろICPCのアカウントに情報を登録するのを完了させたい。国内予選への参加登録手順を今一度確認していたら、誓約書について何も発表がなされていないことに気づく。一体どうなるんだろう。

今日はラノベを読もう。一番最近買ってきたものは机の上に積みっぱなしになっている。その前に買ってきたやつも、またその前に買ってきたやつも、半分も手を付けておらず本棚に押し込まれている。

まず「午後九時、ベランダ越しの女神先輩は僕だけのもの」を手に取る。イラストを担当するみわべさくらさんがかなり好き。「隣のキミであたまがいっぱい。」も買おうとした記憶があるが、なんでか買っていない。確かあらすじを確認してあまり心惹かれなかったのだと思う。今回のこれは設定もよさそうなので購入を決定。

イラストページをなめるように読んでいたら、誤植を発見してげんなりしてしまう。キャラクターの名前のローマ字表記が違っていた。フォントの問題で「き」が「さ」に見えたのかな？イラストページくらいしっかりしてくれよ。

内容は……よくわからない。良いか悪いかでいえば、良い。ヒロインの描写がなんとなく淫靡でドキドキした。

この作者の著作は他にも読んだ記録が残っている。「手のひらの恋と世界の王の娘たち」というシリーズで、2巻打ち切り。比較して何か言おうとしたけど、内容を何も覚えていなかった。

次に「氷の令嬢の溶かし方」を読む。なろう発。ふぁぼんさんが天才クールスレンダー美少女ものの1つとして挙げていたので、なろうのほうで読んだ。そこそこ好きなので購入を決定した。

かなり良かった。なろうのほうは最近更新が滞りがちなので印象が薄れていたが、書籍版という形で読み返すと改めて面白いことを確認できた。

設定的には隣人・同級生の美少女・半同棲ということで「お隣の天使様にいつの間にか駄目人間にされていた件」との共通点がかなりあるが、それをどう料理するかというのは筆者によってさまざまなので、どれだけ読んでも面白い。

どれだけ読んでも、と言ったのには理由があって、この設定の作品は書籍化に限ってもかなり多いのだ。隣人まで入れると結構絞られるが、それ以外の設定が共通しているシリーズなら実際僕も4つ5つくらい読んだ記憶がある。

なんにせよ、1巻はまだ馴れ初めといった感じなので、続刊が出るよう祈っている。そういえば作者が2000年生まれらしくかなりびっくりした。僕の1個下ということになる。

サークルメンバー全員がICPCアカウントへの情報登録を完了したそうなので、チェックをお願いするメールをコーチに出す。正午、就寝。

10/20(火)

午後9時くらいに目を覚ましてメールを確認すると、HHKB プログラミングコンテスト 2020の受賞メールが届いていた。学生3位ということで、HHKBのキーボードがもらえる。やったぜ。

ちょっと前までは無刻印に無邪気な憧れを抱いていたが、冷静になるとまだそのレベルではないだろう。さらにUS配列ということで、普段使いはしなさそう。という考えのもと、素直に日本語配列のキーボードで希望を出しておく。US配列のキーボードはすでに1つ、昨年のICPC横浜の企業賞でもらっている。

そういうのを決めつつうだうだしていたら、こどふぉdiv.3が始まっていたので、慌てて参加する。40分で全完。

全部自明だった。まあdiv.3に出場するのはただの暇つぶしなので、学びが何も得られなくとも問題はない。

E問題は問題文を丁寧に解釈すると数珠順列のはずなのにサンプルは円順列ということでひと悶着あったらしいが、サンプルを合わせに行ったので特に引っかかってはいない。

布団に転がって今日もラノベを読む。「家族なら、いっしょに住んでも問題ないよね？」2巻。設定はかなり好きだったが、残念ながらこれが最終巻らしい。

読んでみると、なんというか文章に難がある。かなり読みづらかった。地の文の途中に台詞がめちゃくちゃ挟まっている。でもこれを毎回改行していたら今度はページ数がかさむだけになるので、難しいところっぽい。

読み終わって、別のラノベを手に取りながらゴロゴロしていたら、午前6時のツイートを最後に寝落ちした。生活リズム戻ってきてないか？

10/21(水)

午前11時くらいに起きてしまう。生活リズム矯正の達人。

また一人「玉葱とクラリオン」に生活を破壊されている人を観測した。いいぞ。

昨日風呂に入っていないが、今日起き抜けから頭がかゆくてかゆくて仕方がない。急いでシャワーを浴びる。

布団でラノベを読んでいたが、どうにもおなかが空いて仕方がないので、学食に行く。起きた時に空を見たら雲一つない青空っぽくていい気分だったのに、今見るとかなり曇っていて残念。

醤油ラーメンを食べて、ブラックサンダーとクーリッシュのマスカット味を買って帰ってくる。

朝読んでいたラノベの続きを読もうとするが、どうにも興が乗らないので、景気づけに別のラノベを読む。

何を読んだのかは書かないので、気になる人は読書記録から辿ってほしい。正直好きではない。シリーズを買い始めたら続刊は必ず買うことにしているので、それでかろうじて買っている。

物理的に薄っぺらいので30分くらいで読了。感想もない。

最近またTLでマルコフ連鎖のツイートを見かけるようになった。前回流行ったときは手を出さなかったが、今回はちょっとやってみようかという気分になる。

思ったより連鎖してくれないんだな。結構な割合でツイート1つがそのまま出てくる気がする。何度も生成して面白いと思ったものを投稿。

最後のは、明らかに『1ケースだけ落ちた京都人「えらい丁寧にテストケース作らはりますなあ」』＋『脱糞された京都人「ええ括約筋お持ちどすなあ」』。そうつながるのか。

おすすめのなろう小説まとめを更新する。「うちの脳内コンピューターが俺を勝たせようとしてくる」が公開状態に戻されたので、これを紹介しないのは嘘になる。改めて累計ランキングを見ると、現在1位の「このすば*Elona」とは本当に僅差である。しばらくしたら抜きそう。

月曜日に読んだ「氷の令嬢の溶かし方」のなろう版を含む4つを追加して更新ツイートをしたら、作者の方に捕捉された。恐れ多い。○○と設定が似ている、というコメントも読まれてしまった。最悪な部類の感想であると自覚はしている。

ところで、「うちの脳内コンピューターが俺を勝たせようとしてくる」で、こんな一文がある。

最後、6六桂と打ってアルファゼロの玉は何処へ逃げても金打ちで詰みと言う状況になる。

うちの脳内コンピューターが俺を勝たせようとしてくる - 一閃 - ハーメルン

これは詰みなのでは？と思っていたが、実際には必至というらしい。確かに、詰みであれば王手をしている必要がある。

ICPCアカウントの情報の登録について、コーチからメールの返信があった。まだ数名エラーが出たままの人がいたらしい。まあこんな複雑な手続きが1発で完了することなど想定していない。毎年エラーが出たままの人が数名発生するので、その修正分の時間的余裕は十分に確保して動いている。

顧問の先生に公欠届を発行してもらおうとしたら、なんと送ったPDFファイルを印刷して署名・押印の後再度スキャンして送り返してくださるそうだ。僕が先生の研究室なり講義室に出向く感染リスクが減らせてうれしい。決して家から出なくてよくなってうれしいわけではない。本当。

あと、紙の公欠届をサークルメンバーに渡すのにわざわざ予定を合わせる必要もなくなった。PDFファイルをSlackで渡して終わりである。最高やな。

FFTやNTTのin-placeで速い実装を学びたい。具体的には、ACLが何をやっているのか知りたい。競プロerが書いたブログ記事を少しあさるが、よくわからなかった。今日はもういいや、という気分になってしまう。

10/22(木)

午後1時に起きる。学食に行く。

帰ってきて、ICPC関連でコーチにメールを送る。昨日、ICPCアカウントへの情報追加が不十分な人にメンションを飛ばして済ませてもらったので、再確認をお願いする。もう1つ、公欠届の書類を作って、これもメールで顧問の先生に送った。

メールを2通も送るとヘトヘトになる。布団に倒れこんでハーメルンを読む。

ダンブルドアは自由に生きられるか - ハーメルン

コーチからメールが返ってきた。まだ1人不十分な人がいたらしい。それと、ICPCに参加する場所の件についてSlackのワークスペースを作ったので参加してほしいとのこと。

今年の特別ルールではチームメンバーが集まる必要性が薄いため、集会許可でちょっと大変で、研究室から全チームが出場するのは許可が下りないらしい。なるほど。

Slackのワークスペースでやり取りをする。投稿にはかなり気を遣うけど、メールを送信するよりは手軽。

サークルから出場するチームは全員集まって参加してほしいと思っていたが、これに関しては今まで全くアンケートなど取っておらず、一方的に押し付けていた。集まって参加してほしいことの理由の言語化にかなり苦労し、最終的には諦めてしまった。

僕は各チーム（特に今年初参加の人を含むチーム）ごとに集まるのは重要だと感じていて、それなら最初から場所を用意して全員で集まるべきだと考え、そのように周知していましたが、実際アンケートなどをとったわけではないです。

このような文面の投稿をした。あとは、現状学生が借りられる大学の施設はどれも1部屋1チームが限界だという話をした。

顧問の先生曰く、青葉山キャンパスにある研究室だけでなく川内北キャンパスの部屋が借りられるかもしれないとのこと。青葉山キャンパスは理学部や工学部があるところで、川内北キャンパスは1、2年生の間の全学教育が行われる場所だ。あと、研究室と同じ建物の別の部屋も借りられる可能性がある。

ということで、青葉山から出るか、川内から出るか、それともチームがバラバラに自宅から出るかアンケートを取った。

Slackのリアクションを押してもらう形式だが、碧黴さんがやっていたのをずっと真似している。多重回答を防ごうとしたら、アンケート専用のサービスを利用する必要がありそうなので、どうしようもない。この形式はSlackで完結しているし手軽でよい。と思っていたら、公式でもこの形式が説明されていた。

アンケートを作成する | Slack

医学部生を含むチームが自宅から参加することを選択した。医学部キャンパスはまた別のところにあったはずだから、そこから移動するのは大変なのだろう。このことは全く意識していなかった。来年もしサークルの運営に携わっていたら、気を付けておきたい。（初参加3人のチームなのでルール的にちょっと不安ではある。）

そもそも、僕自身ルールをしっかり把握しているわけではない。今年のICPCのルールはまだ仮のままで、開発環境の事前準備をどこまで許すか、という部分が難しそう。TLで話題になっている。

僕はVimを使っているので、.vimrcを消し飛ばしておけば少なくともルールに違反することはない。そもそも本質的には以下の4行しかないため、コンテスト中に書き直すのも簡単。

set autoindent
set smartindent
set tabstop=4
set shiftwidth=4

統合開発環境でプログラミングをしている人たちは、事前の準備がどこまで許されるのかに興味津々らしいが、まあ勝手にやっててくれといった気持ち。ただサークルの人にルールを説明する必要があるかもしれず、関係ないやと無視するわけにもいかない。

ICPCアカウントへの情報追加が、全員完了した。やっぱり時間的には余裕だったな。特に今年は登録期限が伸びている。

夜、AOJ-ICPCを進めていた。

10/23(金)

寝落ちしていて、起きたら7時くらいだった。直前のツイートから5時間しか経過しておらず、睡眠時間が足りていない。

しかし、ついうっかりスマホを触りだしてしまい、二度寝できなくなった。しょうがないので起きる。今日はゴミ収集の日なので、まとめて出す。前日の深夜にするつもりだったのだが。

かなり眠いので布団に入ってゴロゴロしていた。学食が閉まりかけたので、慌てて起きて向かう。

昨日とった参加場所に関するアンケートに回答が集まっていた。集計するのだが、本名→ハンドルネーム→チーム名と2段階の変換をかまさないとならず大変だった。特に本名とハンドルネームの対応は難しい。弊サークルの入部届にはハンドルネームを書く欄もあるため、今年や去年のものを見ることで何とか対応をとれた。

それと、昨日青葉山に研究室とは別の部屋が借りられるかもしれないという話があったが、ダメらしい。結局青葉山から参加するならば研究室に集まる必要があるので、研究室チームの方にも川内から参加できないか聞くことになった。

idでタイブレークされるようになったらしい。うれしい。

川内の部屋は、話し合いが行われて無事借りられることになったようだ。メールのやり取りだったらどれだけ時間がかかっていたかわからないが、Slackでやり取りしたので迅速に話がまとまったらしい。なんかこう、すごいな。仕事効率化ってこういうことですか？

AOJ-ICPCを進めようとしたが、うっかり布団にダイブしてしまう。耐え切れず意識を失い、目が覚めると日付が変わりかけていた。6時間も寝てしまい、SRMとyukicoderをすっぽかした。この時間に寝るのは、ヤバい。明日のARCに直撃している。

yukicoderは前回も出ていないので、両方解けるところまで解いておく。今日の分は全部ACできたが、問題のタグが見えている状態で解き始めるので、コンテスト中とは具合が違う。かといってわざわざ未ACの問題のタグを表示しない設定にするかというと、うーん。そこまで問題を大切にしてはいないかな。

夜、またAOJ-ICPCを進めていた。500点問題は残り12問。そのうち7問は1回読んで飛ばしている。どうしよう。

10/24(土)

金曜日の夜は37時に寝た。起きたら土曜日の20時だった。目覚ましを数回逃している。かなりギリギリの起床となってしまった。

生活リズムが崩れているので、せめてもARCの時間に眠くならないようにと、意図して寝る時間を遅めたのだが、遅めすぎた。

シャワーを浴びてご飯を食べるともう5分前だった。

遅めの4完、パフォーマンス2222で全てが崩壊した。海は枯れ、地は裂け、全ての生物が死滅した。

A問題は基本的な全探索。安全性を求めてRubyで実装した。

B問題は明らか。Union-Findを貼った。ACLを使うことも考えたが、メソッド名に自信がなかったため自前のライブラリを使用した。

C問題も明らか。と思ったらWAが出た。N>M-2が怪しい。N=1、M=0で落ちそうだ。ここまで考えて提出結果の詳細を確認すると、実際1ケースしか落ちていなかったため、修正してAC。本来はN=1、M=0のケースは8個くらい存在していたらしい。別にそれでもいいと思うが、本当にそんなことになってハマっていたらたぶん許さなかったと思う。結局次の問題でハマるんですが。

D問題はわからない。去年のICPCバンコク大会でSum[i^k,{i,1,N}]を0<=k<=75で求める問題が出たが、これがDPで解けることを知っていたので、その方針でしばらく考えていた。結局捨てた。

Lに対してRの累積和を使用して計算する方針で、O(NK^2)を書く。遅くて通らない。NTTを使用してO(NK log K)に改善したらもっと遅くなった。

この改善の過程で、A^i/i!のような式が見えていたので、それをもとに式を分離しようとすると、(全ペア-同じもの)/2というい　つ　も　の計算が見える。慌てて計算を進め、AC。1時間かかっている。

残り30分もない中、Eを開く。一切考察が進まず、フィーリングで適当なプログラムを組むと10ケース落ちる。実は探索範囲足りないんじゃないの？という感じでアタフタしている間に終わり。

シンプルに辛い。Fを見てもよくわからないが、TL曰く「次数列が決まると木を数え上げられる」とのこと。それは……覚えがある。

atcoder.jp

まあこれ見てもO(N^2 log N)から落ちないので、無理。

もう本当に絶望してこどふぉdiv.2に出る。5完。E問題は数列が与えられて、連続する部分列のMEX全部のMEX。こんなシンプルな問題設定で既出じゃないのか？かなりびっくりするな。

かなり苦労したが、何とか解けた。ある値xが連続部分列のMEXとなりうるかを調べたい。a_i==xなるiを取ってきたときに、そこから右にあって一番近い値bのインデックスをid_bとしよう。i+1から始まる連続部分列はxを含まないという条件のもとid_x-1まで伸ばすことができ、できるだけ伸ばしておいたほうがいいので、i+1からid_x-1までに1..x-1が全部出現するかを調べればよい。インデックスで言い換えるとforall b<x [id_b<id_x]を判定することになって、Range Max Queryで解ける。あとはa_i==xなるi全部と左端でこれを判定すればよい。

逆に、iについてa_iが連続部分列のMEXとなりうるかを判定できる。右にあって一番近い値のインデックスを計算するという要請から、iは降順に見ていけばよい。降順に見終わったら、左端での判定も同様に行う。

答えが1になる場合は上のコードだと1が「空列のMEX」と判定されてしまうので、別に処理する必要がある。

ハーメルンを読んだ。

【完結】ハーマイオニーと天才の魔法式 - ハーメルン

ハリポタの二次創作で思いっきりチートなの初めて読んだな。

明日の模擬国内予選に出場する場所がちょっと問題。川内ホールの屋内練習場とか会議室とか、借りれないこともなさそうだったけど、前日の午後3時までに申請する必要があった。部室が候補として挙げられている。本当は荷物の出し入れくらいしか許されていないのだが、ちょっとくらい……コンテストに出てもバレへんか。

10/25(日)

12時半に起きる。結構時間に余裕がある。slackのruby-jpを見ると、dsuのgroupsメソッドがバグっているらしい。コードを確認すると確かに間違っていたので、手早くpull requestを作成した。

バグの原因は、parent_or_size配列の要素が常に集合の根を差すという勘違いだ。これは、わかる。多分僕もやらかした・やらかしそうになったことがあったはず。

コンビニで朝ご飯を買いつつ、部室に向かう。途中の交差点は走るタイプのマラソン大会の影響で交通規制があって大変だった。

部室の鍵が開いていないので、地べたに座り込んでパンを貪る。

人が来たので準備をする。窓と扉を全開にして、Wi-Fiを設定する。この設定に手間取って少々遅れたが、ちゃんと3人そろってコンテスト開始。

コンテスト中の様子・結果については参加記を書いた。

kotatsugame.hatenablog.com

記事によって敬体と常体を使い分けている。基準は特にないが、週記は常体にしている。おどけて書いた部分以外は混ざっていないはずだ。ここをおろそかにした文章は全部カスだと思っているので、注意している。

帰ってきて布団に倒れこんだが、うっかりこどふぉに出た。

A問題は27分かかった。途中何度も止めて寝ようか考えたが、せっかく問題を見たのだし……と頑張って考え続けた。ソートして出現回数を数えつつ尺取りする。

B問題は7分。stackでシミュレーションする。直感的に、- xが来たら直前の+でxを並べていたことにしてもよい。直前の+の前にxより大きい手裏剣を買っていたらNG。

C問題は10分。a>bcなら攻撃するたびに回復まで含めても敵のHPは減るため、答えは-1。a<=bcのとき、1度攻撃して回復し切られると敵のHPは増えるか元のままになる。なので、最初に攻撃してからc秒経過するまでにケリをつける必要がある。また、攻撃のタイミングはできるだけ早めるべきである。

i回目の攻撃はできる限り急ぐとd(i-1)秒に行われる。d(i-1)<cよりi-1<=(c-1)/d。

i-1回目の攻撃を加えたあと、i回目の攻撃を加えるまでにHPはbd(i-1)回復する。よってi回目の攻撃で与えられるダメージはa-bd(i-1)としてよい。これが正でないなら攻撃する意味はないため、a-bd(i-1)>0よりi-1<=(a-1)/b/d。

逆に、i-1<=(c-1)/dかつi-1<=(a-1)/b/dである間は攻撃を加え続けたほうが良い。そのようなiの最大値をRとおくと、答えはSum[a-bd(i-1),{i,1,R}]==aR-bdR(R-1)/2。

D問題を考えている最中、何度も眠り込んで意識を飛ばしてしまう。順位表を見ても全然通されていないので、あきらめて上の参加記を書いていた。

ICPC模擬国内予選 2020 参加記

2020/10/25に開催された模擬国内予選にチームAobayama_dropoutで参加しました。メンバーは変わらず碧黴さん・ゆきのんさん・僕です。

今年はコロナの影響で特別ルールが設定されました。模擬国内予選も基本的に同様のルールに準拠することになります。最も大きな変更点としては、1人1台マシンを使用できることでしょうか。あとはモニタに関する制限がなくなりましたが、まあ正直なくてもいいかなという感じです。

Wi-Fiの設定に手間取り、コンテスト開始からちょっと遅れて問題文を読みます。碧黴さんとゆきのんさんがABCを担当している間に、僕はDを読みます。これはどうなんでしょう、3人がそれぞれABCを担当したほうが初動的にはいいのかもしれません。

D問題（途中C問題）

Dはかっこ列の問題です。これが全然わからない。とりあえず普通のかっこ列を目指して、それをもとに考えることにします。

その間にC問題を読んでいたゆきのんさんからヘルプが来たので、僕もC問題を読みます。スタートとゴールの位置関係が固定されていないなど嫌な気分になりますが、まあ実装するのは僕ではないので、とりあえず考察を投げます。

斜めの最短経路を移動していく際、移動できない区画というのは正方形なので、入ってから一度出たらもう二度と戻ってこないということが言えます。なので、どの正方形を通ったかという情報はいらず、各移動に際して新しく正方形に入った個数だけカウントすれば、それがその移動のコストになり、あとは最短経路問題を解けばよいです。移動のコストに関しては、各正方形について辺をまたいで入る移動に1加えればよいです。区間になるので、imos法でできます。

スタートとゴールの位置関係を固定するためには、盤面全体を適切にrotateすればよいです。

これだけ考えて、実装をぶん投げました。後から冷静になると境界の扱いとか盤面全体のrotate（これはflipにしたようです）とかいろいろ大変そうです。実際大変なことになっていましたが、僕は以降ノータッチでした。

Dは何とか光明が見えてきました。普通のかっこ列を目指したとき、余ったパーツは))))(((((のような形をしています。元の文字列をうまく分けて、))))と(((((に分かれるようにし、片方はかっこごと逆にします。分けたあと2つにまたがるようなペアは作らなくてもいいので、)が余る文字列をうまくマッチさせる最小個数の問題をそれぞれ解いて足せばよくなります。

)が余る文字列に対して解を計算します。連続する)を一気に処理することにします。まず(をあるだけマッチさせ、残った分は()にくっつけていきます。それでも処理しきれなかった分は(を新しく追加することでしかペアにできないので、答えに加算します。大体こんな感じのアルゴリズムでよさそうです。

ただし注意が必要です。____をマッチし切ったかっこ列とします。(____))は可能ですが()____)は不可能なので、()に)をくっつけようとしてもうまくいかないものがあります。具体的には、((()))____というものがあったときに、新しく)をくっつけられるのは2個までとなってしまいます。( [ {} ]] ____ ))です。( ( [ {}} ]] ___ )) ))になると4個くっつけられます。

このことを考えると、n重のかっこ(((...)))____ではfloor(n/2)*2個しか受け入れられないことがわかります。

こんな感じでstackをコネコネしてサンプルを試すと合います。テストケースを実行して提出するとAC。2回目も同様にACできました。50分くらい。

E問題

C問題がまだヤバそうですが、かまわずE問題に行きます。碧黴さんが問題を読んでいたので、概要を聞きます。条件が2つあってどちらかを満たせばよい、これは2-SATです。とりあえずその方向で考えます。

ここで頭がバグって、2-SATは2部マッチングを解けばよいと勘違いしてしまいます。辺を張ったときに増加道があるか見ればよい、と意気揚々と宣言して書きますが、正気に戻りました。

強連結成分分解ですね。辺u->vを張ったときに、xとnot xが同時に属するような強連結成分を検出できれば良いです。これは各頂点から到達可能な頂点集合G_uをbitsetで持っておき、G_u |= G_vで更新して、G_x cont (not x)とG_(not x) cont xを判定すればよいですね！

WAです。それはそうで、a->u->v->bみたいなパスを全然考えられていません。最高にアホ。

もうちょっと冷静になります。SCCというのは辺Gと逆辺RGを持って計算します。u->vを張ったとき、uを含むような強連結成分は、uからGを使ってたどり着ける頂点とuからRGを使ってたどり着けるような頂点の共通部分となります。ここにxとnot xが同時に含まれたら2-SATは充足不可能となります。

この判定はO(N)で、辺の追加はO(M^2)回あるので、全体でO(M^2 N)となります。MとNは最大2000ですが、手元実行なのでぶん回してAC。100分くらいのことでした。

冷静になると、そもそもすべての強連結成分を検出するSCCがO(N+M)でした。またしゃくとり法が適用できるので試す回数はO(M)になりますね。辺の追加と削除さえうまくすればO(M(N+M))になります。

そういえば、こうやってぶん回すとき、実行がどれくらい進んでいるのか気になりませんか？出力をファイルにリダイレクトしていると、そのファイルを覗き見するのにはちょっと気を使います。こんなときにteeコマンドを使うと、入力を標準出力とファイル書き込みに同時に出せるので便利でした。

F問題

C問題はWAを食らって大変なことになっていましたが、F問題を読みます。さいころを転がしています。勝ったな！

こういう実装やるだけ問題は、頑張って実装すれば頑張っただけ確実に成果が得られるので、大好きです。頑張っていきます。

まずサイコロ構造体を実装します。面があって、向きがあるので、6つの面にそれぞれ番号とどこを下にするかを割り振り、矢印の方向4つにも番号を割り振り、それぞれの面の矢印がどこを向いているかを持てば必要十分です。

次に読み取りを実装しようとしましたが、冷静になると先に回転を実装したほうが良いことに気づきます。

回転を実装します。まず縦と横で1方向ずつ作って、逆に回す代わりに順方向に3回回すことにします。回転するたびに6面それぞれの矢印が互いに移り変わったり向きを変えたりして大変です。こういうところでバグを埋め込むと後から再チェックが大変なので、絶対にバグらせないぞという決意を持つ必要があります。対称性がありそうですが、楽をしようとすると得てして勘違いでバグらせるので、全てのマジックナンバーについて必ずじっくり考え、1つ1つ丁寧にコーディングを進めます。

これで展開図上をサイコロが動けるようになったので、入力の読み取りの際は実際にサイコロを転がしつつ写し取っていく感じにします。物理的に考えると、現在真下にいる面に反転して写ることになりますが、この読み取りは全サイコロで共通なので、どの面にどのように写し取ろうと変わりありません。僕は真上にある面にそのままの方向で写し取りました。

各サイコロのペアについて、全ての状態を試し、それぞれに違いがどれだけあるかカウントして最小値をとればよいです。(縦回転x4+横回転)x4で試してみたところ、答えより小さな値が出てしまったので、デバッグをします。マジックナンバーに1つ違いがありました。

もう一度試してみると、今度は必ず答え以上の値が出るようになりました。この原因は簡単で、状態をすべて列挙できていないんですね。縦回転と横回転だけで再現する方法もなくはなさそうですが、一番手っ取り早いのは3つ目の軸周りの回転を実装することでしょうか。さっきの4x4ループの内側でさらに新しい回転を4回するとサンプルが合いました。

特に実行時間にも問題なく、AC！170分くらいのことでした。

僕がE問題を実装している最中にC問題もついにACしていたので、これで6完です。ペナルティが結構あります。あとはH問題が解かれていますが、あんまり考える気はないので、残り時間は適当に過ごしました。

総合11位、現役内10位、学内1位でした。

週記（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でレーティングが就活に使えるのがかなりありがたいことなのだと気づいた。