むかでのチラ裏

競技プログラミング現役引退でチラ裏に・・・

週記(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 にも完全に復帰していきたい。