むかでの競プロ備忘録

競技プログラミングについて書きます

週記(2022/04/04-2021/04/10)

新生活が始まる(と言っても相変わらず学生の身分だが)のと、今まで死ぬほど忙しかったのが少しだけ落ち着いてきたのでこのタイミングで週記を再開しようと思う。 去年の $ 9 $ 月から更新がまったくなかったので、一応この半年で何があったかを軽くまとめておくか。

まず 2021/09 はピアノの発表の機会があった。これについては以前の週記でも触れた気がする。 この頃は並列して抱えているタスクが今ほど多くなかったので、そこそこ重めの曲をということでリストの「ラ・カンパネラ」を練習していた。 筋肉痛に悩まされるなどしながらも、なんとか及第点の演奏を本番ですることができて満足だったのを覚えている。

実はピアノが一区切りついてからは、音ゲーを我慢していた反動で beatmania IIDX にハマっていた。 結構熱心に練習したのでうまくなったと思う。ちなみに今はあんまりできてなくて、また下手になりつつある。

そっから先も音ゲー早慶戦というイベントの対策やら運営やら、ICPC 横浜大会やらで、忙しくしていたら気づいたら今になっていた。 なんということだ。文章に起こしてしまうと異常に完結に書けてしまうが、本当に色々な事があった…。

間の時期にイラストの練習をし始めた。 モチベーションとしては、恐らく将来は今の専門に関わる職業に就くだろうと漠然と考え始めており、なら趣味は何かを作るものにしようと思った。 実のところを言うとプログラミングを始めたのはゲームとかを作りたかったところが大きい。 年齢を重ね、それを仕事にするのはちょっと…という風になったのを逆手にとってそちらを趣味にしようと考えたのだ。 どんなものを作るにしてもイラストはマストなのではないかと思い、ここから始めてみることにした。元々絵を描くのは好きだった。 (上手すぎる人間に会いまくった結果、小学校時代以降絵を積極的に描こうとは思わなくなったが…) 高い書籍を買うことで自分を縛って毎日練習していたのだが、流石に以上に忙しくなって休止したのでそろそろ再開しようと思う。

ちなみに近況はと言えば、半年たってまたピアノの演奏会が控えている。 ただ、今回は直前期が結構忙しかったこともあり軽めの曲である。作曲家は去年の秋と同じくリストで「ため息 (Un Sospiro)」だ。

youtu.be

軽いと言っても短くて、そこまで複雑な構成をしていないということなのでまあまあ手への負担はあるようで、音ゲー早慶戦が終わってブランクがある時にいきなり $ 5 $ 時間くらい弾いたら しっかり腱鞘炎になってしまい割と発狂した。ロキソニンの暴力によって今は治りつつあるので本番には持ち越さなさそうで安心した。 ただロキソニンは臭いが強くて何を食べてもロキソニン臭がするのだけはちょっとだけダルかった。

04/04 (MON)

9:00 起床。本当は 7:00 頃に目を覚ましていて、Air pods を外すのを忘れてそのまま寝落ちしたのでめでたく起きたら右耳の方がどっかいっていた。 結果としてなんとか見つけたのだが、ベッドの上を大捜索して疲れたので上記の $ 9 $ 時まで二度寝をさせていただいた。

午前中しっかりと研究作業をした後、昼休憩に Twitter を閲覧。 昨晩 AtCoder 界隈をにぎわせていた tonakai とかいう人がアカウントを消したらしい。ワロス。 この人が何をしたのかと言うと、AtCoder Problems という有志の AtCoder の過去問まとめサービスでは最も速い回答に対して Fastest、最もバイト長が短いコードに対して Shortest と言ったちょっとした名誉みたいなものが与えられて、その数のランキングなんかも見られるようになっている。 某人は、他人のコードをコピペして非本質を換えたりして膨大な量の提出を行うことで Fastest を増やすという所業に出たのだ。 その他には脳死でテストケースを全埋め込みなどやりたい放題である。 誰しもやろうと思えば今までできたことだが、もともと有志サービスの名誉ランキングみたいなものだったので、そこまではやらないという暗黙のルールで成立していたコンテンツであるため結構燃えていたと思う。 意味のない長い変数名を挟んだり、インデントをなくすことで検知されないように図っているところや、CE の提出で反論を呈したりするのも実に小賢しくて僕は大好き(悪い意味で)なのだが、 実際に頑張ってチューニングした Fastest をあっさり奪われてしまった人からしたら笑えないだろう。

人のコードから高速化のアイディアを得る、テストケースが弱めなのを利用してコードを短くしたりする、といったことを今までもあったと思うし容認されてきたと思う。 アイディアを得てさらに高速化できた場合は、当人の+αのアイディアがあるから納得できるし、 後者に関してもテストケースが弱いのは問題の仕様だし、そもそもコンテスト中もそれで AC している人がいるので個人的には問題がないと思っている (脳死完全埋め込みはコンテストから完全に逸脱していると思っている)。 今回は、不正強奪とも呼べるそのやり口と、実際に奪取した数が膨大だったことで滅茶苦茶炎上したんじゃないかなと思う。

そういえば、ICPC の参加記全然書いてねえなと思いつつ昼飯を食べに部屋を出る。

昼飯はレトルトのハヤシライスを食べた。最近ケイジャンビーフチーズステーキ&ライスを食べていなくて恋しい。 来週は大学に行く暇があると良いな。完全にピアノの進捗次第ではあるが…

そんなこんなで今日は意外と集中して研究できて、18:00 になる。 退勤ボタンを押して日報を書こうと思ったら、なんかそのシステムに入ることが出来なくなっていて終わった。退勤だけして日報を書かない人になってしまった。 明日何とかしよう。

その後、すぐにピアノを弾き始める。1 時間ぐらい弾いたぐらいで先生に補講をしてもらえたのでそれに行く。 色々な有難い指摘を得て帰ってくる。本当は帰ってきてすぐにその確認を弾きながらしたいのだが飯もあるし時間も時間なので諦め。

最近は夜の時間が暇になってきたので、ここらでイラスト練習を再開してもいいな~と思いつつ、競プロももう一段上手くなりたいな~ということで CLIST を開く。 明日はインドと SRM があるらしい。インターセクションがあるので久々に SRM に出ようかな。

今日から始めようかと思ったが、正直今日は久々の「日常的な月曜日」だったのでのんびりさせていただくことにした。 明日からはイラスト練習を再開しようかなぁ。なんせ明日は出勤日ではないらしいので無敵なんだよな。

無敵だーとかいいながら忙しかった時期に更新があった Web 漫画や新刊が来ていた漫画を消化していく。 すると普通に良い時間になる。ちょっと競プロをやろうと思ったが、眠かったので風呂に入って寝た。

04/05 (TUE)

10:00 起床。出勤がないからと言って眠りまくった。しかもここから布団でスマホ弄りをしばらくしていたので実質動き出したのは 11:00 頃じゃないかと思う。 その後も微妙にタスクを消化したりしながら昼まで過ごした。

昼飯を食べた。昼飯を食べたらぼちぼち眠くなった(は?)のでごろごろスマホ弄りをずっとしていた。 15:30 頃にピアノを弾き始める。17:20 に一旦休憩に入る。 発表会が控えているため、練習量を増さなければならないのだが、このリモートワークのご時世だと家族が家にいてやりにくいところも多い。 そのため、ピアノの先生が空き時間のピアノを貸してくれるということになった。本当にありがたい、これも 17 年間習い続けた信用がなせるわざかもしれない。

そんなわけで 20:00 前ぐらいまで弾き続けて飯を食べるために家に帰る。 飯を食う。アジフライがうまかった。あと実家の料理は基本的に健康的なので本当に助かる。 このブログの見栄えをよくするために写真にとればよかった。

夕食後、飲み物を大量に買いに行くから荷物持ちをやってくれと母親に言われる。 死ぬほど飲み物を持つことになる。代わりに、自分で買う予定だった檸檬堂とおつまみと少年ジャンプをおごってもらった。 少年ジャンプを買ってもらう 23 歳 (もうすぐ 24 歳) 男性って…

今日からイラストの練習を再開するといったな、あれは嘘だ。 檸檬堂を飲み、おつまみを食べながらジャンプを読んでいたらとてもやる気が起きる気がしなかった。 完全にリアルタイムでこの週記を編集しているのだが、現時点で SRM に出場する気すら起きなくなっている。 多分出ないと思う。

出ませんでした(照) 完

完のあとになんか 1:30 ぐらいまでポケモン LEGEND アルセウスをプレイしていたのは内緒。

04/06 (WED)

今日も出勤はない。なぜならこの曜日は研究室に行っても誰もおらず、ピアノの稽古の日にしているためだ。 出勤がないことになれてしまい 11:30 起床。最悪。朝食を食べることを断念した。

昼食を食べる。実家は起きているだけで昼食が提供されるので本当に神。 D 進する身としては、いつ追い出されるのか戦々恐々としているが…

昼食を取ったらピアノを練習し始める。そこそこ練習した。結構本番のテンポを意識しつつ練習したらむしろ崩れてきてしまった。 一抹の不安を抱えながらもピアノ教室に向かう。 着くと一旦通しで弾くことになる。ゴミ下手くそだった。参った…助けてくれ。

色々と有難い指導を受けたので帰宅。帰宅してすぐは全然弾く気がしなくなってしまっていたので休憩する。 少し休憩してから夕方になったかぐらいの時間から夕食までずっと弾き続けていた。 かなりマシになってそろそろ録音でもするかと思った。 明日からは録音しようかな。

夕食を食べる。おいしい。 夕食後にイラスト練習再開するかとかも思ったが、ずっとピアノ弾いていた精神的疲れがあり断念。 21:30 になってようやく何かをやる気が起きたのでとりあえず週記の編集をした。 コンテストの確認をしたが、自分が出そうなコンテストは今日はないことがわかった。 とは言え、週末には ARC もあるので練習をしておいた方が良いかもしれない。

競技プログラミングをしようとしたら、急に腹痛が来た。別に心的要因ではなくたまに来る胃痛の周期だろう。 仕方ないので横になって漫画の消化をすることにした。

回復してきてふと明日から講義が開始することを思い出す。 しかしいくら自分が単位残りまくりのウンチ M2 だとしてもそんなに授業数はないので明日はないやろと思っていたら、普通にあった。 しかも今学期からほぼ全講義対面である。許せね~。 さらによくよく考えると、明日もピアノの練習を休むわけにはいかないが朝から大学に行くので 大学に置いてあるピアノで休憩時間にちょいちょい弾くでは足りない。つまり大学近くのスタジオでピアノをレンタルすることが確定になってしまった。

はぁ…明日は夜にピアノレンタルか~とか思っていたが、普通に明日が自分の誕生日であることを思い出す。 誕生日の夜に一人キャンパス近くでピアノを弾きながら「上手くなんね~」とか叫び散らかす人間にならなきゃいけないのかと思ったら、 本当に嫌な気持ちになってきた。 本当に悲しいのでせめて夕食メイツを募集することにした。見つからなくても粘り強い勧誘ツイートを明日はしようと思う。

そしてここまで書きながらよくよく確認したらスケジューリングを完全にミスっていて、 MTG と初回授業が被っているものがあった。 普通に最悪だ…。シラバスに教授の連絡先はないので、後輩に後でこっそり内容を教えてもらうか。

人生が下手だなあと感じつつ、明日は早いのでもう寝ることにする。0:00。

04/07 (THU)

誕生日!!!!!!!!!!!!!!!!! 24 歳になりました。まあそれ以上もそれ以下もないんですが… 7:30 起床。そろそろ普段の生活に戻さなくてはならない。 結構ギリギリに起きたのでそこそこ急いで家を出る。

行きの電車の途中で一限が 9:30 からではなく、9:00 からであることに気づく。始業がずっと 9:30 だったから錯覚していた。 初日から遅刻確定で気を重くしながら電車に揺られる。しかもこの時間の電車は普通に混んでいるので最悪。 15 分ぐらい遅刻して入室するも、まだ全然余裕だったぽくて安心した。

夜まで研究をするため、ピアノを弾くためには練習室を予約する必要があることを思い出す。 こんなギリギリで予約できるかなぁ…と思いながら日吉のピアノスタジオに電話をかけるとメンテナンス日で干からびていた。 その後も近辺のピアノスタジオを当たりまくったけど、バカ高いか空いてないかの二択で完全に終わっていた。 仕方ないので最終手段として、地元の先生の教室のピアノを使わせてもらえるように交渉をする。 大変ありがたいことに使わせてもらえることになり、一安心だった。 ピアノはマジで一日弾かないだけでタッチ感覚が天に召されてしまうため、本気で命拾いした。

安心感からか、研究はいつもより楽しく安定してできた。 睡眠が足りてないからか帰りの電車ではもうすでにクソ眠かったが、ここからピアノの練習が控えていた。 眠くなりながら、必死に抵抗して練習をした。1.5 h しか練習できなかったこともあり、そこまで上手くなったきがしなかったが 21:00 に完全に疲れ果てギブアップ。

このタイミングで夕食を食ってないことを思い出す。そりゃ体力持たないわ。 近くにマックがあるので、そこで夜マックさせていただくことにした。誕生日なので倍にした。 当然食べるバーガーはダブルチーズバーガー。チー牛の匠なので。

家に帰ると「誕生日おめでとう」と母親に言われる。そういえば今日は 1 日中外で活動をしていたが誕生日なんだよね。 手を洗ってうがいをしたら倒れ込むようにベッドに入る。 そのまま Twitter を監視したりもしていたような気がするが、気絶した。

04/08 (FRI)

気絶して起きたら、寝巻きにすらなっていないし 4:00 だしで散々だった。 二度寝を試みるも結局 5:30 ぐらいまで寝付けなかった。最終起床は 7:30。今日は一限がないのでこれで本当に大丈夫。

大学に着く。今日は初めての対面ゼミなので妙な緊張感がある。 というのも研究室に配属されてからというもの、某ウイルスの影響でずっとオンラインゼミだったからだ。 一発目が自分の発表回じゃなくて良かったという気持ちが強い。

作業をする。時間が経つ。後輩の発表を聞く。問題なさそう。 夕食はからやまで食べた。

夕食後、今日は練習室が予約で来たので入る。 ピアノの調律が若干狂ってそうで嫌な気持ちになるも、順応する。 外での練習環境を見つけないとそろそろちゃんと上手くなることができないような気がしてきた。 というかそもそも出先でできるゲームだから音ゲーにハマっている(家ゲーは積んでしまっている)みたいなことを考えると、 家で時間を取ってやる趣味というのは結構難しいなという風に感じるようになってきた。

練習中に LINE かなんかを見ると(見るな)、同期とかが近くで飲んでいることが分かった。 金曜なので練習後に混ざることにした。

f:id:spider_0859:20220411104055j:plain

大変良かった。蒸留酒で自分で思ったより出来上がっていたらしく、 家に帰って飲むヨーグルトを冷蔵庫から出す際かわりにスマホを格納するなどの珍行動をしてしまった。

04/09 (SAT)

11:30 起床。休日に起きられないの、そろそろやめた方がいいな。 だらだらしたのち、昼食をとる。

今日は音ゲー早慶戦SOUND VOLTEX 部門打ち上げがある。 その前にピアノを練習しなければならないので昼食後少し休憩ののち練習を開始する。 なんだか段々聴くに堪える演奏になりつつある。というかこんなに弾いてるんだからなってくれないと困るが。

そんなこんなで集合時間 5 分前ぐらいに待ち合わせの場所につく。 こういうのが久々すぎてかなり楽しかった。ボルテのモチベーションも結構上がった。忙しさ抜けたらやろ。

f:id:spider_0859:20220411105050p:plain:w300
ビアヒ 1 ニア。久々でもちゃんとおあずけを食らう。

二週間ぶりぐらいに音ゲーをやるが、メンテナンスが良くて全然プレイできた。 終電で帰ったのでシャワー浴びて就寝。

04/10 (SUN)

11:30 起床。休日、起きられない。 全日と全く同じ流れ。バカです。

今日はマジで愚かで、特に何をするでもなく昼過ぎまで過ごした。 昼過ぎ~夕方ぐらいにピアノを弾き始める。19:00 ぐらいまで弾き続けた。 結構左手に違和感を覚えるようになってしまったが、かなり練習が上手くいった気がする。

夕食後、ABC があるのだが今日は会議が入っていたのでそちらを優先する。 話している内に深夜になるので、今週の活動としてはこれが最後となった。

来週に向けてピアノを弾きまくって来週からはきっと研究が忙しくなる。 4 月をなんとか乗り切ってやりたい。

ICPC 2021 国内予選参加記

はじめに

ICPC 2021 国内予選に 202 Accepted という名前のチームで出場をしていました! 結果は,ABDE 4 完で $ 32 $ 位 の学内 $ 2 $ 位でおそらく通過となりました! よーし.ホスト校枠もおそらく温存かな? 去年ホスト校枠にすらひっかからず予選落ちした時は顔面ぐちゃぐちゃになっていたので本当によかった…

自分自身は BD を担当していました(詳しくは後述).

チームについて

チームメンバーは HayatoY, auaua, centipede_human です.使用言語は全員 C++. 後輩チームに一人今年 ICPC を引退する老の者が混ざった形となった.

「国内予選の時にはみんな黄色っぽいですね」みたいな話をしていたのに気づいたら本番時点で黄色は auaua くんだけになっていました. どうして…

個人的にはチームの構成自体は悪くないなと思っていました. 最近のコンテストで,それぞれのメンバーの結果が芳しくない場合でも OR を取ればまあ…みたいな回も結構あったような気がする. 具体的にどういう風に得意不得意を補っているのか全然よくわからないが,どうやら得意被りはあまりしていなさそうだった. $ 3 $ 月までにお互いの傾向をよりよく知れたら本番のムーブ改善につながるだろうか.

実際,模擬国内でもまあまあぐらいのパフォーマンスで通常選抜圏内だったので流石に国内通過はいけるやろ(というかいけてくれ)と思っていた.

個人的な近況報告

完全に話が横道に逸れるが,個人的な近況のお話.

自分は最近競技プログラミングをする時間が全然取れなくて, 競プロ備忘録であるこのブログで週記を更新していいのか?みたいな気分になりしばらく更新見送りをしていた. (一瞬復帰したけど,競プロやってなさすぎてなんか違うなと思った)

ICPC があるということで最近は無理やり時間を作って一日に最低でも $ 1,2 $ 問は通したり, コンテストには出来るだけ出席するようにしたりした. とはいえ,Codeforeces や SRM には参加できておらず怠慢… すっかり色々なものが脱落していたり遅刻しまくったりして AtCoder のレートは現在すっかり青になってしまった.

直前期は AOJ-ICPC の難しくない問題を使って,毎日 ICPC の問題慣らしみたいなことだけはやっていた. C++getline 関数の扱いなんかすっかり忘れていました. あと準備と言えば,ICPC 国内のデータセットってそんな強い印象がないので近似ソルバみたいなものが効きやすいのではないかと 考えて,そこらへんの準備も一応していた.

本番

直前まで研究に関するミーティングをしていた.正直かなり怒られると思っていたけど全然そんなことなかったのでむしろ怖かった.

自分は恐るべき早解き苦手人間な上にいきなり難易度の高い問題を取り組めない人間なので, A 問題は Hayato くん, C 問題は auaua くんに投げて自分は B 問題を担当.

B 問題は $ H \times W $ マス計算答えから一意に問題を求められるか?みたいな問題.読解が苦手なので困った. ちょっとすると Hayato くんが A 問題を通したと聞いたので D 問題を読んでもらうことに. 上部の最左の数字が $ 0 $ と決まっているので,同一行に数字が書かれていたら推移的に決まっていくなと思い, じゃあ連結性の判定で終了ですねとなる.しかし,今回は差も重要なので心が慎重になっていた. ポテンシャル付き UnionFind を持ち出そうとするも,あまりに早く通されているので問題文をもう一度よく読むと 解は最低一個はあるようなので単純な連結性判定だけでよさそうだ.(本当は Input の部分にも書いてほしかったぜ) AC.少々遅れた.

Hayato くんが D は難しそうで E が解けそうなので E を見ると言っていたので D を読む. 順位表を見るに,D が一番実装と考察のバランス的にマシっぽい. 設定も単純で数列があって,「非 $ 0 $ の最左 $ 3 $ つの要素から $ 1 $ ずつ取る」操作を繰り返す. 数列を自由に並び替えられる時,最大の操作回数を求めよという問題.

制約が要素数,要素の大きさともに $ 50 $ 以下というかなり緩め. Hayato くんが最後に残す要素を固定すれば,嬉しそうな見た目をしているがそう簡単でもなさそうと言っていた. 確かに,最後の要素から逆操作をしそうな見た目をしているが結局分岐しまくって全然うれしそうじゃないし 残りソートとかしても全然できそうにない. ここまでの感じから DP っぽさを感じたがこの方向性だと DP すらきつい.

C が重い全方位木 DP と言って頑張ってくれている auaua くんと E が結構面倒くさいけど解けると言ってる Hayato くんたちに 「D 難しいよ~」などとぼやきながら順位表を見ると続々と D が通されていてかなり焦る.

残すものを考える方針が厳しそうなので,一旦フラットな気持ちになって棒グラフみたいのを書いてサンプルを手で実行してみる. 「一番低い棒グラフの高さで切り取って右から新しい棒グラフをもってくる」をしたときに,いやこれ「無になった上に積み重ねる」のと同義だと気づく.ちょっと考えると,適当に積み重ねて $ 3 $ つの高さの最小で良いと証明できる. 不可能な積み重ね方もあるが,最適解には絡まないので無視できる. 脳を無にすると添え字を $ 3 $ 本の棒グラフの高さにする三次元 DP を思いつくが bool の DP は無駄だと古事記にも書かれているので,($ 2 $ 本の高さ - 最低の棒グラフの高さ) を添え字に持って値として最低の棒グラフの高さを値として持つことによって次元を落とすことに成功. 定数倍を雑に書きすぎたせいか重いので O2 オプションを付けて実行すると速い.一個目のデータを通る. 二個目のデータでなぜかランタイムエラー.メモリ系のエラーらしい.free() のサイズがおかしいと言われるがどう考えても std::vector の内部の話なので参る.ここで時間を浪費

時系列が前後するが,E 問題が解けそうだが重いことから F を auaua くん Hayato くんの二人で話合っていて 反例を見つけたり見つけなかったりしていて,つらそうだったので順位表を見ると流石に 4 完はしないとマズそうで F は厳しい問題っぽいので重そうな E をそろそろ先にやったらどうかという提案おじさんになっていた.

時系列は戻って E を通して再び F に取り掛かる Hayato くんが D のデバッグ手伝いますと言われたのでコードを投げる. 遷移で境界違反してそうと言われ,そうかなあとか戯けたこと抜かしながら見ると DP 初心者みたいな境界違反をしていた. 取り急ぎ直すと二個目のデータが通る.コードが変わっているので三個目のデータを通して AC. コード間違っていたのにペナにならなかったのは普段の行いかな?w

この時点で順位表を見ると,F を通しているチームは非常に少なく厳しそうなので,auaua くんの C のデバッグを全員でやってみる. とはいえ,自分はとくになにもできず試して起こった現象について述べているだけの人になっていた. 最終的にバグ取れたと思いきや二個目のデータで WA

ここでコンテストが終了.割と全員が苦しんでいたが,なんとか耐えました. CE 問題はジャッジが来たら実装練習としてやろうかな. D 問題も高速化できると思うのでしっかりとやっていこうな.

おわりに

僕の ICPC はまだもうちょっとだけ続くんじゃ.

P.S. 今 202 Accepted の PG BATTLE の順位見たけど 14 位なのな.思ってたより高い.僕ましゅまろ遅解き担当だけど.

週記(2021/09/06-2021/09/12)

09/06 (MON)

11:00 起床。たまたま勤務がなかったことをいいことに寝散らかしていた。 朝食を食べて先週の週記を書き上げているうちに、ゼミの時間になる。

ゼミが終わって、週記を投稿すると、もう 14:00 を回っていたので慌てて昼飯を食べる。

昼飯が終わってからしばらくは YouTubeカプリティオチャンネルの動画を見漁っていた。 クイズ系の YouTube チャンネルなのだが、面白い。クイズ系なら Quiz Knock という人も見て欲しい。なんていうかネタのこすり方が、若者とは違う感じでとてもいい。ジャンルが好きな人は両方見ると良いと思います。

さて、しばらく休憩したあとに競技プログラミングをする。主に upsolve の活動なのだが、昨日の Codeforces の E で完全に詰まってしまった。方針は立っているのに、添え字関係で発狂寸前まで追い込まれている。

Problem - E - Codeforces

一応週記が別記事なので、改めて問題概要。長さ $ 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 らしい。今週は週の真ん中にコンテストがあったから間が空かなかったな。

作業開始!今日はミーティングがあるのでデータを確認してたら半分困ったちゃんデータでだったので取り直した。 なんかうっかりしていて困ってないデータの方も消えてしまったりして結局ミーティングに間に合わず… あといつも思うんだけど bashzshスクリプトMakefileスクリプトの出来る範囲がまあまあ異なるのやめて欲しい。 いやまあ、Makefileスクリプトを書く場所でないと言われればそこまでなんだけど… make <command> で様々なことを実行したい人間としては依然からストレスの素である。

そんなこんなで作業終了。ピアノを弾く。 先日に記した通り腕を休めろと言われたけど、最初の通し練習だけは普通のテンポで弾くことにした。

今日は久々にピアノのフタを開けて演奏することにした。発表会も近いしな。 参考画像を載せておく。

f:id:spider_0859:20210909232551p:plain:w300
ピアノ(いらすとや)

ピアノは普段はフタを閉じていて譜面台もついている。いらすとやの画像のように、演奏会とかではフタを開けているのが普通だ。 まあこの画像は若干虚偽で、ピアノのフタを開けるためには棒みたいなパーツで止める必要がある。 ついでに譜面台と本体が一体化しているが、そんなことはなくて実際はスライドして取れます。 フタを取ると全く響きが違う。演奏の観点からしても、普通は音を聞きながらタッチやペダルを調整するのでこの違いは看過できない。基本的に大きくてよく響くようになるので、変な力が入りにくくなるような気がする。

ゆっくり練習というのはもどかしいもので、やっぱり速く弾きたくなってしまうが我慢した。

夕食はカツカレーが作られていた。おいしかった。最高。 ちなみに自分はカレーに溶けるチーズをのせる派閥の人間なのだがカツはとんかつなのでチー牛ではない(弁明)。

夕食後はダラダラする。ダラダラしているのも無駄だなと思ったので、入浴して今日の分の週記を書き始める。 せっかく身体が縦になった記念で競技プログラミングをすることにした。

先日の 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 開始!

f:id:spider_0859:20210912233101j:plain:w300
ひつぶ氏と DDR

途中でちまちま休憩しながら $ 7 $ から $ 8 $ クレプレイしたと思う。 DDR というゲーム、他のゲームと違って適性とちょい上をプレイするとちゃんと $ 10 $ クレまでに限界が来るのでやりすぎることがなくていいですよ。

f:id:spider_0859:20210912233149j:plain:w250f:id:spider_0859:20210912233153j:plain:w250
足14 の一発新規鳥。結構 DDR の地力戻ってきたかも。

沢山動いたら腹が当然減ったので、レストラン街っぽい道を歩く。 和光があり、見るからに約束されたうまさがあるということで入店。 自分はメニューを見て普通のひれかつ御膳では足りないのではないかと思ったので、ひれかつ鍋ご飯を注文。 めっっっちゃ量きた。あまりに量来たのでウケた。絶対腹 9 割ぐらい行くやつだ…

f:id:spider_0859:20210912233501j:plain:w350
和光のひれかつ鍋ご飯というメニュー。想像の倍ぐらいの大きさだった。

同行者をかなり待たせてしまったが、完食。とても美味しかったが、もうしばらくとんかつはいいかなとも思ってしまった。

ここで別れて別々の電車に乗る。 帰ったら 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 を欠場することにしたので、後の寝るまでの時間は今週の週記を書き上げていた。 それでは来週も頑張っていくぜ~。

週記(2021/08/30-2021/09/05)

08/30 (MON)

9:00 起床。最近は普通に作業の時間が多いし在宅だしなのでこの時間について書けることが少ない。 話題作りのためになにか面白いことをしたいね。

というか昨日のマンガワンの無料祭り、途中からすっかり忘れていてせっかく読もうと思っていたケンガンアシュラを読み損ねてしまった。朝に気づいたときはガチで凹んだ。

2021/8/30 ついに、競技用のパソコンから研究などの作業もできるようにしてしまった。 ここに書く生活を見ればわかると思うが、真剣な事も趣味も遊びも連絡も全てパソコンの前で行う人種のためそこの生活の切り分けが難しい。 そのため、今までは複数存在するパソコン事にその前に座ったらやることを決めて頭のスイッチを入れ替えていたのだが、 普通に面倒になってきてしまい、全て Surface でやることにしてしまった

Surface に統合した理由はいくつかある.

まず第一に、競技プログラミングを WSL 2 (Ubuntu 20.04) でやっているためだ。 実は三種類のパソコンを使っていて、キーボードがそれぞれ Windows JIS・Mac US・Mac JIS なので気が狂う。 気が狂った結果、タイプミスが目立ってしまうので競技をやるパソコンを一番多く触るようにしようという試みだ。

次に、ブログの更新だ。何を言っているのかわからない人もいるかもしれない。 しかし先週の週記の句読点がすべてカンマピリオドだったことを振り返ったり振り返らなかったりしてほしい。 そう、先週はうっかり研究につかっているマシンで週記を書き始めてしまったのだ。研究用なので当然デフォルトの句読点をカンマピリオドにしている。 しょうもない半分記録用のブログにカンマピリオド使うのはイタい(個人差があります)ので、Surface を常用することでこれを防ぐねらいがある。

最後に、スペックが低く外部機器の取り付けが難しいし、キーボードも対応したものしかない面倒なタブレットもどきである Surface を常用するデメリットが現状少ないからである。 お恥ずかしいのであまり言いたくないのだが自分の机の上はあまりスペースがない。 汚いというほどではないのだがディスプレイを置くスペースはないし、そもそもマックをスタンドとかに置いて外部機器を挿すようなことも厳しい。 そもそも持ち合わせの良いディスプレイやキーボードもない。あるマウスすら安物である。 ので現状画面ちっちぇと思っても Mac にしたところでそんなに変わらないのだ。 長年 Windows くんと仲良くしてきたし Mac 固定は正直デメリットの方が大きそうだった。

早く机の上のものを捨てまくってディスプレイ買って快適な生活を送りたいです。

ちなみに ssh key の密輸入が一番ドキドキする作業だった。

さて今日の作業が終わると、拷問タイム(ピアノ)だ。ピアノ実は土日に弾けなかったので内心バックバクだった。 ちゃんと下手くそになっていた。平屋なのをいいことに床ドンをするなどして二時間半ぐらい弾いたら戻ってきた気がする。 気がするだけかもしれない。 ラ・カンパネラは本当に演奏者によって全然演奏が違うため、毎日色んな演奏を聴いている。違法音源じゃないことを祈る。

食後はジャンプを買いに行ったあと、週記を書いていた。うっかり先週分のものを公開し忘れていたので公開する。 ジャンプを読んだりしていて、リングフィットアドベンチャーをやってシャワー浴びて就寝。

08/31 (TUE)

8:30 起床。ただし、しばらくは部屋でぐだぐだ YouTube 閲覧をしていたのでこの時間に起きた意味はまるでない。

今日は休みの日なので、朝の時間は基本的にだらだらしていた。 それこそ YouTube 閲覧、スマホでネットサーフィンなどをして過ごしていた。 いや、こういう時こそ競プロをやらないと本当に下手くそになっていくのでしっかり反省していきたい。

さて、上が先日のツイートなのだが、毎日朝晩洗顔料で顔を丁寧丁寧丁寧に洗っているのにニキビができていたいし不快だしでかなり発狂していた。 というわけで洗顔料を新しいものを使い、顔面に塗る液体(クリーム)を購入することが決定した。 幸いにも近所にそういうものをたくさん売ってるドラッグストアがあるので助かった。

剃刀負けにもいいみたいな話なので剃って塗ってみる。ヒリヒリする。まあこれは剃刀負けなのでしょうがない。 経過をみる。なんかいいような気がしてくるプラシーボ効果で肌が健康になりそうである。 満足したりジャンプの続きを読んだりしながら、昼飯の時間になる。

昼飯を食ってひと段落したら、鍵盤をシバきはじめる。 本日は 3~4 時間ぐらい弾いた気がする。普通に疲れた。 本番が 9/23 なのでブルブル震えている。本当にこれ完成するのか?完成してくれ、頼む。

気づいたんだが、これが終わらないと週記でピアノのことばかり書くことになるな。

練習を終えて Twitter を見ると DDR の異次元プレイヤーであるところの CHRS4LIFE がまた 17 を MFC していた。 DDR とかいうゲーム、カジュアルな見た目をしている癖に判定が厳しいため、普通に人間をやめている。 ついでにこの時間に週記を書き進めておいた。週末に履歴を見ながら書くのは何かが違うので…

話題がころころ変わるのだが、現在自分がプログラミングを真面目にやるきっかけとなった HSP という面白言語のプロコンがある。 これは競技プログラミングではなく、ゲームやツールなどの作品を投稿するコンテストだ。 HSP は主に Windows に対応しているスクリプト言語で、一行も書かなくても空の 640x480 サイズ(うろ覚え)のウィンドウが生成されるという プログラミングやったことないとかやり始めたてみたいな人が GUI の something を作るのにはもってこいの言語である。

クラスは愚か関数すら満足に使えないのは辛いところだが、自分で DLL (Dynamic Link Library) とかを用意したりして拡張が効くところも面白いポイントである。 アイディアがあればなんか作りたいな~と思っていたのだが、アイディアが降ってきた。 ただ時間が取れるかが微妙なところである。まあなんか作れそうなら週記に書こうと思う。

休みの日なのだが、ファイル破損などにより作業が押していたので食後は普通に作業を行っていた。 ハァ~競技プログラミングやりてえ~。就寝。

09/01 (WED)

8:30 起床。今日は大忙しの日だ。作業からのピアノからのミーティングだ。

9:30 から作業を開始する。なんとか昨日までの作業で最低限ミーティングが出来るぐらいの感じの進捗になっていたので落ち着いて作業できた。 とはいえ、グラフの生成などをしていたら結構時間が押せ押せになってしまい、ピアノ教室に行く前に手ならしをすることができなかった。 昼飯を食べて急いで教室に向かう。 習う。今週もそれなりに頑張ってそこそこに仕上げたつもりだったがゴミほどダメだった。 死にそうになりながら帰宅。ミーティングがあるので急いで諸々準備をしてつなぐ。 ミーティングをする。ミーティングはやるべきこととか考えがまとまるので良い。

この後夕食まで時間があったが、普通に研究をしていた。 夕食までで完全に力尽きてしまった。夕食を食べたあとうっかり横になってしまい、11:30 ぐらいまで寝ていた。最悪。 もう「夕食の後に横にならない」って貼り紙をするか、ベッドの上にジャンプをたくさん散らかしておくかぐらいしか対応策が思いつかない

11:30 という時間は本当に最悪で、これから競技プログラミングをやるか!という感じにもならないし、寝起きでリングフィットアドベンチャーもやりたくない。 しかも寝ていたせいで次の入眠が悪くなるので、ひたすら虚無の時間を過ごさせられていた。 その後就寝…と思ったら、先日購入した顔面に塗る液体のせいで顔が乾きまくってて全然入眠できなくて困っていた。 えっ保湿じゃないんかと思ってよくよく表示を見てみると DRY って書いてあった。 は?いや、OILY というところにもチェックが入っている。OILYってしっとりするもんじゃないのか? とにかくこういったものを普段使わないため何もわからずストレスのみがたまった。許せねえ(?)

記事に書くようなことがまるでないため、自分が好きな動画の話でも付け加えておくか。

www.youtube.com

この動画はもこうが出過杉くんという フリーゲーム投稿サイトにあるクソゲーをプレイする動画なのだが、主に後半で呼吸困難になること必至なのだ。 マジでしょうもないので時間が有り余ってる人はプレイしてみて欲しいし、この動画もみて欲しい。 こういう馬鹿ゲーともこうの相性抜群すぎてウケる。

↓↓ 出過杉くんの URL ↓↓

https://xn--unityroom-z43h7a6jth.com/games/dekasugikun

09/02 (THU)

8:00 起床。本来なら大学に行く予定の曜日なのだが、昨日鍵盤しばきがあまりできていないため家に残ることにした。 大学に行くついでに帰りにちょっと音ゲーをしたりすることもあるので、音ゲーも多分今週はやらないだろうな… タンドリーチキン丼を週記に載せると言ってから一億年が経過したが来週こそは達成したいと思う。

作業開始。鬼のように眠かった。終了。即ピアノ。 マジで最近の日記の流れ完全にこればっかりで泣いてり。 ワンパターンすぎるので、録音とか貼ってみようかな…はてなブログって音声ファイルを貼ることってできるのかな。

今日気づいたのだが、練習直後の右腕を触るとコロナウイルスワクチン 1㍑ 注入したみたいな温度になっている。 筋肉って酷使すると熱を持つので当然ファンの取り付けが必要な気がしてきたぞ。 前にも言ったような気がするがもうなんか苦しいことに対する達成感みたいなものを感じてしまいつつある。

夕食後、ついに横にならないことに成功する。 ついでに音声ファイルを張り付ける方法を検索するなどしていた。 調べたものによると DropboxGoogle Drive にアップロードしたもののリンクを貼ることで実現をするようだ。 意外と手頃なので現実味を帯びてきた。 問題はそもそも出来が悪いと録音を聞いただけでつらくなるということである。

競プロ備忘録なのに全然競技プログラミングしないのもどうなのかと思ったので競技プログラミングをする。 先週の ABC の upsolve から始めよう。

G - 01Sequence

問題概要。$ 0 $ と $ 1 $ のみが含まれる長さ $ N $ の列 $ A $ を考える。 閉区間とその中も最低でも含まれるべき $ 1 $ の数が $ M $ 組与えられるので 列 $ A $ の中に含まれる $ 1 $ の数を最小化した上でその一例を示せ、という問題。

本番では全然別なことを考えていて実装を嫌がっていたのだが、「牛ゲー」という単語をコンテスト後に観測して感動した。 ここでは詳しい牛ゲーの話は置いておく(書くなら証明まで書かないとあまり意味がなさそうなので)が、この問題にフォーカスして書き残しておこうと思う。

まず、 $ A $ の累積和の配列 $ B $ を用意する。すると長さ $ N+1 $ で $ B _ {i} \leq B _ {i+1} $ が成り立つような配列になる。 今回は $ B _ {N} - B _ {0} $ を最小化したいという問題。 差分制約が複数与えられるので牛ゲーと言いたいが牛ゲーは最大化問題なので、 $ 0 $ の数の累積和として考えなおす。 すると最大化問題になり、しかも正の辺しか存在しないため dijkstra 法が使えて解ける! 因みに最長路問題として考えれば $ 1 $ の数の累積和のまま記述できそうで、負の辺のみなら符号反転によって dijkstra 法で行けるのだが今回は無理。

今日のフリー欄。PASELI の利用額でも貼っておくか。セガゲーはもう近年全然やってないので。

今月の利用額は…7798 円音ゲーマーでなければあまり実感がわかなくて、めちゃやってんなコイツって思うかもしれない。 以前の僕は 2 万とか 3 万とかやってる時もありました…ええ。トップの人が現役で伸びてる人はもっとやってる人もいそう。すごい世界だ。来月は 1 万ぐらいプレイしていい感じに実力を戻していきたい。けど 23 日まではなかなか厳しいな。

f:id:spider_0859:20210902231113j:plain:w350
PASELI 利用額。もう最近 1万すら行かなくなってしまった。

09/03 (FRI)

7:50 起床。最近起床時間が健康的すぎないか? YouTube で動画を漁りながら 9:30 を迎える。作業をする。マジでいつもどおりに作業をする。 そして終わったらピアノを弾くところまでワンセットで早送りします。

食後、yukicoder があるので出ることにする。

yukicoder contest 312 - yukicoder

A 問題。$ a \leq x \leq b $ かつ $ c \leq y \leq d $ である $ x,y $ について $ (x+y) \bmod m $ の最大値を求めよという問題。 制約が緩いので全探索を決めた。まあよく考えると $ x+y $ の値は $ [a+c, b+d] $ の中の整数値全てを取り得ることを考えると $ O(1) $ でもいける。

B 問題。 $ n $ が与えられて、$ n=i^{j} + k $ と表現できる非負整数の組の $ (i,j,k) $ の中で $ i+j+k $ が最小になるようにしろという問題。 $ i=1 $ の時は自明に和 $ n $ になるので $ 2 $ 以上を考えるのだが、底が $ 2 $ 以上なので $ j $ が小さくなることがわかる。 よって $ j $ を全探索することを考えることにした。しかし誤差が怖くて二分探索でやったんだけどオーバーフローの処理が面倒で嫌だった。 いやこの程度面倒臭がっていたらダメだ…

C 問題。交互ゲーム。正整数列が与えられて、$ 1 $ つ要素を選んで $ 2 $ 以上のの約数で割る。できなくなった方の負けで勝敗判定。 これ全く同じ問題を $ 2 $ 回ぐらい見た気がするけど気のせいかな?素因数分解をして、素因数の数で Nim になるので xor とっておしまい。 試し割りだと厳しそうなので篩を使って $ O(\log A_i) $ で素因数分解や。

D 問題。とけなくて困った。ちなみにこれを書いている今も解けないので tmux でコイツのコードを開いたセッションが存在し続けている。

E 問題。これは解けなくてはいけなかったのに解けなかった。 $ N $ 頂点 $ M={0,1,\cdots,N-1} $ 辺の単純無向グラフでサイクルがないものの数え上げ。 実質ラベル付き森の数え上げ。ケイリーの定理を知っていたのでラベル付き木の数え上げは簡単で、$ N^{N-2} $ である。 これを使って頂点をうまいことグループわけする DP をしようと思った。 雑にグループを作ろうとすると、同じ分け方でも先に取ったのと後に取ったので重複を起こしてしまうと思った。 こういう悩みはデジャブであり、どうやるんだっけと悩んでいて現在 $ 3 $ 次元 DP で想定に $ \log $ が付いてしまってかなり怪しいと思って書かなかった。

想定解は、同じような考えの DP だが、グループ分けの重複を避けるテクニックとして現在残っている中で番号が最も若いものが含まれるグループを考える。くそ~これ ABC ですら存在したよな。どの問題か忘れたけど。というわけで普通に $ O(N^{3}) $ で解ける。完。

F 以降はまた今度やろうと思う。

内容が薄いのでフリー欄。 この間ズーラシアに行った。 クソ暑い日だったのでズーラシア行きのバスに乗ったらたどり着くときになったら自分らのグループしかいなかった。

実際にズーラシアに入園してみても人はかなり少なかったように感じた。 暑さがかなり厳しい日だったのでアホみたいに水分補給をしたし、途中でかき氷も摂取した。

f:id:spider_0859:20210906131921j:plain:w250f:id:spider_0859:20210906131914j:plain:w300
バクはプールで排泄するらしい。だとしたらプールって呼ぶなよ。

その日の夕食はそのまま安安に行って肉を食べた。美味しかった。 一日中動物の世話になった日だったな…

f:id:spider_0859:20210906132259j:plain:w300
悪しき肉を聖なる炎で燃やす装置

そんなところで今日は就寝。

09/04 (SAT)

今日はお台場に行く約束をしていた。具体的には大江戸温泉物語が 9/5 に閉館するということで行こうという話になったそうだ。ちなみに自分は野次馬なのでその事情は後程知ることとなった。

11:00 に最寄り駅で待ち合わせをしたのだが、この時点で大江戸温泉物語は死ぬほど混んでいた。11:00 開館なんやが… というわけで昼飯を食べてから戻ってくるという予定になった。 ダイバーシティ に一旦移動して遅れてくるのをラウンドワンで待つ。 2 クレぐらいボルテをやったが、どうも昼飯前の音ゲーは向いていないかもしれない。 みんなしっかり音ゲーをしたおかげでまあまあ時間を消費する(音ゲーマーさん…)。

全員が集まったところで、フードコートで飯を食べる。

f:id:spider_0859:20210906133212j:plain:w300
昼飯のすた丼。これから温泉に行こうっていう人の飯ではない。

食事を済ませたあと、追加で来る友人を拾うために大江戸温泉物語に行くが、$ 3 $ 時間待ちという情報を得て他の温泉に行くことにした。調べると有明にも温泉(スパ?)があるらしいのでそこに向かうことにした。 温泉など入るのは久々なので身体が熱されたり塩漬けにされたり水圧で攻撃されたりして整い倒した。当然、風呂上がりはコーヒー牛乳を飲んだ。

f:id:spider_0859:20210906133647j:plain:w250f:id:spider_0859:20210906133655j:plain:w250
有明の湯。右側はオロナインC とポカリを合わせたオロポという飲み物。

温泉から上がった後はしばらく、寝たりオロポなる飲み物を飲んだりして過ごしていた。 すっかり健康になったところで秋葉原に移動して夕食を食べることになった。 時間短縮も兼ねてガストに入店する。食べ物の写真を撮るのを忘れたがチーズインハンバーグを食べた。久々にスキル無自覚チー牛の匠を発動させていたことに今気づいた。

f:id:spider_0859:20210906134306j:plain:w300
ロボネコチャンが料理を運んできてくれた。すげ~。

その後当然のようにゲームセンターに吸い込まれていく。 まあまあがっつり音ゲーをしてBPL 始まった時間ぐらいに帰路についた。

f:id:spider_0859:20210906134404j:plain:w300
Absolute Domination [MXM] 苦手意識あったが 998 まではいけそう。

BEMANI PRO LEAGUE を見ながら帰宅していたのだが、Lightning -> ステレオミニジャック の小機器がついに壊れてなにも聞こえなくなったので諦めて寝ながら帰った。 帰宅して続きを視聴した。単純な人間なのでまた弐寺のモチベが結構あがった。

実はかなり疲れていたので入眠がスムーズだった。

09/05 (SUN)

11:30 起床。かなり厳しい。疲れていたので途中で目が覚めても一瞬で二度寝を決めてしまった。

朝食を食べて少しばかり作業をした後に、今日は兄と昼食を食べに外出した。

f:id:spider_0859:20210906134915j:plain:w300
KFC を食べた。

昼食にケンタッキーを食べたあとゲームセンターに向かう。 魂の川柳「音ゲーは やれる時間に やっておけ」をモットーにしているので滅茶苦茶音ゲーしました。 今日はボルテがすっかり待ち一億人だったため、ポップン弐寺をメインにプレイした。

f:id:spider_0859:20210906135130j:plain:w300
弐寺リハビリ。1㍉ぐらい戻ったような戻らないような。

両方の機種ともに、少しずつ押し方を思い出してきたのでこの調子で実力を戻して楽しく遊んでいきたい。

帰宅して夕食を食べたあとはベッドにひっくり返って niconico 動画を閲覧していた。 面白すぎワロタ。

Codeforces Div.2 があるので、超久しぶりに出場することにした。

Dashboard - Codeforces Round #742 (Div. 2) - Codeforces

A 問題。$ 2 $ 行 $ N $ 列に 1x2 ドミノを縦横に敷き詰める。一列目の情報が与えられるのでもう一列を復元しろという問題。 U ⇔ D をするだけ。

B 問題。MEX が $ A $ になって XOR 和が $ B $ になるような最短の数列を求めよという問題。 $ 0 $ から $ A-1 $ までの数字は必要。それの XOR は $ O(1) $ で求められることが知られるのでそれと $ B $ との XOR を取る。 その値を追加の数字の XOR で構成する必要がある。$ 0 $ なら空、$ A $ なら $ 2 $ 個で構成、それ以外は $ 1 $ 個で構成できる。

C 問題。繰り上げ桁が通常より一個上にしてしまっている和の話。 10 桁ぐらいしかなくて繰り上がりが発生する可能性があるのは高々 $ 8 $ 桁なので全探索しても $ 2^{8} $ 通りしかない。 それぞれに対して桁数ループをする必要があるが、それを加味しても十分高速に計算できる。 事前に一桁の数字同士の和で数字 $ x $ が何通りの作り方で作れるかを計算しておくと良さそう。 コンテスト後に偶奇に分ければただの足し算になるという知見を聞いて、感動した。天才かよ。

D 問題。和が $ S $ の $ 10 $ 進数の数列を $ 11 $ 進数に解釈してしまったときに大きく解釈できるように構築しろという問題。 できるだけ上の位に数字が集中すると嬉しいなーとなった。制約も緩いし下の位からやるだけに見えたが、一旦 E を見る。そして返ってくることはなかった(ゴミムーブメント)。

E 問題。数列に対してクエリを行う問題。 $ 1 $ つ目のクエリは、数列の $ x $ 番目の値を $ y $ にする。 $ 2 $ つ目のクエリは、数列の $ [l,r] $ に対して、単調非減少の連続列は何通りあるかを求める。

減少する箇所やそれぞれの極大な単調非減少列の通り数の寄与を平衡二分木管理すれば解けそうとわかった。 多分想定じゃないけど、明確に解けたのでとりあえず E から書いたほうがいいかなと思って書き始めた。 バグり散らかし、なぜかコンテストが終了。は???

久々に Codeforces に出たらすっかりムーブが下手くそになっていたので、徐々にアジャストしていきたい。 今週はこんな感じで。来週には Codeforces にも完全に復帰していきたい。

週記(2021/08/23-2021/08/29)

7 月末から 8 月頭にかけて,ワクチンの副反応に苦しんだり忙しかったりして週記を書くのをやめていた. ようやく元の生活リズムに戻りつつあるので,これを機にまたつけようと思う.

最近の変化を言うと,健康のためにリングフィットアドベンチャーを始めたことが一番大きい. リングフィットアドベンチャーをした後,シャワーを浴びて寝ると言うのが完全に健康そのものなのだ. しかし,これには一つ問題点があって,Codeforces のコンテストと疎遠になりつつある. Codeforces に復帰するタイミングを完全に逸してしまっている.できれば今週の VK Cup Final の Div.1 から復帰したいな.

あとはできるだけ外出を減らしてピアノ鍵盤をしばく時間が増えた. 発表が迫っているのに全然上手くならないため,単純に焦っている. 長らく基礎練習とかもサボり気味だったため,久々にしっかりしばく日々に戻ったら腕が痛くて狂っていた

08/23 (MON)

7:45 起床.世間は夏休みが終わったり終わらなかったりしているが,今日は大学に行く. というか普通にお盆周り以外の平日は普通に研究をしているため,もう正直夏休みとかどうでもいい.

行きの電車では昨日の D - Unique Subsequence の解法を再考していた. 昨日のコンテストの後,BEMANI PRO LEAGUEアーカイブを見ながら 「もらう DP をすればセグ木で高速化できそう」と思って書いたら通った. しかし,コンテスト中は配る DP に終始しており,この方向でも解けないか考えていた. やりたい DP テーブルの更新が区間内の同じ数字の中で最左にある要素(のインデックス)」に加算を行いたい (詳しく書くと長そうなのでこの問題を一つの記事にしようかな…). 遅延セグ木でまとめて加算を行ってしまうと最左以外にも加算を行ってしまう事になる. 悩んでいたが,現在着目している要素と同じ数字が次に現れるところの DP の値を 0 クリアしてから配ると良いかも. なんにせよ,あまり見ないタイプのセグ木高速化 DP だったので復習しておきたい.

大学について,モンスターエナジーを購入して気合を入れてから作業を開始する.

前に週記を書いていた時も思ったのだが,大学にいて作業している時間については書きにくいため,困る. いや殆ど生活の記録のためにつけているため退屈な内容でもいいのだがあまり読み返す気がなくなるのもどうなのかと思ってしまう.

今日は昼にケイジャンビーフチーズステーキサンド食べた. 毎週毎週ライスの方を食べていたので,月曜のキッチンカーのメニューを制覇しようと思ったので軽く変えてみた. 思ったより凄まじい見た目をしていたので写真を撮った.

f:id:spider_0859:20210825231734j:plain:w300
ケイジャンビーフステーキサンド.見た目が凄まじい.

17:00 ぐらいに大学を出る.最近ゲームをしていなかったのでゲームセンターに行くことにする. 最近やっていないだけあって全然上手くなくてちょっとしょげたが,色々なゲームを久々にやってかなり満足した. そのまま大学の近くで夕食を食べた. 元気ぼうやなので夕食の後も音ゲーをした.

帰ると 22:30 を回っていた.最近はピアノもよく弾いているので腕が強くなっているかと思いきや,普通に音ゲーで疲れてしまった. どうやら,音ゲー筋とピアノ筋は違うらしい. 疲れたので汗を流してそのまま就寝した.ARC D の別実装は明日以降に回そう…

08/24 (TUE)

8:30 起床.今日は大学に行かないので多少ゆっくりしたスタートだ. なんやかや朝の支度をして作業を開始する.

そういえば最近,使うエディタを VSCode から vim に変えた. というのも,サーバに接続してリモートのファイルを VSCode で編集するとかライブラリのスニペットが怠いとかもう正直うんざりだったのだ. Windows 育ちで GUI呪いのように身体に死についてしまってしまっている自分ですら そう感じるのだから,世間の人はもっとこれを感じるだろうと思う. まあ,大きなプロジェクトみたいなものを弄るときは GUI の方が良いこともある気がするので棲み分けが必要なのかもしれない.

あと長らく一部のマウスイベントがアプリケーションに伝播しないという理由から tmux を敬遠してきたのだが,まあもう普通に面倒臭いので入れることにした. 普通に便利だった.マウスイベントとかもうどうでもよくなった.GUI の呪縛から解き放たれつつあって嬉しい.

ついでと言っては何だが,これに伴って競技プログラミングの環境も完全に WSL に移行した. 元々使っていた WSL 環境が WSL 1 を使っていた. WSL 1 は,厳密には Linux カーネルが動いているわけではない.Linuxシステムコールを受け取って Windowsシステムコールに変換して それを実際に Windows くんが実行しているといった代物である. そういうわけで,ちょいちょい動かないことがあったりした. また,システムコール変換とかをしているためか,ディスクアクセスが異常に遅いのが困りものだった. WSL 2 では本当に Linux カーネルが動くので安心だ.

まあ WSL 2 に切り替えればいいだけなので,切り替えた.ディスクアクセスが速くなって感動した. ディスクアクセスが遅いせいで存在しないコマンドをタイポで入力したときに悠久の時を待たされることが無くなった. fzf コマンドと連携する vimプラグインがあるのでちょっとカスタマイズしてあいまい検索でライブラリを貼り付けすることが出来るようにした. 普通に前より快適で大満足している.今迷っているのが WSL 環境に補完プラグインを入れるかどうかである. 競技プログラミング文脈ではあまり必要に見えないがどうだろうか. AtCoder Library の引数とかが見られたり,uniform_int_distribution とかを補完してくれるのが嬉しいだろうか.

f:id:spider_0859:20210825233319p:plain:w300
現在の競プロの環境.割と満足している.

別に環境整備の作業をしていたわけではないが,作業を終える. 本来は 18:15 まで作業をするのだが,最近は早く上がってピンチなピアノをしばいている.

夕食までずっとピアノを弾く,8 小節ぐらいを時間単位で弾き続けると流石に狂える. 最近は暑いのも相まってうっかり死にそうになっている. 連日で弾いているので腕の筋肉痛が取れないまま再び練習をしていて苦しい.

夕食を食べる. 今日は Codeforces があるが,結局久々でいきなり Div.1 を出る勇気が出なかった. 代わりに MIB 3 を録画してあったので見た. 実は 1 と 2 は既に最近見た.まあシリーズ全て見たことがあったので見返しだったのだが,内容をある程度覚えていても十二分に楽しめるいい作品だ.単純な SF ではなく笑いどころもあるのがとても好みに合っている.

シリーズの 4 作目が出てほしいという気持ちはあるのだが,シリーズが大分 3 作で綺麗にまとまっているのと,単純にトミー・リー・ジョーンズがもうだいぶお爺ちゃんなのとで厳しさを感じている.

夜は寝た.夜は寝る時間なので.Codeforces やっていた頃の自分が信じられない.

08/25 (WED)

9:00 起床.特に時間的拘束がある日ではなかったので自室でまったりしてから,朝食を食べた. 朝食はハムとチーズとトーストにバターを塗って食べた. 世の朝食で最もシンプルでうまいものはバタートーストだと思っている.

一応今日もオンラインでのミーティングがあったため,報告するためのものを見つけたり開いておく準備などしていた. あとは漫画とか読んでいた気がする. 最近は特に新しい漫画を読み始めたりはしていないはずなのに漫画読み返している. 面白い漫画があったら賜りたいが,これ以上追うものを増やしたら終わりそうなので完結しているものを賜りたい.

昼食は親子丼を食べた.美味. 昼食を食べ終えると本日の拷問の時間だ.連日で腕を酷使したせいで今日も腕が重い. 思い切って今日は軽い部分練習のみを一通りこなすことにした. それに今日はピアノ教室に行く日なので疲労困憊で行っても先生が困惑してしまう.

最近はちゃんと練習時間を無理やり創出しているため,教室で惨めな気持ちになることは減った. ただ単純に研究とピアノと少々の漫画 or 競プロだけで一日が終わる日々はなかなか来るものがあるので, 9 月のピンチを抜けたら一旦生活を見直そうと思う.

教室から帰るとミーティングが待っている. 正常に動いたはずの pythonスクリプトがなぜか壊れていてムカつく. 黙って正しいグラフを生成していてほしいな.

ミーティングも終わると,少し夕食まで時間がある. 普段なら時間から結局ピアノを弾くのだが,今日は腕を休ませることに自分の全細胞が同意していたのでやめておくことにした. 代わりにコンビニに行って切らしていたケチャップと自分が飲む酒とつまみなどを購入するなどしていた.

夕食を食べると一気に眠気に襲われた. 父親が iPhone に CD の音源を入れたいというので色々見ていたが,普通にこういうのが一番難しいと思った. 情報工学専攻の人間でもこういう「アプリケーションの操作」みたいなことが全然できない.カンも悪い. いや,コンピュータに詳しい人が使えないようなインターフェースを作ったやつが悪いに決まっている.許さん.

またフリーの時間が訪れた. 暇なのでここで週記の更新を行う. これを書いている途中に先週の ARC D の別実装を書こうとしていたのを思い出す. 遅延セグ木(双対セグ木)を使った配る DP 解法で通しておいた.

Submission #25335428 - AtCoder Regular Contest 125

配る方が直感的に感じるけど,少なくともセグ木高速化の時は貰う DP を採用した方が無難そうだ.

08/26 (THU)

9:10 起床.自宅作業のためギリギリまでゴロゴロできるとはいえ,ギリギリを攻めすぎた. 普段なら大学に行く曜日にしているが,最近はピアノを弾くためだけに自宅にいる日を増やしている. 作業自体は大学にいる方がいい気がするし,家にいると単純に人間と関わらないので寂しい.

今日は作業と練習を終えたら sak さんのアルゴ式でも始めようかと思いながら作業開始. 本日はなかなか VPN に接続できなくてイライラした.

本日も作業を早めに終えて,拷問腕いじめタイム開始. 先日流したのが功を奏したのか腕の重さがなくなっていつもよりいい感じに弾けた気がする. ただし,三週後ぐらいには完成していなければならないと思うと絶望しかない.

夕食.おじいちゃんなので何を食べたのかは忘れました. このあとうっかり YouTube を開きながらベッドに横になっていると,気づいたら 23:45 になっていました… さようなら僕の Div.2 … 寝汗をかいていたので諦めてシャワーだけ浴びて寝た.

08/27 (FRI)

11:30 起床.寝坊しました.まあ今日は休みの日で,兄と近場で遊ぶ予定だったのでよかった. 昼飯を食って外出する.まあ遊ぶと言ってもゲームセンターに行くだけなんだけど… カラオケとか兄と行くのはちょっと嫌だしな.

ゲームセンターに向かう. 近場で SOUND VOLTEX の新筐体が置いてあるゲームセンターが一つしかないので必然的にそこに行くことになる.

最近完全にボルテサボり気味だったのでしっかりやることにした. 色々やっていたら,徐々に戻ってきて最高難易度もボチボチ押せていたので良しとした. あとは pop'n music をプレイした. 自分の地元では全然このゲームが人気ないため有難く連呼させていただいている.

本日の具体的なリザルトは大体下のような感じ.ポップンのリハビリ中かなりつらいな.

f:id:spider_0859:20210829122312j:plain:w250f:id:spider_0859:20210829122322j:plain:w250
本日のリザルト.ボルテは惜しく,ポップンはしっかり押し負けている.

今日は遊んで疲れたから拷問はいいかなと一瞬思ったが, ピアノの神様がいたら相当なケチ野郎で一日でも弾かないとゲボほど下手くそになるので 泣きながら夕食まで弾いた.

夕食後,今日は yukicoder 311 があるので出ようと思う.前回はうっかり酒を入れたが今週は入ってない.頑張る.

A: 指示に従って算数をする問題でした.

B: $ [L,R] $ 内に含まれる整数 $ A,B (A \leq B) $ で連続和が素数のものを数える問題. 立式してみると $ A+B \leq 2 $ か $ B-A+1 \leq 2 $ が自明で精査すると,$ A=B, A=B-1 $ しかないので 単純に区間素数カウントをすれば良いことになる.篩で十分.

C: ゲロムズで困った.最初の $ N-2 $ 個を $ 1 $ にすることで実質 $ 2 $ 個の問題になり,解けてハッピー. 自由度が高すぎる問題は初手適当に固定してみるのが手か. $ 1 $ は分母のみ $ +1 $ という変わった性質を持っているので,試さないのは怠慢という見方もあるか…?

D: 雰囲気がガラっと変わってスタンダードな問題.最初 $ 1 $ を $ K $ 個あって,各素因数ごとの 配り方を重複組み合わせで求めて掛け合わせる. ただしいつもの二項係数ライブラリではだめで,$ \binom{N}{M} $ の計算が $ O(M) $ になるような手法を用いる.

E: 零冪行列とか調べていた.コンテスト後,急に隣接行列に見えたら最長パスの問題だと気づきうつ病に…

F: B の制約強化版.yosupo judge を知っていたので本当に貼るだけだった.ありがとう…

コンテスト順位は 33 位.E でポカをしていることを考えるともうちょっと上を狙えてしかるべきコンテストだったな. というか $ 0,1 $ だけで大きめの行列とかいうの,隣接行列を疑えよ…と過去の自分に言いたい. 累乗とかいうのも誘導ポイントなのにアンテナがヘタっているとしか思えない.

08/28 (SAT)

8:30 起床.朝から WSL 2 のディストリビューションUbuntu 20.04 LTS にするなど,パソコンをいじり倒していた. なんか全然うまくいかないため朝食を食べないまま昼食の時間になってしまった. なぜだか知らないんだけど今まで Ubuntu 16.04 LTS を使っていたんだけど,これはなぜだろう. 多分だけど WSL 1 のせいな気がする. ただしこれのせいで色々なソフトウェアが入らず,色々やっている内になんか環境がぶち壊れたのでもうあきらめた.

具体的には C++ の補完のために clangd を入れようとしたら,もうめちゃくちゃになった. clangd とは,いわゆる Language Server で常駐してソースを解析して IDE とかのリクエストに応じて情報をくれるプログラムだ. こいつが裏で動いていることによって補完したり,関数の定義元に行ったり,引数をポップアップで見られたりするわけだ. vim 全然詳しくないので最近先輩に教えてもらったのだが,vim 側のクライアントのプラグインとして coc.nvim というのがある. 使ってみると普通に便利だ.競プロに補完なんて必要ないと思ったけど,自分のライブラリの命名とか引数とかよく忘れるので実はありがたい. ただ clangd という名前の通り,Clang の C++ を解析するヤツなので GCC 独自仕様については注意してほしい. 競技的には #include <bits/stdc++> がその最たる例だと思う. 当然これを平気で書くと怒られるので, https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/precompiled/stdc%2B%2B.h とかから stdc++.h を落としてきて適当な位置 (今回は /usr/local/bin/bits とするか) に置いて競技ディレクトリのルートに

[compile_flags.txt]

-I/usr/local/bin

をブチ込めば多分大丈夫なはず.正直競技で使いそうなものだけ #include するお手製の stdc++.h を用意するのも良い気がする.

一般的な(広義)プログラマーはこのぐらい知ってそうで長々とウザいと思うが,競技er はなんか知らなそうなのでこの週記に書き起こしておく意味があると信じている.WSL で完璧な競技環境を整えたらブログのエントリーにしたさがある.

マジで気づいたら夕食の時間になっていた.土日だけ時空が歪んでいる. 今日は CodeChef があるらしいが Codeforces も復帰できていないのに Chef に出る元気は出てこないかな.

夕食後,21:00 から BEMANI PRO LEAGUE がある.土曜日のこの時間は ABC が入りがちでなかなか生で見られなかったが今週はなかったので生で見ることができた. 音ゲー大好きボーイなので,最高のコンテンツとなっている. 今回の試合だと SUPER NOVA Tohoku を応援している. 判定厳しめのゲームは当日のコンディションでいとも簡単に BAD でハマったり黄ばみまくるから恐ろしいなと思うなどした.

試合の鑑賞後は WSL 環境のログインシェルを bash から zsh にしたので zsh について調べていたが,情報量が多すぎて混乱していた. 長らく Windows 環境でわちゃわちゃしていたこともあってここら辺のツールの知識がまったくないことに危機感を最近覚え始めている.

08/29 (SUN)

7:30 起床からの 9:30 起床からの 11:30 起床.記憶は曖昧だが 5:30 にも目が覚めていた気がする.病気か?

朝食を食べて週記の編集をしながら漫画アプリの無料ポイントを貪る作業をしていると,マンガワンという小学館のアプリで 無料ポイントが得られないことを確認した. ついにこのアプリは無料ポイントをくれなくなったかと思ったが,よく見たら今日は一大イベントで多くのタイトルが全部無料になる日なのだそうだ.最高かよ.この機会に読もうと思っていたタイトルを読み漁ろうと思った.こんなことならもっとちゃんとタイトルを調べておくんだった…

あと,Ubuntu 20.04 LTS 向けの環境を作ったので設定ファイルなどを全て GitHub に push しておいた. 試しに一か所これで構築したらかなり気持ちよくなれた.もう一か所やろうと思ったら,RedHat だったのでちょっと手を加える必要があった.

さて今日は ABC があるので出ていくぜ.

AtCoder Beginner Contest 216 - AtCoder

A: 言われた通りに判断を下します.譜面定数らしくて草.

B: 文字列のペアの Unique チェック.set でもなんでも.

C: $ +1 $ と $ \times 2 $ を使って $ 10^{18} $ 以下の数字を $ 120 $ 回いないに構築する問題.これは二分累乗法みたいにやるだけ.

D: シリンダーの中の上から同じ色のボールのペアのみを取り出せて,全て取れるか判定する問題.ちょっと悩む.しかしよく考えたら $ 1 \rightarrow 2 $ と $ 2 \rightarrow 1 $ みたいなのが存在したら不可能だと気づいた.というかまあ DAG かどうかですね.よってサイクル検出をすればよし.

E: 乗る度に楽しさが $ -1 $ されるアトラクションが $ N $ 個あって $ K $ 回までアトラクションに乗れる時の,乗ったアトラクションの楽しさの総和を最大化する問題.普通に上から貪欲が最適なのだが,愚直シミュレーションだと間に合わないので,最後に乗るアトラクションのその時点での楽しさを $ X $ として二分探索すると高速化できて嬉しい.愚直シミュレーションの高速化としての二分探索,忘れがち.

F: こういうのは max の方を固定して考えて,それ以下の値のみを選んだり選ばなかったりすればいいってジイちゃんが言っていた. というわけで $ A $ の昇順にソートして制約を見たら解けていた.今までの F が難しかったのでまごまごしていた.

G: データ構造を必死に使った貪欲が見えるも,非想定っぽくて嫌なので粘着していたら落とした.最悪や.

H: 解けるの?これw

G はコンテスト後に牛ゲーと聞いてウケていた.僕にはコンテスト終了直前にはフローに見え始めてオワってました. これが Rated だったら G を必死に貪欲で書いていたに違いないので,やる気が足りないな.

そんなこんなで今週の週記を締めようと思う.来週からもちゃんと書きたいと思います.

週記(2021/07/05-2021/07/11)

07/05 (MON)

9:30 起床。鬼のように身体が重い。おそらく副反応の最後っ屁だろう。 昨日は $ 38.4 $ 度もあったのに全然元気だったのが嘘のように怠いし、頭痛もした。 先日に「 $ 38.4 $ 度あるけど元気だぜ」みたいなツイートをしてしまった手前 Twitter で体調不良ポストをするのが躊躇われた。 情けないぜ助けてくれ。

布団から出られる気がしないし、スマホで典型を確認する気にもならない。 $ 30 $ 分ぐらいゴロゴロした後、今日がゼミであることを思い出す。 流石に出られない可能性が高そうなので、欠席の旨を連絡しておいた。

メール送信ついでに BOX を確認すると、返信の必要な大事なメールが来ていたため対応する。 それだけしたら、食欲もないのでまたベッドに逆戻りした。

12:30 ぐらいになんか回復してくる。頭痛も和らいだし腹も減ったので、街に繰り出して昼食を探す。 昼食探しが下手すぎて、マクドナルドに行きついてしまう。 せっかく元気になってきたのでモバイルオーダーで迅速に注文してなんとか 13:00 のゼミに間に合うようにしたいというねらいもあった。

マックに到着するともう品物が用意されていた。目視できる距離で作り始めてもらったのに速すぎないか?すごい。

受け取るときにアンケートに答えてほしいみたいなことを店員に言われた。 滅茶苦茶早く購入が済んだのでクーポンももらえると言うので答えることにした。 訪問した店舗では、テストで「キオスク」なる端末を置いているらしくて、一般的な質問に加えてそれについての質問があった。

f:id:spider_0859:20210707192851p:plain:w400
キオスク。画像は拾い物でアメリカの写真らしい。

どうやらこの「キオスク」、海外ではもうすでに導入されており日本でのテスト導入が始まったとか。 機能は割と見たまんまで、この端末をタッチして注文をすることができる。 まあ言ってしまえばちょっと機能の多いセルフレジである。

ちなみに余談だが、自分が購入したのは当然のように、トリプルチーズバーガーである。 チー牛の匠なのでこのバーガーの復活期間にこれ以外注文するつもりは毛頭ない。

ちょっと失礼なのだが、ゼミを聞きながらマックを食べた。発表練習回なのと欠席連絡をしたので許してほしい。 あと今の体調だとナゲットが余計だったので頼んで後悔した。

ゼミが終了する。先週分の週記を投稿し忘れていたことに気が付いたので、投稿する。 そのあと Twitter を見たり、先日の ABC をちょっと真剣に振り返ってみたりした。 精進を真剣にするような体力がないので、ダラダラしていた。

20:00 から友人と用事(オンライン)の約束をしていたが、一時間伸びたので夕食までは本当にグダグダしていた。 今日に関しては本当に体調が悪くてだらだらしていたのでしょうがない。

夕食を食べて 21:00 から zoom に繋いで話す。

それすら終わると本当にやることがない。正しくはあるけど、今の元気さで出来ることがなくなる。 仕方がないので(?)追加されたというボルテの 19 の譜面でも見ることにした。

www.youtube.com

簡単と TL で言われている割には難しく見えた。 とはいえ、$ 2 $ 回目再生するとやっぱり PUC できそうな気もしてきたのでやらないとわからないかも。

そんなことでベッドに向かうのだが、本日は根つきが今年一番悪く最悪の夜だった。 明日は 9:30 - 18:30 勤務の something(詳しくは言わないでおくがインターンではない)の初日なのでマジで心配になった。

07/06 (TUE)

8:30 起床。全然眠れなかった。ゲボほど眠い。というかゲボ。 流石にやばいと思って $ 30 $ 分追加で寝る。 起きる。まだゲボほど眠い。助けてほしい。

とりあえず朝食を食べる。9:30 を迎えたので、作業に着手する。 進捗がゴミというか、$ 1 $ ㌨㍍も集中できなかったので昼休みの時間を前倒しで使用して仮眠をすることに決定。

なんとか起きていられるようになったので、作業をする。とてもつらい。 先程の時間の代わりに昼ごはんはマッハで食べる必要がある。あまり覚えていない。

そんなこんなで 18:30 までやった。正しくはボケてて 19:00 ぐらいまでやった気がする。 30 分で何かを生み出せたわけでもないので、どうでもいいが。

散々な日だった。 Twitter を見ると sak さんが以下のような自作問題ツイートをしていた。

ふむふむ。中央値の定義次第で細かいところは変わるだろうが、なんにせよ二項係数の積の和を求めれば良さそうだ。これをすれば前計算で階乗とその逆元(素数 $ \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 の履歴を開きながらその日あったことを思い出しながら書いた。 基本的に TwitterChrome を開いているため、両方を確認すれば自分がその日何を考えて何をしていたかが大体わかる(危険だろ)。

夕食中と食後、母親が佐々木蔵之介主演の「サイバー捜査班」みたいなドラマを見ていたので一緒に見る。 ツッコミどころがないわけではないが、そこはフィクションなので粗さがしをするのは野暮というものだろう。 とはいえ、こういうのはあまりにもお粗末だと興ざめしてしまうのだが、ストレスは特になく受け入れられるものだった。 強いて言えば主人公の一人の女性刑事がちょっと邪魔をしてきて鬱陶しい場面が少しあったぐらいか。

そういえば、今日は 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 ぐらいには中断して家を出た。

目的のキャンパスに到着すると、時間がちょうど昼時になっている。 なんか前言った場所では昼休憩の時間だった気がするので、ちょうどいいし自分も昼飯を食べてから部屋に向かうことにした。 麵屋こころの本店がここにあるらしいという情報をキャッチしたので、向かう。

f:id:spider_0859:20210710161614j:plain:w370
麵屋こころ本店。美味しかった。

麵屋こころ自体久々に食べたのよう沁みる。 本当に美味しかったのだが、ちょっとした方針で店員同士が揉めててちょうどその間が僕の座っている位置だったのだけが困った。 麵屋こころのまぜそばはかなり美しいのでブログに記録したくなるな。

色々あってかなりかなり帰りが遅くなる。 もっとチャチャっと終わる用事だと思っていたのでかなり疲れた。

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 $ も必要だからだ。

やる気が起きな過ぎて親の酒を強奪して飲もうと思ったが、全然缶のものがない。 去年家で作られた梅酒がまだ少しあるので、それを飲むことにした。 コップの半分もなかった。かなりひもじい。

f:id:spider_0859:20210710170149j:plain:w300
ウチの現存する最後の梅酒。

さて明日は学科の発表系イベントが 10:00 からあるので就寝。

07/10 (SAT)

9:55 起床。アラームをかけ忘れていて起きた瞬間、心臓がブラジルまで行った。 なんとか学科のイベントに間に合う。 本来自分が出ても意味ないだろみたいなイベントとはいえ、出ないと怒られるので本当によかった。

このイベント、M2 の中間発表などに対して M1 が質問をしなければならないのだが、研究室の違う(専門の違う)M2 の先輩の研究なんて質問が出来るほど理解できるわけないだろと思う。というかそれがどこの馬の骨ともわからない M1 に理解されていたら、そのテーマで修士号をもらえるか怪しいだろ

愚痴を言ってもしょうがないので、速攻ノルマである $ 3 $ つの質問をこなした。 ところで、今日はついうっかり昼過ぎに散髪の用事を入れてしまったので質問もこなしたし、つないだままちょっと抜け出した。 大分スッキリした。帰ってきてもまだイベントを続いていたので安心した。

イベントが終わる。ここで、週記を溜めていたので現実に追いつかせておいた。

せっかく散髪したので、枕カバーについている死んでいった毛たちをコロコロで丹念に処理しておいた。 結局その夜寝たら髪の毛が付着しまくった…

夕食を食べ終わって、のんびりしていた。 ABC を完全に忘却していた。やっちまった…。完全に日曜日だと思っていました。

$ 50 $ 分遅刻ぐらいで問題を見たが D 問題まではすぐに解けた。C 問題がいつもより難しく感じた。 E 問題がむずそうだった、時間が足りなかったが多分解けているので時間が出来たら書こうと思う。

悲しい気持ちになったので、Div.3 を出ないで寝ることにした。

07/11 (SUN)

8:30 起床。今日は友人宅に行くことになっていたので支度をして出かける。

詳細は省くが、今日は友人宅に行って昼夜はスパイスカレーを作って食べた。 正しく言うと、俺はスパイスカレーの知識が全然ないので観察担当者です。

f:id:spider_0859:20210712134058j:plain:w280f:id:spider_0859:20210712134103j:plain:w280
スパイスカレー。美味しかったです。

久々に高校同期の友人に会えたので満足しながら帰宅。 コドフォ Div.1 があったらしいが気にしない。というかそれに出ないことをなんとなくわかって今日は過ごすつもりだったので。

帰り道に Twitter を見ると、典型 90 の閉会式をやっていた。E869120 さん、お疲れ様です。 というわけで、一応帰宅してから週を終えることができた。

ちなみに、友人宅で競プロの問題を少し解いたので Streak に関しては心配がない。 D - 一刀両断 がその $ 1 $ つだが、これ普通に難しく感じた。 まあ、自分の場合は幾何ライブラリを整えているので、線分同士の交差判定をすれば良いのでいいが、0 から作ると大分しんどそう。 ccw をソラで実装できるし、まあそうでもないかな。よくわからないです。

東京に行くと疲れるのか、毎回就寝がちょっと早くなる。

週記(2021/06/28-2021/07/04)

06/28 (MON)

9:00 起床。夜更かしをしたのに意外と眠くないし、体調も悪くない。 朝ごはんを食べながら今日の典型を確認する。

https://atcoder.jp/contests/typical90/tasks/typical90_bz

問題概要。$ N $ 頂点 $ M $ 辺の無向グラフが与えられる。 自分より頂点番号の若い隣接頂点が $ 1 $ つだけ存在するような頂点の数を答えよ、という問題。

それぞれの辺に対して、頂点番号が大きい方に $ +1 $ カウントする配列を構成して最後に配列を舐めて、$ 1 $ の要素数を数える。 $ O(N+M) $ で解けるし、グラフを構成する必要も実はない。構成した方が慣れ親しんだ手法な気もするが。 キーワードがわからない。「隣接頂点全探索は辺の数のオーダー」とかですか、わかりません。

わからないながらも大学に向かう。時計をどっかにやってしまってめちゃくちゃ QoL が下がっている。 行きの電車内では昨日の AGC-B を改めて見て考えていた。 挿入 DP は昨日散々考えて不可能であると判断したのでのんびり眺めた。

ちょうど全体の和の半分になるような subset を考えた時にその subset を高橋くんが取る場合の数に思いを馳せた。 高橋くんがとらない数字は青木くんが取る。それぞれの subset を独立に並び替えてその順番で取ることを考えると、それぞれの並べかえと 数えたい順列が一対一対応することがわかる。気づいてしまえばボケ簡単だった。

昨日ちゃんと解けた C といいこの B といい、順列の数え上げというありふれたテーマなのにパターンマッチへのアンチテーゼのようで、AGC の問題の質の高さを感じた。

大学に着いたらいつものケイジャンチーズ牛飯を購入してモンスターエナジーとともに摂取する。 食べ終わる時間ぐらいに、ゼミが開始する。今日も B4 の発表回。いい意味でも悪い意味でもスライドにそれぞれの個性がでているなあと思った。 去年の僕もこんな風に見られていたと思うと震えちゃうね。

f:id:spider_0859:20210629120424j:plain:w300
今日のセブンのおやつ。先週から試してるんだけどこれがおいしい。

ちなみに今日のおやつにはいつも通りプリンを買ったのだが、先週から試しているこれがかなり美味しいと再確認した。 三層になっているのだが、一番上がチーズケーキっぽく、真ん中はクリームで、一番下がプリンになっている。

そんなこんなで作業をしていた。今日は途中で先輩方と話こみ、様々な話になった結果、色々な知見とかが得られた。 話の話題に出て読もうと思った論文を Paperpile: Modern reference and PDF management - Paperpile に入れた。 こういうののために研究室に行っているというところが大いにある。本当は頻度を増やしたいと思っているんだけど、研究室に行く日はほぼ確実にピアノの練習ができないため、中々難しいところである。

帰ると 22:00 ぐらい。夕食をむさぼる。 夕食後、上に書いた AGC-B の解法で書いて通した。これで通らなかったら上の解法を消さなければならないのでほっとした。

06/29 (TUE)

11:00 起床。正しくは、9:00 には起きていたのだが布団の中でもぞもぞする時間が長すぎた。

今日の典型を確認する。★3 だ。

https://atcoder.jp/contests/typical90/tasks/typical90_ca

問題概要。$ H \times W $ の二次元配列 $ A,B $ が与えられる。$ 4 $ マスの正方形領域に対して一括で $ \pm 1 $ をする操作を行うことが出来る時、$ A $ を $ B $ に一致させることが可能かどうか判定せよ、という問題。

蟻本には $ \mod 2 $ の世界での問題(正方形フリップ)が載っていたような気がする。 今確認したら蟻本 p.141 にそれらしき POJ の問題が載っているのだが、自分の記憶より難しい問題だった。 こういう問題は、端から見ていくとそこで操作を行うべきかが一意に決まるため貪欲に解ける。具体的に言うと、上にも左にも不確定なマスがないようなマスが左上になるような正方形領域に何回操作をするかは自明にそのマスの値により一意だ。 蟻本のやつは、$ 3 \times 3 $ の正方形領域だったため $ 1 $ 行目を決め打たないと一意にならなかったが、この問題ではその心配もない。

バイト先の slack からの返信を確認した。確認しながら、サボってた時期の典型をちょっと見ることにした。

059 - Many Graph Queries(★7) とにらめっこをすることにした。

問題概要は簡単。$ N $ 頂点 $ M $ 辺の DAG が与えられて、頂点 $ A_i $ から $ B_i $ に到達可能かどうかのクエリ $ Q $ 個に答える。 sample の隣接行列を書いてしばらくグッと睨んでいた。

しばらく睨んでまともな解法がなさそうなことに気づき $ 64 $ bit をまとめて処理することを考える。 到達可能性の行列は頂点番号の降順(トポロジカル順序の逆順)に構築可能だ。 $ u < v $ であるような頂点 $ u,v $ を考えたときに、$ u $ の到達可能性を bit vector で考えたとき、 $ u $ が $ v $ に直接到達可能ならば、 $ v $ の到達可能性の bit vector との OR で更新すれば良いことが分かる。直接到達可能な頂点数は辺の数の $ M $ と一致するため、全体で到達可能性行列は $ O(MN) $ で前計算出来る。 OR をとるパートで $ 64 $ bit ずつ処理すれば $ 64 $ 倍速くなり、多分間に合うのだろう。まあ $ 64 $ bit というかワードサイズなのだが…

ここで書き始めるも、Memory Limit を思い出し計算すると $ 1200 $ MB ぐらいかかりそうなことが判明。最悪や。 冷静になると、DAG の到達可能性なので、$ M _ {i,j} \quad (i \leq j) $ の部分だけあれば十分なので大体半分ぐらいになるから足りそう。 この手の高速化は結構カツカツな状況が多いので offset やブロックのインデックスを求める時に割り算を使うと終了しそう。ワードサイズは当然二冪なのでビットシフトや AND を使おう。でも二冪定数の割り算ぐらいビット演算に最適化してくれそうだけど…どうだろ…

色々工夫して頑張って書いたら $ 500 $ ms を割ったので、記念にソースを貼っておく。 まあ測定結果とかキャッシュミス率とかを監視しながらチューニングをしたわけではないのでもっと速くなるかもしれないけど。 やったことを箇条書きしてみる。

  • 最大ケースで使用するサイズを事前に求めて、そのサイズでメモリプールをグローバル変数で静的確保。
    • malloc でいちいち確保をすると free も面倒だし困る。今回途中で解放や再利用はしないためこれでいい。
    • bitset が全て連続領域なので多少高速化に寄与する可能性あり。
    • マージの時に連続領域だと次の bit vector の先頭ポインタを使うことで楽に後ろから OR を取れる。
  • Fast IO … 入力を一括で静的領域に受け取り、自分でパース。出力はバッファリングして最後に一気に write & flush する。
    • $ 10^{5} $ 行ぐらいあるので、間で何回も flush すると遅そう。入力もそこそこ多いけどこっちの影響は不明。
  • 最適化オプションは O3 にした。何か起これと祈る。

▶ソースコードを展開

そして、毎週恒例のピアノしばき。今週は、最後まで譜面の流れの把握が終わった。 ここからは只管にスムーズに綺麗に速く弾けるかを、訓練によって伸ばしていくパートなのである意味気が楽。

夕食まで少し時間があったので論文を読む。集中力が持たないので終了。

夕食のあとは通話をする用事があったのでする。 そういえば、この前研究室の先輩がやっていたため初めて知ったんだけど、zoom ってスペースキーを押しながら喋ると一次ミュート解除ができるらしい。これを使えば色々な場面で誤爆を起こしにくいし、わざわざどっかに行ってしまった zoom の窓を探してミュートボタンを解除する作業が必要なくなる。 自分は感動したんだけど、実はみんな知っていたりしますか?

通話が終わる。もうなんか今日はいいかという気分になる。 競技プログラミングの問題を一問通してもうだらだらすることにした。

D - アルファベット探し

問題概要。$ 7 \times 7 $ のサイズの $ A,B,C $ の文字のドットパターンみたいなのが与えられる。 これが $ 90 $ ° 単位で回転したり、相似比が正整数になるような拡大が可能である。 大きな図面 $ H \times W $ が与えられるので、それぞれのアルファベットの出現回数を答えよ、という問題。

拡大があるので、真面目にパターンマッチングっぽいことをすると工夫が必要な上、かなり怠い(というか完成させられるか怪しい)実装になりそうだ。 こういう問題は色々な側面からそれぞれのパターンの特徴が得られないかを観察する。 一番ありがちなのは塗られているマスの数とかである。 今回も数えてみると、$ 7 \times 7 $ の $ A,B,C $ の塗られているマス数はそれぞれ $ 12,16,11 $ だ。 これらの数が正整数の相似比で拡大されるので、任意の正の平方数を掛けてもユニークか確認すると、しっかりユニーク。 パターン同士が重なることはないと制約にあるので $ 8 $ 近傍を接続した連結成分のサイズを確認すればいい。 DFS を用いて実装するのが楽で、 $ O(HW) $ の計算量で計算できる。

パターンから取りやすい特徴を抽出して判別をする問題、ICPC のフィリピン地区大会で出会ったため一生忘れなそう。 あれは $ A $ から $ Z $ まであったので特徴を抽出する段階でまあまあ嫌だったけど。 今回はひとつの特徴で完全に判別がついたけれど、$ 2 $ つ以上の取りやすい特徴の複合キーで判別することの方が多そう

就寝。

06/30 (WED)

9:30 起床。10:45 分提出のショートレポートを書く。 物理っぽい内容が含まれている講義なので、大分懐かしく感じる。 情報工学をしているとマジでいわゆる理系っぽいことは何もできなくなっていく。 大学受験化学なんて多分 $ 8 $ 割はもう忘れている。

ショートレポートを書き終えて朝食を食べながら、今日の典型を確認する。★6。

https://atcoder.jp/contests/typical90/tasks/typical90_cb

問題概要。$ D $ ビット以内で表現可能な正整数の列 $ A $ が与えられる。$ A $ の全ての要素との AND が $ 0 $ でないような整数 $ x \quad (0 \leq x < 2^{D})$ の数を求めよ、という問題。

制約を見ると $ N \leq 20 $ で $ D \leq 60 $ だ。こんなんもう桁 DP やるだけではないでしょうかとなる。 bit DP との複合だから難しいということなのかなとか思いながら DP を組む。 $ dp[i][S]$ : $ i $ 桁目まで $ x $ を決めて、$ A $ の各要素との共通部分を持っているかどうかの bit vector が $ S $ の時の場合の数。

この DP は状態数が $ O(DN) $ である。愚直に遷移すると $ O(N) $ かかる。 ここで初めてこの出題の意図を理解する。このままでは計算量が $ O(DN^{2}) $ でかなり怪しい。 事前に $ B_i $ : $ x $ の $ i $ 桁目を $ 1 $ にすることで共通部分を持つことの出来る $ A $ の要素の集合、つまり $ i $ 桁目のビットが立っている要素の集合の bit vector を前計算することで、遷移が $ O(1) $ になり計算量は $ O(DN) $ と余裕になる。 よく考えると、昨日の日記で解いたワードサイズ定数倍改善と同じ。 でも定数倍改善かなり頑張ればそのままでも通ったりするかも

典型が解けて安心しながら多少作業をするも、ピアノがあるのでピアノをしばく。 レッスンに行く。下手くそ。以上。頑張ります。

帰ってきてからは、主に競プロをやっていた。作業もちゃんとした。 夕飯を食べたあとはカプリティオチャンネルの動画を見ていた。

www.youtube.com

僕自身は全然競技クイズはやらず、たまにみんはやをプレイするぐらいの一般人だが、クイズを見るのは好きだし、 カプリティオチャンネル等のクイズ系の YouTube チャンネルはしっかり一般人にも楽しめるように作って合って見やすい。 最近ちょっと YouTube でもこうの短い動画以外のものを見る時間がとれていなかったので面白そうなものから消化していった。

ここで slack を確認すると、研究室内で濃厚接触者が出たらしく(感染者というわけではなさそうだが)、 とりあえず二週間ぐらい全てがオンラインで行われて、かつ研究室にもなるべく行かないようにというメッセージが来ていた。 二週間の間、ケイジャンとはお別れの様だ。というか二週間多分地元すら出ないことが確定した。

嘘をついた。3 日にはワクチンを接種しに行く予定である。なんなら、他の外出の予定も既にあった。ショックで一瞬全てを忘れていた。

■■■■■の予定表を入れなければならなくて、これがなかなか自分が微妙に忙しいせいで埋まらなくて困っていた。 正直困り果てていたが、催促のメッセージが来てしまったのでちょっと無理っぽい感じに入れて後でいろんな人にお話をしなきゃだめかも… こういうなんか懸案事項が複数ある状態って死ぬほど嫌いで、耐えがたい。こういう時の精神の持っていき方が $ 23 $ 年ちょい生きてて一ミリもわからねぇ。

あと、書類って何で一意解釈できない項目のオンパレードなんだろう。 本当に助けてほしい。普通の人間がこういうのを普通にこなしていると思うと信じられない。HELP!!!

取り乱したが、明日は朝に大切な用事があるので今日は持参物を確認して寝るか。

寝る前にサボっていた典型を一つ通すか、と 60 を見たら既視感があったので週記を見返したら考察はあった。

右から見て最大値が $ A_i $ になる LIS が欲しくなる。 LIS の DP は $ O(1) $ で revert が可能なので、事前に右からの LIS は計算しておき順次 revert していけば欲しいものが得られそうだ。

週記(2021/06/7-2021/06/13) - むかでの競プロ備忘録

どうでもいいけど、永続配列を使えば revert の必要すらないな。

書き上げた段階で、自分の脳がおかしいことに気が付いた。 普通に revert なんてことをしなくても左右からそれぞれ $ A_1 \cdots A _ {i - 1} $ と $ A _ {i+1} \cdots A_N $ の LIS の長ささえわかれば答えが出るので、左右から DP するだけ問題でした。う~んこの…

07/01 (THU)

7:10 起床。大切な用事があったのでちゃんと起きられて安心した。 雨がしっかりを降っている。

支度と朝食を済ませて目的地に向かう。行きの電車で今日の典型を確認する。★5。

https://atcoder.jp/contests/typical90/tasks/typical90_cc

問題概要。$ N $ 人の生徒がいて、 $ i $ 人目の生徒の身長と体重がそれぞれ $ A_i, B_i $ となっている。 チーム内のどの $ 2 $ 人を取ってきても、その身長の差・体重の差が $ K $ 以下であるようなチームを作りたい。 作れるチームの最大人数を答えよ、という問題。

実は昨日より悩んでしまった…。昨日のは着眼点を間違わなければ処理するだけの問題だったが、今日はどこに目をつけるかが難しいように感じた。 $ A_i, B_i \leq 5000 $ と $ K \leq 5000 $ という制約があることに気づく。 ここに注目すると、生徒を二次元平面上に点としてプロットすることができる。 情報のペアや、区間を二次元平面にプロットするのは典型なのでここに詰まったのは反省の余地がある。 この時に条件がどのように言い換えられるかを考えると、$ K \times K $ の正方形領域に入る点の集合なら条件を満たす。 というわけで、二次元累積和を前計算することで $ O(A _ {max} \cdot B _ {max}) $ で解くことができた。

典型が解けた安心感から、後は到着するまでうとうとしていた。 用事のためとはいえ、東京に行くのが久しぶりでテンションが上がった。

初めて行く場所だったので早めに着くように調整したのだが、やっぱり迷う。都会難しすぎるぜ。 まあそこは時間に余裕があったので結果として問題がなかった。 問題なのは雨がメチャクチャに降っていたことだ。 自分の革靴は大分前から履いていて裏のゴムは大分ヘタってしまっている。 その関係で雨の日に滑りやすい地面をあるくとヌゥルヌゥルしまくって怖いのだ。 朝から何回も転びそうになっていたんだけど、ついに目的地の目前で大ゴケしてしまった。 その際に左手首を負傷した。ピアノにも音ゲーにも支障が出そうで心から嫌だった。 あと結構色々な植物が繁茂している場所でコケたので汚れるし周りに人が居なかったので感情を抑えられず声出た。 雨の日にはもうその革靴を履いて外出しないことを誓った。というかいい加減買い替え時なのかもしれない。

最悪な気分になりながらも予定よりも $ 15 $ 以上早くに到着していた。 汚れたズボンとかカバンとかを拭いていたので詳しい時間はあまり覚えていない。

さて用事を終えて昼飯を食べなければ餓死する時間になってしまった。 とはいえ、全然親しみのない土地で飯を探すのに苦労してしまった。 困り果ててキョロキョロしていたのだが、完全に都会に出てきたての田舎の若者ムーブをしていたので恥ずかしい。 普段都会人と行動を共にして自分も都会人のフリをしているのだが、いざ一人になると無力な田舎者ということが暴かれていく。

ダイバーシティという施設が近くにあることは知っていたので、ここに向かうことにした。

f:id:spider_0859:20210701223828j:plain:w300
歩いていると、フジテレビくんを発見。

歩いていると、フジテレビくんを発見した。写真を撮っているところを人に見られて恥ずかしかった。 施設に到着すると、ドラえもんが出迎えてくれた(画像無し)。 中に入るとうんこミュージアムなるものまであった。 飯を探しているのにコレに出会ってしまい、もう顔中○まみれや。

施設内でまたしても迷子になる。エレベーターが探せない。やっとの事でエレベーターと施設の案内みたいなのを発見すると、どうやらマクドナルドがあることがわかった。流石にここにきてマックはないなということですんでで思いとどまり、牛カツの店に入る。念のため言っておくと、チーズ要素はない。

f:id:spider_0859:20210701224525j:plain:w370
牛カツ。ダブルにしたらマジで多かった。おいしかった。

今日は研究室内のミーティングの日なのだが、用事のこともあって帰っても全然間に合わないので開き直ってダブル牛カツ膳を頼む。 シングルだと正直足りないかなと思い上のを頼んだのだが $ 1.5 $ 倍ぐらいのボリュームを想定していたら、しっかり原義ダブルの $ 2 $ 枚きて焦った。ちゃんとメニューを見ろよ。$ 1.5 $ 枚を想像していたので最後の半分は相当苦しかった。

胃の健康のために、施設内のベンチみたいなところで休憩をとってから帰路についた。 胃がいっぱいなのと、東京に対する疲れによって帰りの電車では疲れて爆睡していた。 日本の治安の良さに感謝しながら帰宅。

帰宅してから、作業とかスマホ弄りとかを仕様かと思ったが左手首が痛すぎて横になっていた。 気づいたら寝ていて夕食の前だったのだがワロタで済ませておいた。

食後は今日の典型を書いてきた。二次元累積和で実装するのでその幅は $ K+1 $ でなければならないところを $ K $ にしていて、サンプルが合わなくて $ 5 $ 分ぐらい無駄にした。AC。

C - 高橋君と国家 を解いた。 $ N $ 頂点 $ M $ 辺のグラフが与えられる。頂点 $ v $ を交易所にするのに $ c_v $ のコストがかかり、辺 $ i $ を整備するのに $ r_i $ のコストがかかる。全ての頂点が交易所に到達可能にするのに必要な最小のコストを求めよ、という問題。

交易所にする頂点を確定させたら、交易所を各連結成分に含む最小コストの森みたいなものを求めればいいなとか思う。 制約的に交易所にする頂点を選ぶようなアルゴリズムは無理なので頭を少し捻ると、仮想頂点を置いて、交易所にする操作を仮想頂点から各頂点への辺として考えてしまうと最小全域木問題になることがわかる。あとは書くだけで AC。仮想頂点を置くことで最小全域木になる問題、たまに見るな。

今日もサボり分の典型を処理していく。Deck(★2)

整数の書かれたをデックの上に載せる・下に入れる・上から $ k $ 番目の数字を出力する、の $ 3 $ 種類のクエリに $ Q $ 個答える問題。 マジで std::deque を使うとそのまま。

062 - Paint All(★6)

大分前の典型なので問題概要は省略。 冗談抜きで $ 30 $ 分ぐらいかかってしまった。 初手頂点 $ A_i $ と $ B_i $ を結ぶ辺を張ったグラフを考えたのだが、全然いい筋の解法が浮かばない。 よくよく考えると、$ A_i $ か $ B_i $ のどちらかが白なら $ i $ が黒に塗れるという関係は $ i \rightarrow A_i $ と $ i \rightarrow B_i $ の二辺で表せて、こっちの方が良く特徴の現れたグラフになる。これでも解けなかったので逆操作を考える。全部黒の状態で逆操作を考えると、$ i = A_i $ または $ i = B_i $ のような頂点以外は白く塗れない。これ以外の逆操作は、$ x \rightarrow y $ かつ、頂点 $ x $ は黒、$ y $ は白のような場合に頂点 $ x $ を白く塗ることができる。したがって複数始点の逆辺を辿る DFS/BFS によってすべての頂点へ到達可能なら、問題の条件を満たす。行きがけ順の逆順に出力すれば答え。

速く解けなかった理由は

  • 全然うれしくないグラフへの落とし込みをしてしまった。
  • 操作の前提条件が緩く、結果が明確な操作は順操作がつらく逆操作が楽がちなことを忘れていた。
    • 「遷移可能な頂点のうち少なくとも $ 1 $ つが白なら黒く塗れる」がこれに相当。
    • よくあるのだと範囲塗りつぶしみたいな操作もこれにあたる。(塗りつぶし前は任意色だが、後は一定)
    • 「$ x $ の倍数なら $ x $ で割れる」みたいなのもこれか。

就寝。ところで、探している漫画が見つからずにもやもやしていた。

07/02 (FRI)

9:30 起床。からの 11:45 起床した。最悪。

トーストを朝ごはんに食べた後、今日の典型を確認する。★3。

https://atcoder.jp/contests/typical90/tasks/typical90_cd

★3 にしては大分怠い見た目をしている。問題概要。$ L < R $ であるような正整数 $ L,R $ が与えられる。$ x \in [L,R] $ の $ x $ を $ x $ 個ずつ黒板に書いたとき、黒板に書かれている数字の数を答えよ、という問題。 数字というのはどうやら桁のようだ。

$ L,R \leq 10^{18} $ なので愚直系は全部アウト。桁ごとにやるしかなさそうだ。例えば $ 1 $ の位の寄与を考えると、 $ 1 $ 以上の整数の和になる。これ難しくないか? 閉区間 $ [L,R] $ に対して問題を解くのは面倒なので、$ [0,X] $ の問題を解けば $ [0,R] $ の答えから $ [0,L - 1] $ の答えを引いてよし。 なぜかもうジャッジが来ているので提出して AC。

一般の閉区間や半開区間の問題を $ [0,X) $ の問題に落とすことで幾分か楽になるの多いな。

サボり分の消化。063 - Monochromatic Subgrid(★4)

問題概要は省略。こういう問題は片方の軸について固定するともう一つが簡単な問題に落ちることが多い。 制約を見ると $ H \leq 8 $ なので行についてその行を選択するかどうかを決めうつことにする。$ O(2^{H}) $ で決めうてる。 すると、各列に対して取る行について全て同じ数字でない列はそもそも選べない。 また、出現する数字が同じ列のみを同時に選択することができる。 よって std::map などによって、それぞれの出現度数をカウントしてやれば、$ O(2^{H} HW \log{W}) $ とかで解ける。AC。

昼飯を食べる。焼きカレーとかいうの最高にうまい。

064 - Uplift(★3)

問題概要省略。区間加算操作の前後での隣接差の変化は区間の端 $ 2 $ 箇所にしか現れない。これが全てだ。初期状態の「不便さ」と、隣接差(符号付)を計算しておいて、あとは端に関して隣接差と「不便さ」を更新していくだけだ。区間加算が $ 2 $ 箇所に対する操作に言い換えられることは難しめの問題でもよく出る内容な気がする。 区間加算だけじゃなくて区間 xor でも出題がある

065 - RGB Balls 2(★7)

問題概要省略。★7 はやはり結構難しい。赤・緑・青のボールを取る数をそれぞれ $ r,g,b $ とすることによって立式することができる。

$$ \left\{ \begin{align} &r \leq R, \quad g \leq G, \quad b \leq B \quad \cdots (1) \\ &r+g \leq X, \quad g+b \leq Y, \quad b+r \leq Z \quad \cdots (2) \\ &r+g+b = K \quad \cdots (3) \end{align} \right. $$

見てすぐに $ O(K^{2}) $ の解法は思いついた。これは $ r,g,b $ の内 $ 2 $ つを決めうつことによって、式 $ (3) $ によって残り $ 1 $ つも確定する。その $ r,g,b $ が上の全ての式の条件を満たすかチェックして、満たしていたら $ \binom{R}{r} \binom{G}{g} \binom{B}{b} $ だけ答えに寄与させれば良い。

当然この問題の制約では $ 2 $ 乗は間に合わないので、工夫が必要。 $ 2 $ 色のボールに関する不等式制約がかなり煩わしいと思う。グッと睨むと $ (3) $ を使うと $ 1 $ 色のボールの制約にすることが出来ることに気が付く。これを整理すると、

$$ \left\{ \begin{align} &K - Y \leq r \leq R \quad \cdots (4) \\ &K - Z \leq g \leq G \quad \cdots (5) \\ &K - X \leq b \leq B \quad \cdots (6) \end{align} \right. $$

のような制約が得られて、これはかなり分かり易い。$ r $ を決めうってみる。この時に $ g + b = K - r $ であるような場合の数が高速に求められれば解ける。 式 $ (5),(6) $ に注意しながら、有効な $ b,g $ について、$ \binom{G}{g} $ や $ \binom{B}{b} $ の配列を構成すれば、その畳み込みをすれば欲しいものが手に入る。FFT を使えば $ O(K \log K) $ でできる。結局ボトルネックFFT なので、この計算量で解けた。AC。

目的意識を持って、一直線に式を変形するの難しいな。今回は $ 2 $ 変数に関する条件を $ 1 $ 変数に関する条件に変形可能。 こういうのはどこまで行っても ad-hoc になってしまうため、変形の目的と実際の変形のパターンの引き出しをたくさん持っておくのが良い気がする。

あといい加減自分の FFT を作ろうかなと思うんだけど、FFT は定数倍が結構センシティブな気がしていてなかなか… ところで 059 - Many Graph Queries(★7) の想定解について触れる。 想定は、隣接行列を更新していくのではなくクエリを $ 64 $ 個ずつ処理するものだった。背景としては、到達可能性の配列は $ bool $ 型の配列なのでワードサイズの $ 64 $ クエリまで重ね合わせることで速くなるというやつだ。こちらは MLE が気にならないので賢い。

066 - Various Arrays(★5)

問題概要は省略。全ての $ i < j $ を満たす $ (i,j) $ について、$ A_i > A_j $ であるような確率を足し上げた者が答え。 いわゆる期待値の線形性とか、主客転倒とか言われているテクニックな気がする。 期待値の問題は期待値の線形性を利用しない問題はほぼないのではなかろうか。 ちなみに上の実装を完全に全探索で行っても $ O(N^{4}) $ で間に合う。ちょっと工夫をすると $ O(N^{3}) $ になって、頑張ると $ O(N^{2}) $ になると思うが、出題側も主客転倒が問いたいだけなので非本質ということなのだろう。

連続して消化作業をやっているように見えるが、途中に TA 業務やゼミが挟まっている。 TA といえば今週は $ 2 $ 人も質問に来た。心なしか他の TA にも普段より質問が来ているように感じた。 今回の Java の講義内容がテストとラムダに関する内容だった。 学部生ということもあって、テストがどういうものかわかっていなくて混乱するみたいなケースが多そうと感じた。 研究室に来るまでにはちゃんとわかっていて欲しいと思うレベルの解説をした。説明うざいと思われていたら立ち直れない。 壊れている素数判定関数の単体テストを書くみたいな課題が出ていて、最低 $ 2 $ つのテストメソッドを書けとのこと。 何をどうテストしていいのかわからず、正しい素数判定をして $ 1 $ から $ 100 $ までの整数で比較するみたいなメソッドを書いて、もう $ 1 $ つ何を書けばいいのかわからない、とかそれに近しい質問が $ 2 $ つだった。 気持ちはわかるが、その「正しい素数判定」が正しいということを保証をしてくれるものがないので、テストとして不適切ということを言って、こういうのはシナリオ別に分けてメソッドを記述するからこの場合最低でも素数と非素数の $ 2 $ つのテストが必要で、その入力と出力に関しては人間が計算・判断したものを入れる、と言ったら納得してくれた(と思う)。まあ正しくはこれはブラックボックステストなのだが、ブラックボックステストホワイトボックステストの話まで始めたら流石に嫌われると思ったのでやめた。

典型の消化作業続行。067 - Base 8 to 9(★2)

$ 8 $ 進数 $ \rightarrow $ $ 10 $ 進数 $ rightarrow $ $ 9 $ 進数をする関数を定義して、$ K $ 回実行する。 投げると $ 1 $ ケース落ちるのでよく見ると入力に $ 0 $ があるので、$ 0 $ の時に空にならないように直すと通る。 この手のの問題で $ 0 $ があるの本当に不愉快だな。悪口ではなく負け惜しみです。

食後に yukicoder contest 302 - yukicoder があるので出る。

A 問題。最初指数結合法則が足し算だと思っていた(腦)。冷静になると掛け算で、デカいな~と思いながら $ \mod 10^{9}+6 $ を取ってやってから二分累乗をする。

B 問題。この問題難しい!$ (0,0) $ が負け、から遷移を書いたり思い浮かべたりしてガチャガチャ弄っていると証明できそうな構造が見つかる。証明出来て投げる。コーディングミスで 1 WA もらう。

C 問題。最初に与えられた整数の $ \mod 10^{9}+7 $ を求めて $ S $ とする。 $ S $ 以下で $ A^{n} $ 以上の数字の数が $ \left \lfloor \log _ {A} k \right \rfloor \geq n $ を満たす $ k \in [1,S] $ の数。 よって $ 1 \leq n \leq \left \lfloor \log _ {A} B \right \rfloor $ について $ S - A^{n} + 1 $ を足し上げる。

D 問題。一目で $ 2 $ 乗の DP は思いつく。$ dp[i][j] $ : 和が $ i $ で初項 $ j $ の倍数でなければならないような条件を満たす列の数、とする。$ i $ の約数しか遷移が進まないので、遷移を含めた計算量が $ O(M^{2} \log M) $ になる。よく考えると、$ i $ の約数にしか遷移しないので、$ i $ と $ j $ を $ \gcd(i, j) $ で割っても結果が同じことを利用して $ j=1 $ の状態のみを考えることができ、結果状態数が $ O(M) $ になるので、$ O(M \log M) $ で解けた。

E 問題。最初 sample だけを見て、何も考えずに $ 2 $ - 彩色をして少ない方の数を提出した。WA。それはそう。 よくよく考えると解の下界は最小店被覆である。 そして、これは後手が黒く塗りたい頂点以外を優先的に白く塗ることによって達成可能。

FG 問題。前半に時間を使いすぎて考える時間がなかった。復習する。

A はマジで早く解けなきゃいけなかった。というかこれは知っているだろ… B は初手実験を選べなかったのがかなり痛い。これ帰納的じゃなくいい感じに導けるのかな? C も $ 10 $ 進数ではよく問われる問題なのにまごまごして良くなかった。 D は多分こんなもんだけど、スタックオーバーフローなのか手元では Runtime Error ぽかった。 こんな時、minGW くんはうんともすんとも言わないので本当にゴミ。 WSL 環境にした方が絶対にいいなと思う瞬間である。 E は適当をやっている時間がもったいない。あとはトチ狂って Dinic 法で解いたが木の最大マッチングは 木 DP で高速に書けるようにしたいね。

ここら辺の問題を高速に処理できるかどうかが、今の自分の競プロで大切なことな気がする。 明日はワクチン接種なので早めに就寝。

07/03 (SAT)

9:30 起床。今日はコロナのワクチンを打ちに行く。

典型を確認する。

https://atcoder.jp/contests/typical90/tasks/typical90_ce

問題概要。$ N $ 頂点 $ M $ 辺の単純無向グラフが与えられる。$ Q $ 個の以下のようなクエリが与えられるので順番に答える。

  • 頂点 $ x $ の色を出力する。その後頂点 $ x $ とその隣接する頂点を色 $ y $ で塗る。

難しいぜ。クエリ平方分割が脳裏によぎったが面倒すぎるし、かなり計算量が怪しいので実装する気が起きなかった。 途中インキチ解法を思いついたが当然のように嘘だったので、泣いていた。

さて、ワクチン接種の時間が近づいてきたので支度をして三田キャンパスに向かう。 田町駅で降りて、初手方向を間違えた。ちなみに Google Map を見ていたのに間違えたので本当に人間になりたい。

キャンパスに着くと、ワクチン接種の列ができている。 サークルの後輩がすぐ前にいたので退屈しなかった。最も、退屈するほどの時間待つこともなかったが。 長い列のように感じたわりにすぐワクチンを接種できる。筋肉注射は初めてだったので怯えていたんだけど、マジで何も感じなかった。 電車のシートの隣にマッドサイエンティストが居てヤバイウイルスを筋肉注射されても多分気づかないぐらいには何も感じなかった。

↓はめちゃくちゃ焦っている時のツイート。ちなみにしびれはすぐに取れた。

接種が終わった後に後輩と一緒に三田製麺所で昼食をとった。

f:id:spider_0859:20210705141006j:plain:w350
三田製麵所。久々につけ麺を食べたのでよう沁みた。

昼食の後は、日吉に行った。ゲームもした。帰宅。 コドフォも今日はあるのだが、接種直後なので遠慮しておいた。 就寝。

07/04 (SUN)

11:00 起床。なんだか、副反応ぽかったので念のためゴロゴロしていた。 散々ゴロゴロした後に、熱っぽかったら一応家族に報告の必要があるなと思って体温計を持ってきて測ったら $ 38.4 $ 度だった。 普通に熱があってワロタ。元気いっぱいだったので。確かに少しボーっとしていたけど、低気圧のせいだと思っていた。

そんなわけで ABC の時間まで本当にゴロゴロしていた。AtCoder Beginner Contest 208 - AtCoder に出る。 後で出たことを後悔することになる。

A 問題。$ A \leq B \leq 6A $ なら "Yes"

B 問題。こういう場合は大きい硬貨からの貪欲で良い。もっとキツイ条件でも貪欲が適用できるが、まあ今回はいいだろ。

C 問題。満遍なく配る問題。$ a_i $ が小さい順に国民をソートして最初の $ K' $ 人に $ +1 $ 個キャンディを配ればいい。

D 問題。数え上げるものをよく睨む。$ k $ が小さい順に計算して $ 1 $ 頂点ずつ経由点を増やしながら計算することを考える。ワーシャルフロイド法と完全に一致しているので、ワーシャルフロイド法の過程の要素を足し合わせればよい。

E 問題。落とした。今思えば普通に熱のせいで脳が多少不調だったのかもしれない。いや、そうであってくれ。 $ 10 $ 未満の積ということには一瞬で気づく。次の瞬間に $ 2,3,5,7 $ しか素因数がないことに気づく。TDPC のサイコロ?みたいな問題と似たような感じで素因数の数を状態に持っていれば解ける気がする。次元の数がすごいことになる。設計をかなりミスっていて、あれこれやって雑に次元とかを増やしまくった結果、TLE と相成った。結局落とした。最悪。

とは言え、最近方針一瞬だけど実装が結構嫌だなみたいな問題が ABC で出題されるようになってきた気がする。

F 問題。読んでない。

またレーティングをちゃんと下げた。最悪だけど、今回は副反応中に出た自分に責任があり、涙…。

今週は悲しみの内に終了。