09/06(月)
先週の週記を投稿した後は、しばらく人の日記を読んだりKaggleでよく使われているモデルについて調べたりしたあと、布団に移動してしばらく本を読み、午前9時半に寝た。
しかし、ここで先週の週記に書けなかった日本橋ハーフマラソン増刊号の初動についても触れておきたい。この問題では過去の動きが将来にかなり大きな影響を与えるようなので、最後まで操作列を作ってから途中を弄るのは難しい、というより不可能だろう。ということでビームサーチを書きたいが、どういう風に書くかよくわかっていないので、とりあえず幅1のビームサーチに絞って書いてみることにした。
盤面の評価値は、これまで稼いだ金額にプラスして、まだ収穫しておらず枯れてもいない各マスの価値を収穫機からそのマスまでのマンハッタン距離で割ったものの和。これで6132813点。その後すぐ、必ず収穫機が連結であるようにして、将来の各マスの価値を生えるまでの時間で割ったものに置きかえ、さらに現在生えている価値に少し重みづけしたら、120452453点になった。連結性が効いたのだろう、実際その後重みづけを変えて、将来の各マスの価値により大きな係数を掛けると、133149923点になった。これまで稼いだ金額との比も重要のようだ。この点数は当時1位だった。
このあたりでビジュアライザに掛けてみると、将来的なマスの価値を重視するあまり序盤の動きがかなり遅いと感じた。そのため、収穫機が1台の間は現在の価値だけで遷移してみたが、逆に点数は下がってしまった。序盤のマスの価値は終盤に比べて十分小さいため、無視してよいのかもしれない。ここまで貪欲法で実装しているが、実行時間が1800msとちょっと心配なので、適当に高速化。200msくらい削って同じく133149923点を出すコードを提出し、この日は切り上げた。
午後3時半起床。しばらくコードゴルフをして、午後4時半からインターン先の週1のミーティングに参加した。先週の成果を報告する場で、僕が今週発表することは想定されていなかったのか特に資料など用意するようには言われていなかったが、せっかくなので1日稼働してやったことを口頭で述べた。ミーティング自体は問題なく終了。その後勉強会の時間があった。今日はパズル系の発表で、ミーティングに参加している人々と共に頭を働かせた。かなり興味深かった。インターン生でも発表してよいらしいので、毎週の様子を見つつ内容を考えておきたい。
インターン先から僕のところにパソコンが送られてくるかも、という話になったが、モニターとキーボード・マウスはこちらで用意する必要がありそう。自分のパソコンからモニターを引っこ抜くのは寂しいので新しいものを買ってもいいかもしれないが、そうすると今使っている机に並べることはできないので、ディスプレイアームが必要になる。僕はパソコンデスクとしてダイニングテーブルを使っていて、これは幅も奥行きもあってかなり広々使えるのだが、ディスプレイアームの設置に対応しているのかだけが心配。一度駅前のヨドバシカメラにでも行って現物を確認する必要があるだろう。
余った時間で、Kaggleに興味がある面々が集まってチームを組もうという話になった。チームを組むということ自体に非常に興味があって、ぜひやってみたかったのだが、残念ながらコンペのチーム人数制限が3人だったので組めなかった。以前は5人だったらしい。
ミーティングが終わってからはすぐ業務に入らず、しばらく本を読んでいた。「かくりよの宿飯」5巻を読了。3巻ラストの衝撃的なシーンから続く一連の流れがこの巻で終わった。単純なので、悪役っぽい感じで登場したキャラがいたら最初は悪感情を抱いてしまうが、その後しばらくかけてそのキャラの性格や信念などに触れると、すぐ好印象で上書きされる。でも敵だったキャラが味方に付くという展開は非常にありがちなので、その点ではよいことなのかもしれない。また新たな敵キャラが登場したが、今のところはとりあえずやり込めることができており、1巻で提示されたストーリー上の謎も1歩前に進み、総じて非常に満足のいく終わり方だった。
午後8時半くらいから業務を開始して、午前1時半くらいまでずっとコーディングしていた。とりあえずコード読みの一環としてリファクタリングをしており、自分が思うきれいなコードを書こうと邁進していたが、今書いているコードは保守性が求められるものではないため、実は必要ではなかったのかもしれないという思いがぬぐえない。可読性については元からあまり変化がない、というのも、自分が思うきれいさとは、例えば型ヒントをつけてmypyでエラーが出ないことだったり、関数を切り分けたり統合したりすることであって、コメントをつけるという作業はほとんど行わなかったからである。残り1ファイルになって、少し手を入れたくらいで今日は切り上げた。
エクセルファイルをPythonから読み込むことが多いが、この作業は結構重い。僕が読んでいるコードを以前に書いた人も、その点は重々承知しており、エクセルファイルを読み込む関数をいくつか用意して用途によって使い分けていたが、なおかなりの処理時間を使っていた。ある特定のシートしか必要ではない状況にあっても全体を読んでしまっているということに着目し、特定のシートだけを読み出すような関数を用意してみたところ、かなり処理速度がアップした。手元で50分以上かかっていた実行が10分程度で完了するようになり、非常に楽しかった。
Kaggleを少し進める。ほんの少しだけ調べた結果、モデルはLightGBMがよく使われているとか、特徴量を考える作業が多いとかを聞いて、試しに適当にそれっぽい値を増やして学習させたら、スコアが結構上がった。集団を追い抜いたようで、順位も400位くらい上がったのではないか。それでもコンペの参加人数が多いためまだ順位表の下であることに違いはないが、結構元気が出てきた。特徴量というのは本当に必要なものを少しだけ用意するのがよいと勝手に思っていたが、実はそういう重要度を考えるのはモデル側がやってくれるので、こちらは関係ありそうな値を手当たり次第に放り込んで観察するのが基本的なやり方らしい。
布団に移動してしばらく本を読み、午前6時就寝。
09/07(火)
午前11時起床。かなりつらかったが、正午からメンターさんとの1on1をお願いしているため、無理やり起きる。完全に自分が悪い。信じられないくらい頭がかゆかったので慌ててシャワーを浴びたが、よく考えると昨日シャワーを浴びていなかった気もする。
正午まではマラソンの続きをしていた。ふと、昨日の評価について連結成分の大きさを考えていないことに気づいた。将来的なスコアに連結成分の大きさを掛け合わせ、重みづけを少しいじってみたところ、168165265点へと大幅に増加。何とか順位表の1ページ目に返り咲いた。
今日の1on1では、とりあえず今やっていることが終わりそうだということを報告。そのあと何をするかについて話した。いよいよ機械学習をやってみるようで、サンプルコードを紹介されて読み、実際に手を動かしてみることになった。
そのあとは業務に関係のない話として、Kaggleの進め方についてまたアドバイスをいただいた。Kaggleは競プロとは違ってコミュニティで知見を共有しスコアを伸ばすのが推奨されているので、いろいろな提出が公開されるらしい。聞いた感じでは、公開された提出に自分なりのアイディアを盛り込むことでスコアを伸ばすのだという認識。また1回の提出で1時間くらいnotebookを動かすのは普通にあることらしく、競プロとは全然違う時間感覚だなあという気持ちになった。昨日、特徴量を手当たり次第に放り込むということを書いたが、そういう「できるだけ様々な要素を考慮する」ことに関連して、Kaggleでは2つのモデルに結構な精度の違いがあったとしても、ある程度悪いモデルも含めて混ぜ合わせたモデルを作る（アンサンブル）のが結構効くようだ。これは自分の直感にかなり反していて興味深かった。
その後大学生協とコンビニに行って買い物をし、食事。そういえば2回目のワクチンを接種してから2週間が経過したため、fully vaccinatedと言ってよいだろう。帰宅して、業務を開始する気にならず（おそらく、今やっていることが終わったら機械学習という未知の領域に踏み出すことになるという恐れから）、しばらく本を読んでいた。
「かくりよの宿飯」6巻読了。前の巻でストーリーが一段落したので、この巻は比較的まったりしていた。ところがまたラストになってきな臭くなって、5巻ではやり込めることができた敵キャラがまた姿を現した。一体どうなってしまうのか。またその直前、主人公と鬼神の大旦那の関係にかなりの進展があって、こちらは非常に健康に良かった。
7巻を手に取って読もうとしたが、急激な眠気に襲われ、布団に倒れこんで、午後7時くらいから午前0時半まで寝ていた。
夕方に14の1落ちが出ていたのはツイートを見て知っていたが、手元動画も撮影していたようで、投稿されていた。歴史的資料。
結局今日はインターンの業務を一切行っておらず、非常にまずい。まずいが、とりあえず日記を書くことにした。その間マラソンに関していくらか新しいアイディアが生まれたので、それも記しておく。
まず、最初の850ターンは収穫機を買えるなら買うという方針にして、179976413点。次に、将来のマスの価値として「生えるまでの時間」で重みづけしていたのを「枯れるまでの時間」としたところ、202885296点まで伸びた。提出時は21位とギリギリ順位表の2ページ目になっていた。
日記を書き終えてから、1時間だけインターンのコードを書いて、もらったリポジトリのコード読み・リファクタリングが完了した。一応もらった時のコードと出力が変わっていないことは常にチェックしている。これで次から機械学習か、と思ったのだが、その前にコードの出力を眺めていたところ、微妙に怪しい部分があった。明日のミーティングでちょっと聞いてみることにした。
ちょっとコードゴルフをし、ラノベの新刊チェックをして、午前6時前に布団に入った。ネット小説をチェックすると東方遺骸王の更新が来ていたので、読む。前の話から一気に数百年くらい飛んだようで、そういうのはかなり好きな展開である。人間の寿命の短さを感じる。また、かなり昔から出ていた紅美鈴らしきキャラは名前が違っていたが、便利のために改名したという形で、その師匠ポジなどではなく本人そのものだったことが明かされた。かなり膨大なバックグラウンドがついたことになり、感慨深い。誰かの感想に書かれていたが、原作でただの門番をしているけれど、実は（この作品の設定上は）屈指の長命キャラであるというのがかっこいい。
そのあと、流れで捜索掲示板を漁り、1作見つけて読みふけってしまった。20話もいかず完結していたが結構読みごたえがあり、2時間半ほどかけて読了した。
かなり良い。コナンのストーリーは事件発生から解決までの間がほぼダイジェストになっていて、この作品の元となった部分の原作漫画を前半少ししか読んでいなかった自分はなかなかついていくのが大変だったが、それはそれとして少年探偵団と輝夜の関りが非常に健康に良い。輝夜がその美貌でモデルにスカウトされ、一躍時の人となるという設定も好み。ただそういう表面的なことだけではなく、ちゃんと底に一連の流れがあって、綺麗にまとまっているのも満足感が高い一因である。
明日の1on1は午後3時からの予定だ。生活を完全に破壊してしまい、慌てつつ午前11時前に就寝。
09/08(水)
午後2時、かけていた1度目の目覚ましで意識を取り戻す。二度寝するのはさすがにまずいため、根性で起き上がった。しばらくパソコンの前でボーっとした後、1on1が始まった。
昨日発見した出力の怪しい部分は、この後影響が大きいようだったらまた考えることにしましょう、という話になった。まあそういうものか。個人的には納得のいく処置であるが、その納得の理由を詳しく書くのは控えておこう。その後、火曜日に紹介されたサンプルコードの話になって、まだ読んでいなかったのだが、少し手ほどきを受けた。実はそもそもMNISTやImageNetが何を表すかもわかっていなくて、適宜ググりながら話を聞いた。サンプルコードは多少長くて少し骨が折れそうだと思っていたが、今日の話で出てきた部分が勘所のようなものなのだろうから、そこから周りを見ていけば何とかなりそうな気がしてきた。
また、業務に関係ない話として、自分の生活習慣が崩壊していることを申告した。このままではいつか絶対1on1に寝坊すると思ったからだ。まあもともと先方の予定を聞いて空いているところに入れていたので、もっと夕方にずらすならそれで特に問題ないらしい。そのあたりかなり柔軟に対応してくださるのが非常にありがたい。働きやすさを感じている。
1on1が終わったらまた寝ようと思っていたのだが、思ったより意識がはっきりしている。しばらくパソコンの前でグダグダした後、学食に行くことにした。雨が降る中クロックスで外出。帰ってきたらクロックスの中の汚れが足に移ったのか、足からひどいにおいがしてきて、かなりげんなりした。確か大学1年生の時に用意したものだから、もう4年目、さすがに買い替え時か。
帰宅してまたハーメルンを漁っていた。今やるべきことではないという思いが強いが、久しぶりにネット小説を読む体験というのは止めがたいものがある。結局今日のECRのちょっと前まで読んでいた。
こどふぉを開いたら、自分が2件のコメントで言及されたと通知が来ていた。見に行ってみると、Tシャツが当たっていたことを知った。Deltix Roundというちょっと前のdiv.1で上位100人にギリギリ入っていたので1着、さらにCGR15の31～500位にランダムで配られるので1着。これがこどふぉで獲得する初めての衣類となりそう。
午後11時半からECR113に出た。5完。
Dashboard - Educational Codeforces Round 113 (Rated for Div. 2) - Codeforces
Aはギャグ。Bは勝ちたいプレイヤー同士が順繰りに勝つように埋めればよいが、勝ちたいプレイヤーが1人または2人しかいない場合は不可能。2人の場合を見落として1WA。Cは最大値と2番目の最大値の差が1以下でなければならず、ちょうど1のときだけダメな順列が存在するので、求めて引く。Dは、街が道路でマス目に区切られていると考えると、ある長方形の対辺に乗っているペアを数えることになる。座標が106以下なのでそのままBITに乗せて、初期化はいちいち更新をロールバックしたが、座圧すれば1マス取得でよかったようだ。縦横両方にするのも少し面倒。
Eは難しい。トーナメント表の半分ずつ（準決勝の2分の1、準々決勝の4分の1……のこと）をsetで全通り計算するコードを書いてみたところ、は爆速で終わるが、
のときが間に合わない。setに直接insertするのではなく、いったんvectorに溜めてみたところ、手元で4secをギリギリ下回ったが、CF環境が信頼できないので、もう少し根本的な改善をする必要があった。実は全通り計算するのは下から
段目まででよく、
段目については値の存在判定さえできればよい。ということで最後の段を特別扱いすることにしたら、
の場合も
までの計算で済むので爆速になった。
Fは、文字種を座圧したものが15万通りくらいしかないようなので、それを全探索するのかとも思ったが、毎回の判定が間に合わない気がして、一気にdpで計算するのかと考えていたら、コンテストが終わってしまった。TLを見た感じ、全探索した後毎回判定するので合っているらしい。
今日は結局インターンの業務を進めることができなかった。現実逃避のためにECR17を埋めた。
Dashboard - Educational Codeforces Round 17 - Codeforces
Aは、制約からを落とそうとしているのかと思い、
で解いた。約数列挙をすると、昇順の列と降順の列に分けて得られる。Bはソートして貪欲だが、実装ミスのWAを勘違いしてコードを大幅に書き直す羽目になった。Cは左と右から必要な文字の範囲を前計算して、被らないように尺取り。区間の端を含むかどうかの処理で結構サンプルを合わせるのに手間取った。Dはヤバそうな見た目をしているが、実際のところたった5通りの状態に対する遷移を全部書き下せば終わり。Eは
ごとにまとめてその個数ぶんのBITを作り、取得を区間和で行う。
を昇順に持っておいて適宜個数を引いていく。
Fはヤバそうな見た目をしているが、木dpを書くときれいに遷移してくれて、特段変わった処理をする必要はない。に含まれる
を頂点のラベル付きで数えた後、
に含まれる
を全く同じコードで数えて割ることでラベルなしの数え上げをするのは、半信半疑で動かすとちゃんとサンプルがあって感動した。ところがTLEが取れない。ケースを見ると、大きすぎて上のほうしか確認できなかったが、どうやらウニグラフで落ちているらしい。そこで手元でちょっと試してみると、ウニの中心が適当に設定した根以外の場所だと一気に処理が重くなっていた。次数が一番大きな頂点を根として扱うことにしたら、爆速で通った。想定解でも木の中心を見つけるということを行っているが、その後重複を省く方法が、割り算ではなく頂点の割り当てを一意になるようにルール付けするものだった。
午前4時前になって、ようやくゲノコン2021のD問題が公開された。問題文がかなり厳つくて、これまで3問の練習問題がなければ確かに参加者は大幅に絞られただろうという気になる。というか、僕はかなり絶望していて、C問題も2700点くらいを出す提出のブログ記事を読んだのに結局何もやっていないため、これから触れることはなさそう。
Genocon2021 ー DNA Sequence Analysis Challenge - AtCoder
朝方、ハーメルンの捜索掲示板をいろいろ見ていた。自分の大好きな作品で検索したりするのも面白い。自分の好みのジャンルについての捜索が出されているのを見て、いっちょリストアップしてやるかとも思ったが、大抵は過去の似たような捜索で出ている作品であるから、別段自分が言う必要性もないな……と思って止めたりしていた。布団に入ってからもしばらくハーメルンを読んでいたが、午前8時過ぎに寝落ちした。
09/09(木)
午後3時すぎに目を覚まし、またハーメルンを読み始めた。午後4時半に1作読了。「俺の家が幻想郷」。
良かった。オリキャラの名前や最初数話の文体からいかにもな厨二臭さを感じるが、設定が良いためあまり気にならなかった。ミニチュア東方キャラとかいうどう転んでも健康に良い設定、素晴らしい。同作者の別作品に主人公が同じ名前のこれまた東方2次創作があったが、そちらはシンプルなオリキャラ幻想入りであまり興味を惹かれなかった。
続いて別作品を読み始め、午後6時にさらに1作読了。「美少女精霊たちに愛されたいと頑張ったら最強の精霊使いになっていた」。
無双ものを期待し、実際に無双していたのだが、主人公のどういう点が周りと違うのかは説明されていても、それがどのように強さに影響してくるのかにはほとんど理由付けがないように感じられた。まだ物語が始まったばかりだからだろうか。主人公とヒロインの絆を描くストーリーも、クライマックスのバトルシーンもいい感じではあったが、自分の最近の好みに特別当てはまっているわけではない。
またハーメルンの捜索掲示板に戻って東方の2次創作を探す。いくつか良さげなものを見つけては数話読んでやめる、を繰り返していたら、読み進められそうな古代スタートものを1つ見つけた。それを読み始めたが、午後9時半くらいに寝落ちした。
目を覚ましたら午前1時だった。昨日インターンの業務が一切行えなかったのを気にしていて、今日は頑張ろうと考えてはいたものの、ふたを開けてみれば夜中までずっと寝たりハーメルンを読んだりを繰り返していただけ。これはひどい。慌てて起き上がり、とりあえずatgolferの更新を確認してしばらくコードゴルフしていた。HikakinTVに短い動画が上がっていて、以前「チャンネル登録者数995万人から1000万人到達するまで生配信する」と宣言していたが、いつの間にか996万人になってしまったので土曜の昼間から生配信する、ということを言っていた。僕もチャンネル登録した。
午前3時から業務開始。今日はちょっとしたコードを書いた後pytorchのexamplesからおすすめされたコードを読んでいた。午前6時で上がり。
また少しコードゴルフをした。起きてすぐ書いたコードが縮められていたので、縮め返した。
81B→80B→79B。明らかな短縮ポイントがずっと残っていたが、ここを縮めると50msくらいTLをオーバーしてしまうようだった。Vimの補完の際にめちゃくちゃ長い文字列が候補として挙がってしまうのが問題。何とかして実行時間を縮められないかといろいろやってみていたところ、数値をコードに直接埋め込むこと、うまいこと改行を残すこと、掛け算の順番を変えることで数回に1回2000msを切るようになった。4ケースTLEしているので、全部2000ms以下に揃えるのは厳しいかと思いつつ提出したところ、1発で見事に通った。1つのテストケースに対して最大3回実行されるということもあるし、思ったより確率は低くなかったのだろう。とはいえ、その後3回出して3回ともTLEしているので、やはり運が良かったのは大きいか。
CFのTシャツをもらうためにsettingからADDRESSを埋めた。SOCIALという部分にも個人情報を書くべきかと思ったが、必要ないらしい。シャワーを浴びてゴミ出しし、ちょっとだけKaggleを進める。スコアの良い公開提出をコピーしてきて、自分で動かしてみていた。ここに自分なりの特徴量を増やしてうまくいけばスコアがよくなるということらしい。submission.csvを見ると、これまで自分が提出してきたものより行が多くてびっくり。自分のコードのどこかが間違っているのだろうか。それにしては、なぜ正しく採点されているのだろう。よくわからないが、その違いを見極めるには微妙に眠気があるので、今日は寝ることにした。
布団に入ってうっかり1時間ほどハーメルンを読んでしまう。明日は午後3時半から1on1で、この2日間の無みたいな進捗をメンターさんにお伝えしなくてはならない。起きられるよう祈りながら午前11時就寝。
09/10(金)
午後2時半の目覚ましで目を覚ましたが、あまりにも眠すぎるということで30分二度寝する賭けに出た。勝利して見事午後3時に起床。
YouTubeを見たら、HikakinTVのチャンネル登録者数が1000万人を超えていた。生配信はどうなったかというと、今日の昼ぐらいに急遽行ったものの、20分もせずに到達してしまったらしい。アーカイブを見たところ10分弱で1万人増えるというとんでもないペースで、HIKAKINのすごさを思い知った。本当は僕は、5万人増えるのに何日かかるんだろうかとかそんな長いこと配信できるのかとか、いろいろ心配していたのだが。
HIKAKINのこれまでの道のりを詳しく知っているわけではないのだが、より一般に、人が感極まっている様子に弱い。今日のHIKAKINは、直前まで普通の声だったのが、感情がある閾値を超えた瞬間に急にヘロヘロになるという、特に理想的な感の極まり方をしており、何度見てもうるっとくる。
午後3時半から1on1。今週は稼働時間としてはほぼ無だが、一応1on1の度に1段階以上業務を進めている。個人的にはたった数時間コーディングして終わるようなことは大した進捗ではないと考えているが、メンターの方からは思ったより進みが速いと言っていただいて、嬉しくなった。調子に乗らないようにしたい。進捗報告の後はこの後数日やることの確認を行って、1時間もせず終了。
様々な物事に対するやる気がちょっと出てきたので、メールを2通書いた。1つは4年ゼミの先生宛で、長期インターンを開始したことの報告。もう1つはサークルの顧問教員宛で、サークル代表を交代することの報告。さらに代表者交代届をまだ提出していなかったので、自分の分を書いて新代表に残りを埋めるようお願いしたりもした。これはここ数日やるべきこととしてずっと頭の中にあったので、解決できて満足。
夜、学食に行こうとしていたらインターン先からパソコンが届いた。ワクワクしながらとりあえず学食で夕食を食べ、帰ってきて開封。
デカァァァァァいッ説明不要!! pic.twitter.com/N1eqxjV0IS
— こたつがめ (@kotatsugame_t) 2021年9月10日
周辺機器は、会社のお金で買うこともできないことはないらしいが、その時はパソコンとともに会社に返却することになるので、自分で買って使うことにした。明日あたり早速買いに行きたい。キーボード、マウス、LANケーブル、延長コードは必ず必要なもの。あとはモニターとモニターアームも欲しいので、机の寸法など図ってから電気屋に行こう。寸法を測るためのメジャーが家にないため、それもまず買っておかなければならない。
今日はとりあえずパソコンのセットアップだけでもしておくかと思って、モニター1枚のケーブルを移し替えて起動してみたが、LANケーブルがないとネット回線に接続できなかったので、諦めた。
しばらく日記を書いてから、yukicoder 313に出た。全完。
yukicoder contest 313 - yukicoder
Aはよい。Bはびっくりするが、制約がギャグなので愚直に解ける。Cはどのでも立っていない最小のbit。Dは区間setの遅延セグメント木を書きかけたが、priority_queueでシミュレートして区間minのセグメント木でチェック、でよい。Eはdp。Fは構文解析。Gは、Eの考察をさらに進めると、買う・1回交換する・売るを繰り返すことになるのがわかり、最小費用流で解ける。つい最近もABCで最小費用流を見たので、しばらく無意識的に考察から除外していたが、作問者のツイートを見るにこの問題を作ってからABCで出たという流れだったらしい。負辺があるが、除去せずDAG上のDPでポテンシャルを求めて解いた。
しばらくパソコンの前で、朝方からは布団に移動して、ずっとハーメルンを読んでいた。東方オリ主古代スタートもの。オリ主が幻想入りする直前の現代の風景がかなり好みで、ちょうどそのあたりに差し掛かったので、舐めるように読んでいた。幻想入りしてから原作キャラと再会するシーンも好きだが、そのあとはだんだん興味が薄れていきがちなので、どうしようか迷う。最近読んでいた作品はこれ。
午前7時くらいに就寝。明日は買い物。
09/11(土)
午後3時、起床。すぐに準備して、地下鉄に乗って駅前まで出る。
まず、ヨドバシカメラでLANケーブル・延長コード・キーボードとマウスを揃える。今使っているマウスがトラックボール式なのでできれば揃えたいと考えていたが、結構いい値段がするので、あえてガラッと変えてタッチパッドのついたキーボードを購入した。それでも4000円くらいしていたが、トラックボールマウスを買うよりは安いので即決してしまった。あとは前から欲しいと思っていたエアダスターも買って、合計1万円弱。ヨドバシカメラのポイントカードを出したら、クレカ機能が付いたカードに交換しないかと言われ、まあ勝手にやってくれるのなら……と思って頷いたら、機械の前に案内されてさあどうぞ！と言われキレそうになった。
実際にキレることはなくて、唯々諾々と個人情報を入力していたのだが、現在持っているポイントカードと情報が合わないらしい。店員さんが調べに行ってくれたところ、どうやら実家の情報が入力されていたようだ。ポイントカード自体も実家に届いてしまうらしく、さすがに面倒が過ぎる。このあたりで勇気をもって「やっぱりいいです」と伝えることができて、無事会計に戻った。そもそもヨドバシカメラは年に1回行くか行かないかのペースなので、ポイントが失効する前に使えた試しがない。還元率がどれだけ良かろうと無駄。
続いてモニターを選ぶ。ヨドバシカメラにもモニターやモニターアームが置いてあったが、なんだか思っていた値段よりも高い。モニターにスピーカーが付いている必要はないので、そういうものを売っていることが期待できるパソコン専門店、具体的にはドスパラのほうに行くことにする。が、ドスパラにもスピーカー付きのモニターしかなかった。
モニターアームについて店員さんに相談してみた。すでにディスプレイを置いていて、それの上に並ぶようにモニターを設置したいと言ってみた。可能ではあるようだが、ちょっと製品を選ぶ必要があるらしい。ポールを立てて、そこからさらにガス圧のアームを伸ばすようなものなら大丈夫だろうとの話。また、2枚設置したいということを言ったら、1枚用のものを2つ買うのもアリだと言われた。ともかく、目的に合致するものは実店舗には置いていないので、結局はネットで注文するのがよいとおススメされた。
仕方ないので帰る。せっかく駅前まで来たということで、スマホアームを設置している店舗に行ってチュウニズムの手元を撮影してきた。以下のリプライツリーにまとめてある。
Parad'ox 1-0 手元 pic.twitter.com/cDHuvDKMQI
— こたつがめ (@kotatsugame_t) 2021年9月11日
帰ってきてすぐ製品を選ぶ。モニターアームは、結局2枚縦に並べられるものを2つ買って使うのが間違いないと思った。買ってから気づいたが、僕が選んだ製品だと上段のモニターが下段のモニターより奥に行ってしまうかもしれないし、さらに上にだけモニターを取り付けたアームは重心的に不安定で危険な気がする。肝心要のモニターは、15000円くらいを想定していたつもりだが、どうやら20000円を切る製品すら限られてくるようだ。サイズも決めていなかったのでかなり迷ったが、結局↓のモニターを2枚購入した。そこそこ大きくてそこそこ安く、VESA規格に対応しているのでちゃんとモニターアームに設置できる。
あとはパソコンと接続するケーブルを1本で、総額45000円弱。競プロの賞金として得たAmazonギフト券で支払える額だったので、拙速を尊びそれで購入した。代わりに振り込みのためATMから降ろしてきたお金の行き場がなくなったので、また戻しておこう。これまでのお金遣いからするとかなり散財したなという印象だが、インターンでこれ以上の金銭を得られる予定なので問題ないはず。金銭感覚が追い付いていない。
モニターを選んでいるということをツイートしたら、某競プロerさん（匿名希望）からAmazonギフト券7000円分（も！）を送ってもらった。かなり突然のことで、非常にありがたい一方、こんなに貰って自分は何を返せるのかという気持ちになった。とりあえずメンションなど飛ばして感謝の気持ちを大々的に伝えようとしたが、匿名希望らしい。心の中で本当に感謝しているということを、ここにも再度記しておきたい。
午後9時からABC218に出た。6完。もう完全にダメ。
AtCoder Beginner Contest 218 - AtCoder
Aはよいが、短い書き方となるとわからない。BはPerl、そのあとRakuで出しなおした。CはC++で、愚直しか思い浮かばなかったので出したら1200msくらいで通った。結構攻めた制約だな～などのほほんと考えていたが、これが想定なわけはない。Dは座圧した後
を2つ選んでbitset。4secなので自信を持って出したが、これも想定ではなかったようだ。Eは打って変わって非常に簡単、最小全域木っぽいことをやるだけ。Fはなかなか難しくて、迂回路があるかどうかなど考えていたが、しばらくして答えに影響する辺が高々
本しかないため、毎回計算できることに気づいた。
Gが解けなかった。二分探索を一生考えていたが、全然合わない。最後に出した提出は2分探索を2重に行っていて、2ケース落ちた。8問体制になってからABCの600点に苦手意識がついている気がする。何とかしなければならない。
TLをチラッとだけ見たが、二分探索ではなかったらしい。それでさらにしばらく考えたら、ふとdfsを1回するだけで各葉に対して中央値が求まることに気づいた。それからも結構WAを重ねて、ようやく解けた。僕は優先度付きキューを2本持って、取り出したときにすでに考慮しない要素だったら無視する方針で書いたが、解説のようにmultisetを使って直接削除するほうが簡単か。さらにH問題を考えていたが、TLをちらっと見た瞬間にちょうどAlienDPとのキーワードが流れてきてしまった。まあ自力では不可能な気もする。upsolveは後回し。
コードゴルフ。AはVimを書いていたが2B負け。BはRakuに満足していたら普通にdcで縮められた。Cは面倒そうだなと思っていたところ下のHaskellコードがatgolferに流れてきたので、Rubyに直して縮めた。
Dも僕がコンテスト中に書いた方針（を2つ選んで
をカウント）をRubyで書いたが、解説の左上と右下を固定する方針を試していないため縮むかもしれない。pythonはその方針で書かれているようだ。EはPerl。0とのmaxを取るのは
$-に代入するしかないと思っていたが、先頭に'0'を加えて数値として解釈してもできるらしい。そちらの方法だと空白を1つ省けて縮む。以降は手付かず。
午前2時からFHC2021 R1に出た。
Facebook Hacker Cup - 2021 - Round 1
24pt取れば通過できるらしい。僕はA1A2A3とBを解いた。
A1はまあ、できる。A2を考察するときにA1をもう一度よく考えると、これはつまり'F'を無視したときに'X'と'O'が隣接するような場所の個数だとわかる。それを用いると、逆に隣接する'X'と'O'を両方含むような部分文字列の個数だけ答えが増えるということになって、A2が解ける。A3のため、さらにA2を考えてみると、だいたいという値を求めていることになるが、実はこの値は加えて
、
、
、文字列の長さを持っておけば文字列を2倍する操作に対しても更新が可能。間で1つ増える可能性があるが、これは一番左・右にある
'F'でない文字を追加で持っておくことで求められる。オーバーフローしていたがvalidationで落ちてくれたので助かった。
A3を解く前にBを解いていた。しばらく考えていたが、実はギャグで、左上と右上の値だけ増やせばOK。
朝方布団に入ってハーメルンを読む。案の定昨日まで読んでいた作品は微妙に飽きたので、別のものを1つ。しかしよくわからなかった。
別の作品、これもまた東方オリ主古代スタートものを読み始めたり、過去に読んだハーメルンをちょっと読み返したりして、午前9時に就寝。
09/12(日)
午後4時半に起床。午後5時からOpenCupに初参加した。何のリンクを貼っていいのかわからないので、とりあえずCFで議論していた場所を貼っておく。
XXII Open Cup, Grand Prix of Dolgoprudny - Codeforces
ヤバかった。赤3人で組んで5完だが僕自身は1問も通せなかった。前のほうの問題を読んで概要をまとめていたが、どうやら非人間向けだったらしい。考察した問題はDとKで、DはMo's AlgorithmにsetのlogをつけてTLEしていたのを、チームメイトがvan Emde Boas treeでぶん殴っていた。Kは最終的に98チームが提出してAC数2という化け物で、僕も見た目が簡単なのに騙されて適当な解を投げ、考察を進めるたびに難しさを実感して結局放り投げた。他にチームとしてACできた問題は、そもそもまともに考察していないので、upsolveも何もあったものではない。
CFブログにあったDの解法は頭が良い。Mo's Algorithm中で自分より小さい要素の最大と自分より大きい要素の最小を取りたい。結局謎データ構造でになったが、実はDancing Linksを使って線形時間でできるようだ。削除を巻き戻すため、更新順序を良しなにしなければならない。どうするかというと、まずクエリの
でブロックに分け、各ブロックでデータ構造を初期化する。
の昇順に並べるのはMo's Algorithmと一緒だが、
のために毎回ブロックの先頭から
まで進めて（削除して）、クエリに答えたら即座にブロックの先頭まで戻す（削除を巻き戻す）のを繰り返す。Mo's Algorithmの計算量解析からして、このように無駄な操作を行っても高々定数倍しか変わらない。Mo's Algorithmの更新順をいじることで操作を単純にするのは見覚えがある気がする。
5時間椅子を温め続けた。終わってすぐTOYPROのコードゴルフ大会に30分だけ参加した。
なかなか独特な競プロ体験だった。問題文で与えられた変数を使って、サンプルを埋め込んだようなコードを書いて提出すると、対応する変数名の変数にテストケースの内容が代入されてジャッジされるようだ。しかし同時に、代入しない状態でのジャッジ（正常に実行が終了するか）も行われるようで、変数だけ用意していると落ちる。ほかの人のコードを見たわけではないので何とも言えないが、自分は用意した変数を即座に1文字変数に代入してコード長を削ったりした。
1問目からマルチバイト文字を扱っていてびっくりするが、どうにかこうにか2問目から5問目までゴルフっぽいことをして提出した。しかし順位表を見ると、どの問題もより短いコードが存在していたらしく、悔しい。
日本橋ハーフマラソン2021 増刊号が終わっていた。結局、火曜日の提出が最後になって、システムテスト前の順位は100位まで下がってしまった。終わった時間にTLを見ていなかったので解法を終えていないが、どうやら評価関数をうまく設定してビームサーチする問題だったらしい？僕のコードは評価関数が重すぎてただの貪欲が精いっぱいだったが、遷移を絞り込むと幅を増やせたのかもしれない。コードゴルフとしては-1で埋めるのが短いが、この問題では1000行より多く出力していてもACとなるらしい。sedのc-1が最短となった。
ACPCの参加登録が始まっていたので、申し込んだ。
ACPC 2021（会津大学競技プログラミングコンテスト 2021） - connpass
午後11時半からCF CGR16に出た。
Dashboard - Codeforces Global Round 16 - Codeforces
ABCdDEFGを解いて12位、レートは2823→2952(+129)でhighest。大成功だった。
Aはよい。Bは2が必ず達成可能なので0と1を判定すればよく、簡単。Cは(0,1)を必ず切り離して、(1,1)は(0,0)が隣にあったらそれと組む。どちらも左から貪欲に求められる。Dは、D1もD2も座る場所を貪欲に決めることができる。答えを求めるときは、毎回かけても間に合う制約だが、一応BITを作った。Eは葉からどんどん切り離していくとして、最終的にどこに繋げるかは考えなくてよい。
Fは、初期状態ですでに条件を満たした区間を取り除いて考えると、各で分割された間にいくつかの区間が挟まる形になるので、そのまとまりごとに「左からいくつを左の
で取るか」を考えてdpする。dpのキーは、左右にある
を自由に動かせるか、あるいは元の位置に戻す必要があるかの2×2通りだけ。実装を簡単にするために左右に番兵を入れたが、その値をintに収まるよう
にするとマズそうなので、わざわざlong longを持ち出してこなければならず、大変だった。
Gは面倒。辺を短い順に4本取ってきて、それぞれ1、2、3、4とする。1と2が端点を共有しないなら、それらが答えになる。そうでなくとも、この4つの辺のどれか2本は端点を共有しないことがわかるので、考えるべきは(3,4)の組より長さが短いものだけ。それはどんなものかというと、*を1本の辺として(1,*)または(2,*)または(1+2,*)に限られることがわかる。ここで1+2は2本の辺からなるパスで、(1,2+*)や(1+*,2)も適当に組み替えると(1+2,*)にできる。つまり、いまある辺のうち端点がuでもvでもないもののうち最短のものが取得できればよい。各頂点に対し、そこから出る辺（ともう一方の頂点）を短い順に3本保存してセグメント木に乗せて解いた。2つのデータのマージは、辺の先の頂点が重複しないように注意して計算する。辺の追加は簡単で、削除については、各頂点に対して優先度付きキューを持っておいて、そこから上位3つを改めて取り出す（削除された要素は無視）ことで再計算した。この部分については昨日のABC218-Gのようにsetを使ったほうが楽だったかもしれない。
Gのシステムテストが750ケース以上あってびっくりした。
FHCが終了した。出したものは全部通っていた。Cもちょっとばかり考えていたのだが、という制約に気づいておらず諦めてしまった。また順位表にそこそこTimer Expiredがいたので何となく予想はついたのだが、手元で実行してstack overflowした人が多かったらしい。beetさんのブログに回避方法が書かれていたはずだが、もう見ることはできない。
HikakinTVに生配信直後の様子を撮影した動画が上がっていた。そのうち以下のシーンについて。SEIKINがHIKAKINのために急いで買ってきたケーキの話で、HIKAKINが「ホールじゃん」と言ったのをSEIKINが「当たり前だろ」と言ったのがかなり印象に残った。また店頭で頼んで文字を書いてもらったからSEIKINだとバレバレになったりしたことも面白い。
朝方日記を書いている最中にABC218-Aが縮んだ。今回の問題は'o'と'x'を区別する問題で、たまたま'No'には'o'が含まれ、'Yes'にはどちらも含まれない。というわけで、'Yes No'という文字列を用意し、Yesの上にカーソルがある状態で'o'または'x'を検索すると、'o'の場合はNoにカーソルが移り、'x'の場合は移動しない。その後カーソル下の単語を消せば答えが得られるという寸法だ。
