09/13(月)

週記を投稿してから布団に入り、しばらくハーメルンを読み返して寝た。午前9時前だった。先週金曜日の1on1でこの先しばらくやることを確認したと書いたが、結局それから1ミリも進められなかった。

午後3時に起床。15時と午後5時を見間違えたこと、寝ている間に月曜日のミーティングの時間が1時間早まっていたことが合わさって、ついに寝坊してしまったかと冷や汗をかいて飛び起きた。セーフ。

せっかく起きたのでミーティングまでしばらくインターンの業務を進めた。それっぽいコードは書けたが、途中でエラーが出る。サンプルコードをほとんど写したようなものだったが、やはり自分で実行していないコードということで何か勘違いがあるらしい。自分で解決できないこともなさそうだが、設計まで含めて1on1で聞くのが早いだろう。

ミーティングは特に何事もなく終了。今週から自分もスライドを用意して、先週何をやったかと今週何をする予定かをきちんと発表した。来週月曜日は国民の休日らしく、ミーティングが別の日にずれるらしい。そういうこともしっかり考えてるんだなあという気持ちになったが、逆にしっかり考えないと会社としてはまずいのか。

学食に行って帰宅。土曜日に注文したモニターアームが届いていた。思ったより重くて、机の耐荷重が大丈夫か……？という気持ちになる。ダイニングテーブルは奥行きもあって広いが、一方でパソコンデスクほど耐荷重が重くないのが難点であると気づいた。

しばらくハーメルンを読んだりコードゴルフをしたりした後、CF ECR18を埋めようとした。Fはまだ解けていない。

Dashboard - Educational Codeforces Round 18 - Codeforces

Aはよい。Bは難読。特に問題文中の例はゲームの途中から書かれているため、理解するのに苦労した。わかってしまえばシミュレートするだけ、実装は何とでもなる。CはABC182-Cの強化版で、数字に0が含まれること、桁数が10⁵オーダーであること、復元が求められていることから非常に難しく感じた。ABCの方と同じく場合分けをして解こうとしたが、ふとただの桁dpで解けることに気づいた。Dはbitを見て適当にやる。

C - To 3

Eは難しい。各集合の大きさを $n$ か $n+1$ であると定めると、必要な条件は $\exists q\;s.t.\;qn\le a_i\le q(n+1)$ と書ける。ここで $\left\lfloor\frac{a_i}{q}\right\rfloor$ はそんなに種類がないので、適当に $i$ を選んで $\left\lfloor\frac{a_i}{q}\right\rfloor$ と $\left\lfloor\frac{a_i}{q}\right\rfloor-1$ を全部調べればよい。各 $n$ と $a_i$ に対して最適な分け方は上の条件から出る。

インターン先から届いたパソコンのセットアップを済ませることにした。起動してみるとWindows単体が入っていたので、Ubuntuとのデュアルブートにする。頑張ってマザボの例のアレ（ファームウェアインターフェイス）を起動すると、BIOSではなくUEFIだった。マウスによる直感的な操作でいろいろ調べてみると、HDDのところにUbuntuと書いてある。しかしWindowsのほうから確認したら全ての領域にアクセスできていそうなので、すでにデュアルブートになっていたとかいうことはないだろう。聞くところによると、このパソコンは以前Ubuntuとのデュアルブートだったのを、僕に貸与するにあたってわざわざほぼ工場出荷時の状態に戻してくださったそうだから、その時残ってしまった名残なのかもしれない。以前別のパソコンで使った、Ubuntu 20.04インストール用のUSBを差し込み、起動の優先順位を変更していざインストール。

グッド・ゲーム pic.twitter.com/11tCjqgKD1
— こたつがめ (@kotatsugame_t) 2021年9月13日

画面上部に1行だけ映っているメッセージで検索すると、どうやらグラボが入ったPCにUbuntuをインストールするときにドライバがないため起こる現象らしい。確かにオンボードでないGPUが入ったパソコンにUbuntuを入れるのは初めてだ。しかし解決方法が設定ファイル編集によるものらしく、なんだか怖かったのでとりあえず無理やり電源を落として再起動してみると、「Ubuntu (safe graphics)」といういかにもそれっぽい起動オプションが増えていた。それを選んだらちゃんとインストール画面まで進めて感動。デュアルブートを選択して、パーティションも特に弄らずインストール開始。

失敗したというメッセージが出た。Ubuntuにバグレポートを送信すると、既知の問題だった。ブラウザでそのバグのページが開いたので読んだところ、インストールのオプションで「サードパーティー製ソフトウェアをインストールする」にチェックしていると起きるらしい。GPUのドライバはどうするんかいな、と思いながらチェックを外して再度試みると、今度はどうやらうまくいったようだった。

いい感じです、かなり pic.twitter.com/XvzIgB2M4M
— こたつがめ (@kotatsugame_t) 2021年9月13日

ソフトウェアとアップデートから適当にGPUのドライバを入れる。これにも失敗したという表示が出たが、終わってみるとなんだかいい感じになっているようなので、放置。最後に、Pythonの開発環境を整えて、GPUで計算できるようにする。わざわざUbuntuを入れたのは主にはこのためで、WSLからGPUを使うにはWindows Insider PreviewからWindowsのバージョンを更新しなければならなかったりして、かなり敷居が高い。やってみたらUbuntuを入れるのも敷居が高かったのだが……。

Pythonの開発環境を整えること自体はよくある話なので、適当にQiitaから記事を拾ってきてその通りに進めた。途中でAnacondaを使い始めたので、pip派の自分はそこで分かれる。Ubuntu 20.04はデフォルトで入っているPythonのバージョンが3.8と別に古くもないため、その辺りはデフォルトのままでいい気がしている。特に苦労することなくtorch.cuda.is_available()がTrueを返すようになった。

俺の勝ち！ pic.twitter.com/1Z28O14uoB
— こたつがめ (@kotatsugame_t) 2021年9月13日

せっかくパソコンをセットアップしたので、これまでWindowsで動かしていたPython スクリプトを一通りUbuntuでも動かしてみることにした。すると出力が一致しない。なんとなく理由の予想はつくので、また1on1で聞いてみることにしよう。ところで、机の上にキーボードが2台あって、片方でUbuntuを操作してもう片方でWindowsを操作している。かなり誤爆しやすいことが分かったので、十分気を付けなければならない。

これで今日の作業は終わり。シャワーを浴びて布団に入り、本を1冊読んだ。「かくりよの宿飯」7巻。6巻を読んでからハーメルンにハマってしまってちょっと時間が空いた。しかしやはり面白い。僕が好んで読むネット小説とはまた違うタイプの面白さで、たまにはこういうものにどっぷり浸かるのもよい。巻数的に、いよいよクライマックスにつながる流れの中にあるようだ。大旦那様が姿を消してしまい微妙に張り合いがないが、再会を楽しみに読んでいきたい。

午前7時半就寝。

09/14(火)

午前11時くらいにふと起きたところ、ちょうどモニターが届いた。しかしあまりに眠いので放置してまた就寝。次に起きたのは午後3時だった。日本橋ハーフマラソン（増刊号でないほう）で学生15位入賞していたらしく、アマギフを5000円もらった。

今日は丸一日使ってパソコン回りを整えなおす。まず手始めに机の周りのものをすべて取り外し、掃除をした。土曜日に買ったエアダスターが大活躍したが、逆に酷使しすぎて気化熱・断熱膨張によって缶の温度が下がり、結露どころか雫が凍り付いていてびっくりした。

この状態にしたところで1on1の時間が近づいてきてしまった…… pic.twitter.com/tnADG1uguh
— こたつがめ (@kotatsugame_t) 2021年9月14日

ルーターも取り外していたのだが、実は今日は午後5時半から1on1が予定されていた。直前になって全然準備できていないことに気づき、とりあえずネット回線だけ元に戻してノーパソから参加した。コード類は一応GitHubに上げてあったので何とかなったが、画面共有の時に1画面しかないと、脇で見せる資料を準備するみたいなことができないため、非常に不便だった。使うモニターの枚数は、ひとたび増やすともう減らせなくなってしまうことは有名。

1on1では昨日のコードの動かない点を聞いて解決することができた。また、WindowsとUbuntuで出力が食い違う理由もかなりそれっぽいので、一度対処法を試してみることになった。予想がついていたのなら先に試しておくべきだったかもしれないが、今日はパソコン回りを整える日にしていたので、1on1までにそのような時間はなかった。

1on1が終わって、また掃除に戻る。とりあえず一段落して、今度は機器を戻したり取り付けたりする。モニターアームの取り付けは机の後ろに回ることができないとなかなか厳しいものがあるため、机をずらし、まずそれを組み立てて取り付けた。地震が怖いのでネジを閉めるときはできるだけギュウギュウにすることを心掛けた。一か所プラスドライバーを自分で用意しなければならないネジがあったが、1年生の春に家具の組み立てで使ったものが残っていて助かった。

モニターアームを机に立て、モニターの高さを調節しつつ取り付ける。2台あるので、高さや角度を揃えようとしたのだが、ネジを緩めたり閉めたりして高さ・左右の角度を調節するタイプのものだったのでなかなか苦労した。最終的にはちゃんといい感じにできたので、机を壁に寄せ、あとは机に置くモニターを設置し、ケーブル類を全部パソコンに接続して完了。コンセント2口それぞれに6口ある延長ケーブルを差しているのだが、モニター5枚・パソコン2台・プリンター・ルーター・謎の機械（PLCアダプター？）・デスクライト・USBハブでちょうど全部埋まってしまった。そのほか様々なケーブル類は一切まとめていないため、机の下はすごいことになっている。

机の上はこんな感じ。

モニターはあればあるほど良い pic.twitter.com/WRS4WxTnKO
— こたつがめ (@kotatsugame_t) 2021年9月14日

非常に良い。前々から、モニターを縦に積んで上の画面を微妙に下に向ける配置、その角度にあこがれていた。視界を覆うようなモニターたちよ！これぞロマン！何に使うかは考える必要がない、何故なら、モニターはあればあるほど良いため。

しばらく実際に使いつつ、インターンのコードを書いていた。まず、画面が遠くてよく見えないため、Ubuntuの設定で大きな文字を使うようにした。またターミナルではフォントサイズもちょっと大きくしてある。椅子の配置の問題かも知れないが、右上のモニターを見上げるのが一番首に負担がかかると分かった。そこだけ、明確に顔を動かさないと見ることができない。そもそも横にモニターを並べると結構首を動かすことになって辛い、という体験談も聞いたが、僕の机はかなり奥行きがあるので、今まで免れていたのだろう。

昨日発見した、WindowsとUbuntuでプログラムの出力が違う原因を探っていた。実行にそれなりに待ち時間が発生していたので合間合間に本を読みつつ、USBメモリでデータを移してdiffを取る作業を繰り返す。結局昨日予想していた原因はほとんど関係なかった。ライブラリのバージョン違いでもちょっと変わっていたが、最終的に決め手になったのはリストの順番で、とりあえずソートしたら見事に一致した。しかしなぜそれが結果に影響するのかがわからないままである。むしろ影響してはいけない箇所のはずなのに……。

本を1冊読了。「かくりよの宿飯」8巻。大旦那様と再会するまでは剣呑な空気が続くのかと思っていたが、あにはからんや、この巻もそれなりにまったりしていて、安心して読めた。ついに次巻で再会できそうだが、ストーリーが終わるのは10巻なので、まだひと悶着あるのかと戦々恐々としている。

上の段のモニターがスリープで黒くなると、結構視界に入って圧がすごいことを実感した。とはいえ、基本的にパソコンをつけっぱなしで寝る人間なため、スリープを完全に切ると部屋が明るくて困る。

シャワーを浴びて大学生協でラノベの新刊を注文し、日記を書いて布団に移動。

ハーメルンの捜索掲示板をまた漁りまくる。ちょっとでも気になった作品はスマホでChromeのタブに開き、保存している。パソコンのタブはシャットダウンすると復帰する手間がかかるが、スマホだとアプリを落とそうが再起動しようがタブを保存してくれるのでかなり便利。少し前まではかなり神経質にタブを閉じていて、ほぼ常に無の状態だったので、スマホのブラウザでタブを開きまくっている人のことを理解できなかったが、今は読もうとしている作品・読んでいる作品で100個近いタブが開かれている。人は変わるものだ。

1作、最近連載が始まったばかりで毎日更新の良さそうなものを見つけたため、最新話まで追いついておいた。

https://ncode.syosetu.com/n4583he/

逆行転生悪役令嬢もので、財閥を動かす話ということで、かなり「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」に似ている。「現代社会で～」は僕のかなりお気に入りの作品であるから、当然こちらもかなりツボに入った。1話目のあとがきによれば作者は架空史ものを書いてきた人で、なろうで人気の架空史が逆行転生知識チートものばかりであることに対するちょっとした皮肉としていろいろ設定を作ったらしいが、それはそれとして純粋に面白い。

さらに以前読んだなろうを読み返したりした後、午前11時に就寝。

09/15(水)

午後5時起床。ちょっとコードゴルフをした後学食に行き、その足で原付を買った店に行って保険の更新をしてきた。

年齢が上がっただけで保険料が1万円くらい安くなってたまげた。それでもまだ25000円くらいしている。これまで1年に100kmも乗らない原付に対してそれ以上の額の保険をかけてきたのかと思うと、かなりもったいないと感じてしまう。もちろん、たまたま自分が事故を起こさなかったからそう思えているというだけではあるが。

電車に乗ってまた駅前の電気屋に行く。5枚あるうち右上のモニターは見上げにくく、さらにサブマシンに2枚あっても使いどころが少ないことが分かったので、これまでバックグラウンドで垂れ流していた作業用BGMの動画でも表示させておこうかと思うが、そのためにはパソコンから音声を出力できる必要があった。ということで、スピーカーを買う。ついでにUSBケーブルを購入してHHKBを有線でつなぐことにした。bluetoothだとかなり不安定でよく変な挙動をするし、数分操作しないだけで電源が落ち、復帰のために数秒電源ボタンを押さなければならないのもつらい。

どちらも1000円ちょっと。ついでにオンラインゼミのための板タブレットでも買おうかと思ったが、ネットで調べていたより値が張ったので今日は見送る。会計のときにポイントカードを出したら、先週使った金額の10%にあたる1000円弱のポイントが使用できて、かなり安く済んだ。ポイントカードの威力を思い知らされた形だ。

そのあとはゲーセンで深夜まで遊んでいた。最初の数クレは駅前のゲーセンで手元を撮影していた。

Parad'ox 2-0 手元 (1) pic.twitter.com/tY4ByHnAyS
— こたつがめ (@kotatsugame_t) 2021年9月15日

スマホアーム付きの台に待ちができたので移動して新曲のAJ埋めをした。前回ゲーセンに行ったときから狙っていたParad'oxのAJを出せて満足。

Parad'ox AJ！ pic.twitter.com/59wkIIlVCW
— こたつがめ (@kotatsugame_t) 2021年9月15日

最後のほうはHAELEQUINを詰めていたが、どうにも敷地帯ができない。1度など敷地帯以外ほぼAJだったのに、緊張で運指が吹っ飛んでしまった。ノーツが2000ノーツしかなく、赤を100個以上出すので、鳥許容はアタック7個と最近の13+に比べたらかなり少なく、適当にやっていては出ない。でもまあ、今日プレイした感じでは、敷地帯の運指をちゃんと組むことがSSSを出すことの（必要かつ）十分な条件だろう。

帰りにそばかラーメンでも食べようと思ったが、どこの店もやっていなかった。ドンキでパンを買って帰宅。

パソコンにスピーカーを接続したら、マウス操作のたびにゴソゴソと音がする。

スピーカーなんて音出ればいいでしょと思って一番安いの選んだけど、まさか意図しない音も出るとは……
— こたつがめ (@kotatsugame_t) 2021年9月15日

ネットで調べた感じでは、別の回路のノイズを拾ってしまっているらしい？音量を0にしても相変わらず出ているので、これは別のものを買わないとダメかも……と思っていたが、ふと給電用のUSBだけ違うパソコンに差したら解決した。謎だが、別のスピーカーを買わずに済んでよかった。このスピーカーはモニタースタンドにぴったりのサイズなのも面白い。

でもモニタースタンドにピッタリなの面白いな pic.twitter.com/dUB7CUHlha
— こたつがめ (@kotatsugame_t) 2021年9月15日

しばらくコードゴルフをしていたが、最近あまりに何もやっていないことが気になったので、とりあえずECR埋めを進めた。月曜日のECR18-Fはあんまりピンと来ないので放置して、今日はECR19。

Dashboard - Educational Codeforces Round 19 - Codeforces

Aはよい。Bはdpしたが、貪欲でもできないことはなさそうだった。Cは貪欲。Dはsetを持ってマージテクしつつ木dpだが、全然関係ない場所にある同じ値を検出してもよいことを失念して1WA。Eは $k$ が $\sqrt n$ 以上か未満かで処理を分け、前者は毎回シミュレート、後者は前計算。Fは2次元dpを考えて遷移をスライド最小値で高速化。

さらにECR20を開き、A-Eを埋めた。

Dashboard - Educational Codeforces Round 20 - Codeforces

Aは面倒そうな場合分けを考えていたが、書くうちに本当にただの貪欲でよいことに気づいてびっくりした。Bはよい。Cはgcdを全探索して、構築は基本 $1,2,\dots,k$ 全体を定数倍、最後の要素を増やして調節。Dは二分探索。空白とハイフンの扱いは結局のところ一緒なのに問題設定のために別の扱いをされていて非本質的。Eはdp+復元。

Fに詰まったので切り上げて布団に入り、今日もまたハーメルンの捜索掲示板を徘徊する。自分のツボに入った作品の名前で捜索掲示板を全文検索すると、似たような作品を沢山見つけられて生活が破壊されることに気づき、今日はもっぱらそんな感じでやっていた。しかし見つけた作品のタブを大量に開いた後は、前から読み返していたハーメルンの続きを読んでいて、新しい作品には手を出さなかった。

午前11時くらいに寝落ち。

09/16(木)

午後3時から30分おきの目覚ましで意識を取り戻しつつ、最終的に午後4時半に布団を脱出した。

pic.twitter.com/1yPRcYXVMx
— ゲキ！チュウマイ（maimai・CHUNITHM・オンゲキ公式） (@performai) 2021年9月16日

この構文が人気なことは知っていた。一般に広く知れ渡っていると思っていたが、実のところ特別音ゲーマーの間で流行っているらしいと誰かから聞いたのだった。音ゲーの運営がオマージュしたことで、そのことを強く感じた。ネタにするには結構危険な構文じゃないか？と思っていたが、さすがに運営としての自覚はあるらしく、言葉遣いはかなり配慮されていてあまり原型を保っていない。それでも肝は抑えてあって、個人的には評価は高い。

午後5時から1on1。火曜日の夜（水曜日の朝型？）行っていた検証の話をして、これ以上の追加調査はとりあえず必要ないという結論に至った。それ以外に進捗はないため、あとは少しばかり雑談をして終了。会社としてインターン生、より一般にエンジニアが無理なく働ける体制を整えることを重要視しているらしく、僕が生活リズムを崩壊させていても、それでは1on1の時間をずらしましょう……として下さる。以前までの自分であれば、これぞ求めていた働き方だの、やはり生活リズムを整えることは非本質的だのと考えていただろうし、実際そのような思いは今もあるが、自分にとって一概に良いとは言えないことに気づいた。結局生活リズムを崩して進捗を産めなかったとき、その代償を支払うのは自分なのだ。そして、僕は1人では生活リズムを正すことができない……。

しばらくYouTubeを見たりハーメルンを読んだりした後、学食に行って夕食を摂った。帰ってきてからTCB40に参加した。いつものように、日曜日までのコンテストなのでここに問題の感想を書いておく。先に言っておけば、今回は理論値を達成できたものの、最終問題を詰めるのにかなり時間を食ってしまったため、そこの差で優勝はできていなそう。

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

5問目は何でもできそうでちょっとびっくりしたが、結局各要素の出現回数をカウントした。6問目と7問目はほぼ一緒の問題で、両方imos法をやるだけで謎。8問目は $N$ を素因数分解する必要があることに提出直前で気づいて助かったが、その分書き直しに時間を取られた。9問目は明らかだが座圧が面倒だった。10問目はまずディーラーの戦略を整理して勝率を式に表し、適当な範囲で和を取る。範囲を定めるのと式中のmaxの値でさらに場合分けするのをこれでもかというくらい念入りに行っていたら20分もかかってしまったが、その甲斐あって1発でACした。確か時間で点数を引かれるのは想定時間の3割以降だったから、この問題は大体24分、結構危なかったらしい。

日付が変わるまで布団に転がってハーメルンを読んでいたが、今日も何もやっていないため、またECRの続きをすることにした。パソコンの前に戻ってきて、ふと思い立って画面キャプチャのテストをしてみたところ、これまで真ん中のメイン画面をキャプチャできていたのが、いつの間にか左端の画面をキャプチャするようになってしまっていた。調べたところ、regeditでモニタの設定をいったん削除し、改めて番号順にモニターを1枚ずつ増やしながら接続→再起動を繰り返すと正しく設定できるらしい。面倒だったが、何とか真ん中の画面をキャプチャするように戻って安心。

ところで、regeditといえば「人類が増えすぎたので減らしてほしいと頼まれました」というなろうを思い出す。4話目のあとがきにこれが元ネタだったと書いてあった。このなろうは100話くらい読んで放置している。

https://ncode.syosetu.com/n0859fa/

ECRを進める。昨日の続き、ECR20-FGから。

Dashboard - Educational Codeforces Round 20 - Codeforces

Fは昨日、square-freeにして包除したい気持ちになっていた。今日改めて考えなおしてみると、包除に関係する各値は個数さえわかればよく、対応する値にいちいち加算していてもそれほど多くはならない。Gはパッと見厳ついが、区間の区切りだけ取り出して列の圧縮を行うと普通の区間set区間minの遅延セグメント木になる。すぐ気づけてニコニコ。前計算に使用したセグメント木にクエリを投げていてサンプルが合わず、実はsegtree beatsをする必要があったかと焦ったが、そんなことはない。

ECR21。Fは諦めた。GはAho-Corasickのfailure関数を使うはずだが、ライブラリを持っていないので、この機会に作ろうかどうしようか迷ってコーディングしていない。

Dashboard - Educational Codeforces Round 21 - Codeforces

ABはよい。Cは貪欲。Dは左右に分けたとき要素を1つだけ移せると言い換えられるので、分ける仕切りをずらしつつ条件を満たせる要素が存在するかsetでチェックした。Eは重さ3の荷物を何個とるか全探索し、重さ2の荷物の個数で三分探索。

しばらくハーメルンを読んでいた。最近は、今年初めに読了した以下の作品を読み返していた。特に、それまで幻想郷では正体を隠していた世界最強の主人公がその正体を顕わにする緋想天編のラストシーンがお気に入りで、その周辺は定期的に読むのだが、ここ最近は幻想入りのあたりから一連の流れをまとめて読み返していた。やはり面白い。最後までたどり着いて満足。

syosetu.org

朝方、ほかの人の先週の日記を読んだ後、溜めていた自分の日記を書いた。それが終わってからまたハーメルンの捜索掲示板をひっくり返す。今日は「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」で検索していた。えらい似たタイトルが引っかかるなあと思っていたら、この作品の2次創作だったらしい。短編だったのでサクッと読んだ。シン・ゴジラを見ていないのでよくわからないが、文章などそれなりに原作と似ている感じはして、いいんじゃないだろうか。

syosetu.org

ゴミを出して布団に入り、紙の本を少し読み進めて就寝。午前10時半だった。

09/17(金)

午後8時半起床。今日は外せない用事が何もない日だったので、何も気にせず目いっぱい寝た。

大学院に合格したはいいものの、入学意思確認書を提出できていない。今週はもう終わってしまった。期限は09/22(水)である。火曜日あたり徹夜して直接教務課に出しに行きたい。

午後9時20分からyukicoder 314に出た。

yukicoder contest 314 - yukicoder

Aから難しい。XY平面にプロットすると、ひし形内部の格子点を数える問題になる。なんというかギザギザな分布をしていて面倒。45度回してひし形を長方形にしたらいいのかな……と思ってふと、最初から45度回転させておけばよかったことに気づいた。そちらでも求める格子点がギザギザに分布していることに違いはないが、縦横がちゃんと座標と合っているので、真面目にやれば場合分けできる。Bは何も考えずに積と以前の和を持ってdpした。これは2019年JAG夏合宿day1Gで似たようなことをやったのを覚えていた。が、聞くところによると大体の項が正負で打ち消しあって消えてしまうらしい。いやそんな考察いるか？という気分ではあるが、面白さはわかる。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2973

Cは非常に面白かった。コインを加えた時の確率漸化式を求めてみる。Aliceが勝つ確率を $p$ としたとき、 $p$ ではなく $p-(1-p)=2p-1$ から遷移してみると、見事に因数分解できて、最終的な形が各コイン独立な値の積になった。ほぼ同じことだが、 $p-\frac 1 2$ から遷移する方法もあるらしい。こちらは答えへのたどり着き方が少し違う。Dは適当に全探索。

Eはかっこ列を2次元平面の経路に帰着させるやつを行う。二次元平面を斜めにおいて、左端がスタート、右端がゴールとしたとき、ゴールは右端で上からいくらかの区間になっている。足さなければならないかっこの数は、スタートからゴールまでの経路で一番上下にぶれた幅で決まるので、ある場所より上・下にいかないような経路数を求めたくなる。これは2次元平面を斜めに切って反転させるテクニックで計算できる。ゴールとなる区間が下にはみ出ると面倒そうなので、最初は $2M\le N$ の場合だけで解いていた。このとき何を思ったか $M\leftarrow N-M$ としても答えは変わらないと思い込んでしまい、サンプルが合わずしばらく苦しんでいた。気づいて絶望しそうになったが、 $2M\le N$ の場合の答えを何種類か求めることで「全体」引く「 $M\leftarrow N-M$ とした場合の答え」が計算できたのでOK。

本を読みつつ時間をつぶし、日付が変わったぐらいからSRM813。oo-で33位、レートは2480→2443(-37)。Medが遅すぎた。

TopCoder Statistics - Match Overview

Easyは自明。Medは最初にdp[Sの何番目][区間が始まっていない会社の個数][区間が終わっていない会社の個数]を書いた。状態 $O(SC^2)$ で遷移は「区間を始める会社を選ぶ」→「区間を終わらせる会社を選ぶ」で $O(C^2)$ 。これでサンプルが合うことを確認した後、どうやって高速化しようかずっと悩んでいた。実は、今遷移を2重ループで書いているが、1重ループを2回書いても全く同じことができるので、もう4乗になっている。気づいたときは自分の頭の悪さに絶望した。しかしSRM Medの600点の難易度感がよくわからない。今回はたまたま解法ガチャに正解しただけか？

残り20分でHardを読む。たぶん大きいほうから全探索で行けるだろうなという気になり、実際パターンが1桁の場合を検証してみたが、そこで2桁の場合の実装に絶望して諦めた。

ことらんさんの「下水を再利用した街を作る！」シリーズ4本目の動画が投稿されていた。1年くらい空いたのだろうか？今回も非常に面白かった。SRMの残り時間はコメあり・なしで2周していた。

www.nicovideo.jp

チャレンジをコンテストの1部だと認識していないため、コーディングフェーズとチャレンジフェーズの間でも平気でTwitterにコンテストの感想を流してしまう。さすがに直接的なことは書かないようにしているが……。今回のEMは落ちようがないだろうと思っていたが、Medが結構落ちて、システス前から9位くらい上がった。それでも元の順位が低すぎてレートには大ダメージ。Medで包除原理をしていた人が多いと聞いたが、そちらの解法はよくわかっていない。

深夜から昼前までかけて本を読んでいた。「かくりよの宿飯」9、10、11巻。10巻がシリーズ完結で、11巻は短編集だった。非常に面白かった。

まず9巻から。同作者の別作品と多少リンクしているという話は何度もあとがきで目にしていたが、この巻を読んでいる最中にやっと、このシリーズの主人公（津場木葵）と別シリーズのキャラクター（津場木茜）の苗字が同じであることに気づいた。よく描写を見れば、以前の回想シーンに津場木茜らしきキャラが登場していた。髪の毛が橙色という超特徴的な容姿をしているのに、なぜピンとこなかったのだろうか……。

またこの巻で、大旦那様の好物が明らかになる。大旦那様が弁当を食べるときに最初に口にするものだと言われて、そういう伏線が……！と思いつつ9巻の弁当シーンを一通りさらってみると、確かにそうなっている。そういえば1巻冒頭にも弁当シーンがあったな、と思ってそちらも確認したが、残念ながらそのときはれんこんのきんぴらで、9巻で明かされた内容とは矛盾していた。まあシリーズ始めから続くような伏線を用意するのは難しいか。

次に10巻。5巻で登場した敵キャラは物語上のラスボスだったようで、この巻まで嫌らしいことを何度もやっていたが、ついに倒された。伏線という明確な形ではないが、これまでのシリーズで培われた各キャラの特性が存分に生かされてクライマックスを盛り上げており、非常に良かった。大旦那様が天神屋に帰るシーンはなんとも感慨深く、涙が出てきた。そんなシーンでも口調を崩さないキャラのせいおかげで、シリアスな場面にも一つまみの笑いがあるのは、シリーズを通しての特徴かもしれない。

勢いで11巻も読み切った。完結して数年後の話。これまで登場したキャラが総出演で、元気な姿を見ることができてうれしい。いろいろ関係性は変わっていたが、みんなあるべき場所に落ち着いたという感じがした。ただ欲を言えば、もうちょっと現世での話も読みたかったか。主人公と大旦那様が現世で一緒に買い物をしているとき、大学の同級生と遭遇して、大旦那様がキャーキャー言われる……というのは非常に僕好みの1シーンだろうが、回想という形でサッと流されてしまった。天神屋の社員旅行で現世に行くという話が、何度も語られているにも関わらず結局この巻に描かれなかったので、また別の外伝が出るのではないだろうかと楽しみにしている。

さて、2週間とちょっとかけて「かくりよの宿飯」シリーズを読み切った。記憶が新しいうちに同作者の「浅草鬼嫁日記」のほうを読み返して、リンクしている箇所を探してみたいと思う。今は本が実家にあるので、そのうち帰省したらやってみよう。

ECR22のA-Dを埋めた。

Dashboard - Educational Codeforces Round 22 - Codeforces

ABはよい。Cは2頂点からそれぞれ最短距離を求めて、相手よりも自分からのほうが近いような頂点にはたどり着けるので、その中で相手から最も遠い頂点を探せばよい。似たようなことはARC078-Dでやった。Dは2つの部分列を作るのに、現在見ている要素が先頭になっていないほうの部分列の先頭を持っておくdp。問題タグにflowと書いてあってびっくりした。

D - Fennec VS. Snuke

布団に入る。くいなちゃんがミステリー小説を書いたらしいので、読んでみた。一口サイズでいい感じ。様々な可能性が丁寧に潰され、確かに不可能犯罪のように思えたが、解決編で明かされたトリックは割とあっさりしていてびっくりした。多分一番のミスリードは、作中の探偵が誤った結論に達していた部分で、問題編最後の描写も含め素人探偵に対する批判的精神があって面白かった。

くいなちゃんミステリー - くいなちゃん小説

さらに少しハーメルンを読み、午前11時に就寝。

09/18(土)

午後7時起床。

起きてtwitterを見たら、今日の昼頃行われたJOI一次予選の問題が2時間前に公開されていてびっくりした。慌てて解いたが、自明な最短はもうすでに取られていた。AとBはdc、CとDはRaku。Bはテストケースハックで、Dは良さげな演算子を見つけてそれぞれ縮めることができた。

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

午後9時からABC219。今日は7完。序盤にペナを重ねてつらい気持ちになったが、FGあたりをそこそこ速く解けていたらしく、順位表の1ページ目にいた。ただ賞金は逃したようだ。

Sciseed Programming Contest 2021（AtCoder Beginner Contest 219） - AtCoder

Aは面倒。とりあえずAWKで出したらFAだった。直後自明な更新ポイントがあったので1B縮めておいたが、現在の最短は言語から違う。BはPerlで解いた。Cはbashで出したらWA。よくわからない仕様を踏んだかと思ってC++で書き直したが、実は文字を置換する順番が違っていた。

Dは適当にdpを書いたらWA。問題文を読み直したときに、たこ焼きとたい焼きが一瞬同じ単語に見えてびっくりした。しばらく考えて、 $X$ や $Y$ を大幅にオーバーするケースも考慮しなければならないことに気づいた。どうやって書けばいいのかすぐにわからなかったが、しばらくしてオーバーした部分は無視してよいことに気づいた。

Eは面倒。堀をdfsやらで探索するクソ面倒な問題かと思ったが、視点を変えて堀の内側に入れるマスの集合を全探索すればよいことに気づいた。意気揚々と実装して、堀の内側のマスの連結性もチェックし、サンプル1を試したところ、1720が出てしまった。validと判定されたマスの集合を全部出力して適当ににらめっこし、内側に穴が開いたケースが怪しいことに気づいた。問題文からはそういうケースがvalidかどうかよくわからなかった（同じ勘違いで1720が出た人が大量にいたらしい）が、とりあえず省いてみる。省くのも結構難しく、いろいろ考えた結果、周囲1マスを増やして堀の外側も連結になっているか調べることにした。これで再度サンプル1を試すとちゃんと正しい答えが出たので一安心。

Fも面倒。1回の文字列で移動する差分と通過するマスを求めたとき、掃除されるマスの集合は、1回の文字列で通過するマスたちに差分を適当に足した形のマスになる。その重なり具合を調べればいいので、差分をうまく足し引きして通過するマスの座標を正規化し、それの一致を見ることで重なりうるマスをまとめ、それぞれについて差分を何回足した場所のマスが掃除されるかを、区間の和を求める感じで計算すればよい。

Gは最近ほとんど同じ問題を見た覚えがあって、怪しみながら次数の平方分割を書いたら何の問題もなく通った。僕はPASTの過去問（PAST5-O）を思い浮かべていたが、それより典型90問の83問目がよっぽど似ていたらしい。確認したらほぼ同じだった。Hは適当に枝刈りしたら案の定TLEして、なんとなく凸包っぽさを感じたあたりで、残り時間が10分もないこともあって諦めてしまった。

083 - Colorful Graph（★6）

コードゴルフ。Aはdc。BはVimで置換するコードを作って実行するのが短いらしく、Rakuで配列のインデックスを使うコードを書いたがVimより1B長かった。Cはコンテスト中に置換の順番の間違いに気づきbashで提出、その後Vimで出したものが最短。Eは僕のC++が現在の最短になっている。

DはOctaveのglpkで解ける。（ところで、cygwinからOctaveを起動するとやたらめったらオーバーヘッドがかかって非常に重いので、Ubuntuにインストールしてこれからはそちらでコーディングすることにした。）さて、glpkで適当に書いて提出したところ、1ケースREしてしまった。ケースが公開されていないのでなぜ落ちているのかわからない。とりあえず入力フォーマットは正しい。しばらくテストケースの特定作業をした結果、 $N=2$ で答えが $2$ であるようなケースでREしていることが分かった。そこでいろいろ入力を変えて試していたところ、 $X=Y=300$ 、 $A_i=B_i=151\;(i=1,2)$ のケースでglpkがエラーを出すことに気づいた。おそらくglpkのバグだろう。

どうしようもないので、最初は $N=2$ のケースがこれ1つしかないことを利用して、場合分けして直接2を出力するようなコードを書いて通した。その後、入力を増やすことを思いつく。 $A_{N+1}=B_{N+1}=0$ という弁当を増やしても答えには影響しない。残念ながらこの通りの弁当だとREは解消されないが、 $A_{N+1}=-1$ にしたら通った。

午後11時半からCF #743 div.1。ジャッジが詰まりまくってunratedになった。ABが難しくてWAを出していたので助かった。

Dashboard - Codeforces Round #743 (Div. 1) - Codeforces

AはDAGチェックして最長パスを求める問題。ループ検出に失敗して1WA。最長距離が更新されない頂点があったときにループがあると判定していたが、これは誤りで、ループがあってもその外から最長距離を更新される可能性はある。

Bは難しい。基本的には左から貪欲に消していきたいが、左端が1だった場合が困りもの。この場合はそこから右にずっと見て行き、左端から1が続く連結成分のサイズを偶数にできたら（さらにそれが列全体でなければ）OK。最初から連結成分のサイズが偶数の場合はそれでよいが、そうでない場合は途中適宜操作して0を1にしつつ、うまく別の1の場所まで伸ばして、連結成分を1減らすような操作をする必要がある。コンテスト中は、左端がダメでも右端からできるならOKだということで、左右反転して2回チェックしていたが、実は左からだけでよい。左から上記の操作をして列全体になってしまったなら、右から操作してもそうなる。

Bを解いている最中にunratedが決まり、それからはABCに戻ったりして遊んでいたが、情けない結果を残すのも恥ずかしかったので改めて解いていた。Bを通して一度は満足したものの、しばらくしてCも解けたので実装。残り20分もないなかギリギリで書ききって投げたら9ケース目でREした。配列外参照を見つけて修正し、システス後に投げたら通った。Cは基本的には区間dpで、ただし本質的な場所だけ計算する。本質的な場所とは区間の両端が同じ色で塗られているようなもので、そのような区間は謎の制約から高々 $20N$ 個しかない。区間の長さでソートして、以前の結果を使いつつ毎回 $O(N)$ のdpをする。

ABC219-Hを解説を見て通した。難しいデータ構造やアルゴリズムを使うのかと思ったら全然そんなことはなく、ただただ頭のいい言いかえを繰り返してdpに帰着しており、びっくり。僕も区間dpは少し考えたが、距離とスコアを同時に持てなくて棄却したのだった。その距離を、いろいろな言いかえ・計算の分解を経て $O(N)$ 種類の値に収めるのが本質。

朝方ハーメルンを1作読んだ。「創造神が行く幻想の世界」。設定は良さそうだったが文章がカスであまり身が入らなかった。序盤など、もともと台本形式だったものに無理やり地の文を足したらしく、リメイクと称してはいるがただただ読みにくいだけ。オリキャラたちもそれほど好きになれない。ただ、今がちょうど幻想入りしたあたりなので、これからはちょっと面白く感じられる可能性がある。

syosetu.org

布団に入ってしばらくハーメルンを読み、午前11時半に就寝。

09/19(日)

午後4時と4時半の目覚ましでは、意識を取り戻しはしたものの、布団から這い上がれなかった。午後5時ギリギリになってようやくパソコンの前に座った。今日もOpenCup。よくわからないのでリンクは貼らないことにした。

今日はチームで7完。相変わらずチームメイトが強い。明確に得意分野を持っている人という印象で、こんなの無理やろと思っていた問題を通していくのを見てすごいなあと言っている。解法を追っかけているわけではないため自分の身になっていないのがもったいない。僕も2問書いたので先週よりはチームに貢献したと思うが、両方ギャグみたいなものだった。

具体的にはAとHを書いた。Aは真っ先に読んでちょっと考えたが、OpenCupだし激ムズ問題しか出ないだろうと恐れをなして逃げ出した。順位表でかなり通されているのを見て再度考え直し、ギャグの構築であることに気づいた。Hはチームメイトとしばらく考えていたが、まっとうに構築しようとすると頭が壊れたので、適当に生成して埋め込むのをやってみた。案外早く全ケースに対する構築が見つかって、むしろファイル出力だったり、そこから1つのソースコードにまとめなおすほうで少し手間取っていた。僕はサイクルに対角線を張るのを試していたが、maspyさん曰く、ちょっと確率調整したランダムグラフでもすぐ見つかったらしい。

残り時間でGを考えていた。僕は、答えをパターン分けして、それぞれいくらか重複しつつ数え上げたあと、うまく線形和を取ることで答えの値だけ得られないかということを試行錯誤していた。結局それはうまくいかないままコンテストが終了してしまったが、終わる直前にチームメイトが、値を2種類だけ計算することでうまく相殺されるような式を見つけていた。コンテスト後に投げたら通ったらしい。

さて、OpenCupが終わったら直後にARC126だったのだが、その前に、OpenCup中に両親が仙台に来てくれたことに触れておきたい。

結局この夏は富山に帰省しないことにして、代わりに両親が車で仙台まで来てくれた。時間が遅かったので夕食を食べに行くようなことはなかったが、母がラーメンを作ってくれた。自分の部屋のキッチンからまともな料理が出てくることに新鮮な驚きがある。そして、持ってきてくれたお菓子や総菜を部屋に収納し、代わりに既読本だったり大きな段ボールだったりを持って帰ってくれた。滞在時間はかなり短かったが、また近く免許更新のため富山に帰るので、それまでしばしのお別れである。

食事 pic.twitter.com/SEN3bHlAp6
— こたつがめ (@kotatsugame_t) 2021年9月19日

実家に既読本を送るぜ pic.twitter.com/8GG97ZubNV
— こたつがめ (@kotatsugame_t) 2021年9月19日

午後10時からARC126に出た。5完9位。

AtCoder Regular Contest 126 - AtCoder

Cまで通した時点で1位と、序盤はかなりいいペースだった。そういえば先週もOpenCup後にCGR16に出て大成功したのだったか。5時間コンテストの直後はヘナヘナになっていて、別のコンテストに出てもまともに問題を解けないだろうと考えていたが、実はそんなことはないようだ。僕が考えるに、おそらくOpenCupの問題に手も足も出なくて精根尽き果てるほどの考察をしておらず、結果長いコンテストの間にいい感じに眠気が取れ、リラックスし、それでいて頭は競プロモードに入っているのが良い影響を及ぼしているのだろう。あるいはたまたまCGRとARCで得意セットが続いているだけか。

Aは丁寧にやる。考察の流れはこんな感じ：まず長さ $3$ だけ奇数なので2本まとめ、次にすべての棒の長さを2で割る。長さ $3$ の棒とペアにするのは長さ $2$ を1本か長さ $1$ を2本のどちらかで、長さ $1$ を残したほうが後々動きやすくなるため、長さ $2$ と優先的にマッチングする。これで棒が2種類以下になるので、あとは答えまでストレートにたどり着ける。

Bは $a_i$ でソートして実家dpしたい気分になる。 $a_i=a_j$ なる $i$ と $j$ を同時に使わないように、タイブレークを $b_i$ の降順にしておけばOK。Cは、答えが $\max A$ を超えるようならばただの割り算で求まる。そうでない場合は、例えば $g$ が答えとしてありうることは $K\ge\sum\left(\left\lceil\frac{A_i}g\right\rceil g-A_i\right)$ が必要十分だが、この $\left\lceil\frac{A_i}g\right\rceil g$ としてありうる値が $\frac{\max A}{g}$ 種類しかなく、1つ1つ見ながら累積和を使うことで必要な操作回数が求まってチェックが $O\left(\frac{\max A}{g}\right)$ でできるため、 $1\le g\le\max A$ を全探索できる。

Dはちょっとハマった。順列をどれだけ作ったかをキーに持つbitDPをする。見ている要素を順列の外に避けるか、あるいは順列の1部として組み込むか。このうち外に避ける操作の際、作っている順列の左右どちらに避けるかでコストが違うので、両方計算して小さいほうを取らなければならない。ここの処理をよく考えておらず、最初にACしたコードでは左右からそれぞれbitDPして（左から作った順列は左にしか避けない遷移になっている）、最後にマージしていた。マージに $O(K)$ かけたので全体で $O(NK2^K)$ となり、さらに一番内側のループで毎回__builtin_popcountを呼び出していたので、1000msくらいかかっていた。

Eはエスパー。サンプル1の2回目のクエリを考えてみる。数列の全体から $5$ を引いて $(0,0,1)$ であるとしてもよい。これに対し、隣接する2項 $(a,b)$ を $(\frac{a+b}2,\frac{a+b}2)$ にする、という操作だけ何度か繰り返してみた。すると $(\frac 1 4,\frac 1 4,\frac 1 2)$ が得られ、点数は $\frac 3 4$ 点となる。また全体から $\frac 1 4$ を引くと、元の数列を $\frac 1 4$ 倍した形になっていることに気づく。つまり、この数列に対する $f(n)$ の極限は $\sum \frac 3 4\times\left(\frac 1 4\right)^i=\frac 3 4\times\frac 1{1-\frac 1 4}=1$ と計算できて、サンプルの値と一致する。

3回目のクエリも考えてみる。今度の数列は $(0,1,2)$ 。初手で $(0,2)$ を選んで操作すると $1$ 点で終わってしまうことから、どうやら一般にソートしたときに隣接する2項を選ぶのが最適なように感じられる。とりあえず $(0,1)$ で操作すると $(\frac 1 2,\frac 1 2,2)\rightarrow(0,0,\frac 3 2)$ で点数は $\frac 1 2$ 点。ここで、先ほど $(0,0,1)$ から $1$ 点が得られたので、両方 $\frac 3 2$ 倍することで $(0,0,\frac 3 2)$ からは $\frac 3 2$ 点が得られることがわかる。実際 $\frac 1 2+\frac 3 2=2$ となって、こちらもサンプルの値と一致する。

ここでエスパーをする。与えられた数列をソートして、隣接する2項をならす操作だけ考えればいいのではないだろうか？しかもそれは左から順に行われる。いかにもよさそうな見た目をしているので、これで考察を進めることにした。まず、点数を計算するために、 $(0,0,\dots,0,1)$ をならすとどれだけ加点されるかを計算することにした。 $(0,1)=\frac 1 2$ 、 $(0,0,1)=1$ 、 $(0,0,0,1)=\frac 3 2$ 。どうやら数列長に対して線形らしい（ここもエスパーしたが、右端の $(0,1)$ を $(\frac 1 2,\frac 1 2)$ と操作することで帰納的に示せるようだ）。

さて、先頭 $i\;(2\le i\le N)$ 項をならすことを考える。先頭 $i-1$ 項はならされているので、その値は平均、 $\frac{\sum_{j=1}^{i-1}A_j}{i-1}$ 。これを先頭 $i$ 項から引くことを考えると、先ほど点数を計算した数列の定数倍になるので、得点もその定数倍、具体的には平均を引いた後の $A_i$ を $\frac{i-1}2$ 倍した値になる。まとめると、ソート済み数列に対する答えは $\sum_{i=2}^N\frac{i-1}2\times\left(A_i-\frac{\sum_{j=1}^{i-1}A_j}{i-1}\right)$ となるようだ。

適当に $\sum$ を分解することで、 $\frac{-N-1}2\sum A_i+\sum A_i\times i$ を得る。これは1点変更が発生しても差分を考えれば更新できる。ソート済み列に対する挿入・削除を実現すればよくて、挿入は、自分に振られるインデックスを求めて掛けた後、それより後ろにある要素はインデックスが1増えるので、値の総和だけさらに増やす。BITで要素の分布と分布に対する値の和を持つことで計算でき、削除も同様。今回は値が大きいのでクエリ先読み＋座圧が必要。実装して、サンプル2は $N=2$ なのであまりあてにならないがとにかく答えが一致することを確かめ、提出。

WAを食らって絶望してしまったが、オーバーフローだった。答えのmodを取らなければならないことに終盤気づいて、出力の部分だけ書き換えたのだが、値を保持する変数もmodintにしておく必要があった。値とインデックスの積の和は最大で $\frac{N^2}2\times 10^9\approx 4.5\times 10^{19}$ くらいになる。