09/06 (MON)
11:00 起床。たまたま勤務がなかったことをいいことに寝散らかしていた。 朝食を食べて先週の週記を書き上げているうちに、ゼミの時間になる。
ゼミが終わって、週記を投稿すると、もう 14:00 を回っていたので慌てて昼飯を食べる。
昼飯が終わってからしばらくは YouTube でカプリティオチャンネルの動画を見漁っていた。 クイズ系の YouTube チャンネルなのだが、面白い。クイズ系なら Quiz Knock という人も見て欲しい。なんていうかネタのこすり方が、若者とは違う感じでとてもいい。ジャンルが好きな人は両方見ると良いと思います。
さて、しばらく休憩したあとに競技プログラミングをする。主に upsolve の活動なのだが、昨日の Codeforces の E で完全に詰まってしまった。方針は立っているのに、添え字関係で発狂寸前まで追い込まれている。
一応週記が別記事なので、改めて問題概要。長さ $ N $ の整数列 $ A $ が与えられる。 これに対して以下の $ 2 $ 種類のクエリが与えられるので、処理をする。
- $ x, y $ が与えられるので、$ A _ {x} = y $ の代入を実行。
- $ l, r $ が与えられるので、連続部分列 $ [l, r] $ の連続部分列の中で、単調非減少のものを数え上げて出力。
しばらく悩んでいて、平衡二分木をふんだんに使うことでなんとか $ O(N \log N) $ ぐらいにできそうなことがわかった。 数え上げの考察をする。連続する長さ $ M $ の単調非減少列が存在する（それ以上は左右に伸びない）と、その中には $ M(M+1)/2 $ 個の連続単調非減少列が存在することがわかる。 よって、それ以上延ばせない単調非減少列の区間を管理することを考えると良さそうだ。 区間を管理するのは骨なので、$ A _ {i} > A _ {i+1} $ であるような $ i $ を平衡二分木に追加すると少し楽かも。 ただし、場合の数が長さに線形でないので区間内の和を求めるのにも工夫が必要だ。 区間ごとに事前に場合の数を平衡二分木に追加しておく（インデックスは上記の平衡二分木のものと同期させる）。 こうすることで、$ l,r $ の両端でしか中途半端な区間は存在しないので、場合の数の区間和を平衡二分木で出すようにすれば $O(\log N) $ で出力クエリに答えることができる。
更新が厄介で、更新する前後をチェックして平衡二分木のノードを削除したり追加したり更新したりが必要。 こちらの添え字が合わなくて発狂している。これを通した後で想定解を読んでおくことにしよう。
そんなこんなでピアノを弾く。週末、あまり弾けていなかったせいかゴミのように下手くそになっていた。 それでも死ぬもの狂いで戻そうとするも、本日は撃沈。発表の日が近づいていることもあり、マジで精神衛生が最悪になる。 他の人がつらく思うようなことでも普通に生きていることが多いがピアノはかなり自分という存在の根幹にある趣味なので これが下手くそだと一気に自己肯定感が低下する。最近複数の趣味を回せていないので一つ壊れると非常にマズい。 助けちくり～
食事を食った後はしばらく精神安寧を測るためにネットサーフィンなどをして本当になにも考えないようにしていた。 メンタルが回復してきたので、週記の編集をする。
E がついに通る。ぐえ～。方針があっていることが確認できたので耐えかな～つってる。 1600ms 越えているのでなんなら落とそうと思われていた解法の可能性すらある。 とは言え、自分が競技用に使っている平衡二分木は古に書いた Treap なので今度書き直そうと思う。
Submission #128054919 - Codeforces
精神衛生が明らかに悪いので、明日の欠勤にしようかかなり迷っている。多分すると思う。
09/07 (TUE)
8:30 起床。欠勤の連絡を入れる。 精神衛生を回復すべく、ネットサーフィンと YouTube 徘徊、漫画閲覧をする。 どんな時でもこの $ 3 $ つだけは楽しいので助かる。 精神が疲れていない時は無為にこの動作を続けるとむしろ自己嫌悪するが、こういうときは頭が空にできて良い。
少し作業をしたのち、昼食の時間になる。せっかく欠勤したので外食をしようと思う。 近所においしいうどんを食べられる店があるので、カレーうどんを食べる気マンマンで出かけると臨時休業の張り紙が。 この店の定休日はしっかりと把握していたが、臨時休業は予知できないな…
しぶしぶ唐揚げ専門店で唐揚げを購入して、家に残っている白米とサラダと一緒に食べた。 専門店の唐揚げを食べたのは久々だったのでこれはこれでよかったなと思った。
美味しいものを食べて満腹感を得て少し休憩した後、精神衛生が悪くなったところのピアノをしばく。 そもそもこれが下手なままだと、胃痛案件はいつまでも続く。 $ 3 $ 時間以上弾き続けてなんとか、耐えレベルまで持ってくることができた。 これなら後 2 週間あればギリなんとかなりそうだ。
安堵したところで夕食を食べる。おいしい。 CLIST を確認するも、自分が参加する予定のコンテストはないようだ。 明日（水曜日）には Educational Codeforces Round があるので、しっかり覚えておこう。
昨日通した週末の Codeforces の E 問題の想定解法を見る。 なんかをセグ木に載せることによって頑張っているっぽいが、詳しく書いてあるわけではないのでパッと見ではわからない。 Standings をみると SSRS さんが凄い速さで通していたので、この解答を見る。 なにやら行列を載せている様子。ちゃんと見ていたわけではないのであとでちゃんと理解しておこう。
ここにきて今週のジャンプを購入していないことに気が付いた。 急いでコンビニに買いに行くも、売り切れ。実はこれには裏話があって、最近コンビニが改装工事のために 1 店舗しまっているのだ。 便利な場所にあるコンビニなので、もう一方のコンビニの方にジャンプ購入者が集まってしまった結果だと思われる。 毎週本誌を購入しているのに今週だけ電子というのも癪なので、次に近いコンビニを探す。 $ 1 $ km ある。雨も降っていないしこれなら走っていくぜ！といって走る。 しっかりとジャンプを購入していくも、往復 $ 2 $ km をまあまあな速さで駆け抜けたので汗をかいてしまいそのままシャワー。
そのあとは母親が見ているドラマを盗み見たり、ジャンプを読んだりして過ごした。 就寝。この一日、好き放題して過ごしたのでむしろ平常時より元気いっぱいになった。
09/08 (WED)
10:00 起床。アラームをかけ忘れました。幸いにも今日は早く起きる必要がなかった。 朝食にチョコクリームブッセを食べた。 こういうのが一番朝の胃に負担をかけなそうとちょっと思った。
昨日の好き放題が癖になってしまい、昼食までベッドにひっくりかえってスマホ弄りとジャンプの続きを読んでいた。
昼食を食べた後に少し休み、ピアノの手ならしをしてから教室に向かう。
少し乱れている箇所が目立ってきたことを指摘される。
リズム練習などの筋肉に負担をかける練習をやりすぎではないかと言われた。図星だ。
どうやらこういったことをやりすぎて、疲労や妙な癖から乱れが出始めている可能性が高いらしい。
今日明日はゆっくりとした練習をしてクールダウンするように言われた。
やっぱり腕が熱を持ちまくるような練習はダメか。
帰宅。そろそろ好き放題に時間を使えるフェーズは終了した。 某で与えられたタスクの消化の続きをすることにした。ふと見たら slack で某の方からちょうどのその通知が来ていた。 タイミング良すぎてワロタ。
夕食後はだらだらもこうの動画などを閲覧していた。 昔のもこうの情緒やばすぎて笑い狂うかと思った。 厨ポケ狩り講座、今見直すとえげつないぐらい活舌が悪い。
コドフォの時間がきてしまう。明日はただの平日だけど、でちゃうか。
Dashboard - Educational Codeforces Round 113 (Rated for Div. 2) - Codeforces
A 問題。$ a $ と $ b $ から構成される文字列が与えられ、各文字の出現数が等しくなるようなセグメントを $ 1 $ つ出力せよという問題。 普通に隣接が異なったところの $ 2 $ 文字を切り取ればよい。
B 問題。 $ N $ 人がリーグ戦を行う。二種類の人がいて、「 $ 1 $ 回も負けたくない」と「 $ 1 $ 回は勝ちたい」。全ての選手の希望通りになることはあるか判定せよ、という問題。 負けたくない人は負けることができなくて、勝つことのメリットもないため全て引き分けで良い。 となると、実質もう一種類の人だけでリーグをしているとみなせる。$ 1 $ 回は勝ちたい人はジャンケンのようなサイクルの勝敗関係があれば全員満たせそう。$ 1,2 $ 人でサイクルを作ろうとするとリーグ戦の概念が壊れる。よってそこだけ NO にしてほかは vector にでも入れておいて巡回構成すればよし！YES 出し忘れて時間を無駄にした。
C 問題。(ランダムに) $ 1 $ から $ N $ までの番号が付けられた $ N $ 人の審査員がいて、それぞれ共有したいタスクを $ A_{i} $ 個持っている。 番号が若い方から順番にターンを巡回させてタスクが残っていたら共有することを続ける。 連続で同じ審査員がタスクを共有することのないような審査員への番号の付け方は何通りか、という問題。 まず最大値が $ 2 $ 番目に大きい数より $ 2 $ 以上大きかったら、どうやっても $ 0 $ 通りだろう。 また最大値が $ 2 $ つ以上あっても自明で、$ N! $ である。(本番うっかりこれを挟む場所を間違えて発狂していた) つまり最大値が $ 1 $ つしかなく、次に大きい数が最大値より $ 1 $ だけ小さい場合のみ考えれば良い。 次に大きい数以外の順序はどうでもいい。最大値 + 次に大きい数の中で最大値が最後に来るとまずいことがわかるので、そのように場合の数を計算する。まあ殆ど階乗。
D 問題。グリッド平面の問題。縦に無限に伸びる道 $ N $ 本と、横に無限に伸びる道 $ M $ 本がある。 道の上に $ K $ 個の点が存在していて、点のペアの内マンハッタン距離より道を辿る最短距離の方が長くなっているものを数える問題。 まず交差点にある頂点からは任意の点へマンハッタン距離で移動できるので除外。
ここからは面倒なので水平線のみ考える。 横のレーンが異なるような点へもマンハッタン距離で移動可能。 よくよく考えると縦のレーンのみが同じ点の組み合わせのみを数え上げればよい。 二分探索とかして実装すれば良いが方針を間違えるとやや面倒くさい。 本番は面倒な方針を選んでしまったら、うっかり縦横両方同じレーンにいるペアも数え上げてしまい発狂。
AtCoder のぬるま湯につかっていたら気が付いたら普通の競技プログラミングができなくなっていたので反省。 E を考える時間がないのはどう考えてもダメだな。 グロフォでは勝つぞ～。就寝。
09/09 (THU)
8:00 起床。
昨日のコドフォは実装方針が中々だめだったので、実装を書き直したり人のを見たいしながら週記を付けていた。
D 問題の実装方針正解は、各セグメントに対して座標を与えてそれをキーとする map を持っておくことだったっぽい。
この問題、$ \log $ 落とせるのかな。点の数が少ないことを利用しているからどこかで二分探索が必要そうに見えるが…
今日は普通に作業をしなければならない、休み癖が付いてきたのでちょっとだけつらい。ほんのちょっと。
CLIST を確認すると次出るコンテストは明日の yukicoder らしい。今週は週の真ん中にコンテストがあったから間が空かなかったな。
作業開始！今日はミーティングがあるのでデータを確認してたら半分困ったちゃんデータでだったので取り直した。
なんかうっかりしていて困ってないデータの方も消えてしまったりして結局ミーティングに間に合わず…
あといつも思うんだけど bash や zsh のスクリプトと Makefile のスクリプトの出来る範囲がまあまあ異なるのやめて欲しい。
いやまあ、Makefile がスクリプトを書く場所でないと言われればそこまでなんだけど…
make <command> で様々なことを実行したい人間としては依然からストレスの素である。
そんなこんなで作業終了。ピアノを弾く。 先日に記した通り腕を休めろと言われたけど、最初の通し練習だけは普通のテンポで弾くことにした。
今日は久々にピアノのフタを開けて演奏することにした。発表会も近いしな。 参考画像を載せておく。
ピアノは普段はフタを閉じていて譜面台もついている。いらすとやの画像のように、演奏会とかではフタを開けているのが普通だ。 まあこの画像は若干虚偽で、ピアノのフタを開けるためには棒みたいなパーツで止める必要がある。 ついでに譜面台と本体が一体化しているが、そんなことはなくて実際はスライドして取れます。 フタを取ると全く響きが違う。演奏の観点からしても、普通は音を聞きながらタッチやペダルを調整するのでこの違いは看過できない。基本的に大きくてよく響くようになるので、変な力が入りにくくなるような気がする。
ゆっくり練習というのはもどかしいもので、やっぱり速く弾きたくなってしまうが我慢した。
夕食はカツカレーが作られていた。おいしかった。最高。 ちなみに自分はカレーに溶けるチーズをのせる派閥の人間なのだがカツはとんかつなのでチー牛ではない（弁明）。
夕食後はダラダラする。ダラダラしているのも無駄だなと思ったので、入浴して今日の分の週記を書き始める。 せっかく身体が縦になった記念で競技プログラミングをすることにした。
先日の Problem - E - Codeforces の行列をセグ木に載せる解を理解した。 人のコード読んでも全然頭に入ってこないので、諦めて行列で行けそうということだけ念頭に置いて考えた。 $ 1 $ つの要素ごとに場合の数を計上するような線形の更新式を考える。 現在の連続非減少数 $ x $ と現在の合計の場合の数 $ y $ を持てばいけそうだ。
- 非減少な要素を末尾に付けるとき、$ x \leftarrow x + 1 $ と $ y \leftarrow y + x + 1 $ で更新できる。
- 減少する要素を末尾に付けるとき、$ x \leftarrow 1 $ と $ y \leftarrow y + 1 $
定数項のある線形の更新式なので、次元を $ 1 $ つ余分にとることで事なきを得る（斉次座標？）。
ニッコニコで提出すると TLE …。よく考えると定数倍 $ 27 $ かかっているからかなり厳しいのでは…
よく見ると、人類は std::vector ではなく std::array にしている。 std::array は静的配列なので生配列と遜色ない速さを見せてくれるはず…と思って出すと通る。もう二度と行列演算で std::vector つかわへん…。
自分の Matrix ライブラリも書き直しておこう。
行列演算なんてまさに Loop Unrolling やその他最適化の恩恵を得やすいタスクだなぁと思ったので、 最適化のディレクティブを追加しておいた（自分で書き替えるのは手間なので）。やっぱり速くなったぜ。
想定解を見ると行列を使っていなくて、奇妙なマージをしている。 よく見ると区間内の prefix と suffix の非減少列についての情報を持つことによってマージを可能にしているっぽい。 なるほどこうすれば定数倍が持つ情報のサイズに線形なので軽いな。ただシンプルにマージが面倒。 まあこの記事の冒頭で書いた平衡二分木の解法よりは $ 5000 $ 兆倍マシなんだけどね。
09/10 (FRI)
8:00 起床。が、二度寝して 9:15 起床。 急いで作業を開始する。今日の作業は虚無整備パートだったのでなかなかつらかった。 そういう意味では競技プログラミングは虚無パートがほぼなく、全てが本質なのでストレスを感じにくいところがある。 実装が只管つらい問題が出たときに虚無実装みたいなことを言うかもしれないけど、 一般的なプログラミングではガチで問題に対して本質的じゃない真の虚無があちこちに転がっているのだ。
作業の虚無さが酷いときは最近はドラクエの音楽を聴くようにしている。 ドラクエの音楽は初代のものから全てオーケストラの編成で作曲されているため、全シリーズをオーケストラで聴けて良い。 ジャンルもクラシック寄りであり、作業の邪魔になる感じもなく聞き飽きも発生しにくい。
うっかりゼミの時間までに昼ご飯を食べることに失敗してしまい、昼ご飯を異常な時間に食べる羽目になった。 それ以外はいつも通りの流れだった。
当然、作業を終え次第ピアノしばきタイムをして、残された時間の少なさにまた苦しくなっていた。
夕食後、ちょっと疲れていたのでスマホを見ながらうっかり横になってしまう。あれほど夕食後は横になってはいけないと言っていたのに… 案の定眠りについてしまい、起きたら 10:15 ぐらいで yukicoder が始まっていてうつ病。 そのままだらだらツイッターなどをしていた。もう今日なんらかの活動をすることを諦めた。
明日はひつぶ氏と DDR をする約束をしているので、寝る。
09/11 (SAT)
10:00 起床。なんかアラームをかけ忘れたらしい。昼から約束なので時間的には全然余裕がある。 カステラかなんかを食したのち、家でだらだらしていた。 マジでこの時間に作業か、せめて趣味に使えばいいのに寝ぼけた脳は YouTube やインタネッツ徘徊を求める。
流石に実力が衰えてしまうことを危惧して $ 1 $ 時間程度かる～くピアノを触る。 昼食を食べて、出発。
到着。とりあえず DDR 用のシャツに着替えよう。男性用トイレの個室が全部占有されている。 待つ。かなり待つ。全然一人すら出て来やしない。 受験生時代、予備校の自習室棟の唯一のトイレにずっと立てこもって（おそらくスマホとか弄っている）やつに対して 最初はノックとかしていたが最終的には「おい！！！！！」つって扉をぶっ叩いたのを思い出した。今考えれば知り合いでもない人から扉越しに恫喝されたら余計出てくるわけなかったな。 まあこの場合は自習室棟の貴重なトイレを占有する謎行為に煮えていたのが大きい。
今回はこの時の反省を活かして、おとなしく多目的トイレで着替えることにした。 多目的トイレ、明らかにもっと使うべき人が居る気がするのであの広大なスペースをオタクの着替えに使うのは本当は気が引けるんだよな…
待ち合わせ相手も到着。DDR 開始！
途中でちまちま休憩しながら $ 7 $ から $ 8 $ クレプレイしたと思う。 DDR というゲーム、他のゲームと違って適性とちょい上をプレイするとちゃんと $ 10 $ クレまでに限界が来るのでやりすぎることがなくていいですよ。
沢山動いたら腹が当然減ったので、レストラン街っぽい道を歩く。 和光があり、見るからに約束されたうまさがあるということで入店。 自分はメニューを見て普通のひれかつ御膳では足りないのではないかと思ったので、ひれかつ鍋ご飯を注文。 めっっっちゃ量きた。あまりに量来たのでウケた。絶対腹 9 割ぐらい行くやつだ…
同行者をかなり待たせてしまったが、完食。とても美味しかったが、もうしばらくとんかつはいいかなとも思ってしまった。
ここで別れて別々の電車に乗る。 帰ったら 20:55 ぐらいなことを確認した。流石に汗をシャワーで流す前に ABC に出場するのは険しいと思ったので欠場を決めた。 欠場するなら BPL でも見ようかなと思っていたが、こちらも 2nd Stage 最終回だったので 20:00 からなのを失念していた。 最近、Lightning -> ステレオミニジャック のやつを壊したので電車内で見ることができないので諦めて遅れて追うことにした。
帰宅してシャワーを浴びてから、BPL を見始める。ここで長々と語ってもしょうがないと思うので感想などは割愛するが、選手である UCCHIE と WELLOW さんのファンなので二人ともしっかり勝利をおさめ、それぞれのチームがセミファイナルに進出したのですごい良かったです（小並感）。SuperNOVA Tohoku が WELLOW さんが 2 タテしなければセミファイナル進出できない場面で、しっかり勝ちをもぎ取った場面がいっちゃん感動した。
就寝。
09/12 (SUN)
一旦 9:00 に起きたのだが、思いのほか体に昨日の DDR が効いており、二度寝して 11:30 起床。 今日は早起きすることが出来たら DDR 以外の機種を軽くやりに外出しようかなと思っていたのでかなりショックだった。
朝食を本当に軽く（ロールパンにハムとか挟んだ気がする）食べる。
日曜はかなり家族が家にいて、ピアノを長時間弾けるような時間が存在しないので 軽く $ 1 $ 時間ぐらい弾く。この後、自分はサークル関係の会議があったので急いでパソコンの前に向かう。
会議が終わる。うっかり昼食を摂るのを忘れていたため、大急ぎで食べる。 今日はなんかわたわたする日だな…。
遅い昼食の後は、昨日の BPL の余韻がまだ残っていて今まで見られなかった BPL 関連の動画（振り返り配信のアーカイブや選手紹介動画などなど）を漁りまくっていた。
CLIST によると今日は Codeforces Global Round なのですが、こいつはあまりにも人権がないので出場したくない。 Codeforces とかいうの健康を害することしかしてこないんだよな。
夕食の前後は音ゲーの判定を取る感覚を忘れないように、Sparebeat（スペアビート）| 無料音楽ゲーム をしていた。 とりあえずで選んだウミユリ海底譚を再理論値出そうと思ったらまあまあ判定が厳しくて、3-4 回かかってしまった。 そのあと有志の作った結構鬼な譜面たちを触っていたら、まあまあ効いてきたのでいい感じかなと思った。 手首が痛くなったタイミングで終えた。 発表回直前で腱鞘炎でおしまいとか一番最悪なので、手をいたわっていきたい。
Codeforces を欠場することにしたので、後の寝るまでの時間は今週の週記を書き上げていた。 それでは来週も頑張っていくぜ～。
