07/05 (MON)
9:30 起床。鬼のように身体が重い。おそらく副反応の最後っ屁だろう。 昨日は $ 38.4 $ 度もあったのに全然元気だったのが嘘のように怠いし、頭痛もした。 先日に「 $ 38.4 $ 度あるけど元気だぜ」みたいなツイートをしてしまった手前 Twitter で体調不良ポストをするのが躊躇われた。 情けないぜ助けてくれ。
布団から出られる気がしないし、スマホで典型を確認する気にもならない。 $ 30 $ 分ぐらいゴロゴロした後、今日がゼミであることを思い出す。 流石に出られない可能性が高そうなので、欠席の旨を連絡しておいた。
メール送信ついでに BOX を確認すると、返信の必要な大事なメールが来ていたため対応する。 それだけしたら、食欲もないのでまたベッドに逆戻りした。
12:30 ぐらいになんか回復してくる。頭痛も和らいだし腹も減ったので、街に繰り出して昼食を探す。 昼食探しが下手すぎて、マクドナルドに行きついてしまう。 せっかく元気になってきたのでモバイルオーダーで迅速に注文してなんとか 13:00 のゼミに間に合うようにしたいというねらいもあった。
マックに到着するともう品物が用意されていた。目視できる距離で作り始めてもらったのに速すぎないか？すごい。
受け取るときにアンケートに答えてほしいみたいなことを店員に言われた。 滅茶苦茶早く購入が済んだのでクーポンももらえると言うので答えることにした。 訪問した店舗では、テストで「キオスク」なる端末を置いているらしくて、一般的な質問に加えてそれについての質問があった。
どうやらこの「キオスク」、海外ではもうすでに導入されており日本でのテスト導入が始まったとか。 機能は割と見たまんまで、この端末をタッチして注文をすることができる。 まあ言ってしまえばちょっと機能の多いセルフレジである。
ちなみに余談だが、自分が購入したのは当然のように、トリプルチーズバーガーである。 チー牛の匠なのでこのバーガーの復活期間にこれ以外注文するつもりは毛頭ない。
ちょっと失礼なのだが、ゼミを聞きながらマックを食べた。発表練習回なのと欠席連絡をしたので許してほしい。 あと今の体調だとナゲットが余計だったので頼んで後悔した。
ゼミが終了する。先週分の週記を投稿し忘れていたことに気が付いたので、投稿する。 そのあと Twitter を見たり、先日の ABC をちょっと真剣に振り返ってみたりした。 精進を真剣にするような体力がないので、ダラダラしていた。
20:00 から友人と用事（オンライン）の約束をしていたが、一時間伸びたので夕食までは本当にグダグダしていた。 今日に関しては本当に体調が悪くてだらだらしていたのでしょうがない。
夕食を食べて 21:00 から zoom に繋いで話す。
それすら終わると本当にやることがない。正しくはあるけど、今の元気さで出来ることがなくなる。 仕方がないので（？）追加されたというボルテの 19 の譜面でも見ることにした。
簡単と TL で言われている割には難しく見えた。 とはいえ、$ 2 $ 回目再生するとやっぱり PUC できそうな気もしてきたのでやらないとわからないかも。
そんなことでベッドに向かうのだが、本日は根つきが今年一番悪く最悪の夜だった。 明日は 9:30 - 18:30 勤務の something（詳しくは言わないでおくがインターンではない）の初日なのでマジで心配になった。
07/06 (TUE)
8:30 起床。全然眠れなかった。ゲボほど眠い。というかゲボ。 流石にやばいと思って $ 30 $ 分追加で寝る。 起きる。まだゲボほど眠い。助けてほしい。
とりあえず朝食を食べる。9:30 を迎えたので、作業に着手する。 進捗がゴミというか、$ 1 $ ㌨㍍も集中できなかったので昼休みの時間を前倒しで使用して仮眠をすることに決定。
なんとか起きていられるようになったので、作業をする。とてもつらい。 先程の時間の代わりに昼ごはんはマッハで食べる必要がある。あまり覚えていない。
そんなこんなで 18:30 までやった。正しくはボケてて 19:00 ぐらいまでやった気がする。 30 分で何かを生み出せたわけでもないので、どうでもいいが。
散々な日だった。 Twitter を見ると sak さんが以下のような自作問題ツイートをしていた。
{1,2,...,N}の空でない部分集合は2^N-1 個ありますが、このうち部分集合の中央値がKのものはいくつありますか。
— sak (@sak_algo) July 6, 2021
制約
1≦K≦N≦3000
水〜青diffくらい？
ふむふむ。中央値の定義次第で細かいところは変わるだろうが、なんにせよ二項係数の積の和を求めれば良さそうだ。これをすれば前計算で階乗とその逆元（素数 $ \bmod $ の世界で答えることを想定している）を求めてしまえば、全体 $ O(N) $ で求まりそうだ。
因みに、二項係数の積の和という形は結構非自明に $ 1 $ つの二項係数に落ちがちな気がする。理由がわからないので適当を言っている。D - Binomial Coefficient is Fun とかまさにその波動を感じる。 頭がよくないのでこういうのを見たらとりあえず Wolfram|Alpha: Computational Intelligence に投げることにしている。今回のもちゃんと $ 1 $ の二項係数になったのでめでたしめでたし。
一応意味を考えてみると、グリッドの最短経路数問題で二項係数を考えると、二項係数の掛け算はある中継地点を通る時の経路数になりそうだ。とすると、式をよく見ると単一始点単一終点の最短経路数問題の答えと和が一致することが確認できる。
この形の二項係数の変形って式から行くより意味を考えた方が却って分かり易いことが多いと思う。
その後、Streak のために C - 蛍光灯 を開く。
問題概要。$ L $ メートルの廊下があって、$ N $ 個のライトで廊下を全て照らしたい。$ i $ 番目のライトは左から $ l_i $ から $ r_i $ メートルまでを照らせて $ c_i $ だけ使うのにコストがかかる。最小のコストで廊下全てを照らせ、という問題。
見た瞬間困惑した。これ自分が初めてからの ARC 級のコンテストで全く同じの出題されたぞ。解法は簡単で $ r_i $ でソートして左から照らしていくことを考える。$ [l_i, r_i) $ まで照らせたときの最小コスト + $ c_i $ で $ r_i $ まで照らせた時の最小コストを更新するような DP をすれば $ O(L \log L) $ で解ける。 ちなみに全く同じ問題というのはこれ→D - Shortest Path on a Line
明日も 9:30 - 18:30 なので就寝。
07/07 (WED)
8:30 起床。生活リズム自体は勤務によって正されていていいかも。 今日は死ぬほど眠くはない。助かった…
朝食を食べてから 9:30 に作業を開始する。 12:30 から昼休憩に入る。進捗は正直微妙だが、昨日に比べれば…
今日はピアノの稽古があるので途中の非勤務時間を通常の $ 1 $ 時間から $ 3 $ 時間にした。 母親が昼食を用意してくれていた。ソース焼きそばがメインで他は残り物だ。美味しかった。
さて、稽古までの時間はウォーミングアップが必要なので練習をしていた。
ついに目的地の目前で大ゴケしてしまった。 その際に左手首を負傷した。
週記（2021/06/28-2021/07/04） - むかでの競プロ備忘録
正直この一週間は先週のこれのせいで左手首を少し捻ると痛いので練習ができなかった。 $ 1 $ 時間程度で何ができるのかと泣きながら練習をしたが、$ 2 $ 時間分ぐらいはうまくなったかも。
帰ってきて、ちょうど $ 3 $ 時間なのを確認して作業に戻る。 読んでいる論文の $ 1 $ つが面白くて賢く、非常に良かった。
さて、18:30 になって一息つく。 具体的にはインストールしている漫画アプリの動画広告を再生しまくって無料ポイントをむさぼる時間にしていた。 複数の漫画アプリを入れて毎日動画を再生しまくると結構馬鹿にならない量のポイントがゲットできる。
夕食前に、今週の週記は開始が副反応で全然書けていなかったため、Google Chrome の履歴を開きながらその日あったことを思い出しながら書いた。 基本的に Twitter か Chrome を開いているため、両方を確認すれば自分がその日何を考えて何をしていたかが大体わかる（危険だろ）。
夕食中と食後、母親が佐々木蔵之介主演の「サイバー捜査班」みたいなドラマを見ていたので一緒に見る。 ツッコミどころがないわけではないが、そこはフィクションなので粗さがしをするのは野暮というものだろう。 とはいえ、こういうのはあまりにもお粗末だと興ざめしてしまうのだが、ストレスは特になく受け入れられるものだった。 強いて言えば主人公の一人の女性刑事がちょっと邪魔をしてきて鬱陶しい場面が少しあったぐらいか。
そういえば、今日は Codeforces のコンテストがあった気がする。 その前に Streak をつないでおかねば。今週が典型 90 の最終週なのでそちらも処理したいが Streak はモチベの一つなので切るわけにはいかない。
Streak をつないだところで、Dashboard - Codeforces Round #730 (Div. 2) - Codeforces をやる。
A 問題。$ 2 $ つの正整数があって、両方に対して $ +1, -1 $ する操作が任意回数できて、$ \gcd $ を出来るだけ大きくする問題。 差が一定が自明で、$ \gcd $ は差の約数であることが有名なので差になるようにする。
B 問題。長さ $ N $ の数列 $ A $ が与えられて、総和が変わらないように再分配し、$ \sum _ i \sum _ j | A_i - A_j | \quad (i<j) $ が最小になるようにして最小値を求める。 均等に配るのが最適と簡単に証明できる。最後の一周配られる数を $ x $ とすると答えは $ x (N - x) $。
D 問題。部分点がある。$ a \oplus _ k b $ を $k$-itwise XOR ということにして、これは $ k $ 進数にして各桁ごとに $ \pmod k $ の和を取るという演算と定義される。$ 0 $ から $ N-1 $ のパスワードを $ N $ 回使って当てるというインタラクティブ問題なのだが、$ 1 $ 回外すと、元のパスワードを $ x $ 、間違ったパスワードを $ y $ として $ x \oplus _ k z = y $ のような $ z $ に変更されてしまう。
D1 は $ k=2 $ で固定。これにより $ \oplus _ k $ は $ \oplus $ になって、$ z = x \oplus y $ 今までの $ y $ の累積 xor を持っていれば元々のパスワードが $ 0,1,2, \cdots $ の順に検査できる。
D2 も基本方針は同じ。ただ $ k=2 $ の時と違ってしっかり符号を考えなくてはならない。$ z = y \ominus _ k x $ のように書ける。元々の演算が各桁の和なので逆も簡単に定義できる。計算量を小さくするために $ y $ の方を累積させていきたいが、結構符号合わせが面倒でしばらく地蔵になっていた。
C 問題。解けね～。参っていた。しかし TL を見ると自分がボツにした「 $ p $ 以外の確率の状態を持てば十分で、$ Invalid $ が出るまでは $ \frac{v}{2} $ 刻みだし状態数は見た目より制限される」という解法がはびこっている。は～これは $ v $ がちっちゃかった時に結局状態数 $ 10^{8} $ ぐらいは余裕で行きそうだなと思ってあきらめたのだが、よく問題文を見直すと $ 0.1 \leq v \leq 0.9 $ と書いてある。ゴミ～～～。 これだから俺は同じ単位・次元の数値で、$ 1 $ つだけしれっと入力制約のところで弱い制約になっているのを許せないんだよね。 せめて太字にしませんか？
明日も勤務なのでシステス待たずに就寝。
07/08 (THU)
9:00 起床。結構危ない。朝食を食べて、作業開始。 とはいえ、今日は 某大学 O岡山キャンパスに行くので 11:30 ぐらいには中断して家を出た。
目的のキャンパスに到着すると、時間がちょうど昼時になっている。 なんか前言った場所では昼休憩の時間だった気がするので、ちょうどいいし自分も昼飯を食べてから部屋に向かうことにした。 麵屋こころの本店がここにあるらしいという情報をキャッチしたので、向かう。
麵屋こころ自体久々に食べたのよう沁みる。 本当に美味しかったのだが、ちょっとした方針で店員同士が揉めててちょうどその間が僕の座っている位置だったのだけが困った。 麵屋こころのまぜそばはかなり美しいのでブログに記録したくなるな。
色々あってかなりかなり帰りが遅くなる。 もっとチャチャっと終わる用事だと思っていたのでかなり疲れた。
20:00 ごろ、帰りの電車で TCO の話題になっているのに気づく。 そろそろ TCO Round 3 の時期かと思って CLIST を確認すると、7 分後とかなっていた気がする。 マジで心臓がなくなった。 因みに普通に電車内なのでもうどう抵抗することもできずにそのまま諦めた。 クソみたいなスケジューリングミスで大切なコンテストの出場失敗するのは金輪際辞めたいと思った。
帰って失意のまま夕食をたべた。 そのまま就寝しようと思ったが、自分がかなり解釈に困っていた E - White and Black Balls についての話題が Twitter であったら熨斗袋さんが鏡像法で考えると分かり易い（？）旨のリプライをいただいた。 鏡像法って言うと、あの $ 1 $ 年の頃に物理学をやっていて、鏡像の点電荷を想定することで見通しが良くなるような計算手法だった気がするなあと思いながら 結局どこら辺が嬉しいのかいまいちわからず、その旨を返しておいた。
どうやら、鏡像法についての何かを書いてくれるようなので勝手にかなり期待している。
07/09 (FRI)
11:20 起床。勤務じゃない日なので当然起きられない。こういう日もちゃんと起きられる体になりたい。 今週は色々なことがあって疲れた。こんなことで疲れちゃだめだと思っていても疲れたので、朝飯を食べたら 読んでいないで溜めてしまった漫画作品の消化などをする。
先日、潮が舞い子が舞いの最新刊が 7/8 に発売されていることに通知で気づく。 即刻購入する。ジャンプは紙派なのだが、すべての読んでいる漫画を紙で持っているのは割と無理があると思ったので新しく買い始めた漫画は殆ど電子書籍版を購入している。
潮が舞い子が舞いは確か部隊は兵庫のあたりの田舎の高校生たちの話で、ジャンルで言えばいわゆる登場人物がたくさんいるタイプの日常系だ。自分はキャラが多い日常系作品は取っ散らかってて苦手なのだが、この作品は各キャラごとの関係性がちゃんと描かれていて、ナマモノな感じがとても好みだ。ついでにナマモノ系作品ってシリアスだったりして読んでいてつらかったりすることが多いのだが、この作品はシリアスすぎず（というがギャグなので）かなりこの作品からしか摂れない栄養素があると思う。
なぜこんなことを記録しているかというと、金曜日は週記に各内容がないよう、なのだ。 いつも通り 14:30 から TA をして、それが終わったら続きでゼミがある。 それを終えればもう 19:00 前とかそんなんなので、字に起こすとかなり退屈な曜日だ。 当然だが、ゼミで面白い論文が読まれれば、ちょっと調べものをしたりしてそこそこ知識が増えたりもするので 字面ほど退屈な日ではない。
夕食後、確認を忘れていた怪獣 8 号をチェックする。 現在、隔週連載になってしまっているのでもっと大切に読むべきかどうか悩んでいる。 大切に読もうと思った結果、確認を忘れまくってもう話がどこまで進んでいたのか忘れてしまうケースもあるので本当に悩みどころである。ちなみに SPY FAMILYはためすぎてこれになっている。
夕食後なにかをしようと思っていた気もするが、特に書くほどのことはしなかったように思う。
一応 D - サプリメント を解いた。
問題概要。サプリメントが $ N $ 個あり、$ M $ 種類の味ある。サプリメントには $ 1 $ から $ N $ の番号が付けられており、若い番号順に高橋君は摂取する。$ 1 $ 日にいくつでも高橋君は摂取することができるが、 同じ味のものは飽きるので食べられない。この時、すべてのサプリメントを食べる食べ方は何通りあるか。$ \pmod {10^{9}+7} $ で答えよという問題。
$ N,M \leq 10^{5} $ という制約。まあこんなものは DP で考えればいいので考えると、特に持つべき情報がなさそうで一次元の DP が見える。ただし、高橋君がその日にどれだけのタブレットを食べるかが遷移なので、遷移が $ O(N) $ になってしまい計算量が $ O(N^{2}) $ になる。ちょっと考えると、「被りがないよう連続領域を取る」みたいなのは尺取り法の典型だ。ある左端を固定したときの被らない区間を求めてそれに全て遷移することになる。遷移が連続区間なので、高速化はどうとでもなる。セグ木系を使ってもいいし、今回は区間に対して加算の寄与なのでいもす法っぽく DP をすると速い。 いもす法っぽく DP をするときは初期化に注意したい。$ dp[0] = 1 $ だけでなく $ dp[1] = -1 $ も必要だからだ。
やる気が起きな過ぎて親の酒を強奪して飲もうと思ったが、全然缶のものがない。 去年家で作られた梅酒がまだ少しあるので、それを飲むことにした。 コップの半分もなかった。かなりひもじい。
さて明日は学科の発表系イベントが 10:00 からあるので就寝。
07/10 (SAT)
9:55 起床。アラームをかけ忘れていて起きた瞬間、心臓がブラジルまで行った。 なんとか学科のイベントに間に合う。 本来自分が出ても意味ないだろみたいなイベントとはいえ、出ないと怒られるので本当によかった。
このイベント、M2 の中間発表などに対して M1 が質問をしなければならないのだが、研究室の違う（専門の違う）M2 の先輩の研究なんて質問が出来るほど理解できるわけないだろと思う。というかそれがどこの馬の骨ともわからない M1 に理解されていたら、そのテーマで修士号をもらえるか怪しいだろ。
愚痴を言ってもしょうがないので、速攻ノルマである $ 3 $ つの質問をこなした。 ところで、今日はついうっかり昼過ぎに散髪の用事を入れてしまったので質問もこなしたし、つないだままちょっと抜け出した。 大分スッキリした。帰ってきてもまだイベントを続いていたので安心した。
イベントが終わる。ここで、週記を溜めていたので現実に追いつかせておいた。
せっかく散髪したので、枕カバーについている死んでいった毛たちをコロコロで丹念に処理しておいた。 結局その夜寝たら髪の毛が付着しまくった…
夕食を食べ終わって、のんびりしていた。 ABC を完全に忘却していた。やっちまった…。完全に日曜日だと思っていました。
$ 50 $ 分遅刻ぐらいで問題を見たが D 問題まではすぐに解けた。C 問題がいつもより難しく感じた。 E 問題がむずそうだった、時間が足りなかったが多分解けているので時間が出来たら書こうと思う。
悲しい気持ちになったので、Div.3 を出ないで寝ることにした。
07/11 (SUN)
8:30 起床。今日は友人宅に行くことになっていたので支度をして出かける。
詳細は省くが、今日は友人宅に行って昼夜はスパイスカレーを作って食べた。 正しく言うと、俺はスパイスカレーの知識が全然ないので観察担当者です。
久々に高校同期の友人に会えたので満足しながら帰宅。 コドフォ Div.1 があったらしいが気にしない。というかそれに出ないことをなんとなくわかって今日は過ごすつもりだったので。
帰り道に Twitter を見ると、典型 90 の閉会式をやっていた。E869120 さん、お疲れ様です。 というわけで、一応帰宅してから週を終えることができた。
ちなみに、友人宅で競プロの問題を少し解いたので Streak に関しては心配がない。
D - 一刀両断 がその $ 1 $ つだが、これ普通に難しく感じた。
まあ、自分の場合は幾何ライブラリを整えているので、線分同士の交差判定をすれば良いのでいいが、0 から作ると大分しんどそう。
ccw をソラで実装できるし、まあそうでもないかな。よくわからないです。
東京に行くと疲れるのか、毎回就寝がちょっと早くなる。
