週記(2022/05/09-2022/05/15)

05/09(月)

午後2時前に起床。1時間ほど布団でゴロゴロした後、シャワーを浴びて購買に向かった。この時間帯、すでに購買のパンやおにぎりは売り切れている。仕方なくお菓子とカロリーメイトを買って、帰り道でコンビニに寄り昼食を確保した。

先週金曜日の配信アーカイブを改めて確認していると、チャットリプレイができないことに気づいた。設定を弄った記憶はなかったが、調べてみるとカット編集を行ったアーカイブはそれができないようになってしまうらしい。配信画面にコメントを表示するのはこれの対策という意味もあったのだと知った。昔は設定していたものの、いろいろソフトの連携が必要で面倒になり、最近は止めてしまっていた。

午後4時半からインターン先の定例会。GWを挟んで2週間分の進捗を報告する。といっても先週は帰省先でのんびりしていたので、なんとさらに一週前の火曜日にコーディングしたのが最後の進捗であった。ここまで間が開いてしまうと、考えておいた改善点や実装案も全部頭からすっぽ抜けてしまってかなり効率が悪い。たまにドカッとやるよりは、毎日少しずつでも進めたほうが良さそうだとだんだんわかってきた。最近は1on1の頻度も低い。1on1駆動開発を再開するべきなのかもしれない。

勉強会はgitの操作について。Online Judge Verification Helperを導入していると、ファイル編集を行った後はいつも自動でverifyが行われるのだが、このときタイムスタンプが記録されるようになっている。そのせいで、ローカルの変更を続けざまにpushした場合、間でタイムスタンプが更新されているとローカルが最新でないと言われて怒られてしまう。そのあと何とかして直してもcommit履歴によくわからないものが入ってしまって気に入らないなあと思っていた。同様に怒られる事例が紹介されていたので、謎のcommitを出さない方法を質問したところ、pull時のマージ戦略を適切に設定すればよいと言われた。細かくは理解できていないが、そういう方法があると知れてよかった。調べるとよくある話らしい。

Merge branch 'master' of github.com:kotatsugame/library · kotatsugame/library@f2689ee · GitHub

Merge branch....みたいなコミットログをなくす - by shigemk2

終了後、先週の日記を書き上げた。YouTubeに目を奪われつつ読み返して校閲し、午後10時を回って何とか投稿した。

ABC250Exを通した。ブルーフカ法という話を聞いていたので、考える方針だけは与えられた状態だった。各家から多始点dijkstraをして、別の家にたどり着いたらその間の距離をMSTの辺にする、ということをしたい。しかし実際に実装してみると、ある家から別の家に向かうパス上では当然逆方向からも近づいてくるので、真ん中でぶつかってしまっていた。そこで、ぶつかった瞬間にパスの距離を計算することにした。各頂点について、そこに最も近い家uとその距離d_uを記録し、別の家vからスタートしたパスが距離d_v\ge d_uでそこにたどり着いたとき、距離d_u+d_vuvパスをMSTの候補にする。これはうまくいった。別の家wd_wがあってvwパスを考えたいとき、d_v+d_w\ge d_u+d_v,d_u+d_wであるから、いったんuを経由しても損しない。公式解説の別解と近いかと思ったが、それよりユーザ解説にリンクがある記事と全く同じだった。

Submission #31574240 - AtCoder Beginner Contest 250

tokoharuland.hateblo.jp

午前2時までかけて課題を2つ倒した。その後ラノベを読み、午前5時に寝た。

05/10(火)

午後2時起床。しばらくYouTubeハーメルンで時間を溶かし、午後4時くらいになってようやく布団から出た。

さくらインターネットからメールが来ていた。atgolferのサーバが攻撃の踏み台にされているらしい。

特に重要なデータを置いているわけではないので、サーバの中身はもう何も触らずOSを再インストールした。そこから改めてPythonの環境を整え、atgolferを実行できるように。何もかも初期化された後の最初の実行は、現存するすべての最短コードが新たに打ち立てられた扱いとなるため、ツイートしない設定で行う必要がある。--verboseオプションをつけて進捗をしばらく見守っていたのだが、かなり時間がかかるようだった。一度キャッシュが保存されればいくらか高速になるのだろう。

chokudaiさんにリプライを送ってみたところ、今日あーだこーだーが行われること、そこにゲストとして呼んでいただけることが確定した。いよいよである。

午後8時を過ぎたあたりでchokudaiさんがあーだこーだーの予定を忘れていたことが発覚し、今日は配信しないことになった。来週はGW中で自分が帰省しているので、また再来週以降となる。

週記(2022/04/25-2022/05/01) - kotatsugameの日記

学食で夕食を摂り、しばらくラノベを読んで、午後8時から配信の視聴を開始。30分前には入っていてと渡されたZoomリンクを待ちきれず踏むと、僕の準備ができていることをchokudaiさんも認識したらしく、今日のお知らせが少なかったこともあって少し早めに登場することになった。

www.youtube.com

そこからはずっとマシュマロやチャットに寄せられた質問に答えていた。答えたい質問を拾ってと言われても全部答えたくなってしまう。自分に興味を持ってもらえるのは嬉しくて、さらに自分のことについて話すのが好きなこともあって、実に80分も喋っていたらしい。いくらchokudaiさんに許しを得られたとはいえ、普通一時間のあーだこーだーを40分も延長してしまったのは少し反省。ただ喋っている間は本当に楽しかった。同時接続数も安定して200人を超えていて、ありがたい限り。

配信を終え、chokudaiさんに出演料としてアマギフを頂いて、解散。エゴサーチをしながらしばらく余韻に浸っていた。

声が好きだというツイートをいくつも目にしてかなり嬉しかった。以前から配信する度たまにそういう感想を見つけていたのだが、より多くの人の耳に入り、より多くの人に言及されたという事実を確認して、自尊心が非常に高まった。さらに、発言の間を埋める意味のない言葉が少なくて良いというツイートもあった。配信に乗るからには常に意味のある言葉を喋るよう努力すべきであると考えていて、ある程度達成できていたからこういうことを言っていただけたのかなと思う。これも大変嬉しい。一方で、よく整理できていないうちに話し始めてしまうことも多かったと感じているので、うまいことバランスを取れるようになりたい。

さらにいくつかの出来事を述べる。まず父からLINEが来て、受け答えがしっかりしていると褒めてもらえた。次に、配信で言及したこの「kotatsugameの日記」が、新しく記事を出したわけでもないのに一日のアクセス数400を記録した。最後に、マシュマロの画面を配信に直接映しながら新しい質問を確認したのはちょっと不用心であるとの指摘があった。いやはやその通り。度を過ぎればマシュマロ側で弾かれるとは言え、問題のない質問ばかり来ていたのは単に運がよかっただけに思える。

赤になったときにGoogleフォームで質問を受け付けたのだが、これをもう一度やってほしいと要望があったので、用意した。もう一つ、最近おすすめのなろうを教えてほしいという質問を保留しているので、これも含め近くこのブログでちゃんと回答する。しばらくお待ちいただきたい。

午後11時半からCF #790 div.4があったので参加した。2回こどふぉって45分スタートになっていた。

Dashboard - Codeforces Round #790 (Div. 4) - Codeforces

Cまではよい。Dは交点を決めた後、毎回斜めに和を取っても十分間に合う。Eもよい。Fは誤読して大変だった。[l,r]が数列の区間を表すと思い込んで実装。幅の最大値ではなくそれを達成する(l,r)を出力しなければならないことに気づいて書き換えるなどした後サンプルを実行すると、値が全然違っていてちょっと固まった。読み直して間違いに気づき、ソートしてランレングス圧縮して解いた。この問題は8分もかけてしまった。Gは頂点番号の大きいほうからループを回せばdfsの必要がない。Hは普通。

コンテスト直後の結果は12位。ただ上のほうに怪しいアカウントがいくつかあって、後から確認したら10位に上がっていた。SSRSさんが言語の壁を物ともせずに優勝しているのはすごすぎる。Fの誤読がなかったとしても全然敵わない。

ラノベを1冊読了。「最凶の魔王に鍛えられた勇者、異世界帰還者たちの学園で無双する」2巻。ヒロインが能天気なのはイライラするが、面白い。主人公と現学園最強がバトルするようだったので楽しみにしていた。主人公の油断具合がちょうど良かった。見くびっているのではなく、情報を集めるために手加減していたという描写。主人公は未だに実力を隠したままなので、人目につかないところで戦っていた。まあ2巻から大々的に公開するわけはないか。巻末の次巻予告を見ると、今よりもっと人前に出るような立ち位置になるらしいので、どんな感じに実力が明かされていくのか非常に楽しみである。そのカタルシスを辛抱強く待ちたい。

しばらくYouTubeを見て、日記を書き、午前4時半就寝。

www.youtube.com

05/11(水)

いつ起きたのか不明。正午あたりにChromeの履歴が残っていて、おそらくそれからYouTubeを見ていたのではないかと思う。二度寝できていなかったはず。

午後2時半くらいに布団から出た。1時間後に健康診断があるので、それに向けて準備する。シャワーを浴びるのすらグダグダしていたので、かなりギリギリの時間に出発することになった。

健康診断は事前の予約制で、10分刻みで定員がしっかり決められていたため、全く待ちもなくスムーズに終了した。身長が記憶より縮んでいて悲しい。実は僕の世代は麻しんワクチンを一回しか接種しておらず、紙に「二回接種していない人は別の医療機関で健康診断してください」と書いてあったのが気になっていたが、ダメもとで聞いてみたら問題なく受けさせてもらえた。助かる。

生協で運よく売れ残っていたおにぎりやパンを買った後、しばらく講義棟を徘徊して、競プロサークルのチラシを探した。

帰ってきて、明日のセミナー発表に向け教科書を読み始めた。DiestelのGraph Theoryという本。結構頻繁に集中を切らしていたので、その時何にかまけていたかを順に記録する。

イラストレーターのrurudoさんもVtuberとして活動されていることを知った。この方の声も良い。

るるどらいおん - YouTube

www.youtube.com

すとらさんのチュウニズム配信を見ていた。15の理論値を狙い始めて、午後9時過ぎ、ついに「Trrricksters!!」の理論値が出た。見ているこちらまで心臓が痛くなってくるので、作業中に流し見できるようなものではなかった。そのしばらく後に「Killing Rhythm」の最後のタップスライドで散った回があったのだが、こちらは結局出ずに終わった。片方出るだけでも時代が変わったのを感じる。

www.youtube.com

ラノベを1冊読了。「英雄と賢者の転生婚」。主人公最強+学園モノで面白かった。クラスメイトのかませ犬みたいな立ち位置のキャラもそこまで嫌らしくなく、実は立派な人間であったという風に描かれていて気持ちが良い。主人公がなぜ強いのかはまだ全く明らかにされていない。後書きを読む限り考えなしなわけではなく、ただ秘密にされているだけのようだが、特に意味なくハチャメチャに強いとしてもそれはそれで面白いかもしれないなと思った。

教科書を読む作業は思うように進まなかった。YouTubeを見てしまったので当たり前か。GW前、先生に「2章までは終わらせてきたいですね」と大言壮語してしまったが、結局1章も終わっていない。午前6時になって、寝坊のリスクを避けるためいったん寝て明日起きてからまたやることにし、就寝。

05/12(木)

午後0時半起床。

1時間ほど頑張って、とりあえず1章の最後まで目を通すことに成功した。証明も自分の中では納得した気になっている。それが正しいかどうかを確かめていないが、もう時間もないので、破綻していないことを祈るしかない。あとはセミナーの準備として今日話す内容を整理する必要がある。しかし持ち時間1時間で何をどう話せばよいのだろう。適当に先頭から命題を書き出してみるも、どう考えても終わらない量になっている。後半まで突入したら教科書をチラチラ見ながらやらせてもらうか、と諦めて、途中で切り上げてYouTubeを見ていた。なぜYouTubeを見ているのか。

www.youtube.com

家を出て時間通り教室に到着。午後3時からセミナー開始。結論から言うと、今日はもう一人の発表内容が難しくて皆でいろいろ考えていた結果、僕の発表が来週に持ち越しになった。

先々週の予告通り、今週はコンビネータ論理の話。面白そうと言っていたが手を動かすのが楽しいだけであって、命題の証明は大変そうだった。

もう一方の発表は面白かった。面白かったというか次回が面白そうというか。ラムダ計算自体にはあまり触れたことがないが、SKIコンビネータはUnlambdaの経験があるのでそれなりに手を動かしたことがあり、そのパズルみたいな作業が面白かった記憶がある。

週記(2022/04/25-2022/05/01) - kotatsugameの日記

不動点コンビネータの話になった。Unlambdaで再帰関数を実装するのに使った覚えはあるが、今は自力では書けないだろう。まあその仕組みは今日の本題ではない。不動点コンビネータは教科書に載っているもののほかにも大量に(無数に)あり、Wikipediaでも数種類紹介されている。そのうち見た目が面白いものについて、先生にどうなっているか確かめてみよと言われた。

不動点コンビネータ - Wikipedia

L=\abcdefghijklmnopqstuvwxyzr.(r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))とおいて、Y=(L L L L L L L L L L L L L L L L L L L L L L L L L L)とするもの。昔見たときはややこしそうだと思っただけで放置してしまっていた。今日改めて考えてみると、非常に簡単というか、なんだそんなことかとなるような仕組みであることに気づいた。YLが26個続いた形であり、Lは26個の引数を取る関数であるから、そのうち25個までがLで埋められてY=\r.(r (L L L L L L L L L L L L L L L L L L L L L L L L L L r))=\r.(r (Y r))となる。「this is a fixed point combinator」は文字rが末尾にしか登場しない27文字のものであるということだけが重要だったようだ。当然、変数を束縛する順番を入れ替えればもっと自由にできる。

かなり延びて午後6時半に終了。川内で食事して帰宅。ABC250BがRakuで縮められていた。やっていることはPerlと同じに見える。自分でも書いてみたらさらにいくらか縮んだので、それで取り返した。

火曜日に設置したGoogleフォームにそこそこの数の質問が来ていたので、ちゃんと記事を1本作って回答することにした。午後8時に書き始めて、午前7時まで書いていた。もちろんその間には何度も集中を切らしていたわけであるが。

作業用BGMとして、ずっと花譜というバーチャルシンガーの動画を流していた。もともとVtuberが出したフォニイの歌ってみたをいくつかループ再生していて、オリジナルが実はボカロではない合成音声だということを聞いたので気になって調べ、「可不」のオリジナルである「花譜」にたどり着いたという経路。特徴的な歌い方・掠れたような声にハマった。

www.youtube.com

朝になって眠くなってきたのでいったん切り上げることにした。午前7時半就寝。

05/13(金)

午後1時くらいに目を覚ました。二度寝するつもりで布団に横たわったままYouTubeを見たりハーメルンを読んだりして、午後5時まで起きていた。その後もう少し眠って午後7時にまた起床。さらにハーメルンを読み続けて、午後8時に1作読了した。「転生したら始祖で第一位とかどういうことですか」。勘違いものの宿命か、主人公が内心でナヨナヨしているのがあまり気に入らなかった。

syosetu.org

起き上がって食事。腹が減っていたのでパスタを200g茹でた。こういうことをするといつも多すぎて後悔する羽目になっていたが、今日はスルッと食べられた。

少しコードゴルフしたあと、また質問に回答する記事を書いていた。yukicoderは、僕がテスターした問題が2問出題されているが、今週もサボり。先週金曜日に配信画面に映してしまった問題の一部なので、出題の直前にそういうことをしてしまったということでことさら申し訳なくなった。

yukicoderで1問テスターを行った。詳細は当然書けないが、面白い問題だと思った、くらいは言っていいだろう。

週記(2021/10/25-2021/10/31) - kotatsugameの日記

午後11時半から2時間、ECR128に出た。

Dashboard - Educational Codeforces Round 128 (Rated for Div. 2) - Codeforces

Aは最大値と最小値を同じにできるかで場合分け。Bは一番上の行にある一番左のロボットを左上に寄せたとき、その下の行で左にはみ出るロボットが存在するか判定。

Cは難しい。さらにコストが2数のMAXではなく和だと誤読して、一度実装までしてしまった。c_i[0,i)に存在する'1'の個数を表すとすると、i\le jに対して\max(c_{|s|},j-i)-(c_j-c_i)がコストとなる。コンテスト中はここからiとしてはj-c_{|s|}0だけ考えることにしてもよいとして実装したが、その理由は全くもって正しくなかった。j-i\ge c_{|s|}のときコストは(j-c_j)-(i-c_i)なのだから、-c_iではなくi-c_iのMAXを管理しなければならない。

しかし通った。日記を書いているときに調べてみると、j-i=c_{|s|}の場合だけチェックすれば正しい答えが得られることが分かった。これはなぜかというと、(i,j)がそのような条件を満たすとき、[i,j)'0'とその外側の'1'の個数が等しくなるからである。そこからiを左右にずらすとどちらかは大きくなるので、コストも大きくなってしまうというわけ。運がよかった。

Dも難しい。まずa_i=0の場所を埋めるときは、高々1つ中途半端になる値を除いてすべて\pm kであるとしても良さそう。最初にその個数を求めておくと、今見ているインデックス、+kを何個使ったか、中途半端な値を使ったかの3つから現在の位置を計算できる。これでdpすればよいかと思って、左端のMINを達成する方法と右端のMAXを達成する方法をそれぞれ持って実装してみたら、最後のサンプルで落ちてしまった。

考え直して、とりあえず中途半端になる値の位置を決め打ってみることにする。すると残りは\pm kで埋めることになるが、ここでi番目の移動で最小値を達成する場合を考えると、i番目までにできるだけ-kを使って、それ以降は+kを優先的に使うのが最適だと分かった。最初に+k,\dots,+k,-k,\dots,-kと埋めておき、1個ずつずらしていく差分更新を遅延セグメント木で行うことで、O(n\log n)で全ての場合が計算可能。これで解けた、と思ったがWAが取れず、いったんEに移った。

Eは簡単。2行それぞれ駒が存在するかの4通りを次元に持つdpを左右両方向から行って、合流する地点を全探索すればよい。問題なく通ってDに戻ったところ、i番目の移動で最小値ではなく最大値を達成する場合についても考えなければならないことに気づいた。つまり最初の状態が-k,\dots,-k,+k,\dots,+kの場合。書き足してDもAC。残り時間はFを考えて、すべての奇閉路に含まれる辺があればよさそうと思ったが、実装してみても全然検出できずに終わった。遅めの5完で順位は崩壊してしまった。

コンテスト後も記事を書き続け、午前3時半にようやく投稿できた。質問に答えるのは楽しいことではあるが、やはりエネルギーを使う。自分の考えをうまく言語化するのは難しいし、質問を読んで考えたことを全部書くのが良いわけでもない。質問の意図から外れていそうなことは言うか言わないか決める必要があって、もし言うと決めたならせめても論理の流れが自然になるように気を使いたい。とにかく、普段日記を書くよりよほど力を入れて文章を書いたのだった。

kotatsugame.hatenablog.com

そのあとは日記を書いていた。午前7時くらいに切り上げて布団に移動し、ハーメルンの捜索掲示板をいろいろ眺めた後、読み止しにしていた作品を少し読み進め、午前10時前に就寝。

05/14(土)

午後3時起床。しばらく布団でYouTubeを見ていたら、午後4時過ぎに生協の冷凍弁当が配達された。今日は午後6時半からCFがあるので、そのまま起きていることにした。

コンビネータ論理について少し考えていた。Haskellコードゴルフテクニックにポイントフリースタイルというものがある。abstraction eliminationが、これを機械的に行う方法に見えてきた。しかしさすがにSを多用するわけにはいかない。僕の経験によれば、ポイントフリースタイルは基本的に関数合成演算子.を使って進めていくものだったはずだ。Wikipediaを見ていると、さらにC=\f x y.(f y x)B=\f g x.(f (g x))を定義する場合もあると見つけた。Cは明らかにflipである。では、B(.)ではないだろうか?

まずBの型を考えてみる。f:a\rightarrow bとするとg(x):aであるから、g:c\rightarrow ax:cがわかる。つまりB(a\rightarrow b)\rightarrow(c\rightarrow a)\rightarrow cである。Hoogleで調べてみると、見事に(.)がヒットした。感動。意味を考えれば当たり前であるが、純粋に形式的に導けたのが嬉しかった。

(a->b)->(c->a)->c->b - Hoogle

しばらく日記を書いて、午後6時半からCF #791 div.2。

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

Aは、まずn4以上の偶数である必要がある。後はn/2\bmod 2\bmod 3で場合分けすればよい。Bは要素ごとの書き換えタイミングと全体の書き換えタイミングを記録して頑張る。Cは行ごと・列ごとにいくつルークがあるかセグメント木で持っておいて、区間MINでチェックした。setを使う方法をTLで知って、そちらのほうが楽そうだなと思った。Dは二分探索。各頂点についてそこから何回操作できるかをdfsで求める。ループ検出も良しなに。

Eはちょっと大変。回文の中心を決め打ち、長さを伸ばしていくことで、各部分文字列が回文になる場合について「自由に決められる'?'はいくつか」「どの文字が使えなければならないか」を全体O(n^2)で計算できる。自由に決められる'?'の個数を持っていても扱いづらいので、使える文字の種類数を決め打って場合の数の形に直しておく必要がある。'?'の個数がO(n)通り、使える文字集合2^{17}通りでヤバそうに見えたが、部分文字列を見ているとき同時に計算すると実はO(n^2)通りであるとわかった。あとは使える文字集合についてゼータ変換。

Fは面白かった。操作は巻き戻すことができるので、何らかの正規形を考えて数え上げる方針を取りたい。操作で作れる数のうち辞書順最小のものを選ぶとよいのではないかと思った。n桁から9の位置を決めて、8の位置を決めて……とすると組み合わせで立式できた気がするが、各数字を使った個数を覚えておく必要があり不可能。桁dpのほうで実現できないか考えてみる。前にある大きな数字とそれより小さい数字を入れ替えられなければよいので、最後に使った数字を持てばよさそう。これを実装するとサンプルは合った。しかし5ケース目でWA。

ランダムケースで試してみると、結構小さいケースでも間違っていることが分かった。(u,v)=(0,1),(1,2)のケースでWAになることを発見したので、10進法ではなく3進法に制限していろいろ出力してみたところ、201からより小さい120に変換できるのに別のものとして扱っていることに気づいた。01を入れ替えても小さくならないが、それより先と入れ替える場合も考慮しておく必要があるケース。そこで、最後に使った数字ではなく「今何が来ればより小さいものに変換できるか」の文字集合を持ってdpすることにした。その集合がUの状態で、新たに数字d\not\in Uを追加したとき、dと交換できる文字集合VとするとU\leftarrow\{v\in V\mid v\lt d\}\cup(U\cap V)とすればよい。追加した数字と交換した時点で小さくなるか、あるいはそこを乗り越えていけるケース。これで通った。

全完7位。かなり良かった。僕の上に4人も日本人がいてかなり面白かった。

午後9時からABC251に出た。

Panasonic Programming Contest 2022(AtCoder Beginner Contest 251) - AtCoder

AはVimtypoで1WA、|S|=1のケースで足りておらずもう1WA。最悪。BはRubyで書こうとして、先ほどAでWAを吐きまくったのだから慎重にと思い直してC++で実装したのに、うっかりRubyで提出してしまい1ペナ。言語選択ミス、相当久しぶりにやらかした。Cはset。Dは6桁の数を2桁ごとに分割する方法を初手で思いつけた。コンテスト後のTLを見た感じかなり冴えていたらしい。Eは一周回るdpを一か所固定して切り開くやつ。

FのT_1は水曜日にグラフ理論の教科書で見たばっかり。こういう性質を持つ全域木にはNormal treeという名前がついているらしいが、図を見て一目でDFS木だとわかった。例えばLowLinkはこの性質を利用している。T_2についてはT_1と対にして聞かれていることからメタ読みし、DFS木から連想してBFS木を考えてみるとピッタリ当てはまった。

Gで大炎上。多角形による点の包含判定は、右に半直線を伸ばして辺と交差した回数を数える形でライブラリ化されていた。凸でない多角形に対応するためこのような実装になっていることに気づかず、しばらくこの方針で考えていた。他に、逆にクエリの点をずらした多角形がPに内包されるかチェックするようなことも考えるも、いずれも現実的なオーダーにならない。多角形の共通部分を計算するしかないのかと思っていろいろ検索すると、平面走査して特定のX座標における多角形の辺のY座標を管理する方法を見つけた。これを使えば共通部分を計算しなくても判定できるかもしれない。つまり、M個の多角形が直線x=a_iとそれぞれ2点で交わり、その間にb_iが位置しているかをチェックする。多角形の上側だけ考えて実装すれば、下側は符号反転で対応できる。その上側について、辺を線分とみなせばCHTで解ける。さらに今凸多角形を考えているので、辺ではなく直線を考えてもよいということに気づいた。これを最初に気づけていれば……。

うしさんのライブラリを窃盗し、O(NM)個の直線をCHTに追加してみると、まずコンパイルが通らなかった。どうやらテンプレート引数に浮動小数点数が渡せないらしい。ライブラリ自体を文字列置換で書き換えた。ACLのセグメント木の単位元を無引数関数で受け取る実装は、こういうケースを想定していたのかもしれないと思った。さらに、ライブラリで一様に型Tとなっている値のうち一部は整数型でないとまずいことにも気づいた。幸い、今回値を取得する点xは常に整数なので、これも何とかなる。そのほかいろいろ間違いがあったのを修正して残り80秒で投げると、1ケースだけ落ちてしまった。浮動小数点数の比較にEPSを使うようにして残り14秒で投げなおし、念のため別のEPSも試そうとしたらコンテスト終了。祈りながら結果を確認すると……AC!かなり嬉しかった。

7完81位。ギリギリまで粘って通せたため気分はよいが、全体として見れば愚か者の一言に尽きる。

間20分ですぐGCJ R2。コードゴルフは後回しになった。

https://codingcompetitions.withgoogle.com/codejam/round/00000000008778ec

Aは移動できるマスの差分を観察する。N=5の図を見ると、一周目から二周目へは(+15,+13,+11,+9)、二周目から三周目へは(+7,+5,+3,+1)となっていることがわかる。また、例えば+11を使った次は+7,+5は使えないこともわかる。通常の移動では常に+1なのだから、そこからの差分はすべて偶数。つまり、まずN^2-1-Kは偶数である必要がある。これがチェックできたら、あとは全部2で割って、(N^2-1-K)/2(+7,+6,+5,+4)(+3,+2,+1,+0)でうまく構築できないか考える。

実は貪欲でよい。貪欲に取ると最大で+7+3が作れて、これはそれぞれの四つ組から一つずつしか取れないことを考えれば確かに最大。それ以下の数が全部作れると仮定して、四つ組の個数で帰納法を回すことで証明できる。実装の際は、差分を達成できるマスを求めておく必要がある。一周目から二周目のマスだけ手で埋め込んだら残りは規則的に決めていける。このとき埋め込むマスを間違えて1WAしつつ、なんとか通した。

Bは難しい。まずround関数とsqrt関数の組み合わせでどのような値になるのか観察する。roundを表す数学記号が思いつかないのでこうやって文字で書くことになってしまった。ある整数X\gt 0をsqrtしてroundすると、値がY\gt 0になったとしよう。このときY-1/2\lt\sqrt X\le Y+1/2である。辺々2乗してY^2-Y+1/4\lt X\le Y^2+Y+1/4Xとして整数だけ考えているので、Y(Y-1)\lt X\le Y(Y+1)と書き直せた。このようなYは確かにただ一つ定まる。

この式を使って、draw_circle_perimeterで塗られるマスは必ずdraw_circle_filledでも塗られることが確かめられた。x=0またはy=0の点はどちらでも必ず塗られるので、第一象限だけで数えて4倍することにする。1\le x,y\le Rかつx^2+y^2\le R^2+Rなる(x,y)それぞれについてdraw_circle_perimeterで塗られるかチェックしたい。これはx^2+y(y-1)\lt r^2\le x^2+y(y+1)またはy^2+x(x-1)\lt r^2\le y^2+x(x+1)を満たす整数rが存在するか確かめることで行える。式が2本あるのがつらいが、よく見るとx\le yの場合前者だけでチェックしてよいことがわかる。

さて、ここでxを固定して、r^2の分布とy(y+1)の分布を考えよう。y(y+1)のほうが密に存在し、それを+x^2r^2が疎になるほうへずらすので、x^2+y(y-1)\lt r^2\le x^2+y(y+1)を満たす解rは常に高々一つになる。つまり、チェックしたいyの個数と解になり得るrの個数をそれぞれ求め、引くことで、解が存在しないyの個数を一息に求めることができる。x=yの場合を丁寧にケアして実装し、実験コードとしばらく比較して小さいケースで一致していることを確かめ、提出した。

Cも難しい。それぞれの子供について、1番目のお菓子以下の距離にあるお菓子を列挙し、辺を張ってみる。最も近いお菓子しか取れないという条件をなくせば二部マッチングになる。そうやってマッチングしたペアが、実際に残っている中で最も近いものならそれでよい。どの子供もそうでない場合、適当にマッチングを組み替えられるのではないかと考えた。ここにユークリッド距離を使うという問題設定が効くのだと思ってしばらく考えてみたが、まったくうまくいかない。純粋にグラフ的なアプローチを取るしかなさそう。

今、うれしい点として、残っているすべての子供についてマッチング先のお菓子より近くに別のお菓子が存在している、つまり二部マッチングを計算したグラフで子供から出ている辺は常に2本以上存在するということがある。これなら適当にdfsすれば交互閉路が見つかりそう。それっぽく実装するとWAだったので、もうちょっと丁寧に考えてみる。まず、ある子供のマッチング先を最も近いお菓子に変えようとしてみる。当然そのお菓子にはマッチングしている相手がいるので、今度はその子供に注目して最初からやり直す。こうして子供を辿っていくと行き止まりにはならないため、いつか必ずループする。ループの始点は最初に見た子供ではないかもしれないが、とにかくそのループに入っている子供のマッチング先を一斉に最も近いお菓子に変えても破綻しないことになる。実装を頑張って何とか通った。

残り15分ちょっとしかない。Dのsmallを通せないか頑張ってみる。とりあえず正の位置にあるビーチボールだけで考えてよい。01で分けてソートしてみると、わざわざ交差した感じでペアにする必要はない。つまり今どのボールまで回収したかを持つO(N^2)のdpができて、これはsmallなら通る制約になっている。ここまでの考察がトントン拍子に進んで、実装もシンプルだったためすぐ書いて提出。何とか通せた。

Hiddenのジャッジ結果が出て、ABCdで29位。かなり良い順位。途中800位台で少し焦っていたが、Hiddenまで通していた人が思っていたより少なかったようだ。自分に自信を持ってもっとどっしり構えていたい。

ABCのコードゴルフに戻る。Aは速度でも長さでも負けていてボロボロ。BはOctaveで書いてみたら縮んだ。CはシンプルなAWKが最短になっていて、Vimで粘ってみたが最短タイから縮まなかった。Dはi=0\dots 299に対して\lfloor i/3+1\rfloor\times 100^{(i\bmod 3)}を出力するのが天才的。EはRuby。以降は手付かず。

その後朝まで日記を書き、布団でしばらくハーメルンを読んで、午前9時くらいに寝落ちした。

05/15(日)

午後3時半起床。ハーメルンを読み続けて、午後5時半に1作読了。「Vの者!~挨拶はこんばん山月!~」。

syosetu.org

昨年末から読んでいた。かなり面白かった記憶だけ残っていて、どこがどう良かったのかはあいまい。普段の面白おかしい配信の様子とシリアスなシーンの寒暖差がかなり大きくて大変だった。ただどの章もハッピーエンドで終わってくれたので一安心。キャラクターの元ネタは、僕が分かったものは全部現実の芸能人・Vtuberだったので、そのあたり詳しければまた違った読み方ができたのだろうか。起こった出来事のいくつかに他のVtuber小説で見覚えがあったので、それも実は現実のVtuber界隈で起こったことなのかもしれない。

布団から出てずっと日記を書いていた。午後9時からARC。

AtCoder Regular Contest 140 - AtCoder

Aは|S|を周期的にすることを目指す。周期を全探索。BはA...ARC...Cという部分文字列に分割して、奇数回目の操作は長さを2減らすことになるので長いものから、偶数回目の操作は部分文字列を1つ削除することになるので短いものから優先的に使う。Cは\{\dots,2,N-1,1,N\}\{\dots,N-1,2,N,1\}が嬉しさN-1と最大で、これを達成できない場合は\{1,\dots,N\}\setminus\{X\}で同様の列を作って先頭にXを置くと、嬉しさを1だけ減らした状態にできる。ここまで20分弱。

残り100分はずっとDを考えていた。全然解けなかった。連結成分を作らない辺の本数を数えることと、各連結成分で最も小さい頂点番号の頂点を数え上げることを考えて、どちらもうまくいかず苦しんでいた。終盤になって、各連結成分がなもりグラフになること、さらに最初から連結になっている成分ごとに行き先が決まっていない頂点が高々1個であることに気づいて、その成分に分割した後ループの個数を数えるdpを書こうとしたが、値が全く合わずに終了。

3完171位。3完最速は昨日に引き続き愚か者。本当に助けてほしい。

午後11時半からCodeChefでMay Lunchtime 2022。

https://www.codechef.com/LTIME108A

ANDEQは残る値が必ず全体のbitwise ANDになる。この値になるように左からまとめていくと、達成した瞬間そこで切っても良いことがわかる。最後だけ達成できない可能性があるので、ちゃんと検出する。

B01Tは最初の部分点が大きなヒントになった。uの部分木について1の個数から0の個数を引いた値をc_uとおくと、c_1/2=-\sum_v c_vが満たされればよいことになる。Nが偶数なので、c_1/2は必ず整数になる。ここで最初の部分点は直線グラフだからc_1/2=-c_vを満たすvを見つける問題になるが、木をどんどん降りていくとc_v\pm 1ずつ、つまり十分連続的に変化するので、どこかで必ず見つかるという寸法。そしてこれは、木の頂点をDFS順に並べることでも同じことが行える。

RERNGは最後のステップに時間がかかった。P_i\lt P_{i+1}を分割する必要があるのは、L\le j\le RであってP_i\lt P_j\lt P_{i+1}なるjが存在する場合であるとわかる。いったんjの制限をなくして左右からそれぞれ最も近いインデックスを探し、l_i,r_iと名前をつけておくと、クエリに対する答えが\#\{L\le i\lt R\mid L\le l_i\lor r_i\le R\}+1と書ける。条件を反転してR-L-\#\{L\le i\lt R\mid l_i\lt L\land R\lt r_i\}+1を求める。

R=1\dots Nの順番に求める。i\lt RかつR\lt r_iであるようなインデックスの集合は管理できるので、それらからl_i\lt L\le iなるものの個数を数えることになる。l_i\lt Lだけ見ると、区間に対してある数未満の値をカウントするデータ構造が思い浮かぶが、僕が持っているものは静的である必要があったため使えない。しばらく考えて、遅延セグメント木の(l_i,i]1加算しておけば実現できることに気づいた。これで実装。加算する区間の右端がiであることに気づかずに1WAしつつ、通った。

PWMULは3つ目の部分点まで。Aの位数が小さければ愚直に計算できる。大きければすぐ見つかると信じて答えを全探索し、BSGS。このときBaby StepとGiant Stepのどちらかはテーブルを前計算できるので、そちらをunordered_setに持っておくこと、またもう片方のサイズを小さめにすることで高速化ができる。4つ目の部分点も通らないかと定数をいろいろ変えて投げていたが、全然ダメだった。BSGは1つ目の部分点まで。Aliceは最も左にある0か最も右にある1を、それと最も近いものとペアにするのが最適。Bobはその2つをペアにするのが最適。よって0のインデックスと1のインデックスをそれぞれ集め、列の左右からどこまで使ったかを持ってO(|S|^4)のメモ化再帰ができる。

375点で10位。2628→2708(+80)。

午前5時まで日記を書いていた。平日頑張って書き進めても、週末に5個もコンテストに出るともう追いつかなくなってしまう。一段落ついたところでインターン先勉強会の準備を始めた。なんと明日(狭義には今日)の勉強会は僕が担当なのであった。前々からわかっていたのにちっとも準備せずのんびりしていたツケを必死に支払うことに。一応何について話すかは考えてあったので、ガリガリスライドを作っていた。

午前10時になってひとまず完成。いったん寝て、起きて時間があればもうちょっと確認しておきたい、というくらいの出来。そこから1時間ほどかけてこの日記の校閲をした。

kotatsugameに質問 Part2

www.youtube.com

嬉しいことにまた質問を受け付けてくれという要望があったので、Part2を開催します。Part1は赤になったときの記事をご覧ください。

kotatsugame.hatenablog.com

以下のGoogleフォームはまだしばらく開けておく予定なので、これからもドシドシご投稿ください。

forms.gle

質問

次回の小説の構想はありますか

最短経路問題で何か書こうと思っているのですが、話が全然組み立てられません。起承転結の「転」の部分が思いつかないとどうしようもない感じがしますね。

大学卒業して院にいったんですか?

そうです。そもそも飛び級制度が早期「卒業」であることを抜きにしても、特に何かスキップしたりはしていません。

学業と競プロはどのように両立していますか

両立していません!……と言いたいところですが、ストレートで卒業できたのでそれなりに両立できていたほうなのでしょうか。課題は提出しましたし、テスト前にちゃんと勉強していた記憶もあります。逆にそれ以外、予習復習などの継続的な勉強はしなかったので、そのように必要最低限のことしかしないようにするというのは一つの方法かと思います。もちろん成績は落ちるはずなので、どちらにどれだけ重きを置くかですね。と、さもいろいろ考えていたように言っておいて、実際のところは自分がそのとき一番やりたいことを破綻しない限り貪欲にやっていただけかもしれません。

「質問などなんでも」って書いてあるの何個ありましたか?

1つです。と思っていたらこの記事の下のほうで2つ目がありました。

読むラノベ / ネット小説はどのように選んでいますか?

ラノベはタイトルとあらすじですね。まずタイトルを見て、気になったもののあらすじを確認して買うものを決めます。買ったものを全部読めているわけではないためしばらく机に積まれるのですが、そこからその時一番気になっているものを選んで読んでいます。

ラノベのパッケージングとして表紙イラストは重要な位置を占めています。しかしこれだけを頼りにラノベを購入するのはあまり良くありませんでした。なぜなら、当然ながら、文章の好き嫌いとイラストの好き嫌いには一切関係がないからです。

ネット小説は、TLに流れてきたり、読んでいる作品ページの下のほうでレコメンドされたものから選ぶ場合と、自分でタグやキーワードで検索する場合があります。後者はハーメルンの捜索掲示板で行うこともあります。どちらにしても、それぞれの作品はあらすじと最初数話を確認して読み続けるかどうか決めます。

例えば東方Project二次創作の古代スタートものが読みたいとか、金融知識を縦横無尽に振るう話が読みたいとか、気分は細かく変化すると思いますが、そういうニーズに対応するためには検索機能が非常に有効です。またさらに、一つ好みの作品を見つけた場合に、そのタイトルで検索することで似たような作品を探すこともよく行います。捜索掲示板でそれを行い作品がどういう文脈で紹介されているかチェックすることは、自分が一体何に心惹かれたのか言語化する助けになります。そこで得たキーワードで検索をかけるのもお勧めです。

こたつがめさん大好きです!もっと動画出してください!

ありがとうございます!動画、出したいんですけどね……。画面キャプチャの撮り溜めはあるのですが、それを編集する気力がない状態です。なぜかちっとも手が出なくて自分でも驚いています。もうしばらくお待ちください。

こたつがめさんは'''糧'''という単語を使いがちだと思うんですけど、うちの広辞苑を見てもないです。こたつがめさんの広辞苑には載っていますか?

糧、を引用符で強調しているだけです。当然広辞苑に載っています。食べ物のことをちょっと捻った言い方をしたくて使っているだけなので、普通に辞書的意味を当てはめていただければと思います。

東北大学にちょっと興味を持っている高校生なのですが、東北大学での学生生活はどのような感じでしたか?また、競プロerからの視点で大学の良い点や嬉しい点なども教えてください!

学生生活は非常に良かったですね。仙台市は、駅前は十分発展した都会ですが、そこから少し離れればごみごみしていない住宅街が広がるという点で、住みやすさと便利さを両立した街だと感じます。

競プロerからの視点としては、競プロが盛んな大学であるのが良い点だと考えられます。サークルには黄色の方もたくさん在籍しており、大学として年々強くなっていると思います。同じ趣味を持つ仲間がたくさんいて、ICPCにチームを組んで出るのもサークルを経由すれば簡単でしょう。一応、予選突破がだんだん難しくなるだろうことは注意しておきます。

あーだこーだーの切り抜きお願いします

しません。僕から見て切り抜くほど特徴的なシーンはないからです。……しかし考えてみると、僕は80分も喋っていたんですね。これは確かにアーカイブを見るのも大変です。

大学院での目標を教えてください

心身の健康です。特に精神的に調子を崩す話をよく聞くので、ちょっと怖がっています。

【睡眠用ではない】耳が完治したのでASMRやる【怒らないで】【Not suimin】 - YouTube

いいですね。前半は思ったより良かったです。後半はごちゃごちゃしていてよくわかりませんでした。しぐれういさんは配信で普通に喋っている声も耳に心地よいと感じているので、わざわざASMRである必要はないかなと思いました。

なんでフォロバしてくれるんですか?

僕のツイッターの運用方針がいわゆるフォロバ100%だからです。なので、申し訳ないのですが、フォロバしたからと言って個人をちゃんと認識しているわけではありません。

最終的にInstagramはログインできたの?

一度もログインできていません。指定された番号を手書きした紙とともに顔面を写した、まるで犯罪者みたいな写真をメールで送信しましたが、音沙汰なしです。

ブラックサンダーの良いところを教えてください

ちょうどいいサイズと価格、また箱買いが簡単なところです。

streakを維持することはレートに寄与しますか

寄与しないと考えています。自分の好きなペースで解いていくのが一番です。熱中した結果として維持されていることもあるでしょうが、目標に据えるのはお勧めしません。なぜかというと、いずれ無理が出てくるだろうからです。別のことに熱中したりして忙しい場合はすっぱりお休みするのが健全でしょう。その結果競プロから心が離れていくのなら、残酷ですがそれまでの話だったというだけです。

今年のICPCはどんな感じですか?

チームも含め、何も決まっていません。

お尻のほうを使ったことはありますか?

ありません。

学食での1回の食事でサラダと納豆をそれぞれ最大で何個まで頼んだことありますか?

スマホのアルバムを見返してきました。まず、納豆は二パックです。これは結構頻繁に注文しています。サラダはおそらく四つで、これを副菜という範囲に広げると九つ食べたときの写真が見つかりました。

「眠らないビル」の更新を待ってます。

ありがとうございます。ただ、一番上の質問でも答えたように、書こうと思ってもなかなか書けない状態にあります。別の話を書くとして「眠らないビル」のキャラを使いまわすかも迷いどころです。気長にお待ちください……。

文章を読むときに頭の中で声が聞こえますか?(聞こえる人と聞こえない人がいます)

この質問、認知特性を診断するテストでよく聞かれますよね。僕はそのたびに悩んでいるのですが、この質問を目にしてから文章を読もうとしても雑念が入ってしまい、なかなかよくわかりません。とりあえず、「文章を集中して読むときは聞こえる」と答えておきます。ネット小説は気楽に読むので聞こえていないはずで、ラノベなど物理書籍になると聞こえてくるときもある、はずです。

日本語の文章を書くときもVimを使ってますか?

レポートで\TeXを打つときはVimです。それ以外だとTeraPadを使っています。「眠らないビル」もこれで書きました。

「父も配信を見てくれて、受け答えがしっかりしていたと褒めて貰えました☻」とおっしゃってましたが、父親にはこたつがめもTwitterアカウントバレてるのでしょうか?致したとかツイートしてて大丈夫なんですか?

バレているというより、自分のTwitterアカウントはこれであるとこちらから伝えた覚えがあります。「致した」については聞かないでほしいとお願いしてあります。僕はそれで触れられなければ大丈夫で、話題にしない以上父がどう思っているかは気にしてもしょうがないと考えています。

アニメやマンガよりはラノベ(Web小説含む)派ですか?ラノベを読むと問題文の把握が速くなったりしますか?

前半については、明確にその通りです。むしろ意識的にアニメや漫画を避けています。これ以上物語に手を出す余裕はないはずだと考えているからです。後半について、問題文の把握には関係ないと思います。より一般に、いわゆる国語力は競プロの問題文の読解力と関係ない気がしていて、これを鍛えるには競プロの問題にいろいろ触れるのがいいでしょう。

精進にあたって書籍は必要だと思いますか?

今時はネットに大量の記事があるので、必ずしも必要とは言い切れないのかなと思います。ただ、買って損はないです。書籍の最初から最後まで目を通すことで体系的に知識を得る、あるいはそこまで至らなくてもどんな問題を解くアルゴリズムがあるか知ることは重要です。また蟻本については、たまに(第2版の)ページ数を使って特定のアルゴリズムに言及されることがあります。

日記を読んでみたいのですが,どこから読むのが良いですか.

興味を持っていただきありがとうございます!日記を読み物として捉えてみると、別に僕の日常は山あり谷ありというわけでもないため、どこを読んでも面白さは大して変わりないのかなと思います。そのため、とりあえずリアルタイム性を重視して最近のものを読むとして、そこから引用の形でリンクされている過去の日記(そういう引用は結構な頻度で使っています)を読んでみるとかは考えられます。または同じイベント、例えばコンテストに僕とあなたが同時に参加していたなら、その日のものを読むのもありかもしれません。

板タブの次に買おうと思ってるデバイスはありますか?

今のところPC環境には満足しています。タブレット端末にはちょっと興味がありますね。

ベランダさんの作品のおすすめはなんですか

「黒髪少女の羞恥快楽地獄」/「ベランダ」のシリーズ [pixiv]

アマギフの使い道

毎月ペットボトルの爽健美茶を1箱買っていて、それの支払いで2000円弱ずつ消えています。また過去にはモニタを買うのにも使いました。

ハンドルネームの由来

TwitterのIDの末尾の_t というのはsize_tのように構造体であることを明示するためですか 違います。これは僕の苗字のイニシャルです。

AtCoder 赤色になりました - kotatsugameの日記

名前はこたつ 亀 ですか?こたつ game ですか? 亀です。こたつむりという言葉のシノニムのつもりです。こたつむりはあまりに一般的すぎるので、このように変えました。

AtCoder 赤色になりました - kotatsugameの日記

大学院後の進路

大学院の後は企業への就職です。では大学院をどこで終えるのかについて、博士課程は……どうでしょう。今のところなくはない、くらいの気持ちでいます。

タイピング早すぎませんか?寿司打の記録と練習方法を聞きたいです。自分は寿司打高級コース+3000円前後くらいしか出せません(泣)

高級コースでプラスになるのは十分速い部類に入るはずですね。上には上がいるということで、僕より速い人も界隈では珍しくなさそうです。寿司打のプレイを続けると単語に慣れて速度は出るのかもしれません。「生麦生米生卵」を時間内にタイプできますか?僕はなかなか苦労しましたが、覚えると安定します。また、少し速度を落としてでもミスを減らせば、却ってスコアが上がることが知られています。

他に僕が意識していることとして、FキーやJキーを積極的に使うこと、記号キーを確実に押せるようにすること、「ん」をタイプするのに不必要な連打を減らすことが挙げられます。一番最後は難しいですが、画面のローマ字表示を参考にすると多少やりやすくなるように感じます。

コードゴルファーで「この人すごいな」と思った人はいますか?

tails(Atcoder ID:saito_ta)さんを挙げます。AtCoderにはほとんど提出されないため競い合わせていただいた経験は少ないですが、そのいずれも隙のないコードで、当時感服していました。他の人と競い合って負けてしまった問題にも、いくつもすごいなと思う最短コードがあります。ただ、すごいと思ったコードではなく人ということなので、この方を挙げました。

sgruiのえっち絵で好きなやつ教えて下さい

Pixivでフォローしている絵師さんが描かれたのを目にすることはありますが、特に好きではありませんでした。性欲の対象になっていないと思います。

質問などなんでも

「質問などなんでも」カウント+1

競プロを始めたのはいつですか?競プロ以外でプログラミングすることはありますか?

競プロを始めたのは、あーだこーだーでも答えた通り2016年5月、高校2年生のときです。競プロ以外のプログラミングも多少します。長期インターンで業務としてコーディングしていますが、稼働時間が短めなので多少という言い方になっています。あとは、自分でクローラを作って最短コードをクロールしているのも競プロ以外にカウントされるでしょうか。

日記やTwitterで「シュッと」という表現(「シュッと解けた」など)をよく使っている印象があるのですが、この表現をいつから使うようになったかなど覚えていたら教えてください(個人的にほかではあまり聞かない表現なので気になりました)。

それぞれ検索して探してみました。Twitterのほうはこのころから時たま出てきていたようです。そちらにしても日記にしてもそれほど頻度は高くないので、あまり聞かない表現と感じたからこそ印象に残ったということなのでしょうか。どういう経緯で使うようになったかはよく覚えていません。ニュアンスは伝わるかと思いますが、それを擬音で表現しようとした場合、自分の中では「シュッ」が該当しました。また、検索すると大阪弁に存在するという話がヒットするため、その地域の方と交流する中でうつったのかもしれません。

Cはそこそこびっくりしたがシュッと解けた。

週記(2021/01/11-2021/01/17) - kotatsugameの日記

ホロぐらってやつ、オススメですhttps://www.youtube.com/hashtag/%E3%83%9B%E3%83%AD%E3%81%90%E3%82%89

別にホロライブが好きなわけではないんだよな……と言いながらいくつか見ましたが思ったより面白かったです。ありがとうございます。

これ好きなので是非感想をください!【みっころね24】みこち、ゲラを止められなくなる【ホロライブ切り抜き】 - YouTube

さっきのやつなんですが、こっちを観てください【神回】医者からyoutuberになろうとする父から始まるシャクレ家族の家庭崩壊w【ホロライブ切り抜き/みっころね24/天音かなた/常闇トワ/姫森ルーナ/大神ミオ/戌神ころね/さくらみこ】 - YouTube

誰もよく知らないんですがそれでも面白かったです。パパが強硬に退職を主張する部分が特に好きでした。ありがとうございます。

銅冠、銀冠、金冠、鉑冠になる予定はありますか?

銅冠にはなりたいなと思っています。それより上は……正直難しいでしょう。

英語の問題文を読む時に、翻訳機(deeplなど)を使っていますか?

単語ごとの意味はよく検索していますが、翻訳機に文章を投げることはしません。競プロの問題文はとにかく正確に読まなければなりませんから、単語・熟語の意味はともかく構文の認識は自分で行うべきだと考えています。特にDeepLはいくら自然な日本語に翻訳されるとは言っても、途中の文章を脱落させるケースがあると聞いていますから、競プロで使うべきではないはずです。少し上で競プロの問題文の読解力について触れましたが、多く読むことで鍛えられるのは英語の問題文についても同じです。頻出する表現に慣れれば格段に読みやすくなるのではないでしょうか。

あーだこーだーだと変な質問できなかったので Google フォームによる質問感謝します!!!!!

どういたしまして。答える側としてもこうやって質問がたくさん来てくれると嬉しいです。質問する側に立ってみると、その匿名性が重要なのかなと考えて、それで僕の作ったフォームは回答者の名前を聞かない構造になっています。マシュマロも匿名性という点では同じですが、こちらの感覚が配信で答えるのと違うこと同様、質問者にとっても違う感触なのだろうなと思います。

Chromeのブックマーク管理についてお願いします(配信で写っていたのを見て綺麗だなーと思いました)

これ、特別なことをしているつもりはないので、何をどう答えるかかなり悩みました。ブックマークのフォルダ分けについてよく使うところを大まかに説明すると、競プロのコンテストサイトやそれに関するデータを表示するサイトをまとめたフォルダと、コーディングで参考にしたサイト・ページをまとめたフォルダを用意してあります。後者はさらに、特別頻繁にアクセスするものを除き、言語ごとにサブフォルダでまとめてあります。

覚えておきたいコードゴルフのテクをまとめるため、そのテクが出現した提出の詳細ページをブックマークしているのですが、これが調べてみたら300個以上ありました。なのでサブフォルダでもまとめておく必要があったわけです。そうやってフォルダ分けされて階層的にずらっと表示されると確かに綺麗に見えますね。この質問はそういうことなのでしょうか。

週記(2022/05/02-2022/05/08)

05/02(月)

先週の週記を投稿してからの話。徹夜を決めた。ついでに新幹線の予定も早めることにしたので、時間的な余裕はすでにほぼなく、そそくさと出発。高校生の通学ラッシュと重なってしまい、駅から吐き出されてくる人々に逆らって歩くことになった。

仙台駅に着いて、朝食のパンをコンビニで購入して乗車。さすが朝早めの新幹線、さらに仙台駅始発ということもあってか、中はガラガラだった。

車内ではラノベを読んでいた。ふとTLを見ると、日曜日のOpenCup-Aが怪しいという話が流れてきた。詳しくは先週の週記に追記しておいた。解説のリンクをまだ手に入れられていないため、想定解がどのようになっているのかわからない。問題文に縦と横にしか切れないという注釈を書き忘れているのだろうと思うが……。

2022/05/04追記:Aは自明ではない。より正確に書けば、H×WH×Wのシートから同じ大きさの正方形をKK個切り出すとき、正方形の1辺の長さは最大いくらにできるか?という問題。特にH=WH=Wの場合、有名な未解決問題になる。問題文のどこを探してもそのようなことは書かれていないが、縦と横にしか切れないという制限を勝手に設けて解くと上に書いたようになる。

週記(2022/04/25-2022/05/01) - kotatsugameの日記

午前10時過ぎ、大宮に到着。このときもまだ車内はガラガラだった。僕が乗った先頭車両には他に1人しかいなかった。乗り換え待ちが40分程度あるので、一旦改札を出て駅前のゲーセンへ行き、1クレだけプレイ。素手なので軍手をつけている普段と感覚が違い、全然精度が取れなかった。

すぐ戻ってきてホームに上がると、今度はかなり人が多いようだった。列に並んでしばらく待ち、乗車。新幹線を外から見たときはかなり混んでいるように感じたが、何人か降りたのか多少座れる余地はあった。10分前から並んでいたこともあり、無事座ることに成功した。

車内ではカクヨムを1作読了。「絶対に目を付けられてはいけないVtuberに見つかってしまった」。正直あまり好きではなかった。登録者数1万人の主人公が登録者数100万人のヒロインに見つかってグイグイ迫られる、という展開に面白さよりも先に恐怖が来た。ギャグ時空なのでそういうことはないとわかっていても、めちゃくちゃ炎上しそうな展開に見えてしまう。主人公が弱気なのも好みではない。

kakuyomu.jp

ちょうど読み終わったあたりで黒部宇奈月温泉駅に到着。そこから父の車に乗り、食事しつつ富山市に向かった。どうせなら最初から富山駅で降りれば良かった。

パスポートセンターでパスポートの受け取り。3月末に代理申請をしてもらっていたのだった。受け取りの際に生まれ年の干支を聞かれ、答えに窮してしばらく上を向いて黙っていたら、係の人から「卯年ですか?」と助け舟を出された。そういうのでもアリなのか。

富山県のパスポートセンターに電話して代理申請について聞いてみた。こちらは僕が6か月以内に受け取りに行くことも含めて問題なく行えそうだったので、必要な書類を聞いておいて、再度パスポートセンターに行って申請書+委任状をもらい、またその近くの写真屋でパスポート用写真を撮ってきた。これらとパスポートを合わせて、近々仙台に来る親に渡せば間に合いそう。

週記(2022/03/07-2022/03/13) - kotatsugameの日記

本屋に寄りつつ何も購入せず帰宅。パスポートセンターで貰ってきた、ゴルゴ13と外務省のコラボの海外安全対策マニュアルを読んだ。めちゃくちゃシュール。ゴルゴはそんなこと言わないだろというセリフばかり登場する。漫画は過去の話をコピーしてセリフだけ置き換えて作っている、と書いてあったような気がするが、そうだとしたらそれは凄いことだと思う。ネットでも読めるようなのでリンクを貼っておこう。

外務省 海外安全ホームページ|ゴルゴ13の中堅・中小企業向け海外安全対策マニュアル

話自体に見覚えがあったので、もしかしたら5年前にパスポートを作ったときも同じ冊子を貰ってきていたのかもしれない。2021年に版が変わって後ろにコロナについての話が増えたようなので、そこは確実に今日初めて読んだとわかる。

布団に入って少しカクヨムを読み、午後6時就寝。

05/03(火)

午前4時起床。

カクヨムを1作読了。「幼馴染がVtuberになった、何故か配信の度に俺がトレンドに上がるようになった。」。面白かった。イラストレーターがVtuberになりそうになっているので気に入った。実質しぐれういさんみたいなところがある。ただ最近の更新は、女性Vtuberであるヒロインが男性である主人公に言及するのは炎上の元になるという話が始まって、少し不穏。

kakuyomu.jp

もう1作Vtuberモノのカクヨムを開いてしばらく読み進めたが、途中で止めた。俺TUEEEは否定したくないが、ヨイショが鼻につきすぎる。この感覚は作者の別作品を書籍で読んだときにも感じたもので、自分の苦手な作者であるとの認識を強めた。

【PV170万突破】ぼっちの俺がゲームスキルで大人気配信者になった件(相野仁) - カクヨム

午前7時から午前11時まで二度寝。起きてから部屋の掃除。実家に届いていた学位記の写真を撮った。

食事してしばらくハーメルンを読み、午後1時から灘校文化祭コンテスト 2022 Day1に出た。ソロ。

灘校文化祭コンテスト 2022 Day1 - AtCoder

Aはよい。Bはギャグみたいなもの。Cは2回くらいBFSをする面倒なやつ。Dは大変苦労した。全探索で解を見つけて、\{0,1,-2,3,\dots,N/2,\dots,-3,2,-1\}となっていることをエスパーした。これに気づけたのはかなり奇跡的な気がする。EはEven Degtreesを思い出せば連結成分ごとにかなり好き勝手できるとわかるので、見ている頂点の次数の偶奇を持って木dp。Fはfunctional graphに言い換えれば自明。Gは行ごとのdpを考えると遷移が多項式のべき乗になったので、二分累乗法で通した。700ms。

Hは与えられた点を連結にする辺だけ残した部分木を考えて、それの辺数の2倍から直径を引く。残す部分木の辺数(の2倍)については、dfs順に並べて円環と見たとき隣接する点の距離を足し合わせたら求まるらしい。典型90問で知った話。直径は、与えられた点だけを見てdouble sweepすれば求まる。葉となりうるのがそれらしかないため。Jは素因数を1000未満と以上に分けて、未満はそれぞれセグ木に乗せ、以上は個数をカウントした。何も考えずにセグ木を全部更新するとTLEしたので、関係する素因数のところだけ見るようにしたら1000ms。

Iは区間に辺を張るテクをしてdijkstra、700ms。Kはかなり苦労したが、タイルIを2枚横向きに置く枚数を固定したら解けた。タイルLは2枚組で使う必要があって、Iの2枚組とLの2枚組を並べた後、間にタイルIを置いていく。タイルLに挟まれた箇所では横向きになるが、結局どこでも1枚ずつ置いていくことになるので、単純な重複組み合わせで書ける。最後にタイルLの向きを考えて2^{A/2}倍する。

残り20分でLに特攻し、解けなかった。11完で9位。Dは\{-0,1,-2,3,-4,\dots,-(N-2),N-1\}と見るとわかりやすいようだ。2個ずつ見れば\pm 1で、これで上手く行く理由も納得できる。Gは考察すると普通にcombinationで解けるらしくびっくり。自分が使った多項式\sum 2^{M-i-1}x^iで、これを2^{M-1}\times\sum 2^{-i}x^iと見ると、確かにべき乗後の各項が閉じた形で表せる。

Iは頂点でコストがかかると考えれば辺のコストが0になって、dijkstraによる更新が高々1回になるので一度見た頂点は消して良くなるようだ。Kの解説はよくわからなかったが、f(x)^nの先頭N項を求める話はnが負でも適用できるということらしい。フィボナッチ数列の畳み込みをOEISに投げて一般化した漸化式をエスパーした人もいたので、そのような漸化式の存在が先頭N項を求める話にも効いているのだろう。

コードゴルフ。Aはdc 13Bでホクホクしていたら12Bに縮められた。\lfloor N^2/2\rfloor-\lceil N/2\rceil。BはRubycombinatio.sizeをそのまま使える。Vimで書いたものに1B更新があって取られた。Dは2段落前に書いた集合をRakuで実装。符号を切り替える部分がどうにも短くならず、あまり納得のいかないコード。他は手付かず。

upsolveを2問行った。まずコンテスト中に考察していたL。方針としては、頂点を深さごとに分類して、ある深さの頂点について問題を解くときに、1段深い頂点たちについて同じ問題を解いたときの辞書順で並べておいて使うというもの。考察のダメだった点として、頂点数の少ない子を先に使えばよいと考えていたのがある。一番浅い頂点が先に来るので嬉しいと思ったのだが、それ以前に部分木で大小関係が決まってしまうことがある。次に実装で、同じ部分木を生成する頂点には同じ順番を割り当てなければならなかった。この2点を修正してAC。

次にO。各机について、右にどこまで寄せられるかを計算できればよい。ある机iに対して、i\lt jかつA_i+A_j\gt Kとなるような最小のjを求めてみる。この机jを限界まで右に寄せた後、机iもその1つ左まで寄せられるのではないかと考えた。これはA_i\le A_jのとき正しい。机jの左に出てくる机は机iとも交換できるようになるため。そうでない場合は2A_i\gt Kなので、代わりにA_i\le A_jなるjを求める。机jの左に出てくる机を机iと交換できることを保証するため。机jの右には行けないのでその1つ左……とはならず、i\lt k\lt jで机iの左に出せない机の数も考慮に入れる必要がある。範囲内のkではすべてA_k\lt A_iなので、A_i+A_k\le Kならほかの机も越えて机iの左に出すことができる。jを求めるのは区間MAXのセグ木の二分探索、後半の区間カウントはライブラリになっている。

ラノベを1冊読了。「転生ごときで逃げられるとでも、兄さん?」3巻。凄かった。凄い理由は一応ネタバレ配慮ということで次とその次の段落に書くので、これから読もうとしている方は注意して読み飛ばしてほしい。ストーリーに注目して感想を述べれば……いや、この本に限ってはそんなことをしても意味はないだろうか。前半もちょっとダークな感じではあるものの、素直にドキドキしながら楽しんでいた。

終盤のちゃぶ台返しがすごかった。これまでの展開が全部無意味になってしまった。ストーリーが意味を成さないというのはそういう意味。裏表紙のあらすじにある「神の筋書きさえ殺す」というのは完全にメタ的な意味だったらしい。章題も書き換えられていた。イラストページの最後にこの巻の目次がついていたのだが、実はそれは途中までしか載っておらず、本の途中で目次が追加されるというかつてない体験をした。300ページ以上ある本の目次なのに200ページちょっとで小節が途切れているのに違和感を抱くべきだった。

登場人物一覧も改めて書かれて、結構な数のキャラがあっけなく殺されてしまったらしく横棒を引かれていた。これも信じていいのか迷ってしまう。横棒が書かれている→死んでいる、ということは別にどこにも明記されていない。ただ、そういう機能的なページでは嘘をつかないみたいな信条もありえるので、本当にわからない。

部屋の整理を始めた。仙台から実家に送った段ボールのまま放置されていた既読本を本棚に詰める。現在すでに部屋の棚が満杯なので、これからは物を減らす必要がある。中学校のときに使っていた絵の具セットやらを捨ててとりあえず空けてみたが、キャスター付きの棚だったので本をギチギチに詰めるのはマズいようだ。実際、詰めてから動かしてみて、敷物から恐ろしい音が鳴っていることに気づいた。そこで、その場所に別の棚から物を移して場所を空けることにした。とりあえず今ある分は収納できたものの、すでに横向きに本を詰め込んでギリギリのため、本当にマズい。

F問題のコードゴルフを少し。コンテスト中はcombinationライブラリを持ち出したが、よく見るとただの階乗だったらしい。dcでも通ったので、それで縮めておいた。

布団に入ってハーメルンの更新を確認。読んでいるうちに寝落ちした。午前2時だった。

05/04(水)

午前9時前起床。しばらくカクヨムを読んでいた。

帰省してからテザリングばっかりしているので、気になって通信量を確認していた。過去の月も見ていると、面白い期間を見つけた。目に見える変化が3回しかない。ちょっと学食に行くだけではこんな急激には増えないので、この3回はそれぞれゲーセンなどのため街に出かけていった日を示しているはず。当時の日記を調べてみると、02/16、03/03、03/08、03/09にそのような外出をしていたとわかった。03/08-03/09をくっつけて考えれば、確かに3回であるようだ。

午前11時になって布団から脱出。昨日寝る前に縮めたF問題が更に縮められていた。適当にテストケースハックを試みると通ってしまったので、さらに-2Bで取り返した。

部屋の整理の続き。思い切ってゲーム機を捨てることにした。インターネットに接続して、DSiうごメモを熱心に集めていた記憶がある。その中でもやはり有名なのは100%さんの棒人間バトルだろう。この作品(と関連作品)でSouthern Crossを知った人も多いと思う。検索すれば動画が出てくるのでピンと来ていない人はぜひ見てほしい。コピーが多すぎて、原作を見つけたときはかなり興奮した記憶がある。

うごメモもインターネットにおける時代の流れに取り残されてしまったデータであるようだ。うごメモ発掘云々というタグが存在するのを見つけた。それなら、今手元にあるメモたちをただ捨ててしまうよりはいいかと思って、とりあえずSDカードのデータを吸い出しておいた。3165個。

日記のこの部分を書くときいろいろ調べているうちに、当時僕が熱心に作品を追っていたミラーパネルさんが今も活動されていることを知った。YouTubeに上がっているPV集がエモい。ただ僕としてはオリキャラの話やPVのほうが好みだったので、それが上がっていないのは寂しい。男の子2人と女の子1人の3人組がいたことを覚えている。

ミラーパネル【松坂奈夜】 - YouTube

午後1時から灘校文化祭コンテスト 2022 Day2。ソロ。

灘校文化祭コンテスト 2022 Day2 - AtCoder

AはM/\gcd(M,K)\mid Nを判定。BはA=\max A_iを固定すると使える区間が定まって、A\gt 0なら\min B_iは小さいほうがいいので使える区間を目いっぱいに選択、A\lt 0なら\min B_iは大きいほうがいいので1点のみの区間を選択。A=0なら0である。全てのAについて計算したものの最小値を答える。Cは今日もまた面倒なBFS。それで前計算してbitDPで答えを求める。

Dにかなり苦労した。グラフが連結であれば、辺数が頂点数以上であることを確認するだけでよい。よって連結成分に分解する方法を考える。1点uを選んで、それと接続されている頂点を全部集めたい。ある頂点集合Uの中に接続されている頂点が存在するかどうかは、クエリUの答えよりもU\cup\{u\}の答えのほうが大きいことを確かめることでチェックできるので、Uを半々に分割していくことでそれなりに高速に求められそう。今の操作は\{u\}がもっと大きな頂点集合になっても同じように行えるので、増えなくなるまで繰り返せば良いとわかった。ただ数ケースQLEしているらしい。苦し紛れに、QLEする直前にNoを出力するようにしたら通ってしまった。

Eはシュッと解けた。\sum_{i\ne j}\min(|A_i-A_j|,|B_i-B_j|)を求めたい。まずA_i\lt A_jB_i\lt B_jA_j-A_i\le B_j-B_iと固定してみよう。するとA_j-B_j\le A_i-B_iが得られるので、A-Bを座圧してセグ木にAの和と個数を乗せることでこのケースの総和が求まる。B_j-B_i\ge A_j-A_i\gt 0なのでB_i\lt B_jは自動的に満たされる。A_j-A_i\gt B_j-B_iの場合はABを入れ替えることで同様に。B_i\gt B_jの場合はA_j-A_i\le B_i-B_jよりA_j+B_j\le A_i+B_iなので、A+Bを座圧することになる。ABを入れ替えてもう一度やるのも同じ。以上でA_i\lt A_jとしたときの全ての場合を求めたので、2倍すれば答えになる。

Gは商列挙が面倒。\forall i.k\mid C_iという条件で数え上げた後、倍数のケースを引けば求まる。1\le k\le Mについて求めるのではなく1\le k\le 10^5について求めなければならないのは注意。kを固定すると、各iに対してC_i\lfloor B_i/k\rfloor-\lceil A_i/k\rceil+1通り存在するので、これをかけ合わせればよい。区間の端点が変化するポイントはO(\sqrt{A_i}+\sqrt{B_i})種類しかないので、全部列挙してちまちま弄っていく。全体の積をセグ木で求めたらTLEしたので、掛け算と割り算を繰り返すことにした。ただしゼロ除算が困るので、そのようなケースは別にカウントしておく。これで4000ms。商列挙でMLEしてしまったので、pair<bool,int>intに押し込んでデータを圧縮している。

Fは最小費用流。区間の端点を列挙することで、使える給水機の集合が等しい区間に分割することができる。分割した後の区間をそれぞれ1つのノードと見て、始点→給水機→区間→終点という感じに辺を張ればよい。コストが負になってしまうが、負閉路は存在しないので、最初のポテンシャル計算を手で行うことで問題なく計算できるやつ。今回はそもそもDAGなので、頂点番号がトポロジカルソート順になるように振って、先頭から順に計算した。後からよく考えれば、この場合はdijkstraがそのまま使えるので、ポテンシャルを0にしておいて問題なかったようだ。1回目の提出が2087msで、定数倍高速化して約1600ms。

Hは二重頂点連結成分分解。名前だけ知っていて、実装したこともこれを使う問題も解いたことがなかった。いろいろ調べるうちに、こちらも二辺連結成分分解と同様、分解後のグラフを木に見立てることができると知る。しかしその方法はかなり複雑に思われた。自分で実装できる気がしなかったのでもうちょっと調べ、以下のブログに何もかも書いてあるのを見つけた。このライブラリを貼り付けた後木dp。各頂点についてそれをLCAとするペアについて計算したが、解説を見て、単にそこを通る回数を数えればよかったということを知った。

Block-cut tree - ei1333の日記

Iは面倒。整理すると、長さNの順列であって、特定のc個の要素が1\dots KK+1\dots 2K、……の少なくとも一つを埋め尽くしているような場合の数が十分高速に求まればよいとわかる。包除原理でO(c)で求まる。……と思ったのだが、この場合の数を後から指数として使うので、\bmod 10^9+6で求める必要があることに気づいた。恐る恐るfactorに投げると2\times 500000003素因数分解されたので、\bmod 2\bmod 500000003をそれぞれ求めれば復元できるようだ。後者は十分大きな素数なのでいつも通りmodintで計算できる。前者はリュカの定理などを使って気合いで頑張る。O(c)が十分高速であることは全く確認せず、とりあえず投げてみたら、通った。解説を見て\sum c\le\sum_i\log A_iであることを知り、納得。

残り20分はK問題に取り組んでいた。どうせAlienDPだろうと思って適当に実装し、サンプルまで合わせるもWA。適当にポンポン投げて4ケースWAまでにじり寄ったが結局通せなかった。9完9位。

Bは試すべき区間N+1種類に絞れるようだ。解説がなかなか理解できず苦労した。長さ1の区間で十分と書いてあるところは、{\rm argmax}_i\;A_i{\rm argmin}_i\;B_iを選ぶ場合を考えればわかる。Dはある頂点に隣接する頂点を全部一気に求めるのではなく、1つずつ求めるようにすればよかったらしい。Uを半々に分割するとき、隣接する頂点を1つだけ検出する場合は、片方だけ聞いてどちらを次のUにするべきか判別できるからだと考えた。ここで両方聞いてしまったときの定数倍が効くのを意識していなかった。

Eの解説の式変形は頭が良い。\max(|x_i-x_j|,|y_i-y_j|)を差の絶対値の和に置き換える箇所は、普段マンハッタン距離で45度回転しているテクの逆と見なせるようだ。初めて見る気がする。GはMLEした部分のデータの持ち方が違うだけで、変わらず商列挙が想定解だった。Fは解説と全く異なっていた。実行時間的にも想定解でないのは明らかで、何も考えずフローを流してしまいすみませんという感じ。

コードゴルフはA問題だけ。dcで解いておいたら、夜になって実は\gcdを求めなくてもよいことが判明し縮められていた。M\mid NKを判定すればよかったらしい。言われてみればそれはそう。

Kのupsolveをした。AlienDPであることは間違っておらず、絵を取り外す時ではなく残すときにペナルティを与えるようにしたら通った。びっくり。これが本質的な違いとは思えなかったため、誤差が問題になっているのではないかと考えた。それで、日記を書いているとき、試しに全体を264倍して__int128で実装してみたところ、見事通った。この方法はちょっと覚えておきたい。ただ、long doubleでもそれほど変わらない桁数の精度があるはずなので、相変わらずよくわからないままである。

食事してしばらくSSを読んだ後、深夜まで日記を書いていた。今日の部分までたどり着かないうちに眠くなったので切り上げ、布団に移動。

そこからTLに流れてきたハーメルンを開き、1作読了した。「【ダンジョン配信】元社畜TS異世界転移者のホームレスから始まるダンジョン配信者生活!!」。主人公が強いのはいいが、現在初心者からステップアップするフェーズにあまり興味が持てない。正直なことを言えば手っ取り早く地位を上げてほしい。こらえ性のない人間になってしまった……。

syosetu.org

05/09追記:ハーメルンのほうでは削除されてしまっていた。なろうでは連載が続いているので、リンクを貼っておく。

https://ncode.syosetu.com/n3202hp/

午前2時過ぎ就寝。

05/05(木)

午前9時前に起床。昼前までずっと一度読んだなろうを読み返していた。

少し日記を書いてから祖母宅に行き、顔を見せた。会う度に僕の小学校入学以前の思い出を無限に語られるので正直辟易してしまう。思い出話を聞くのも孝行の一種であろうと理解はしているが、どうしてもそっけない対応になってしまう。ただ、じゃあ自分から話題を振って、今やっていることなどを説明したいかと言われると別にそうでもない。こうやって溝が深まるうちに残りの時間を過ごすのも、最近はまあそういうものかと受け入れてしまっている。

帰宅してまたしばらくなろうを読み、夕方になって焼き鳥屋に行った。混み具合はそこそこ。帰ってきてからもまた夜までなろうを読んでいた。

今日読み返していたのは「逆行転生したおじさん、性別も逆転したけどバーチャルYouTuberの親分をめざす!」。完結済みで、2月に閑話のようなものを毎日更新していたらしい。それを読んでからうっかり読み返しを始めてしまったというわけ。その閑話、配信アーカイブと名付けられている1話ごとの話が非常に良い。完結してからの話なので難しいことも苦しいこともなく、永遠の安寧を味わえる。

ハーメルンでいろいろVtuber小説を漁ってから読み返してみると、かなり毛色が違う作品だったなあと思った。かなり初期のVtuber界隈を題材にしており、Live2Dによる生配信ではなく3Dモデルによる動画投稿がメインの活動となっている。スーパーチャットの描写もなく、コメントとは会話せず、Vtuberから視聴者へは一方通行である。

https://ncode.syosetu.com/n3530fy/

午後11時半まで日記を書き、眠気が強くなったので布団に移動。少しハーメルンを読んで就寝。かなり久しぶりに、徹夜明けでもないのに日付が変わる前に寝られた。

05/06(金)

午前9時起床。

ハーメルンで読んでいた作品が1作、完結した。エピローグ5話がかなり良かった。中学卒業後からバンバン時間が飛んで、主人公たちの将来を描く。そういう締め方は一般に健康に良いとされている。

syosetu.org

仙台に帰る準備を整える。ラノベを3冊持ってきたのに、来るときの車内で読んでいた1冊以外はちっとも読み進められず2冊持って帰ることになった。昨日一日ネット小説に吸い取られてしまったのが痛い。昼前に家を出発。

昼食は回転寿司に行った。一応平日の昼間なのにそれなりに待ちがいてびっくり。写真の右に見えているのは白エビ軍艦。何気なく取ったら760円の皿で、大変恐縮しながら食べた。甘みがあり、巻いているとろろ昆布も合わさって非常においしかった。

黒部宇奈月温泉駅から新幹線に乗り、大宮へ。車内ではラノベを読んでいた。大宮に近づくにつれ人が増え、僕の隣の席も埋まってしまった。

大宮に到着。事前のチェックでは乗り換えの時間が5分でちょうどいいなと思っていたのだが、乗る予定だった列車がGW中の特定の日しか運行しておらず、30分後の新幹線を待たなければならなくなった。改札を出てゲーセンに行くとチュウニズムが埋まっていたので、待たずにすぐ引き返した。まだ微妙に時間があるので、ゲーセンとは反対側の出口にも出てみることにした。そちら側はペデストリアンデッキがあって、仙台駅を思わせる感じでなかなか面白かった。

ようやく来た新幹線に乗り仙台へ。人はそこそこ、1席開けて座れるくらい。また車内ではラノベを読んでいた。午後6時に到着。ホームに降りてみると、今乗ってきた列車にここから乗り込むらしき人が大量に列を成していてびっくりした。

駅前のヨドバシカメラで板タブを購入。液タブのモニター機能がないやつ。昨年からオンラインのゼミだったり競プロ配信だったりで、手書きの図を即座に画面に映せるようにしたかったのだ。この先使う機会がどれくらいあるかわからないので一番安いものを購入。それでも6000円くらいした。

たいぺーから誘われたので一緒に食事する。待ち合わせはサイゼ。行ってみるとたいぺーがスープを注文していたので、間違い探しをして待っていた。今日はかなり冴えていて、たいぺーが食べ終わる前に10個全部見つけることに成功した。気分よく店を出てしばらく食事する場所を探し、やよい軒に入った。

食べた後少し本屋をうろついて帰宅。しばらくYouTubeを見てからシャワーを浴び、板タブの設定を始めた。初期設定では3枚並べたモニターが横幅を圧縮されて小さいタブレットの画面と対応しているようだったので、これを1画面のみに対応させたい。設定画面に最初からその対応を弄るページがあることに気づかず、wacom IDの作成と製品登録が必要だと早合点してしまった。このIDの登録にもかなり苦労した。twitterログインだけだとダメで、直接メアドで登録したら成功。ここでようやく最初から設定できたことに気づいて、無事1画面だけに対応するようにできた。

ラノベを1冊読了。「時々ボソッとロシア語でデレる隣のアーリャさん」4巻。夏休みの期間ということで、この巻では生徒会長を目指すバトルはお休みし、全編ラブコメだった。前半のデート2本はシンプルに好みのシーン。そこから生徒会合宿に行って、そこでヒロインからの恋心に主人公が気付くシーンがある。普通はくっつくまでずっと勘違いじゃないか悶々しているところ、途中でそうやって明言するのはなかなかびっくり。確かに、この主人公ならそういうところも目ざとく気付くほうが納得感がある。一方で主人公からヒロインに向ける感情にはまだ決着がついておらず、この巻のラストはそれに続くようなシーンで終わった。途中の伏線らしき描写から予想していたのとは違う人物が最後の挿絵に描かれていて、どういう関係だったのだろうかとかなり気になっている。

午前1時から、今日買ってきた板タブを考察に使ってみようと競プロ配信を始めた。

まず、この配信内で起こしてしまったことについて。yukicoderを解いていて、うっかり問題一覧のページに遷移したところ、僕がテスターをした未公開問題の問題名・難易度・タグ・writerが一瞬配信画面に映ってしまった。その時点での視聴者数は7人。即座に配信の巻き戻し機能をオフにし、また配信終了後にアーカイブを非公開にしたのでそれ以上の拡散はないものと信じているが、これ以上は視聴者の良心に恃むしかない。writerに連絡を取って何とか許していただけたものの、作られた問題には代わりとなるものが存在せず自分では何をどうしても贖うことができないため、大変肝を冷やした。

配信で解いたものについて。最初にCF #764 div.3を埋めた。A、Bはよい。Cは先頭から見て、残りの要素で作りにくい値を作るようにしたら通った。コメントで値をnから降順に作ればよいと言われてびっくり。n以下になるまで2で割った後、同じ値を同一視してよいことを意識していなかった。このことがわかれば、僕の解法の「作りにくい値」とはすなわち作れるうちで最も大きな値であったこと、それを貪欲に作ってよかったことがわかる。Dは作る文字列の長さの偶奇を決め打つ。Eはdp。Fは二分探索。適切にcを定めて、\lfloor x/n\rfloorが増えるかどうかを判定の条件とする。ちょっと面倒。Gは辺集合を持ち、上位bitから見て、そのbitが立っていない辺だけ使っても全域木が作れるなら辺集合を更新することを繰り返したら通った。

Dashboard - Codeforces Round #764 (Div. 3) - Codeforces

次に、今日のyukicoder 342のA-Eを解いた。A、Bはよい。Cは、子の数が1の頂点にそれ以下であぶれた部分木のうち最大のものをくっつけてやりたいので、あぶれたものをマージテクで管理。Dは半分全列挙。Eはちょっと難しい。最初、bitごとに考えようとしてしばらく詰まっていた。iを固定するとjの条件がi\le j\le L+R-i\le Rと書けるため、2i\le i+j\le L+Rとわかる。区間全体のXORを、さらにL\le i\le (L+R)/2でXORするため、(2L,2L+1),(2L+2,2L+3),\dotsのようなペアごとに出現回数の偶奇が変わる。ここで、ペアになる2数のXORは1であるから、奇数回出現するペアを数えるだけでよい。L+Rが偶数の場合はそれだけ単独で出現するので、別に数えておく。

yukicoder contest 342 - yukicoder

コメントでオススメされて少し前の問題を1問解いた。実際面白かった。とりあえず重複を取り除く。張る辺の\gcdを決め打ってみると、gで割り切れる要素のうち最小のものとそれ以外を繋ぐことだけ考えれば十分とわかる。そこから、各頂点に対して接続している最も重みが小さい辺を求め、それらで最小全域木を作ろうとしてしまいしばらくWAを重ねた。実際は、先ほど絞り込んだ辺を全部使って最小全域木を作らなければ連結にできない場合がある。

No.1917 LCMST - yukicoder

午前3時半ごろ配信終了。配信アーカイブは非公開のままにするのではなく、見せてはいけない部分だけカットして公開してはどうかと言われたので、そうすることにした。アーカイブをダウンロードして、手元でカットして再度アップロードする必要があると思っていたが、実はYouTube Studio上で簡単に行えるようだ。そういえば、Vtuber小説で配信アーカイブのカット編集に言及していたものがあった気がする。ずいぶん手軽そうに書いてあったのは、こういう機能が存在したからなのか。先ほど触れた配信の巻き戻し機能のオン・オフもVtuber小説から得た知識で、ちゃんと現実にも存在しているんだなあと感動した。

カットした動画が反映されるのにはしばらく時間がかかるようなので、今日は非公開にしたまま布団に入った。午前5時就寝。

05/07(土)

午前10時半起床。YouTubeを見たり本を読んだりしていた。

フォローしているアカウントを頂点、共通のフォロワー数が多いペアを辺としてグラフを作り表示するサービスがTLに流れてきたので、自分も試してみた。頂点が多いのでかなり壮観。ただめちゃくちゃ重いし、出力した画像のサイズもそのままではツイートできないくらい大きくて大変だった。

Furland

昨日の配信アーカイブの編集が完了していたので、ほかに映ってはいけないものが映っていないことを確認して公開設定に戻した。

午後3時就寝。次に午後5時半、目覚ましで起床。またしばらくYouTubeを見て、午後7時くらいに布団から起き上がった。食事し、シャワーを浴び、人の日記を読んだり自分の日記を書き進めたりして時間を過ごし、午後9時からAGC057に出た。実に5か月ぶりのratedである。

AtCoder Grand Contest 057 - AtCoder

A。abの部分文字列であることは、bの最上位桁か最下位桁を落とすことを繰り返してaにたどり着けることと等しい。よって、数を頂点とし、最上位桁か最下位桁を落とした数に向かって辺を張った有向グラフを考えると、良い集合はすべてのペアがこのグラフで互いに到達不可能でなければならない。ここで、このグラフで入次数が0である頂点を選ぶのがよいと思った。確かコンテスト中は、入ってくる辺があるならそれを逆に辿った頂点を選ぶことにしてもよいから、と考えていたはずだが、これは良い集合の状態を保てない操作のため、理由としては間違っている。しかし結論は合っていて助かった。

入次数が0である頂点を数えるため、桁数に注目する。Rの桁数をrとしたとき、r桁の数は全部数えて、r-2桁以下の数は数えない。r-1桁の数については、最下位桁に0を増やすか、最上位桁に1を増やした数がR以下ならば数えない。つまりr-1桁の数x\min(x+10^{r-1},10x)\gt Rのとき選べるということで、この不等式からxの下限が出せる。L以上という条件を確認し忘れて1WAしつつ通した。

B。2進数で桁を揃えたい、というところから考察を始めた。Xの影響を実験してみると、Aの上位桁であって数回操作しても弄れないところは、そのあと何回操作してもずっと弄れないままであると感じた。そうならば、最小値を達成する桁数はそれほど大きくならないはず。各要素の操作回数を決め打つと、達成できる値が区間で表せて、このときの最小値は区間の右端の\minから左端の\maxを引いた値(負なら0)になる。左端が最も小さい要素を選んで1回操作し、また最小値を求める、ということを繰り返せばよさそう。\maxは単に変数を更新すればよく、\minにはmultisetを使うことにした。区間の右端で判定するとオーバーフローしたり操作を試す回数が足りなかったりしたらしく、左端が262未満の間という条件でようやくACした。2200ms。

残りのsolved数は絶望的。若干多かったDに進んだ。とりあえずSが奇数の場合は自明で、しばらく実験してSを割り切らない最小の数pが重要そうなことに気づく。\{S/2+1,\dots,S-1\}という集合があって、ここからいくつか選んでx\leftarrow S-xとする(反転と呼ぶ)と考えられるが、このときまず反転後にpの倍数になるものが選ばれる。それ以降は大きい順に、反転しても良い数列になるなら反転することを繰り返すことになる。Sを作れないという条件は、反転した数だけ無視してチェックしても答えが合ったので、そうした。

そうやってpの倍数にならないのに反転するものを出力してみると、ある数xが反転されたらx-pも反転されているようだった。なので、x\bmod pごとに最大のxを求められればよさそう。そのようなxについて、S-xSp未満の数で割った数の近くになっていそうだったものの、この時点で時間切れ。適当にコードを弄って実験結果と一致するか試すのを何度も行っていたので、もうちょっと頭を使うべきだった。

2完3ペナ118位、パフォーマンス2670、レートは2852→2835(-17)。軽傷で済んでよかった。まずAの考察が正しくなかったのがヤバい。Bもまともな考察をしていなくてヤバい。左端の上限をちょっと下げるとすぐWAになってしまうので、通ったのは本当にたまたまだったらしい。

コンテスト中にとんでもないリザルトが出回っていた。つい最近別の人が1落ちを出していてかなり驚いたものだが、そこから理論値がなかなか出ず、大変苦労している様子がTwitterで見られた。その人を差し置いて先に全部噛み合わせたのは、やはりこの人だったか、という感想。

www.youtube.com

解説を読んでDを通した。反転する数の集合を考えるのはよくて、それが和で閉じていることには一切気づけていなかった。ここは考察が必要だったところ。解説の「Xに追加できる次に小さい数を探す」の部分はかなり難しい。これまで反転した数だけで作れる値を\bmod pで分類し、それぞれ最小のものだけ保存しておく。次に追加する数\bmod pを全探索する。先ほど保存したそれぞれの数Tについて、Tに今追加する数を何回足せばT\bmod pS\bmod pが一致するかが前計算でわかる。そうやって一致させたときにS以下になっていると、さらにpを足してSを作れてしまうので、これがSより大になるという条件が追加する数の下限を与える。Tを全部試して\maxを取り、全探索した中でこの値が一番小さいものが、次に追加できる数となる。それを用いてTの集合を更新する。

コンテスト中にたどり着けたところからもまだかなり遠かったな、という印象。無理だ。

日記を書き始めたが、朝方はかなり集中を切らしてなろうを読んだりしていた。寝る前にatgolferを確認するとAGC-Aが結構縮んでいたので、自分もゴルフしてみた。L\le lとして、区間[l,R]が良い集合であるときのlの最小値を求めたい。二分探索せずとも定数時間で求まるらしい。Rの桁数をrと置いて、l=\max(L,\lfloor R/10\rfloor+1,\min(r-10^{r-1}+1,10^{r-1}))としたら通った。これをdcで書いて60B。

dcコードをずっと睨んでいたが特に縮まないうちに椅子の上で一瞬寝てしまったので、布団に移動。午前9時就寝。

05/08(日)

午後2時半起床。しばらくYouTubeを見てから起き上がり、日記を書いていた。

午後5時からOpenCup。Grand Prix of Yuquan(と書いておかないと後から読み返したとき辛いことに気づいた)。今日はかなり調子が良かった。チームでFDJBCHILMAの10完11位、自分はDBCIを解いた。M問題の問題文に急に魔理沙のイラストが出てきて面白かった。

www.pixiv.net

Dはソートして小さいほうから順に取る場合しか考えなくてよい。全部同じケースで配列外参照を起こしたり、割り算を掛け算に直して比較するときにオーバーフローしたりで2ペナ生やしてしまい大変だった。Bはある条件を満たす数を数えるという問題だが、条件がかなり厳しいので、実験して全部埋め込めそうと感じた。PCが空くのを待って実験を回すと、なんと1つしか見つからなかった。サッとコーディングしてAC。Cは、チームメイトの考察を眺めていると連結成分ごとにサイクル基底を取ればよいことに気づいた。同意を得られたので実装。S=Tのケースにしてやられ、1ペナで通った。

Iも順当に解けた感じ。u\lt vかつp_u\lt p_vとすると、u\lt i\lt vかつp_u\lt p_i\lt p_vなるiに対して一気に差分が求まればよい。A_i-B_iで場合分けしてみると2通りしかないようだったので、それぞれ対応する列に持っておいて、大小関係を満たす要素をカウント。これはrangefreqというライブラリにしてある。書き始めてからC_uC_vの更新がそこそこ大変であることに気づいたが、変更される位置を集めてA_iB_iの計算をやり直せばよかった。実装はかなり面倒。一発で合って嬉しかった。

以降は考察のみ。MはMAOであることを指摘し、しばらく考えてみたものの、操作回数の上限が2L^2で全然ダメだった。通したチームメイトの手法もよくわからない。Kは難読。必死に解読するも微妙な箇所が残ってしまった。基本、言われたとおりに書けば工夫せずとも通りそうだったが、ABCが近づいてきたのでHackMDにいろいろ書いて逃亡。結局僕が書いた考察もまだ難読だったらしく、実装はされなかった。

午後9時からABC250。

AtCoder Beginner Contest 250 - AtCoder

Aで入力の1行目と2行目を取り違え1WA。Bはよい。Cは順列と、各要素からインデックスを引けるテーブルを持てばよい。このテーブルは逆順列である。右端のswapを誤読してサンプルが合わずびっくりした。Dはq\le \sqrt[3]{N}を全探索。Eは、数列Aの各項に対し、その要素が数列Bで出現する位置のうち最も左のものを計算する。そうして作った数列の先頭x項における最大値がy以下のとき、Aの先頭x項は集合としてBの先頭y項に含まれるとわかる。逆も行うことで集合としての一致が判定できる。Fは操作を何回でも行えると誤読してかなり長い時間固まっていた。1回しか行えないので尺取りでOK。

Gはなかなか解けず、苦労した。売値が高い日から貪欲に売ってみたりして迷走し、残り10分になって考え方を変え、ようやく正しい解法が得られた。先頭から見て、売る日・何もしない日を管理する。今見ている日の株価がPであるとする。この日はまだ買う日にはなれない。売るとした場合、何もしない日を1日選んでその日に買ったことにするか、売る日を1日選んで、それとペアになっている買う日を代わりに今見ている日とペアにするか。前者は単純に何もしない日が1日減り、後者は売る日が1日減って何もしない日が1日増える。どちらか利益が大きいほう、または何もしないことを選ぶ。

これが最適であることは、コンテスト中は証明しようとしなかった。サンプル3を試したら合っていたので提出、残り2分で通った。今日記を書いているときにも考えてみたが、どうにもよくわからない。公式解説における説明もかなり難しかったので、行間を少し埋めておこう。まず、多重集合の操作は「Aを2個追加」→「最小の要素mを削除して答えにA-mを加算」と言い換えられる。Aを1つだけ追加する場合が、m=Aとなって対応している。このことは最短コードを読んで気づいた。

dpの折れ線はj=0からスタートして単調減少、加えて上に凸である。傾きはある位置を境に-A以上から未満に切り替わるので、\max(dp_+,dp,dp_-)はその位置に横幅2、傾き-Aの線分を付け加えた形になる。これはj=-1スタートになっているので、一番左から横幅1の線分を削除する。つまり、傾きの列である多重集合にAを2個入れて、最小の要素を削除。操作が正しいことは確認できた。

答えに加える値も見る。j=0における値の変化を追いたい。もともとそこにあった点は、折れ線dp_+においてj=-1の位置にずれ、次の折れ線に必ず存在してくれるため、ここからj=0に戻せばよい。まずdpdp_+になるタイミングで上にAずれて、その後右に1個ずらすとき下にmずれるため、合わせて確かに+A-mとなっている。

7完98位。Fも遅いしGも解けないしでプライドがボロボロになりそうだった。何とか耐え。Eは解説とかなり雰囲気が違う。いろいろやり方があるらしい。

コードゴルフ。Aは4-(\lfloor 1/R\rfloor+\lfloor R/H\rfloor+\lfloor 1/C\rfloor+\lfloor C/W\rfloor)をdcで書いた。[x code]dxのテクを使って、まったく同じcodeを2回実行する。スタック操作をうまく組み合わせるとそこそこ縮んで21B。BはPerlで書いた。あまり短いとは思えないが自力では縮まない。なんだか僕が考えもしなかった書き方がありそうな雰囲気。DはRubyで書いてVimで縮めた。解説とは逆にqを全探索することにすれば、全探索できることが容易にわかるし、pをカウントするテーブルも同時に作ることができる。というかstackに直前の素数を入れて、条件を満たさない間popしていけば十分。他は手付かず。

午後11時半からCF #789 div.1に出た。

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

Aはcaをこの順にnから全探索。cを減らす前にカウント配列の(p_c,n]1加えると、bを決めるごとにdの個数が即座に求まる。aを減らす前にb=aとした場合のdの個数をそうやって求め変数に足しておき、減らした後のap_a\lt p_cを満たす場合にそれを答えに加える。特別なデータ構造を使わず全体でO(n^2)になり、気持ちよかった。

Bは縦横をそれぞれ計算。横は、各1\le i\le nmについて(i-m,i]'1'があるか調べ、あったならi,i+m,i+2m,\dots1加算。iに加えてからm個おきの累積和を取る。縦はインデックス\bmod mが不変なので、その列で初めて'1'になるインデックスを求め、それ以降に1加算。縦横が入り乱れてちょっと頭が壊れそうになったが、一発でサンプルが合って興奮した。

Cはfunctional graphと見て連結成分に分解。頂点の値を昇順に並べると、係数を\dots,-2,-2,(0,){+2},+2,\dotsのようにするのが最適。何回か見たことがある。3種類それぞれカウントして、1から順に小さい係数を割り当てていく。最初、頂点番号の係数ではなく区間の係数を見てしまい、最適な割り当てを作れずに1WAした。

Dは難しい。まず、操作はバブルソートの一部になっている。k回操作したら後ろk項は決定される。逆にこれを巻き戻してみよう。例えばk=1のときを考える。末尾のnがそれ以前にどこかにあったはずで、その位置は、先頭であるか、または先頭から見て累積maxが変化する点の直後である。また累積max以外の場所は一切変化しない。途中にnを置いた場合はその直前にある値に乗り換え、同様にして先頭までたどり着いたら巻き戻しが完了する。ここで(n以外の)累積maxの個数cを考えてみると、1回操作を巻き戻した後、その個数は0\le i\le cについてi個になるのが\binom{c}{i}通り存在する。無視していたnを戻してi+1個。nの代わりにn-k+1,\dots,nとして順番に巻き戻した後の場合の数を数えたい。cを次元に持つdpを手で計算してkごとにOEISに投げると、k!(k+1)^cであると判明した。

後は、k回操作後の列をcごとに求められればよい。挿入dpにcを保持する次元を増やすと多項式と見れて、遷移が1次以下の式の掛け算になった。大量の1次式の積をセグ木みたいにまとめていってO(n(\log n)^2)で計算するやつを実装。最大ケースでも1.3sec程度になったので提出したら、爆速で通った。そういうケースがpretestに入っていないようでかなり心配だが、まあ解けたのでヨシ!

残り1時間。Eのsolvedがかなり少なくほぼ諦めモードだったが、何とか気力を奮い立たせて考察を始めた。とりあえずbeautifulな区間の右端をrと固定してみる。この時、左に見て累積maxが更新される位置の列を\dots,(m_a,i_a),(m_b,i_b),\dotsm_a\gt m_bi_a\lt i_b)として求められる。\max=m_bと決め打ち、lであってi_a\lt l\le i_bかつp_ip_j=m_bとなるようなl\le i\lt j\le rが存在するものを求めよう。

1\le j\le rのそれぞれについて、m_b/p_jが整数となるか調べ、整数ならばm_b/p_jが列のどこに位置するか取得して、その位置iであってi\lt jを満たすものだけを集めて最大値i_{m_b}を計算すれば、li_a\lt l\le \min(i_b,i_{m_b})とわかる。i_{m_b}の計算では、m_bと制限せずp_jの倍数を全部調べる方法で、r=1\dots n全体が調和級数O(N\log N)で計算できる。

さて、r1から順に調べるごとに、累積maxの列の(m_b,i_b)それぞれを見て上のような区間に1足せば、r_i=rであるようなクエリについて[l_i,r_i]区間和を求めることで答えがわかる。しかし累積maxを毎回見るのはどう考えても間に合わないため、高速化が必要。ここで、i_{m_b}の更新回数がO(N\log N)であることに注目する。現在列に存在する累積maxであって更新されたもののみ取り扱えばよさそう。今取り扱わなかったものについては直前と全く同じ値が足されることになるが、その「同じ値」が足される回数は、対応するi_{m_b}が最後に変化した位置(あるいはその累積maxが出現した位置)とrの差で求められる。つまりrの1次式なので、区間和と同様遅延セグメント木に乗せ、取得の際にx=rとすればよい。

かなり大変そうだが何とか書き始められそう。実装したら、コンテスト終了の10分ほど前にとりあえず書きあがった。デバッグも含めると間に合わないかな、と思いつつサンプルを試したら、なんと一発で全部合ってしまった!恐る恐る提出すると通った。これで5完。

システスも全部通って27位、レートは2869→2916(+47)。DとEがかなり通されていて、思ったより伸びなかった。Dは求めたい値が多項式fに対するf(k+1)だったので、最初からx=k+1として積を取ればよかったらしい。n\le 10^6O(n(\log n)^2)を2secは攻めているどころの話ではない。ただ僕が書いたコードはかなり高速だったようで、コンテスト後にいくらかHackの試みを観測したが結局落ちていない。Eは2次元の領域和で解いた人が多い。そちらはよくわかっていない。

OpenCup-Kを解いた。問題文に書いてある表から数値を取り出してコードに埋め込むだけ。コンテスト中に残した読解が微妙な箇所は、僕が考えていたことが間違いだったようだ。経験値を溜めてレベルを上げるとき、特定のレベルで一旦ストップしなければならないと書いてあったのを、経験値をたくさん稼いで一気にスキップできないだけだと勘違いしてやたら面倒なことをしていた。実際は、そのレベルに到達した瞬間未反映の経験値が全部消し飛ぶらしい。端数を管理しなくてよいので簡単になる。

OpenCupのページでは問題文が画像で表示されるため、僕は以下の表を全部手動で埋め込んだ。しかし、実はPDFの問題文も存在するらしい。

05/09追記:原神というゲームの経験値テーブルだったらしい。OpenCupでこのゲーム見るの何回目だよ。レベルシステムをちょっと調べてみたところ、途中のレベルでストップしていたのはレベル上限の解放が必要だったからということが分かった。それなら未反映の経験値が全部消し飛ぶのも納得。こういう知識がないとまともに読めないような問題文はカス。経験値テーブルをドンと置いて何食わぬ顔をしている時点でカスか。また、以下のツイートにあるリンク先のテーブルは微妙に異なるようだ。具体的には49Lvにおける値が違うのと、81Lvに80Lvと同じ値が1個挿入され、以降一つずつずれている。

朝まで日記を書いていた。今週は微妙に遅れ続けており、今日は土日の部分を書いていた。朝方、ABC-Gの正当性を考えていたら急激な眠気に襲われたので、週記の完成を明日に回して寝ることにした。午前8時半就寝。

週記(2022/04/25-2022/05/01)

04/25(月)

先週の週記を投稿してから。学食に行って食事し、今日もまた予約していた新刊ラノベを受け取って帰ってきた。そこから1時間インターン関連のコーディングをした。一度寝たら定例会まで起きられないことが分かっているので、寝る前に進めておこうという魂胆。一応少しだけ進んだのでちょっと満足し、切り上げた。後は布団に入ってすぐ寝るつもりが、うっかりハーメルンを読み始め、睡眠時間が1時間ほど減ってしまった。午後1時就寝。

午後4時起床。布団の上で20分くらい意識朦朧としていた。何とか起き上がって定例会へ。今日報告する進捗は朝方の1時間のみで、内容が薄い以外は問題なく終了。

勉強会の内容は数学だった。体であり、全順序を持ち、連続の公理を満たし、\{0\}でないならばそれは実数体と同型であるという話。そういう実数の構成は初めて知ったので面白かった。ただ微妙に正しくない読み取り方ができる。例えば有限体は要素が有限個しかないのだから、適当に並べれば全順序を入れることができる。それに意味があるかはさておき。調べてみると、「体であって全順序を持つ」の部分は正確には「順序体」である必要があって、その定義には体の演算と全順序の関係が記述されていた。先ほどのような、有限体の演算を無視した全順序ではダメだということ。この演算と全順序の関係を暗黙的に仮定していたか、あるいは自分がひねくれている。

勉強会も終わりかけの時間にコンテストTシャツが届いた。この時間なら確実に起きているということで再配達を依頼していたのだが、自分が勉強会にコメントした直後に来たので非常に危ないタイミングだった。Mサイズだったので自分には少し大きい。ちゃんとSサイズに設定を変えてあるので、なぜMサイズが送られてきたのか謎。しかしよく調べると、このTシャツを獲得したコンテストは「Deltix Round, Summer 2021」という去年の8月末のコンテストだったから、その時の設定で送られてきてしまったのかもしれない。届くのが遅すぎる。

課題を1つ倒し、CF #784 div.4を解いた。全部自明だったので特に問題ごとの言及はしない。一応コンテストリンクだけ貼っておこう。

Dashboard - Codeforces Round #784 (Div. 4) - Codeforces

しばらくハーメルンを読んでから、今日の分の日記を書いた。このとき、今朝方投稿した週記のタイトルに日付の終端がないまま投稿してしまっていたことに気づいた。修正しておいたがツイートの文面に名残が残っている。

午前0時半就寝。

04/26(火)

午前5時過ぎに目を覚ましてしまう。うっかりハーメルンに熱中し、午前11時まで布団で読みふけっていた。1作読了、「転生男の娘は道化の海賊を王にする」。

syosetu.org

ワンピース二次創作。主人公が副船長という立ち位置であったり、一つの能力で多彩な攻撃が行えたりということから「正体不明の妖怪(になった男)、情緒不安定な百獣の腹心になる」と似たものを感じていた。それの設定が好きだったので、こちらも好き。当然細部は全然違っていて、こちらだと主人公に多少の人間味があって良かった。能力の設定も良い。一か月ほど前にワンピースネタバレがTLに流れてきたが、そこで見た展開がこちらにも盛り込まれていたのも好きだった。主人公が強いと嬉しいから。

布団から出て学食に向かう。今日は麺の気分だったので、それを出す店が開く午前11時半以降を狙っていた。結局出るのが遅れて45分に着いた。もう人だらけで大変だった。正午を過ぎると本格的に昼休みになるため、帰宅時は凄まじい行列を横目に帰ってきた。そのような時間帯にはできるだけ大学に来るべきではなくて、今日のようにギリギリアウトみたいな時間になりそうだったら午後1時になるのを待つほうが良い。気を付けよう。

帰宅してしばらくパソコンを触った後、午後1時半からインターンのコーディングに取り掛かった。昨日、これまで書いたコードをテストするためのデータをいくつか用意してもらったので、それの前処理と、実際に実行してみる部分。手作業で前処理するのはかなり面倒だった。いずれもっと多くのデータでテストするつもりなので、前処理をどのように自動化するかも考えなければならない。

実際に実行してみると、自分が考慮していなかったケースがいくつも見つかって、それの対応も少し行った。エクセルで結合したセルの内容は、結合した領域の左上のマスに入っている。ただ、領域のそれ以外のマスにも内容が入っている場合があって、それを適切に無視しなければならなかった。普通に結合操作を行うとそのようなマスの内容は破棄されるので、なぜこんな状態になっているのかわからない。最初、エクセルで開いても見えない値がプログラムから読まれていて、しばらく頭を抱えていた。

午後3時から1時間1on1。先ほどまでやっていたことを説明しようとして、全く整理できておらずかなりとっ散らかった感じになってしまった。とりあえず一通り話した後、前処理の自動化などについて相談して終了。一段落するまでさらにしばらくコーディングをして、今日は終了。

最近は星街すいせいというVtuberの歌ってみた動画をループして作業用BGMとしていた。するとYouTubeのおすすめに配信切り抜きの手描き動画が出てきて、うっかり視聴してしまった。かなり良い。それにしても手描きとは、熱意がすごすぎる。

www.youtube.com

しばらくパソコンを触っていたが、今日はもう眠い。午後8時からあーだこーだーに出る予定なので、しばらく仮眠することにした。

僕が登場するあーだこーだーは再来週の火曜日、04/26になりそうだ。

週記(2022/04/11-2022/04/17) - kotatsugameの日記

寝過ごさないようこまめに目覚ましをかけつつ横たわっていたが、午後8時に近づいても連絡がない。自分も眠くてギリギリまで寝ていた。午後8時を過ぎたあたりでchokudaiさんがあーだこーだーの予定を忘れていたことが発覚し、今日は配信しないことになった。来週はGW中で自分が帰省しているので、また再来週以降となる。正直、今日は生活リズムが合っていなかったため助かった。

そのまま布団でハーメルンを読んでいたら、午後9時半ごろに寝落ちした。

04/27(水)

午前3時起床。明日のセミナー発表のために論文や教科書を読んでいた。午前7時を過ぎて眠気が強くなってきたので、二度寝しようと思って布団に移動。しかしそこからうっかりなろうを読み始めてしまった。昼間までなろうを読んだ後はラノベを開いた。さらにしばらく読んで、午後4時になってようやく就寝。

午後9時、目覚ましで起床。生活リズム的にこのくらいの時間には起きたいと思っていた。しかし実際に起きてみると眠すぎる。もう少し眠りたいと思いつつ、その決心もつかずにしばらく布団からスマホで論文を読んでいた。午後11時になって布団から脱出。

寝る前に見ていた切り抜きをツイート。なぜ切り抜きを見ているのか。しかしこのフニャフニャ感はかなり健康に良かった。

www.youtube.com

GWに後顧の憂いなく帰省するため、課題を倒した。今週までの課題と、来週までの課題。来週までのものは講義スライドだけ公開されていて動画はまだないのだが、わざわざ待っていられないので提出してしまった。課題が提出できるようになっているということは、向こうも動画を見ていないくらいで何か言うことはないということだろう。

今日の作業用BGMは星街すいせいの歌枠だった。正直、歌枠という配信アーカイブを作業用BGMにするのは微妙かな。ほとんどの曲を知らないのであまり面白くないというのと、歌を聞きたいのだったら歌ってみたとして作られた動画をループしたほうがいいと感じた。これは生歌がどうこうではなく、後ろの曲がよく聞こえなかったということから。合間にあるトークを求めるのならトークメインの配信アーカイブを使えばよさそう。

ラノベを少し読みつつ、明日のセミナー発表の準備を始めた。結局、今週読んでいた論文を発表するのは諦めて、先週眺めたものから1つ取り上げることにした。用語は教科書で確認できたのだが、事実とされていることが全然わからないし、証明もそこだけ読むのは厳しかった。一方先週のは何とかなりそう。多分。

論文のほうは飛ばし飛ばしで1つを眺め終えた。眺めているだけでは何もわからない、というのはそれはそうとして、別に読めないわけではなさそう。ただ用語がところどころ怪しくて、少なくとも何か参照するべき教科書が必要と分かった。

週記(2022/04/18-2022/04/24) - kotatsugameの日記

結局ずっと歌枠を流し聞きしていたので、ラノベはあまり集中できず全然読み進められなかった。発表の準備は紙に話したいことと話さなければならないことを書き出しただけ。グラフの論文を初めて取り扱うので、一応グラフ周りの用語定義から始めるつもりである。

午前8時半就寝。

04/28(木)

午後1時、目覚ましで起床。寝過ごすと怖いので二度寝は諦め布団から出た。のどが渇いていたのでお茶をグビグビ飲んだらてきめんに腹を壊してしまい、数回トイレと部屋を往復した。

腹の調子が持ち直したところで、セミナーに向け出発。学食に滑り込む。閉店する午後2時の直前だった。そこで食事して、帰省のための学割を発行してから山に登ると午後2時半。セミナーまであと30分ある。こう、学食の営業時間と微妙に噛み合わないのが辛いところ。院生室に友人がいたのでしばらく喋った。

午後3時からセミナー。まず僕の発表について、昨日考えた順番で説明していったつもりなのに説明忘れだったり余計なことを口走ったりして、自分でも一貫した流れの発表になっていないなと感じた。こういうのはやはり自分で一度説明してみるべきだったのだろう。必要な用語をきちんと洗い出せてすらいなかった。黒板の使い方も下手くそで、真ん中のほうに重要なことを書いてしまって、その左右を往復したりしていた。内容はまあ満足。

もう一方の発表は面白かった。面白かったというか次回が面白そうというか。ラムダ計算自体にはあまり触れたことがないが、SKIコンビネータはUnlambdaの経験があるのでそれなりに手を動かしたことがあり、そのパズルみたいな作業が面白かった記憶がある。まあ今日は久しぶりすぎて失敗したわけだが。

\x.\y.\z.x(yz)をSKIコンビネータで書く話。まず\z.x(yz)=S(\z.x)(\z.yz)=S(Kx)yとして、次に\y.S(Kx)y=S(Kx)として、最後に\x.S(Kx)=S(\x.S)(\x.Kx)=S(KS)Kとなる。いやこれだとちょっと不正確か。同じ変数名を使っているところは同じ値に関数適用したい、という気持ちで読んでほしい。関数適用するためには基本的にSを使うしかないのだなあと思い知った。やっていることをよく見ると、Unlambdaを書いているとき参考にしたサイトで紹介されていた方法と同じだったのもびっくり。当時は単純に記号を置き換えるだけで、意味を深く考えてはいなかったか。

Unlambda -Function Coding-

午後5時くらいに終了。お腹も空いていなかったので即座に帰宅した。

今日はしぐれういというイラストレーターの配信アーカイブを流しながら日記を書くことにした。聞き流すのに心地よい声だと感じる。と、チャンネルに行ったら、ちょうど今日の午後11時から配信があることに気づいた。試しにリマインダーをオンにしておいた。

いくつかアーカイブを渡り歩きながら日記を書き進めていたのだが、全然進まなかった。動画に集中してしまったというよりは、日記に集中できていなかった。何を書くか文章に迷っていた時間が長かったように思う。午後11時になったので配信の視聴を開始した。

……見事に2時間見続けてしまった。その間も日記を書き続けて、何とか今日の分までたどり着けた。

その後またしばらくYouTubeを見た後、ゴミを出して布団に入った。少しラノベを読もうとしたがあまりに眠く、目が滑りまくる。諦めて就寝。午前4時だった。

04/29(金)

午前11時くらいに目を覚ます。

腕が筋肉痛になっていてびっくり。実は心当たりがあって、昨日、院生室に転がっていたダンベルを持ってしばらく腕を動かしていたのだった。やり方がまずかったのだろうか。特に腕を伸ばした時の痛みがひどい。

それはそうと、昨日の睡眠時間的にもう少し寝ておきたいなと思った。そう思いながらもYouTubeを開いてしまい、そのまま眠れなくなった。午後2時半くらいに諦めて起き上がって、布団で見ていた切り抜きから1つツイートした。

www.youtube.com

今セメスターの時間割をツイートした。一度コマがずれている状態でツイートしてしまったので、消してツイートしなおした。セミナーは対面で行うので教室名を書き入れておきたかったが、よく覚えていないので空欄のままにしてある。数学棟3階はその教室と図書室しか見当たらないので、番号を覚えていなくても間違えようがないのだ。ではその上の「数理論理学特論」と同じ教室ではないのか。しかし、もしそうだとしたら、1部屋しかないのに305という名前がついていることになって謎。

本当は今日ゲーセンに行くつもりだった。月曜から帰省する予定なので、仙台にいるうちにチュウニズムを1度プレイしておきたい。イベントの終了が近付いている。しかし天気が悪いのと、中途半端に眠気が残っているのと、先ほども述べたように腕が痛いので見送ることにした。再度布団に戻り、しばらくラノベを読んで就寝。ちゃんとラノベをそばの机に置いたので寝落ちしたわけではないが、就寝報告のツイートをしておらず、またChromeの閲覧履歴からも復元できないため、時刻は不明。午後6時前ではないかと思う。

04/30(土)

午前1時起床。ハーメルンからVtuberものでまだ話数が少ない作品を2作読了。

syosetu.org

「TSして人生やり直すことになったのでVtuberやる」。逆行転生して世界初のVtuberになるやつ。5話で幼少期の努力から準備まで完了してテンポが良かった。似たような作品の「逆行転生したおじさん、性別も逆転したけどバーチャルYouTuberの親分をめざす!」は11話だったので、どちらにしても多少短いくらいが過去の厚みとしてちょうどいいのかも。活動開始後の配信の内容、また登録者を増やす過程はそれとはまったく違った感じで楽しめた。いずれにしてもバズらないと大変なんだなあと感じた。

syosetu.org

「秋宮ゆららは青を喰む」。序盤はかなり闇が深そうなことが書いてあるが、現在更新されている分では特に何事もなく安穏と活動している。キャラたちの関係性は楽しめたものの、その闇がこれからどう関わってくるのかちょっと気になってしまう。

その後ラノベを1作読了。「王様のプロポーズ」2巻。今巻には展開やシーンとして僕にぶっ刺さるような箇所がなかったため、ちょっとがっかり。もちろん、細かく散りばめられたギャグはどれも面白く、ずっと笑いながら読んでいけた。しかし全体を振り返ったとき、あのシーンが良かったなあとか、この展開は僕好みだなあとか思うところがなかったということ。主人公があまり活躍しなかったのが残念。ラストで、この本が構成としてなかなか粋な演出がされていることに気づいて興奮したが、これはfunnyではなくinterestingである。

午前7時、再度就寝。次に午前11時起床。布団でしばらくYouTubeを見た後起き上がった。

今日はコンテストもないし、天気も良いので絶好の外出日和。ただ1点まだ腕が痛むのが気になるが、無理を押してゲーセンに行くことにした。ついでに帰省のための切符も買う。GWに入ってみどりの窓口が混んでいるみたいな話を聞くので、当日買うのでは時間がかかるだろう。窓口でコミュニケーションに失敗しないよう買う切符を文章にまとめて、必要な金額も大まかに計算しておいた。

自転車で家を出発。二郎ラーメンの店の前を通ったら、近くの交差点まで続く列ができていてびっくり。こんな混むなら駅前の人混みは酷いだろうなと思いつつ進み、つけ麺屋で食事して仙台駅へ。確かにペデストリアンデッキは人まみれだったものの、みどりの窓口はガラス戸の中に入れるくらい人が少なく助かった。20分弱並んで無事購入。ゲーセンに移動。SEGAGiGOになっていて面白かった。

午後3時から閉店までチュウニズムをプレイ。8時間半で実に47クレ使ったらしい。今日は理論値8、14+のSSSが1、SS+が1、そして15のSSSが1つ。15は他にも2つほど伸びた。

まず理論値について、前から1クレ3曲全部新規理論値ということをやってみたいと考えていて、今日はかなりいいところまで行ったのだが、緊張に負けて1つ出してしまった。また今日はVtuberのオリジナル曲もいくつか出そうとした。特に星街すいせいの「自分勝手Dazzling」を狙ってみたのだが、信じられないくらい難しい。どこででも出る。かっこいい曲ではあるのだが、リズムが取りにくかったり音が少なかったりで、音ゲー向きではない。

「TiamaT:F minor」のSSSを出した。狙ったのは今日が初めてだが、ゲーセンに来るたびにプレイしてはいた。いつの間にか後半はそれなりに通るようになっていたので、問題は前半。譜面を見て運指を組んだらシュッと出た。運指を組むといっても擦りの手順を覚えるくらい。気を付けるポイントとしては、五鍵は思ったより遅いこと、後半のフリックとタップ+エアーの忙しい箇所は無闇に手を速く動かすのではなく、ちゃんとフリックが取れるよう大きく動かすこと。

ここはよくわからない。数個くらいアタックを出してよいので安定する運指を、と考えたらこうなった。やってみた感じ、ミスはあんまり出ない気がする。直後の両手トリルはいつの間にか普通に押せるようになっていたので感動した。それ以外にも押そうとしてみたら案外行ける配置が多く、自分の成長を感じた。

82小節目

いつもの立ち食いそばではなくラーメンを食べた。呑み屋街はあり得ないくらい人がいた。日付が変わってから帰宅。

疲れ果ててパソコンの前から動けなくなり、しばらくYouTubeを見ていた。

www.youtube.com

かわいいの権化みたいな咳でめちゃくちゃ健康にいい。「○○助かる」とコメントしている人の気持ちが分かった気がする。我々ばかり健康になっても意味がないので、しぐれういさんにもぜひ健康でいてほしい。

シャワーを浴び、布団に入ってカクヨムを開く。眠気に耐えつつ更新分を読み、午前4時就寝。

05/01(日)

午後1時過ぎ起床。YouTubeを見たりカクヨムを読んだりした後、OpenCupまでの間に二度寝できないくらいの時間になって布団から出た。

www.youtube.com

「ふ~許せん!」が好きすぎる。好きすぎて元動画でしばらく探していた。35分10秒くらい。「お茶を飲んで落ち着くね」と言ってしばらく静かになった後、怒りの吐息が漏れ出すところからマジで可愛い。どうなってるんだ。吐息助かりまくり。僕が一人で勝手に助かるだけ。

昨日サークルの活動日が決定していた。今セメスターは月曜午後4時半から。これは僕のインターン先の定例会と完全に被ってしまうため、参加が不可能になった。日程を決めるアンケートに票は入れていたので、やむなし。まあ4月中まったく参加しなかったので、日程が合っていたとして定期的に参加するかは微妙か。新歓に顔を出せなくなったのはちょっと残念かな。何気に対面の新歓で新入生を迎えたことがないため。M1とかいう老人に迎えられてもお互い困るか。

2022/05/04追記:大嘘。2019年は対面で新歓を行った。複数人が同時にテキストを編集できるツールを使って画面共有みたいなことをしながら、ABCの問題を解いた記憶がある。

4月が終わったので、読書記録をツイートした。今月は先月にもましてネット小説にメタメタにされてしまった。ここでちょっとネット小説もカウントしてみよう。いつの間にかカクヨムでは自分が読んだ文字数が記録されるようになっていて、確か最後に見たときは230万文字くらいだったはず。これに加えてハーメルンでも150万文字くらい読んでいるので、文字数ベースでは500万文字くらいになるだろうか。全部ラノベに割り当てると考えれば、2019年4月に記録した月40冊ペースくらいになりそうとわかる。ところで、カクヨムが公式でデータを出してくれるのは大変ありがたいが先月分が見れないのは困る。

食事して午後5時からOpenCup。

Aを読んだら自明二分探索だったので慌てて書き始めた。\lfloor H/M\rfloor\times\lfloor W/M\rfloor\ge Kを判定する。しかしよく考えると誤差が怖い。幸いK\le 10^9なので、境界ギリギリでは浮動小数点数でも十分表現できそう。念のためlong doubleを使って書いたら通った。少ししてHとJがポンポンと通された。

2022/05/04追記:Aは自明ではない。より正確に書けば、H\times Wのシートから同じ大きさの正方形をK個切り出すとき、正方形の1辺の長さは最大いくらにできるか?という問題。特にH=Wの場合、有名な未解決問題になる。問題文のどこを探してもそのようなことは書かれていないが、縦と横にしか切れないという制限を勝手に設けて解くと上に書いたようになる。いわゆるバカ発見器。恥ずかしい。

Square packing in a square - Wikipedia

しばらく時間が空く。Eは単なるBFSで解けそうという話になったので書いてもらっていた。しかし題意の微妙な違いに大変苦労したらしく、コンテスト開始2時間で通った。その後すぐC問題が通された。実験してエスパーしてOEISだったらしい。その後、僕がGを書き始めた。この時点でまだ提出すら1つもなかったが、やればできそうに見えた。

値または値への参照を持つ変数と、それらを引数に取る関数を宣言する構文が定義されて、借用チェッカを実装しなさいという問題。問題文がカス。例えば、値を持つ変数は一度使うと無効化される一方、参照を持つ変数は使っても無効化されないらしい。また、ある変数の値が書き換わった瞬間、以前の値への参照もすべて無効化されるらしい。この2点は問題文中のどこにも書いていないため、clarを投げた。Rustと言っておけば伝わると思うなよ。また関数名のダブりについても確認して、これらをはっきりさせたら、あとは構文解析。関数シグネチャをチェックした後、そこで使われた変数を一つ一つ見て無効化されていないか確かめる。値の無効化時にそれへの参照も全部無効化していいので結構楽だった。変数に変数を代入するのは注意が必要。a:=&aとすると、これ自体はvalidな文だが、aが指す値はすでに無効化されたとみなされるらしい。サンプル2にあって助かった。さらに適当な変数bを経由してこのように代入される場合もあって面倒だった。1ペナ吐いて、3時間22分時点で通したのが全体で2番目だった。

何やら誤読していたらしいIが通ったのを横目にDを考察。二分木のrotate操作で木を平衡化できれば解けそうとなって、splay木のライブラリを持っていたチームメイトに実装を託してBに進み、何もわからず終了。Dもバグらせてしまったらしく通らず、7完で16位となった。なかなか調子が良かったように見える。まあ自分は自明のAとカス問題文のGしか解いていないわけだが。他に通った問題の考察をちっとも追っていない。

しばらく日記を書いて、午後11時半からCodeChef、May Cook-Off 2022 div.1。

https://www.codechef.com/COOK141A

TRIPLE_INVSで人生終了。自明なのにうっかり復元しようとして30分をドブに捨てた。何とか書きあがってからサンプルを見ると出力例にYES・NOしかなく、さすがに声が出た。自分のコードの出力部を消してAC。この時点で100人近くのsolvedがいて目の前が真っ暗になった。DIFSUBARRAYSは同じ値をまとめ、出現回数の降順に並べたものと、それの先頭から一番出現回数が多い値(のうち一つ)を全部後ろに回したもののペアだけを解の候補とすればよい。これでダメなケースは、過半数が同じ値か、または同じ値がN/2個ずつあるか。前者は明らかにNOで、後者も同じ位置に同じ値を置いてはいけないことを考えればNOとわかる。

SPLITPOWOF2はdp。集合の和の差(ただし常に正とする)を考え、下の桁から見て、繰り上がりを次元に持ってみる。繰り上がりがi個ある場合、i\ge 1ならその次への繰り上がりは0以上\lfloor(i+A)/2\rfloor以下のどれでもOKであるとわかる。i=0の場合は0以上\lceil A/2\rceil以下で、Aが奇数の時は操作回数に1加えられる。これらを見ると、繰り上がりの範囲の代わりに上限だけ考えて遷移してもよいことがわかる。遷移時に2で割って切り捨てるのが難しいので、逆にiを取得するときに2i2i+1を両方見るようにすれば、各iに対して0\le A\le Bでの遷移が区間和で書けるようになる。imos法で実装。状態数2\times \max B\le 10000、遷移回数N\le 5000で不安になるが、普通に書いたら0.43secで通った。

MAXMINCRCDIFは解けなかった。ソートした後(A_i,A_{i+N/2})みたいなペアを適当に入れ替えて並べればよいのではないかと思い、それっぽいものを実装するもWA。その後n=9,10での実験を経てこのエスパーは正しいことが分かったものの、入れ替えと並び替えの規則性が全く掴めず、いろいろな方針を試してみるも大した進展はなくコンテスト終了。3完。1問目があり得ないくらい遅かったにしてはまあまあ耐えて23位、レートは2654→2628(-26)。

朝方、日記を書きつつカクヨムを1作読了。「煽り系ゲーム配信者(20歳)、配信の切り忘れによりいい人バレする。」。かなり面白かったがもうちょっと視聴者とのプロレスを描いてほしい気持ちになった。最近の更新分はリアルの話が多め。また、主人公がさすがにいい人すぎる気もする。これで煽り系をやっていたとなると近いうち心の健康を損ないそう。まあそういう作品なので仕方ないか。

kakuyomu.jp

今週はコンテストが2回しかなく、文字数は最近のものと比べると控えめになった。とはいえそれらが日曜日に集中した結果それなりに時間を使い、今、ここまで書いて午前6時。明日が帰省で、できれば午前9時発の新幹線に乗りたい。ヤバい。一瞬諦めてカクヨムを読んでしまったのが響いている。書き上げて推敲のため読み直していたら午前6時半。あ~あ。

週記(2022/04/18-2022/04/24)

04/18(月)

04/17 午後11時半ごろ起床。ちょうどCF div.2が始まったころだが見送った。

すぐ日付が変わって、TCB46の結果が出た。3位と1点差で2位。1位とはかなり差を付けられていてショック。問題ごとの減点を見返してみるに、やはり2度以上提出するのが大きく響くようだ。スコアの計算式を改めてよく見ると、まず提出回数によって基本スコアが減らされて、さらにそれを元にボーナス2種類が計算されているらしい。つまり得点全体を減らしているようなものなので、影響が大きいのも納得。

https://techful-programming.com/faq/problem#q2

ちょっとカクヨムを開いたらかなり面白い場面で、そのまま午前1時半まで読んで最新話に追いついた。「自作3Dモデルの素材を宣伝するためにVtuberになったら予想外に人気出てしまった」。

kakuyomu.jp

Vtuberではなく中の人とその周囲をメインに描いている。複雑に絡み合った人間関係が徐々に明かされて行って、そのこんがらがった様子がかなり面白かった。Vtuberと中の人の関係は一般に秘密にされるということも効いている。一方配信活動の描写はそれほど力を入れていなさそうで、その分特に大きなイベントが起こったりもしない安定したVtuber活動が見れるのは安心感がある。以上がVtuberモノとして見た時の感想。他に、主人公がめちゃくちゃ鈍感なのが僕の好みだった。女性に粉をかけられているのに全然気づいていない描写など最高にニヤニヤできた。

そこから午前4時半くらいまでは別のカクヨムを読んだりハーメルンを読み返したりしていた。いい加減二度寝するのを諦め、布団から起き上がって食事した。

ちょっとコードゴルフをしたところ、提出制限が「2つ前の提出から5分間提出できない」になっていることに気づいた。以前は間隔が1分間だった。一応、1つ前の提出からは相変わらず5秒でよいようだ。これは先週の週記でも触れた、無限ループを延々投げられることへの対策だろうか。5分だとさすがにちょっと辛いので、コンテスト中だけでも制限が弱まったりすると嬉しい。

かなり久しぶりにラノベを1冊読了。「男子だと思っていた幼馴染との新婚生活がうまくいきすぎる件について」。至って普通のラノベではあるのだが、上流階級出身でお見合いでヒロインと結ばれるという設定と、幼馴染だったヒロインを昔は男子だと思って接していたという設定が、それぞれ同レーベルの現在売れている別作品と被っているのが気になってしまった。まあ前者はお見合いをする必然性からどうしても入ってしまう設定か。似たようなことを、その別作品を読んだ時にも考えていた。後者に至ってはタイトルからわかることだし……。内容としてはラストで祖母との確執がスムーズに解決するのが良かった。

作中では結婚可能年齢が男女とも15歳に引き下げられていた。あと、登場人物が軒並み名家の御曹司・令嬢だった。この2つの設定はどちらも単独で主人公がお見合いをすることの理由になりうるが、2つ合わさっても別に最強には見えない。その設定両方いる?

週記(2020/11/30-2020/12/06) - kotatsugameの日記

先週遅れて課題を提出した講義に、その課題の講評が投稿されていた。そこに僕の回答も紹介されていて嬉しくなった。真偽が明確に定まる文を自分で作り、その真偽を判定せよという問題。定義があいまいな事物を持ち出したり、断りなく変数を導入したりした回答がダメ出しされていた。さらに真偽の判定についても、例を挙げるなら具体的でなければならないということを突っ込まれていた。一方、僕の回答である「『この課題を遅れて提出した人がいる』は真である、何故なら自分がそうだから」は完璧だったらしい。

すでに期限が過ぎた課題を見つけた。今週分のようだ。遅れると1日ごとに点数が引かれていくシステムだったので、慌てて提出しておいた。

週記(2022/04/11-2022/04/17) - kotatsugameの日記

昼前まで先週分の週記を書いていた。完成させて投稿、さらに今日の分の日記を少し書き進めもした。また、上で触れた講義の今週分の課題を提出した。そうやって時間を過ごし、いい感じに昼休みが終わったのを見計らって学食に行って食事。予約していたラノベを受け取り、床屋にも寄ってきた。

帰宅してから1時間ほどかけ、「研究倫理教育」という大学院ガイダンス時に貰ってきた書類に書いてあったものをこなした。ネットでテキストを読み、選択問題の小テストを解く。もう全然やる気がなくてテキストはまともに読んでいなかったが、小テストはそれっぽい選択肢を常識に基づいて選ぶだけでそこそこ正解できた。合格点に届かなかった場合も、解答を確認した後即座に再挑戦できて、今度も問題の並ぶ順番がシャッフルされるくらいの違いしかないので、覚えておけば簡単。

今週は午後4時からインターン先の定例会。普段より30分前倒しになっていることに気づいておらず、予定アプリの通知が来なかったら危なかった。先週の分の進捗報告は本当にみそっかすみたいな内容しかなくて、自分で振り返りながら唖然としていた。一体自分は先週何をやっていたのだろう。まあ僕のうっすい報告以外は特に何事もなく、勉強会まで終了。勉強会では思わぬところから圏の話が出てきて、その枠組みで取り扱おうという気持ちすら全然わからなかった。

健康診断のため、ライフスタイル調査というものに答えていた。食生活に関する質問で、朝昼夜のどれをよく欠食してしまいますかだとか、間食・夜食はどれくらい摂りますかとか聞かれた。これは非常に難しい。そもそも朝昼夜という枠組みで食事をしているわけではなく、お腹が空いたら食べるということを繰り返しているから。時間帯も深夜が多く、何とも言えない。食べた順番に朝昼夜か?その場合、間食は原理的に発生しなくなるが、よいか?深く考えても仕方ないと思ったので、適当に朝食にしておいた。そういえば、「朝ごはんを食べると一日元気に過ごせますよ」とは、起きてからすぐ食事すればよいという理解でいいのだろうか。

定例会が終わってから少しラノベを読んでいたのだが、あまりに眠くまともに読み進められないため、とっとと寝てしまうことにした。ただ、布団に入ってからもうっかりハーメルンを読むなどしていた。午後9時就寝。

04/19(火)

午前2時半ごろに起きていた形跡がある。午前3時にはまた二度寝できたようだ。次に、午前7時半起床。

ハーメルンで1作読了。「ディストピアゲーに転生したら行政側だった件について」。連載が始まったばかりで10話しかなく、一口サイズ。内容はかなり面白かった。ワクワクする設定が大量に散りばめられている。

syosetu.org

起きて、健康診断の予約をした。そのまましばらくパソコンを触った後外出。まず原付に乗って生協に行った。以下で言及した教科書が届いたらしいので、それとラノベ1冊を受け取り、あとはミールカードを使い切るためお菓子や飲み物を買って帰宅。またすぐ、今度は自転車に乗って街のほうに出た。

ゲーム理論の講義を取ったのだが、これは教科書が指定されていて、来週からその演習問題が課題として出るようだ。今のうちに手に入れておく必要がある。

週記(2022/04/11-2022/04/17) - kotatsugameの日記

今日はゲーセン。食事を挟んでちょうど40クレ、実に9時間ほどプレイした。アップデートで追加された新曲を埋めていた。今日はかなり上手で、低難易度を埋めていた時に初見AJを10連続で達成した。しかも初見理論値を3譜面含んでいる。特にカウントもできていないが、Lv.14までの新曲は全部99AJを出したはず。

14+はまだ埋め切れていない。頑張って初音天地開闢神話のAJを出した。レートの最高値も16.93に上がった。プレイする度に赤が増えていく。それでも99AJを達成できる精度くらいなら頻繁に出ていたのに、いざAJする時だけギリギリ足りなくなってしまって悲しい。毎回毎回アウトロが苦手で、この時も2個出して絶望していた。

時間は前後するが、午後4時半ごろに食事した。油そば。大盛300gという記述を見て、朝にパンを食べたきりだから余裕かなと思っていたのだが、僕が注文した太麺の商品は大盛が400gになるらしい。食べている最中にそのことに気づいて、一気に満腹になったような気分を味わった。何とか腹に押し込んだ。麺が硬かったので、300gも400gも体積はほとんど変わらなくて、密度の違いが表れているのだろう。

朝早く起きたので眠気もあり、疲れ果てながら帰宅。買ってきたプロテインの写真を撮ってツイートした。これまでバニラ味とココア味を食べたことがあって、バニラのほうが好みだったので大袋で購入。蓋つきの容器に入っているプロテインは300g弱で2000円ちょっとする一方、大袋だと1000gを超えるのに価格は5000円と、めちゃくちゃ安くなってびっくりしてしまった。一体なぜなのだろう。

先週、あるアカウントがABC248-Exに無限ループを延々投げ続けるということがあった。今日のこの時間にまったく同じことがVjudgeを経由して行われていた。AtCoderはノックアウト形式ではない、つまり一度ACではないとわかっても変わらず以降のテストケースを実行してくれるし、TLEは念のため後2回実行されるしで、こういう攻撃には他のコンテストサイトより弱くて大変そう。

午前10時くらいにABC248に提出するとめちゃくちゃジャッジが詰まっていて、何かと思って全体の提出を見ると、Ex問題に延々無限ループを投げ続けているアカウントがあった。

週記(2022/04/11-2022/04/17) - kotatsugameの日記

シャワーを浴びたら少し目が覚めたので、コンテストに出ることにした。午後11時半からCF #783 div.1。

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

Aは250点がつけられており、瞬殺しなければならないという意気込みで臨んだ。bはどこか1か所で必ず0になるべきなので、その位置を全探索する。すると残りは左右それぞれ貪欲で良い。一応、値があまり大きくならないことも確かめた。素直な考察で解けて安心。Bは難しい。まず考察として、総和が正にならない連続部分列は1要素ごとにバラしても損しないことがわかる。あとは総和が正になる場合。累積和を座圧してインデックスにしたセグ木があれば、1点更新区間MAXで貰うdpが計算できそうだな、しかしn\le 5\times10^5だしちょっと不安だな……と思いつつTLを見たら、なんと4secだった。これに気付いて、解法が正しいことの確信を得た。

Cは実験。まず、他の駒を飛び越えてよいのか気になったが、代わりに飛び越えた駒が移動すると考えればよいことに気づいた。左上から埋めていく枝刈り全探索を書いて回し、出力を図に書いてみると、何となく構造が見えた。左上に駒を固めて置いて、縦横の移動で行と列をある程度潰し、最後に残った長方形領域を斜めの移動で潰す。どのような置き方をしても残ったマスは(間隔の空いた)長方形みたいな形をすることになるので、この考え方は不変。残る長方形を効率よく埋めるにはできるだけ固まってくれたほうが嬉しいので、左上に駒を固めて置くのもそう決め打ってよい。駒をk個置くとすると、残った長方形は縦横n-kで、対角線の本数2(n-k)-1k以下である必要があるため、逆にk\ge \lceil(2n-1)/3\rceilとわかる。実験の範囲では、この下限が達成できているようだ。

あとは、それを満たすような構築を探る。kが奇数の場合が一番ギリギリなので、それをいろいろ試してみると、右上から左下の向きの線を2本引く感じに置けばよいことが分かった。それぞれ(k+1)/2個と(k-1)/2個で、縦横が被らない範囲で詰めて置く。kが偶数の場合は、k\leftarrow k-1の場合の構築をした後(k,k)に置けばよい。念のためn\le 1000を全部試してから提出した。

Dは当然難しい。そもそも眠気が強くなってきて、考察しながら意識を飛ばしそうになっていた。しばらく考察して、頂点の次数に着目するといい感じなことに気づく。次数は、最初の時点での偶奇により、偶数→奇数の変化の回数と奇数→偶数の変化の回数がそれぞれ固定できる。この変化が辺の両端点で一致するときにその辺を削除できる。木dpすることを考えると、変化のどちらが余っているかを状態として持つことになりそう。dpした後もう一度dfsすることで復元も可能に見える。書いて、2ペナかけ残り10分時点で通った。復元するときに操作列を連結する操作が必要になると思ってlistのマージテクを書いたのだが、うっかり片方を反転してしまう実装になっていたのが1ペナ。実際は操作列を後ろに伸ばすことしかしないので、完全に無駄な工夫だった。

4完49位で2881→2887(+6)。結果的には出てよかった。

午前2時から日記を書き始めた。途中で昔読んだハーメルンを読み返したりしつつ、午前5時くらいに切り上げて布団に移動。そこからハーメルンの更新を読み始めたが、耐えられずすぐに寝落ちした。

04/20(水)

正午くらいに起床。

そのまま布団でハーメルンを読み、1作読了。「解説の宮永さん」。原作は少しだけ読んだことがあるはず。その内容の記憶はないが、面白かった。主人公が強いので。相手の能力に対するメタの強さというのもまた一味違った無双で良かった。

syosetu.org

この作品の「読者層が似ている作品」から別のハーメルンを1作読み始めた。午後5時くらいに寝落ち。

04/21(木)

04/20 午後11時半ごろ起床。水曜日がほぼ終わってしまっている。先週木曜日、先生からグラフ理論の論文を紹介してもらって、次の次の週に少しセミナーしてくださいということを言われていた。つまりまだ1週間猶予があるわけではあるが、それにしても1週間読んでみてどんな感じだったかは言えるべきだろうし、もし手も足も出ないほど難しかったらそのことを伝える必要があるので、今週のうちにある程度読んでおかなければならなかった。ということでスマホにPDFをダウンロードし、ハーメルンと交互に読み進めていた。

午前6時に再度入眠し、午前10時に目覚ましで起床。それからもまた同じことをしていた。論文のほうは飛ばし飛ばしで1つを眺め終えた。眺めているだけでは何もわからない、というのはそれはそうとして、別に読めないわけではなさそう。ただ用語がところどころ怪しくて、少なくとも何か参照するべき教科書が必要と分かった。

午後1時に布団から脱出。とりあえず学食に行って食事し、予約していたラノベを受け取って一旦帰宅。荷物を置いて、今度は山に登った。

今週は、博士課程の留学生の方が研究していることについてセミナーしてもらうという内容。もうめちゃくちゃ大変だった。まず英語が聞き取れない。統計学の話のため語彙が全然なかったことが一番の問題じゃないだろうか。数式をいろいろ書いてもらい、ようよう理解していくような形だった。そんなことをしていたら当然発表は先に進まず、先生の指示でかなり序盤のほうで切り上げることになり、最後は線形代数に関する単純な事実を一つ確認して終わった。これについても学部時代の知識がほとんど抜けており、大変苦しんだ。

院生室に寄ると人がいたので、一緒に学食で食事し、路上で1時間ほど駄弁って帰宅。即座に布団に入り、午後8時半就寝。

04/22(金)

午前2時半起床。ハーメルンを読み続け、1作読了。「プレイしていたゲームの能力で転生するやつ」。

syosetu.org

魔法先生ネギま!」は途中まで読んだことがある。大変面白かった記憶。ではなぜ途中で止まっているかというと、その漫画が自分のものではなく、途中から自分で買う気力もなかったため。中途半端にしか内容を知らないので、二次創作を読むのを微妙にためらっていたのだが、ついに手を出してしまった。こちらもめちゃくちゃ面白かった。設定としては、オリ主が大量の別ゲーキャラの能力をネギま世界に持ち込むといういかにも地雷っぽいものである。しかし原作キャラとのバランスが良かった。オリ主が当然強い一方で、原作で強いキャラも強いままに描いてくれている。

そのあとPixiv小説やノクターンノベルズをいくつか漁り、午前8時くらいに起き上がった。YouTubeを見たりカクヨムを読んだりしていたら午前11時。学食に行って食事し、予約していたラノベを受け取って帰宅。

「個数制限なしナップサック問題の解」と言われた。

週記(2021/05/10-2021/05/16) - kotatsugameの日記

帰宅して即座に布団に倒れこむ。しばらくラノベを読んで、午後1時就寝。

04/23(土)

04/22 午後11時起床。ラノベを2冊読んだ。

1冊目、「鴉と令嬢」。面白かった。主人公が強くて嬉しい。学校では実力を隠していて、さらに嬉しい。テロリストが襲ってくるシーンがあって、1巻から隠された実力が明らかになるかと思ったが、今回は陰からのサポートにとどまった。どのタイミングでどれだけの人に実力が知れ渡るのか、以降の展開が楽しみ。またヒロインに学校で声を掛けられて目立ってしまうシーンも好み。様々なラノベで使われるだけの良さがある。

異能強度という10段階の指標が用意されていた。これの分布についてはちょっと疑問が残る。下から3段階に7割がいて、下から6段階では9割になる。一番上の段階は0.00001%らしい。正規分布の上側だけで考えれば、順に0.5\sigma1.3\sigma5.2\sigmaくらいで、間隔がよくわからない。また、上から4段階までの人間は1割もいるのに希少と言っていたのも正しくは見えない。その位置にいるヒロインに訓練の相方が見つからないという描写があったが、複数クラス合同の授業でそのレベルの人間が1人しかいないということはないだろう。ただ、冒険者ランクなどの分布に言及している作品で感覚的に正しいことを言っているものを読んだことがないので、仕方ないのかもしれない。

この作品はカクヨムコンの受賞作らしい。ということはカクヨムで探せば続きが読めるのでは?と考えてコンテストページを確認して、もとになったものを見つけた。しかし1巻分しか連載されていないようだ。残念。いや、最近こうやって見つけたネット小説に時間を吸い取られることが多かったから、そうならなくてむしろ良かったのかもしれない。ところでこの作品は書籍化に当たって改題されていて、もともとはネット小説にありがちなあらすじそのままのタイトルだったらしい。シンプルなタイトルからあらすじタイトルへの改題はよくTLで話題になっているが、逆は初めて見た気がする。知らなかっただけか。

2冊目、「俺は星間国家の悪徳領主!」5巻。相変わらず良かった。ただし何が良かったのか言語化するのが難しい。設定とキャラがめちゃくちゃ気に入っているから当然好き。仕方がないのでこの巻で好きだったシーンでも挙げておこう。やはり第七話「剣聖」とその前のバトルシーンだ。主人公が存分に無双しているのは読んでいて楽しい。

さらに別のラノベを開いて少し読んだ後、午前10時に就寝。次、午後4時半に生協の弁当を受け取るため起きて、そのあと二度寝できなかった。ハーメルンカクヨムの更新を漁っていると時間が過ぎて、午後7時くらいになって布団から出た。

食事したりちょっと日記を書いたりして、午後9時からABC249。

Monoxer Programming Contest 2022(AtCoder Beginner Contest 249) - AtCoder

Aはどう見ても短くはならないので、先にBを解いた。sedで条件を3つ書く。次にAに戻って、とりあえずC++で通すことにした。X回ループを回すのが一番簡単そう。以降もC++。Cは「ちょうど」Kであることに気づかず1WA。Dはサンプル3が合わなくてしばらく苦しんだ後、どこにも(i,j,k)が相異なるとは書かれていないことに気づいた。優しすぎ。この場合出現回数をカウントした配列cを作って、c_ic_jc_{ij}1\le i,j\le 2\times 10^5で単純に足し合わせるだけでよくなる。調和級数

Eはなかなか難しい。適当にdpを書こうとすると、Xの長さとYの長さを次元に持って、さらに遷移がO(N)になってしまう。ここで遷移をよく見ると区間加算の形で書けるため、imos法で高速化。Fは簡単で、t=1の操作を決め打って、以降のt=1の操作を全部無視した後y\lt 0の操作もできる限り無視するのが良い。後ろから計算し、無視できるyの集合を優先度付きキューで管理することでt=1の操作を全部試せる。(t_0,y_0)=(1,0)という操作を追加すると実装が簡単になる。キューの中身を正しく動かすのに失敗して1WA。

Gは難しい。しばらく考えているとA_i\times 2^{30}+B_iの基底を取ればよさそうなことがわかってきた。Aの上位bitから決めて、あるbitを入れない代わりに残りの基底をどれでも使っていい状態を計算する、というのを繰り返すことになる。最後、Aの総XORがちょうどKになる場合も別で計算しておく。カードを1枚も選ばない状態を検出するのが難しい。まず基底がN個未満だった場合は、総XORを0にできるので、答えの最小値は0になる。そうでない場合にBも含めた総XORが0になることはないので、逆にそうなったら1枚も選んでいないとわかる。判定の位置をミスしたため1回目にACした提出にはHackケースが存在するが、通った。

Exは全く分からず、7完8位。賞金が得られそうでうれしい。

コードゴルフ。AはdcでO(1)解法を書いた。Bはコンテスト中にテストケースハックで少し縮んでいた。大文字と小文字が両方出現することをチェックするとき、大文字と小文字がこの順で隣接していると決め打ってよい。「この順」というのが嘘。CはRubyだと思っていたらPerlで縮んでいた。粗探しして-1B。DはAWKで、カウントのループと答えを求めるループをまとめた。といってもループの最初のほうでカウントして、カウントが終わってから答えを求め始めるだけ。ちょっといじってループ回数を少しだけ減らし、何とかTLEの回避に成功した。以降は手付かず。

午後11時半からCGR20。

Dashboard - Codeforces Global Round 20 - Codeforces

Aはよくわからなかったのでgrundy数で解いた。解説を見たら、操作によらずゲームが終了するまでのターン数が決まるようで、確かに……という気持ちになった。Bは'B'よりも前にある1個以上の'A'と一緒に消すと考え、後ろから見て「まだ'A'とくっつけられていない'B'の個数」を管理すれば判定できる。末尾が'B'でない場合は場合分けで取り除いておく。Cはdpしそうになったが、面倒そうだったのでちゃんと考察して解いた。1回以上操作するなら最後に操作した位置で必ずa_i=a_{i+1}となるので、もともと同じ値が隣接していた位置をすべて含むように操作しなければならない。そのような位置の両端を調べて間を埋めるための操作回数を計算する。調べた値から1回も操作しなくてよい場合も検出できる。

Dは操作を、a_rの直前にa_l=a_rを挿入すると捉える。両方の数列を後ろから比較していって、異なった場合はこの操作で前から持ってきたことにするか、もしくはそこから後ろに飛ばしたことにするか。前者を優先的に使う。Eはまずh_w=1となるような最小のw=w_0を二分探索で求め、以降は行数を全探索する。行数hに対してはw=\lfloor (w_0-1)/h\rfloorとしてh_w=hであることをチェックするだけでよい。もしh_{w-1}=hだった場合、1行にまとめたときの幅がhw以下と分かってw_0\le hw\le w_0-1になってしまうから。この問題はシステスで結構落ちていて、みんなうっかりw=0でクエリを投げてしまっていたようだった。自分はh=1をスキップしていたので助かった。

F1は簡単。2点swapなので、値たちを頂点とし、操作前と操作後を辺で結んだときの連結成分数を最小にしたい。値ごとの出現回数cntを求めると、連結成分数は必ず\max cnt以上になって、これが達成可能。実装は、値ごとに出現する位置をvectorで持ち、それらの先頭1\le i\le \max cnt番目だけを取り出してループにするのが簡単だった。F2は同様の考察から連結成分数が必ずこの値であるか調べればよい。連結成分数がこれより増えるときは、必ず1つ以上の閉路が{\rm argmax}\;cntを含まないので、逆に{\rm argmax}\;cntからスタートして同じ値を2度含まない閉路だけで全部の辺を取り切れるかチェックすることになる。よく考えると、これは{\rm argmax}\;cntに接続された辺を全部削除した後のグラフがDAGであるかチェックする問題になる。

ここまで1時間もかかっておらず爆速で、F2まで通した時点では全体5位だった。その時点ですでにH問題にそれなりのsolvedが出ていたのでGを飛ばすことにした。しかし以降2時間手も足も出ず、そのまま終了。最終的にH問題は100人以上が通したため87位まで落ち、レートは2887→2868(-19)。Eのシステス落ちが結構いて少しだけ傷が浅くなった。

コンテスト中のHの考察について。010...101...のグループに分割して、左端から貪欲に繋いでいくのがよいと考えていた。ある2つを繋ぐときは、その間にあるグループを先に全部削除しておく必要があるので、繋ぐ関係が交差してはいけない。「現在末尾が01のグループが左にあるか」を持つ4状態のdpを書いてみると、遷移が足し算とminの操作によって行列とみなせる(トロピカル半環)ため、これをセグメント木なりに乗せればクエリに答えられる。しかし5ケース目で落ちたまま一生先に進めなかった。ランダムケースを書いてみるも、そもそも正しい答えを計算するのが難しい。誤った考察を元にコードを書き、ランダムケースの出力もその方法で作っていたので、当然それで落ちるわけもなかった。

正しくは0011の個数に着目して、その多いほう+1らしい。一度の操作ではそれらを最大2つ巻き込むことができるが、0000を巻き込んだ場合は残った00がくっつくので00は1個しか減らず、0011を巻き込んだ場合はどちらも1個ずつ減る、という考察で示せるようだ。考えもしなかった。

夜中、日記を書きつつハーメルンを1作読了。「とある転生者の遊興日記」。前世の知識で競馬で大儲けする話だと思ったら、あれよあれよという間に雑誌記者になっていた。物語として面白かったが、逆行転生大好き人間としては最初1、2話の雰囲気が良かった分、後半はあまり……。

syosetu.org

布団に入ってラノベを開いたら即座に寝落ちした。午前8時前のはず。

04/24(日)

午後2時半起床。布団にラノベが落ちていて焦る。特に曲がったりはしておらず、安心。食事して、午後3時からAHC010に出た。

ALGO ARTIS Programming Contest 2022(AtCoder Heuristic Contest 010) - AtCoder

とりあえずコードゴルフ0を900個出力するより10^{899}を出力するほうが短くなった。dcやbcは途中で改行されてしまい使えないため、Ruby。以降は普通に参加した。ビジュアライザが手元で動かず、Rustをアップデートした。

大まかな方針としては、外側のループと内側のループに分けるというもの。左上にある右と下に繋げられるパーツを決め打ってループを作りたい。ただし道が互いに干渉しないようにする必要がある。そこで、スタート位置からi-jが一定になるような直線で領域を切り、右上と左下からはみ出ないようなパスを作って最後に繋げることにした。パスを作るのはBFS。BFSで状態を溜めるqueueをstackにしたらよいのではないかと思っていたら、これまでの道と干渉してしまった。

何とかループを作れるようになった後は、外側と内側に分ける方法を実装する。ループを作るときに「使ってよいマス」を指定できるようにして、外側のループは端から何マス、内側のループはさらに端からもう何マス……とする。どうしてもBFSということから真ん中を通る最短距離のループを作ってしまいがちなので、手動で真ん中を通らないように指定している。これで見つかった解を出力すると411868点、スコアを計算する関数を実装してmaxを取ると2205256点に爆増した。

BFSを何とかする。とりあえずstackに置き換えて、これまでの道と干渉しないように一度踏み入ったマスは二度と使わないようなコードを書いた。もちろん「これまでの道」ではないマスも使えなくなってしまう場合があるが、しょうがない。この変更を入れると結構ループが伸び、また実行時間にも余裕が出たため探索範囲を拡大することができて、3062504点になった。

以降はループの途中を切って伸ばすための実装していたが非常に難しく、結局REが取れないままコンテスト終了。直後に正常終了するコードが書けたものの、点数は伸びていないので、おそらく実装が正しくないのだろう。55位でパフォーマンス2118、レートは1836→1910(+74)。

TLでAHC002と似ていたという話をよく見た。言われてみれば確かにそう。さらに、マス目をいくつかの区域に分割してそれぞれdfsし、適当に接続するという方針を取った人もいた。これは僕のAHC002における解法とほぼほぼ同じであり、非常に悔しい気持ちになった。分割しなくてもdfsは効くらしくて、時間を決めて回すとか、一度訪れたマスのフラグを消さないとかの方法を見聞きした。

午後9時からARC139。

AtCoder Regular Contest 139 - AtCoder

Aは簡単。先頭から条件を満たす最小の数を求めていけばよい。基本的にはA_i=\left(\lfloor A_{i-1}/2^{T_i}\rfloor+1\right)\times 2^{T_i}になる。ただこれだとサンプル4で落ちる。括弧内が奇数でなければならないことに気づき、1とbitwise ORした。

Bは難しい。kA+lB\le Nなる0\le k,lに対してNX+k(Y-AX)+l(Z-BX)の最小値を求めることになる。まずY\leftarrow \min(Y,AX)Z\leftarrow \min(Z,BX)としてよい。このときl=\lfloor(N-kA)/B\rfloorとできる。0\le k\le N/Aを全探索するのは不可能なのでもうちょっと考察が必要。NABで割ったあまりを考えてもいいんじゃないかと思って実装し提出するとWAになった。これがなぜか全然わからず、ずっと紙でいろいろ計算していた。どうしてもわからないのでランダムケースをたくさん試すと、(7,2,3,10,5,5)というケースで落ちるのを発見した。もうダメダメ。

k=k_1+k_2Bと分解する。0\le k_1\lt Bを全探索すると、k_2としては0か上限ギリギリだけ考えていいようだ。このことは、スコアがk_2の一次関数になることからわかる。探索回数は\min(N/A,B)になって、A\ge Bとなるようswapしておけばこの値は\sqrt{N}以下になることがわかる。これで解けた。

Cはめちゃくちゃ難しい。選ぶ点のどのペアも、(\pm 1,\mp 3)(\pm 1,\mp 3)で互いに移り変わらない必要がある。片方だけ考えると、幅3の棒とそこから横に生える幅1の棒みたいな領域の点集合になるようなので、これをうまくずらして重なる点をできるだけ増やすことになる。Y=1全部とX=N全部と左下の3x3正方形、を提出したらWAになった。もうちょっと重ねられるということなのでいろいろ構築方法を考えていたが、頭が爆発しそうになったので方針を変えた。

(x,y)\mapsto(3x+y,x+3y)と変換する。変換後のx'=3x+yy'=x+3yは互いに一致してはならないので、とりあえずそれぞれありうる値を列挙する。(x',y')から(x,y)を復元することができるので、(x',y')のペアを数えればよい。復元した(x,y)は整数で、かつ値の範囲の制限がある。整数であるという条件はx'\bmod 8y'\bmod 8を固定することで達成できる。値の範囲の制限については、x'y'を昇順に並べておいて、値が範囲から外れていたらその外れ方に従ってどちらかを1段階大きくするという方法で探索し、ペアを作ることにした。これで出したら通った。残り時間は5分だった。

3完101位。人生終了。

コードゴルフはA問題のみ。Aは最初に書いたdcがTLEしたのでとりあえずPerlで通しておいたが、朝方書き方を変えたdcコードを投げてみると通った。偶奇に従って値をずらす部分でmodつきpowを使うのは遅いらしい。単に2で割った余りを使うとコード長据え置きでかなりの高速化になった。オーダーレベルの改善なのでそれはそうか。

ARC-Dを通した。Cを通した後に少し考えていて、削除しなかった場合の数列を作って小さいほうからX,\dots,X+K-1番目を削除すると考えればよいだろうと思ったのだが、これはどう頑張っても計算量がO(MK^2)になる。どうしようもなくなったので解説を見た。数列の値を2値にするのは頭が良すぎる。これで、これまでdpの遷移として0\le i\le j\le Kなるi\rightarrow jを全部試さなければならなかったところを、0\rightarrow i\rightarrow Kだけにできるようになる。必要な係数については依然としてi\rightarrow jを全部試す必要があるものの、多項式の掛け算と見なして前計算することでO(MK\log K)で求まる。十分間に合うようだ。

Submission #31251400 - AtCoder Regular Contest 139

多項式の掛け算というか、f(x)^k\bmod x^{K+1}0\le k\le Mで求めることになる。f(x)フーリエ変換後を保持して、値だけk乗した後戻してもよいという話を聞いた覚えがあって、定数倍速そうに見えた。しかし合わない。いろいろ試してみて、そのようなテクを使うには最初から長さ{\rm deg}\;(f(x))\times M+1の列をフーリエ変換しておく必要があると分かった。冷静に考えると当たり前で、フーリエ変換後の値たちはf(x)^k\bmod x^{K+1}ではなくf(x)^kそのものを表現しているのだから、長さが足りないまま復元すると高次の部分だけずれてしまう。変換後の値をべき乗することで変換前の式のべき乗が求まる話は、思い出してみればbit演算系の畳み込みで聞いたはずで、そちらは列の長さが変化しないためそもそも高次の部分が出現し得ないという理屈だったと知った。

ゲーム理論の課題を提出した。火曜日に買ってきた教科書の演習問題。利得行列を見てナッシュ均衡を求める問題で、面倒なだけ。解答がすぐ後ろにあるので、それを写していないということを証明するために無理やり考え方などを書き込んでおいた。

ラノベを1冊読了。「自炊男子と女子高生」。ヒロインが大学に来たり主人公が高校に行ったりするシーンが、周囲の反応が見られて好きだった。終盤の流れとその決着も非常に良かった。一方、序盤中盤は自炊シーンがメインで、調理の描写に興味を持てずあまり楽しめなかった。

朝まで日記を書いていた。なんと今週はインターンの作業を一切行っていない。非常にまずい。寝て起きてから少しコーディングしようと考えていたのに、今から寝るともう定例会直前まで起きられないような時間になってしまった。情けないぜ。

週記(2022/04/11-2022/04/17)

04/11(月)

先週の週記を投稿した後の話。

学生証を手に入れたので、NHKの家族割引を申し込む用意が整った。書類を記入して、学生証のコピーとともに封筒に入れた。大変不快な思いをしながら作業していた。受信機器の設置日なんか知らんて。携帯買った日でも書けというのか。適当に調べた感じ、慣例的に空欄でも受理してくれているという記述をネットで見つけたので、空欄にしておいた。

現在支払っているNHKの受信料は、学生ということで家族割引が適用されている。次の4月からそれが終了してしまうというハガキが来たので、続けて適用してもらうための手続きが必要となった。

週記(2022/02/28-2022/03/06) - kotatsugameの日記

外出。気温は24℃らしい。いつの間にか通る道の脇の桜が満開を迎えており、目を楽しませるものだった。ポストに寄って書類を出し、学食に向かった。サラダにドレッシングがかかっていないと思ったら、今日から自分でかけるようになったらしい。およそ2年ぶりにドレッシングと給水機が復活しており、大変感慨深くなった。

帰宅し即座に就寝。正午だった。

午後4時半、目覚ましで起床。これはインターン先の定例会が始まる時刻である。布団から飛び起きてオンライン会議に接続した。

先週の進捗は火曜日に書いたコードのみ。いろいろ考えながら書いたので、その考えていることを含めて進捗報告のスライドを作成した。特に何事もなく勉強会まで終了。

勉強会で関数型言語の話がチラッと出てきたので、参照透過性について少し調べて、出てきた記事を読んでいた。非常に興味深い話だった。

www.timedia.co.jp

明らかに副作用を持つ入出力関数は、本当に参照透過性を満たしているのか?という疑問がある。これに対する回答は、「実はそれらのIOアクションはすべて一つの引数をとる関数の形をしていて、その引数が都度変わるので、そもそも全てが以前と同じな状態で評価されることがない」となるようだ。聞くだけならただのとんちであるが、もう一つ意味があるように思った。IOアクションの引数は何かというと、直前に実行されるべきIOアクションの戻り値(の一部)なのである。これによって、すべてのIOアクションが望む順番で実行されるということが保証される。

午後8時、外出。ゲーセンに行く。昼間はそれなりに暑かったが、夜になってちょうどいい気温に下がってきた。一年にほんの少ししかない、非常に快適な時期。

到着してから閉店まで2時間半ほどしかなかった。成果は理論値が1譜面だけ。グッズキャンペーンのポイントは15クレ分増えて、107ポイントになった。

油そばを食べて帰宅。帰り道、西公園(という名前の公園らしいことを調べて知った)の横を通った。いつも夜はスケボーのガラガラという音が非常にうるさいのだが、今日はそれに加えて人の声もかなり聞こえてきて、ただでさえ大きい物音に加えて深夜まで大声で騒ぐのはさすがに迷惑じゃないかという気持ちになった。

少しコードゴルフをした。ABC247-BがAWKで縮められていて、何かと思ったら嘘解法があったらしい。性と名をすべて混ぜてuniqueを取ったときの要素数2N-2以下ならばNo。こういうのはRakuで書いたほうが明らかに短くなるので、そうして取り返した。さらに、uniqueを取った時の要素数2N-2個ということは重複した要素が2個以上あったということなので、そちらで判定するようにして-1B。重複する要素を抜き出すメソッドは、存在こそするものの名前がrepeatedと少し長めであり、コードゴルフで効いたのはこれが初めて。

思い立ってインターンのコーディングを少し進めた。明日は久しぶりの1on1なので、それに向けて進捗を追加する。データをテキストファイルで取りまわすことにしていて、CSVファイルの形式にしようかと思っていたのだが、JavaCSVファイルを読み書きするライブラリが外部のものに頼るしかないようだった。それで、ライブラリを使わずにコーディングしている。自分で書き出したデータを自分で読み込むので、特定の形式にだけ対応できていればよい。読み込み部分を完成させて、さて本題に入るぞと意気込んでコードの形を考えていたら、眠くてうっかり意識を飛ばしてしまったので、切り上げた。1時間程度だった。

シャワーを浴びたら少し目が覚めたので、YouTubeを見たりゴルフしたりしていた。午前5時半ごろ布団に入り、少しだけカクヨムを読んで午前6時過ぎ就寝。

04/12(火)

午後0時半起床。

午後1時から1時間、1on1を行った。書いたコードの設計を説明するとメンターさんが文章にまとめてくださり、さらに何種類か別の方針を示してくださった。今の設計は、まずやりたいことがあって、それらが可能な範囲で最初に思い付いた形をコードに起こしているので、そうやって別の方針があるということすら考えていなかった。まあ、とりあえず今のところは、別方針と比較しても現在の実装が良いと思っている。今日はメンターさんが大忙しの日らしかったので、きっちり1時間で終了した。

Twitterをしていたら午後3時を回ってしまった。今日も外出しようとしていた。準備して、午後3時半ごろ出発。原付に乗ってクリーニング屋に行き、預けていたスーツ一式を受け取ってきた。そのまま学食に寄るもまだ夜の部が始まっていなかったので、購買でミールカードを使い切って、一旦帰宅。

ゲーセンに行くつもりだったのに、TLの話題に乗っかってツイートしていたら午後5時になってしまった。会社のSlackなどにおけるtimesチャンネルについての話。別に可否について議論していたわけではなく、人それぞれの使い方についてのツイートが多かった。僕もインターン先で用意してもらっていて、Twitterと同じ……とまではいかないが、メモとしてそこそこ気安く書き込んでいる。しかし最初は、わざわざ自分のために用意された場所なんだから何か書き込んだほうがいいだろうという義務感を元に使用していた気がする。そういう風に、自分がいわば「主人公」である場所であるというのが、今感じている気安さの正体だと考えた。

いい加減切り上げて出発。そういえば、昨日の真夜中に西公園から大声が聞こえてきたのは、今が花見の最盛期だかららしい。試しにちょっと寄ってみて、写真を撮った。

f:id:kotatsugame:20220413055516j:plain
西公園の桜

イオンの地下のフードコートで食事している最中、chokudaiさんからリプライが来た。今日の午後8時からのあーだこーだーにゲストとして来られないかとのこと。直前に連絡することになってしまったからか、今日ではなく再来週でも大丈夫だと言って頂いた。今日は思いっきりゲーセンで遊ぶつもりなので、お言葉に甘えてパスさせてもらった。というわけで、僕が登場するあーだこーだーは再来週の火曜日、04/26になりそうだ。それまでに少しアーカイブを見てどんな感じか把握しておきたい。

chokudaiさんからリプライが届いていた。僕をあーだこーだーのゲストとして呼んでほしいという希望が来たらしい。chokudaiさんもリプライしてくるぐらいだから乗り気なのだろう。僕ももちろん悪い気はしないため可能であるとの返事をした。結構すぐになりそう。

週記(2022/03/28-2022/04/03) - kotatsugameの日記

ゲーセン。午後6時前から閉店まで遊んだ。グッズキャンペーンのポイントは29クレ分増えて136ポイント、何とか目標の120ポイントを溜めることができた。今日はひたすら低難易度の譜面の理論値埋めをして、Lv.11で2譜面、Lv.11+で8譜面、Lv.12+で1譜面の合計11譜面出せた。かなり調子が良かった。12+の理論値のツイートだけ貼っておこう。

最後のクレでは3連続でIMPACTをプレイした。1トラック目で6-1-0などという信じられないスコアが出たので、何とかAJを捻り出したいと思っての選曲。2トラック目は11-0-1。

祈るように3トラック目をプレイし、最後の最後までAJで通ったのに、ラストの黄タップトリルが抜けてさすがに変な声が出た。3244ノーツの譜面で3241コンボってなんだよ。精度もどんどん悪くなっていて厳しい。

立ち食いそば屋で食事して帰宅。帰り道でも西公園の桜を撮ってきた。屋台こそ閉まっているもののまだ花見客がいた。これが昨日のうるさかった声の真相か。

f:id:kotatsugame:20220413061038j:plain
西公園の桜(夜)

日付が変わったあたりで帰宅。YouTubeで今日行われたチュウニズム公式の生放送を飛ばし飛ばし視聴した。

atgolferのコードが置いてあるGitHubリポジトリの管理者が僕になったので、Twitterのatgolferアカウントのbioを修正した。kotatsugameというユーザ名が長すぎて、GitHubリンクが省略されて表示されてしまう。しかもその状態で再度bioを変更→保存すると、省略された部分を示す「…」がURLの一部になってしまうようで、リンクが切れる。大変面倒であった。その更新ついでに、botであることを示すラベルの設定もした。

GitHub - kotatsugame/atgolfer

朝まで日記を書いていた。コードゴルフのことを書くために提出を確認しているときに、bashコマンドfmt -1というのを知った。幅1を指定してフォーマットすることで、空白区切りだったり改行区切りだったりする入力を、改行区切りに統一できるらしい。これはtr ' ' '\n'の完全上位互換である。空白区切りを改行区切りに直すというのは至る所で必要になる処理で、他にもdc -e?ffactorによる方法が存在し、前者もまた順番こそ変わるものの1B縮む。factorは行の後ろに大量のゴミがつく、dcは遅い、と汎用的な短い書き方がなく、これまで大変だったのだ。革命的。しかし探し方が悪いのかあまり効くコードが見つからなかった。

atcoder.jp

ECR126Fを通した。当日のTLで解法を知ってしまっていた。コストの変化の種類数が少ないことではなく、変化が単調であることに注目すべきだったらしい。「変化がd\le -1)以下だった場合に使う」と決めると、区間ごとに二分探索することで変化を全通り生成せずともどれだけテレポーターを追加するか計算できる。あとはdも二分探索すればよい。最後に増やしすぎたテレポーターを減らすときは、1つ減らすごとにちょうど-dだけコストが増えると考えられる。二分探索の条件から、コストの変化がd-1以下のものを解消する前に総コストがギリギリになるからだ。

https://codeforces.com/contest/1661/submission/153499691

布団に入って2時間半ほどカクヨムを読み、午前10時半就寝。

04/13(水)

午後5時起床。パンを食べて即座にCFのICPCミラーに出た。5時間コンテスト、ソロ。

Dashboard - 2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) - Codeforces

最初AとBを読んで解けんなあと言っていた。別の問題にぽつぽつsolvedが出てきたので、以降はそれに従って解いた。

まずC。こういう3点を連結にする道を作るには、どこか合流する1点を決め打って、そこから3点にそれぞれ最短経路で行くのが良い。今回もその方針で考えてみると、合流する1点としてはX座標とY座標それぞれ3点の中央値となるような点にするのが最適に見える。出したら通った。後からTLを見て気づいたことだが、これで総距離が\max x-\min x+\max y-\min yとなり、明らかに最小。Dは後ろから見るだけ。

Lはちょっと悩んだ。終点が決まっていれば流量2を流せるかチェックする蟻本のやつに落ちるが、今は関係ない。最初無向グラフだと思っていて、dfs木を取って後退辺を探せばよいかなと思っていた。実際は有向グラフ。次に、適当にBFSして、初めて同じ頂点に2回たどり着いた瞬間2通りの経路が得られたと判定することにした。これはサンプル2で落ちて、途中から分岐するタイプの経路に対応できない。ここで閃いて、始点の次の頂点がどこだったか覚えておくようにした。これが同じだったら、後から来たほうは無視してよい。違った場合にやっと2通りの経路を復元する。これで通った。なかなか面白い。無視してよいことを正確に説明するのはちょっと難しい。無視が起こった頂点の先で初めてぶつかるような経路は、それ以前の両方の経路と一切ぶつからないから、という理由になるだろうか。

Jは頂点を好き勝手並べ替えてよいと誤読していた。実は元の順番を保っている必要があるらしい。そこで、区間内のどの頂点をその部分木の根にするか決める区間dpで解いた。部分木の外に行くようなコストの和を2次元累積和で求めることで、辺ごとにそこを通る必要があるペアのコストの和を足していける。

Fは難しかった。偶数番目に何を置くかを後ろから決めつつ、余ったブロックを間のどこに配置するか掛けながらdp遷移を行う。dpの添え字は、ブロックが置けるにも関わらずまだ置かれていない位置の個数とした。n番目のブロックは一意に定まるので、最初にそれを配置して、あとは(n-2,n-1)(n-4,n-3)とペアにして考えていく。ブロックの出現回数を番号の降順に見て、位置n-4にブロックを配置したら次のループから位置n-3が使えるようになる、という具合。ただこう分けると、位置1を使えるタイミングがよくわからなくなる。しばらく考えて、これまで見たブロックの数と今の空きスペースを足しnと比較することで、直前に位置2にブロックが置かれたか否かが判定できると分かった。

Iはすんなり行った。角を2か所聞くことで、r_1+r_2c_1+c_2がわかる。また、r_1\le r_2とした場合に(r_1,r_2)を定められるような辺上の位置があるようなので、全探索で探して聞いた。(c_1,c_2)についても同様にして、これで、4回のクエリでrの候補2つ、cの候補2つが決定できる。組み合わせ4通りに対しここから3手しか使えないが、実は十分で、最初に試したものが成功するか失敗するかで一意に定まる。

Eはsolvedが少なく怯んでいたが、考えてみるとすんなり行った。まず、区間幅の最小値を最大化してよい。これが最大でないような解は、そのとき幅が最短の区間を必ず伸ばすことができる。伸ばすことができない場合は家の位置がギリギリということになって、区間幅の最小値の最大値を達成できなくなるから。ということで最初に二分探索でこの値を求めると、あとはもう一回二分探索して区間幅の最大値の最小値を求めることで答えが出る。復元も二分探索のチェックを逆にやる感じでできる。ペナが出て絶望するも、単純なミスを直したら通ってハッピー。

ここで崖に突き当たった。残りの問題はどれもsolvedが1とか2の問題しかなく、困る。とりあえず全部眺めて、一番筋力で解決できそうだったGに挑戦した。まず、水面上に出ている三角形の面積は、三角形全体の面積を求め、Z座標から出せる高さの比率を相似比として、その2乗倍することで出せる。言い換えれば、面積はZ座標の2次式で表せる(正確には、この2次式はZ座標の範囲によって最大3回変化する)。これがおそらくメインの考察で、あとは水面が下がっていく過程をシミュレートし、連結になった面をUFでつないで、連結成分ごとに面積の式を足していけばよい。隣接する面が連結になるタイミングは、共有している辺の端点の片方が水面上に出た瞬間である。実装して投げるとWAで絶望したが、念のためdoubleをlong doubleに投げたら通ってひっくり返った。全体3チーム目のAC。横着して3次元座標と2次式を同じ構造体で表したりしている。

残り時間はHを考えていて、サンプルも合わせられず終了。8完9位、ソロでは3位。

atgolferの更新を眺めていたら、C++コードゴルフに新手が出ていた。ACLmodintを出力する際には、printfに変数を直接渡せばよいらしい。確かに、modintのメモリ上の位置と内部で持っている整数の位置は全く同じだから、納得できないこともない。型検査で弾かれないのは、コンパイル時にフォーマット文字列の解析をしていないからか。cout<<x.val()printf("%d",x)よりも短いが、これがstd::cout<<x.val()になると縮むようになる。

明日は山に登ってセミナーをする。指導教員に今セメスターの一週間の予定を教える必要がありそうなので、履修科目を決めなければならない。院生は必要な単位数こそ少ないものの、頑張って1年生のうちにあらかた取っておくのが普通らしい。数学専攻向けの講義には目ぼしいものがなかったので、別のところに目を向けた。「学際高等研究教育院」という支援機関みたいなものがあって、指定科目から6単位以上取得するという条件を満たした学生から選抜して奨学金を与えるシステムらしいのだが、この指定科目には様々な研究科の講義が含まれており、受講するだけなら誰でもできるようだ。ここからいくつか選ぶことにした。

2つほど気になる講義を見つけたが、片方はシラバスにClassroomのコードが書かれておらず、諦めた。とりあえずもう片方を履修登録して、Classroomにも入っておく。と、すでに期限が過ぎた課題を見つけた。今週分のようだ。遅れると1日ごとに点数が引かれていくシステムだったので、慌てて提出しておいた。

海外の人から競プロのコーチをしてくれとDMが来た。……これだけだとよくある話なので、なぜ日記に書くに至ったかの背景を説明しよう。まず、日記にもツイートにもほぼ書いてこなかったが、この人とは昨年の7月からDMでやり取りをしていた。向こうが競プロの問題に関する質問をして、僕が答えるというもの。CFでもメッセージに質問が来たら答えるようにしているので、同様の対応。ただし向こうは僕のパーソナリティにも興味があったらしくて、急に年齢を聞いたりしてきたので、競プロの問題に関する質問以外はDMをしてくるなと言っておいた。こちらは質問自体に興味があるのであって、質問者には興味がないのだ。

「競プロのコーチになってくれないか?」というメッセージは、この制限を逸脱している。実は以前にも何度か同様のメッセージが来ていて、最初は「AtCoder ProblemsのRecommendationを解け」と真っ当なアドバイスをしたのだが、レートが伸び悩んでいるとかいう理由で繰り返しやって来るので、だんだん断りの口調も強くなっていった。今日は「二度とそのようなメッセージを送ってくるな」と返した。すると、「コーチの意味について勘違いしているのではないか」と返ってきた。向こうはこれが競プロの問題に関する質問だと思っているらしい。

ここで僕も自分の基準がどこにあるのか再確認した。つまるところ、主体的に相手に何かを与えるつもりがないのだ。「あなたに質問の答え以外を与えることはない」と言ってみると、今度は「なぜ怒っているのか」ときた。決まっている。この人が何度も何度も何度も何度も質問以外のメッセージを送ってきたからだ。今になって、適当なタイミングでブロックしておけばよかったと後悔している。

さらに少しやり取りして、何とか僕がその人の競プロ能力だったり精進に興味がないことをわかってもらえた。するとまだ「自分がもっと強くなったら興味を持ってくれるだろう」ととぼけたことを言っている。そういうことじゃないんだよな。この人がもっと強くなったら、僕が答えられるような質問はなくなって、それで関係は終わりである。また急に「自分はbotではない」とも言いだしたので、「自分にとっては質問を送ってくるbotと何も変わらない」と返したら、もう会話を続けたくなくなったと言い残して、今度こそ関係が切れた。

以上のことは、僕がこの人とのDMを振り返ってまとめた所感であり、DMという性質上この文章を読んでいる人にはほかの情報源がないので、一方的に印象を貶めることになるのかもしれない。まあ日記ってそういうものか。嫌いなものは、嫌いだ。もうちょっと毒を吐きたい。レートが伸びないからって急にメンヘラみたいなメッセージを送ってくるな。それは個人のモチベーションの問題に還元されて、本当に全然全く完璧に興味がない。

そもそも、別にこの人に限らず僕がコーチをすることはない。本来競プロというものは一人でプレイするゲームだと思っていて、知の高速道路が急速に整備されている現在、一人ですら強くなれない人間が僕に師事したところで何も変わらないはずだし、何も変わらないべきであるとすら信じている。また、僕の競プロ人生においては「精進しているならば強くなっている」が常に真だったので、それなりに多く問題を解いているようだったこの人のレートが伸びないのは、僕にとっては全く意味が分からないため、どう頑張ってもまともなアドバイスは出ない。

もう朝。明日のセミナーで発表する内容の準備を始めた。先週も書いたようにSWAGと、その前振りとして適切かは微妙だが累積和について話そうと思う。紙に喋る内容をまとめておいた。一応、実装例も用意しておく。先週は純粋関数型言語が話題に出ていたので、HaskellでSWAGを実装することにした。TLEが出て絶望するも、入出力高速化で通ってくれた。

#753694 (Haskell) No.1036 Make One With GCD 2 - yukicoder

セミナーを行うことになった。自分が取り組んだことをちょっと準備して説明する。院試の面接のときに取り上げようとしたSliding Window Aggregationについて話そうと思っている。

週記(2022/04/04-2022/04/10) - kotatsugameの日記

午前7時になって一部のゲーセンが開店し、チュウニズムのバージョンアップ情報が流れてきた。いつもの定数変動で、今回はLv.14+からLv.15への昇格が2譜面。「Contrapasso -inferno-」と「otorii INNOVATED -[i]3-」。このうち前者はSSS達成していたため、この昇格でLv.15の初SSSが出たことになる。これまでは、自分がLv.15でSSS出せるとは思えず腰が引けていた部分があるため、これをきっかけに他の譜面でも戦えるよう頑張りたい。

布団に入って少しハーメルンを読み、午前9時就寝。

04/14(木)

正午あたりに起床。寝坊が怖くて二度寝できず、2時間ほど布団でグダグダしていた。

起き上がって、もうちょっと履修を考えてみた。昨日からさらに2つ増やして、学際高等研究教育院の指定科目からは3つの講義を受講することに決めた。履修のためには教務課に書類を提出する必要がある。そんなことをしていると結構ギリギリの時間になったので、山に登る。雨が降っているので地下鉄を使いたかったが、それだと間に合わないかもと思ったので、カッパを着て原付を出した。

何とかちょっと前に到着するも、コンビニでパンを買い込んだり教務課で履修申請の書類を貰ったりしていたら予定の時刻になってしまった。ここで同じ担当教員についた人から連絡が来て、先生が研究室にいないことを教えてもらった。とりあえず合流してどうするか考える。僕は食事がまだだったので、買ってきたパンを食べながらしばらく履修について話していた。食べ終わったあたりで先生から、時間を間違えているのではないかとメールが来ていたのに気づく。どうやら集合場所が研究室ではないようだ。では、どこか。

先ほどのメールには肝心の場所が書かれていなかった。これについては確か、事前に先生がメールを送ってくださることになっていたはずで、それがなかったので今回は僕らのミスではないはず。仕方ないので探し歩くことにして、とりあえず1階下の教室を覗くとすぐ見つかった。僕らのミスでないと思っているとは言え、謝り倒しながら入室。留学生の方もいて突然英会話が始まり、聞き取りに失敗しまくって大変だった。

セミナー。僕の発表は、1時間の予定だったところを20分くらいオーバーしてしまった。SWAGの導入もStackからQueueを作る手順を元にして話そうと思っていたのに、焦って天下り的に与えようとしたせいでかなり不自然な説明になってしまった気がする。しかしその分、前半のアルゴリズム・考察の説明は手厚くできたつもりなので、そこは満足している。もう一人の発表も、記号の定義などを念入りにやってもらった結果終盤時間が足りなくなっていたが、そちらはバッサリ見切りをつけることで見事時間内に収めていて上手かった。また、発表と発表の間に休憩時間を取ってもらい、その間に履修申請の書類を記入し、走って教務課に行って提出した。

学食で食事し、午後8時前に帰宅。パソコンの前に座ってみるも凄まじい眠気に襲われ、たまらず布団に移動して寝落ちした。午後8時半から午前0時まで寝ていた。

起きてからしばらく、もう一度寝ようか迷いながら布団でスマホを弄っていた。TLにめちゃくちゃバズっているツイートが流れてきた。投稿から1時間も経っていないのに、すでに4万いいねくらいついている。実際に信じられないくらい面白かったので貼っておこう。

セミナーで先生から貰ってきた問題が非常に競プロチックで面白そうだったので、しばらく考えていた。小さいケースだけでも解けないかという話だったので、それに狙いを絞って考えてみると、無事解決できた。あまり具体的なことは言わないほうが安全だろう。答えが綺麗な形になったので、何か特別な解釈があるのかと思ったけれど、僕の採ったアプローチでは特にそれらしいものは見えてこなかった。

水曜日のコンテストのeditorialが出ていたので、K問題を解説ACした。冷静になるとコンテスト中はこの問題をほとんど考えていなかったので、精進としての効果は薄そう。頂点を3種類に分割して最小カットみたいなものを求めたいとき、頂点を倍加して適当に割り当てることでうまく重みを対応付けられるらしい。こういう方法があると知れただけでも良かったか。ただ、そうやって2000頂点4000辺くらいのグラフを作って最大流を流した時、高速に動作する正当性がよくわからない。出したら15msで通ってはいる。

https://codeforces.com/contest/1666/submission/153673254

すでに朝になっている。途中にゴミ出しやコードゴルフを挟みつつ、寝るまでカクヨムを読んでいた。午前10時半就寝。

04/15(金)

午後11時起床。たっぷり寝られた。このままもう一度寝て金曜日をスキップするか迷いながらゴロゴロし続け、午前2時にようやく起き上がった。

履修が確定したので、今週分として出ていた課題を片付ける。ゲーム理論の講義を取ったのだが、これは教科書が指定されていて、来週からその演習問題が課題として出るようだ。今のうちに手に入れておく必要がある。その本を生協で注文するついでに、新刊のラノベもチェックした。4月下旬から1月分ほどの新刊をチェックして、20冊予約した。ところで4月買った本は全然読めておらず非常にまずい。代わりにカクヨムに全てを吸い取られている。カクヨムは今月読んだ文字数を勝手にカウントしてくれるようで、見るとすでに200万文字を突破していた。

午前5時過ぎからTCB46に参加した。-167pt。例によって今週日曜日終了なので、ここに各問題の感想を書く。

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

4問目から難しい。初手がすぐに出ず、しばらく適当な値を入れて計算するという謎の作業をしていた。解法は、期待値をpqを用いて表し、qを変化させても期待値が変わらないようなpと、pを変化させても期待値が変わらないようなqをそれぞれ求めるというもの。問題文によれば求めるpqはそのような性質を持つらしいが、あまり正当性がわからなかった。ゲームといいつつ2人が同時に行動している感じだから単純に最大・最小を考えることはできなくて、期待値が均衡する点はこのように求めなければならないのかもしれない。さらに、そのようなpqが一意に定まるのは式の形からわかる。この問題は14分かかって-8pt。

6問目もかなり神経を使った。まず作れる個数が\lceil N/M\rceilになって、この値が1なら余りを取る操作は行わない。2以上なら最初に1回だけ余りを取る操作を行い、1\dots(N\bmod M)\lceil N/M\rceil個存在するようになるので、Kに一番近いものをずらして合わせる。ただしN\bmod M0の場合は0\dots M-1がすべて\lceil N/M\rceil個存在するようになる。11分かかったが何とか減点なしに。

7問目は大変だった。p+n\le Nに対して\binom{N}{p+n}\binom{p+n}{p}\binom{U-1}{p-1}\binom{D-1}{n-1}を足し合わせることになる。ただし\binom{-1}{-1}=1とする。適当にバラすと畳み込める形になるので解けた!と早とちりするも、残念ながら\bmod 10^9+7なのでそう簡単にはいかない。convolution_llでもオーバーフローするようだ。そこで、自分のライブラリから任意mod NTTを引っ張り出してきた。modを変えて3回NTTを行い、garnerで復元するやつ。ACLも多分同じようなことをしているはずだが、64bitどころか3つのmodの積未満までは正確に復元できる。その上限は64bitより大きく、今回のように最大(10^9+7-1)^2\times 10^5なら十分。しかしこれで手元では合ったのに、TCBのページでテストすると落ちた。次に書くように、これは僕のライブラリの設計と運用が絶妙に噛み合ったとんでもないバグだった。修正も含めて28分かかり、-14pt。

自作のcombinationクラスは、階乗とその逆元を前計算することで、組み合わせの記号3種類と階乗そのものを定数時間で計算してくれる。この定数時間とはならし定数時間であり、vectorのように大きな引数が来たら倍々で前計算の列を伸ばしていくことで、事前に前計算する最大値を指定しなくても動くようになっている。ここで階乗の逆元は関数の形で提供していないため、ほしい場合は内部のvectorに自分でアクセスして拾ってきていた。今回もそうしていたのだが、すぐ近くで組み合わせの関数も呼び出し、掛け合わせるようなコードを書いていたのがバグの原因。組み合わせの関数内で前計算の列が伸びたとき、式の評価順によってはアクセスしていたvectorが別の位置に移動されてしまい、メモリに残された変な値を読んでしまうことがあるようだ。これを受けて、ライブラリに階乗の逆元を返す関数を実装した。

8問目はよくわからない。そもそもこのゲームが終了することすらすぐには分からなかった。冷静になると、2人が操作するごとに(X-Y)\bmod N1減らせるので、そう。これが分かったので、最初8手程度を全探索して細かい場合分けを無視し、残りを(X-Y)\bmod Nとするコードを書いた。しかしサンプルで落ちる。どうやらNが奇数の場合、FULくんは\lfloor N/2\rfloorの移動を2回行うことによってY\leftarrow Y-1ができ、これが効いてくるようだ。必死にそれっぽい式を書いたり適当に実験したりして何とかサンプルを合わせ提出するも、1ケース落ちてしまった。もうちょっと考えてより複雑な式を書いたりしたのだが、WAが取れない。

最終的にすべての0\le d\lt Nに対して(X,Y)=(0,d)の場合の答えを求めてくれるような実験コードを書き、そこからエスパーして求めた。Nが偶数である場合は1種類、Nが奇数の場合はN\bmod 3で3種類に分岐するようだ。答えの最大値が\lfloor N/3\rfloorになっていたので、N\bmod 3に注目する発想はすぐ出た。最初からこうしておけば……。3時間弱と3ペナで-66pt。

9問目は最初O(N^3)のコードを書いて高速化しようとしていた。そのままだと11secで、グラフ系の問題はベクトル化も効きづらいため絶望的。しばらくして諦め、ようやく真面目に考え始めた。FULくんは常にTechちゃんに近づくように移動するべきである。よって、2人がいる頂点の組(u,v)と、そこから2人それぞれの移動を1手ずつシミュレートした遷移先の組は、Techちゃんの移動の種類数に等しくなって全体でO(N^2)個しか存在しない。その移動を有向辺として作ったグラフはO(N^2)頂点O(N^2)辺であり、しかもゲームが常に終了するのでDAGとなり、トポロジカルソートの逆順で期待値が求まる。実装時はvからuに1歩進んだ頂点をO(\log N)かけて求めてしまったので4secくらいかかっているが、一発で通った。最初の迷走が高くついて40分強、-23pt。

10問目は面白かった。よくある、端で跳ね返る代わりにそのまま突き抜けて反転した長方形に突入すると考えるやつに見える。ただし跳ね返り方が特殊。まず、角に当たるまで縦・横の壁を何回通過するか求めた。これは回数を変数にして時刻の等式を立て、拡張ユークリッドの互除法で解けばよい。そのあと、跳ね返り方について考える。奇数回目の跳ね返りの度に長方形が反転するので、縦横それぞれの跳ね返り方について、それが奇数回目の跳ね返りであるものの個数を求めたい。反転回数を求めたいのだから個数の偶奇さえ分かればよいので、何回目の跳ね返りかの和を求めることにする。

最後以外同時に跳ね返ることがないため、各跳ね返りについて、それより前に起こった跳ね返りの回数が求まれば良い。X軸方向でk回目の跳ね返りは、X軸方向にkHだけ進んだとき、つまり時刻\frac{kH-S_x}{a_0}に起こる。このように各跳ね返りの時刻の式がわかるため、それより前にY軸方向で何度跳ね返ったかを時刻を比較することで求めることができる。具体的にはkの1次式を定数で切り捨て除算した形になるので、すべてについての和を求めるのにfloor_sumが使える。さらに同じX軸方向の跳ね返りを考慮に入れることで、求めたかった和が手に入る。1時間強かかり、さらにうっかりミスで1ペナつけて-56pt。ペナではassertによるREが出て、再現するケースも小さい範囲のランダム生成で見つかったので、それの解消を目標にデバッグすればよくかなりやりやすかった。assertの威力を体感。

終わって午前11時半。そこから食事して、TCBについてのみ日記を書き、就寝したのが午後1時半だった。

04/16(土)

午後5時くらいに、今度こそ今年度初の冷凍弁当を受け取った。また寝て、午後8時起床。シャワーを浴びたり食事したりして、午後9時からABC248に出た。

UNIQUE VISION Programming Contest 2022(AtCoder Beginner Contest 248) - AtCoder

Aは桁和を見ると短く書ける問題。Rubyで文字列のsumメソッドを使い、サンプルで定数を合わせて提出した。Bは短く書けそうで書けない問題。とりあえずC++で書いておこうと思ったらオーバーフローで1WAしてしまい、ひっくり返った。ここからもずっとC++。Cはdp。この位置にdpが置かれるのは驚き。ただ、確かにそれだけ簡単な問題である。Dは要素ごとにインデックスを集めて二分探索。

EはK=1の場合を処理した後、まずあり得る傾きを全列挙した。その後、傾きで点の位置ベクトルを正規化し、重複する個数を数えてK個以上あれば答えに加える。正規化は「割った余りを取る」操作に近い。典型操作の組み合わせなのでほとんど何も考えずに書いていたのだが、提出すると1400msくらいかかってしまった。よく見るとO(N^3\log N)で、想定解じゃなかったんだなあと思った。

Fもdp。縦2つの頂点が連結かどうかと、そこから辺が伸びているかをそれぞれ考えてみると、必要な状態を4つに絞り込むことができる。それらの間の遷移もいちいち手で求めて、コードに写した。任意modだが、何となくACLを使わず遷移ごとに手でmodを取ることにした。ただN\le 3000O(N^2)に定数倍がちょっとつくのが怖いと思って、%演算子を使うのではなくmodの値以上になったら引き算するような形で書いていたら、実装にかなり時間がかかってしまった。この日記を書いているときに出しなおしてみたら、別に普通に余りを取っても十分間に合うようだった。

Gはちょっと難しい。約数包除をしたいなと思った。すると、すべての1\le d\le 10^5に対して、d\mid A_iなる頂点iだけを考えた上で全パスの頂点数の和を求める必要がある。逆に頂点id\mid A_iである場合しか考えなくてよいので、全体でO(N\sqrt{\max A_i})個の頂点を見ることになる。約数の個数なので実際はもっと少ない。ここでTLが8secであることに気づき、実装を決意。各dに対して考えるべき頂点をvectorに持ち、先頭から舐めつつ木dpをする。グラフを毎回構築せずとも、uに到達したら隣接する各頂点vに対しd\mid A_vを満たすか判定しても良い。この判定回数が十分少ないことは、辺に注目して、一方からもう一方を見る回数を考えればわかる。パスの長さではなく頂点数を考える必要があるため木dpもちょっと難しかった。最後に包除原理……ではなく、いわゆる除原理を行うことで\gcdを固定したときの全パスの頂点数の和が出る。固定した\gcdを掛ければ答えに。

Exがちっとも分からず、残り時間はコードゴルフをしていた。7完1ペナで28位。Eは2点固定した後、傾きを求めるのではなく直接その直線に乗る点を数えればよかったらしい。

コードゴルフ。A問題は、桁和\bmod 9を求めてしまうと09が判別できない。ただし、dcでは読み込みの基数を変えられるので、10進法から外れることでまたいろいろできる。試行錯誤して、13進法で桁和\bmod 12を求め、9からその値を引くことで答えが出せることを発見した。ただし全く同じコードがコンテスト開始10分程度で提出されており、敗北。Bもdcで書いてみたが、朝になって見覚えのあるテクで縮められ残念。衰え。Cは普通にRubyで書いた後Vimに直したものが最短になっている。DもRubyで二分探索。インデックスのリストはgroup_byで見つけることにしていて、そこの改善で結構争っていた。以降は手付かず。

午後11時半からCodeChef、April Lunchtime 2022 div.1に出た。

https://www.codechef.com/LTIME107A

GCD_LCMは簡単。とりあえず、直感的にn素数で操作するとしてよさそう。その方針で考えると、X素因数分解したうちのp^eの項について、e\leftarrow \min( (e\bmod c),c-(e\bmod c))とすることができるとわかる。ここまで操作が把握できれば、n合成数として操作しても特に状況に変わりはないことが言える。

CONSTMEXはちょっと面倒。P_L\lt P_Rと固定して変化を観察してみる。元々MEXがP_L未満の部分列はどうでもよい。MEXがちょうどP_Lになる部分列が存在するなら、P[L+1\dots N]はその一例になっているはずで、とりあえずこの部分列のMEXはP_L未満である必要がある。次に、MEXがP_Lより大きかった部分列からP_Lが消えることがあるかどうか。これは部分列P[1\dots R-1]をチェックすれば十分。この部分列のMEXもP_L未満である必要がある。逆に、以上の2条件を満たせば交換可能であるとわかる。よって、まず両端からのMEXの列を求め、P_Lの昇順にカウントすることにした。Rの条件はL\lt RL\gt Rに分けて考える。BITを持って、条件を満たすようなRの位置に加算しておくことで、区間和でカウントできる。実装はちょっと大変だった。

MODCIRCはすんなり。とりあえずAはソートされているものとする。基本的にB=Aとするのが良さそう。なので、逆に\max A=A_Nから\min A=A_1までをどのように繋げるか考えればよいという話になる。残った要素は昇順に並べれば全部丸々使えるので、そこから引いてA_NA_1を繋げる一部にするときのコストを定める。つまり、iの次にjを置くコストが-A_i+(A_i\bmod A_j)となる。で、コンテスト中の僕はこの次にj\rightarrow kとするのではなく、いったんj\lt j'なるj'を挟むケースがあるのではないかと思っていた。まあ区間MINから遷移すれば対応できるかなと思いつつ、実装時にはそれをすっかり忘れてしまっていた。サンプルが合って提出直後に気づくも時すでに遅しで、しかしそのまま通った。冷静に考えれば、(-A_j+(A_j\bmod A_k))-(-A_{j'}+(A_{j'}\bmod A_k))=(A_{j'}-A_j)-( (A_{j'}\bmod A_k)-(A_j\bmod A_k))であり、(A_{j'}\bmod A_k)-(A_j\bmod A_k)\le ( (A_{j'}-A_j)\bmod A_k)\le A_{j'}-A_jとなるため、j'を挟むような遷移は得しない。

PALANDはヤバい。貰う遷移の区間dpを考えた。「あるbitが立っていない、最も近い要素」を左右で求めておくことで、bitwise ANDとして候補に挙がる高々30種類を効率的に列挙できて、さらにそれぞれについて貰ってくるべきdpの範囲もわかる。ただしその範囲は2次元の領域になっている。これを2次元BITでゴリ押してみた。O(N^2(\log N)^2\log \max A)。1回目の提出は当然TLE。手元で適当なケース(2のべき乗引く1しかない)を試すと3.5secだったので、区間が潰れているときは即座に0を返すという高速化を入れた。すると今度はWAになった。さてランダムケースでチェックするか……と思いつつ実装を進めていたら、modの値を勘違いしていたことに気づいた。修正して投げなおすとAC。1.5sec。

最後の問題は全然わからなかったため、ラスト30分はハーメルンを読んでいた。4完13位で2640→2654(+14)。途中何回か順位表を確認していたのだが、一時1ページ目の25人中15人が日本人でさすがに面白かった。

PALANDの想定解はさすがにこんなわけがなくて、遷移順を工夫することで2次元累積和を求めながら更新できるということだったらしい。また僕のコードがTLEするケースもTLに流れてきた。以下のコードで生成した入力だと手元で4.15sec。もうダメダメ。

ノクターンノベルズから1作読了。およそ一年ほど前にいろいろ読み漁っていた時の残骸がスマホのブラウザのタブに延々残り続けていて、そのうちの一つを消化したという形。今の好みではない。

https://novel18.syosetu.com/n7278ce/

日曜日は久しぶりにOpenCupもAtCoderもないので生活リズムを気にしなくてもよい。朝から昼までずっと溜めていた日記を書いていた。めちゃくちゃ集中が切れて、終盤は大部分の時間でYouTubeを見ていたようだ。午後3時までかけて水・木・金しか書けなかった。午前10時くらいにABC248に提出するとめちゃくちゃジャッジが詰まっていて、何かと思って全体の提出を見ると、Ex問題に延々無限ループを投げ続けているアカウントがあった。すぐにBANされて、朝からお疲れ様ですという気持ちになった。

布団に入り、1時間ほどカクヨムを読んで午後4時半就寝。

04/17(日)

消えた。土曜日以降の日記は月曜日の朝に書き上げて投稿した。

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

04/04(月)

午前6時半ごろ目を覚ます。僕が寝ている間にTLが盛り上がっていた。

この考えは今も持っていて、つい最近も埋め込みしたという記述を日記に残していた。言い訳じみたことを言っておけば、さすがにこれは虚無すぎたので、これ以来やっていない。この時はFastest 600問から陥落する瀬戸際で、何とか耐えようと遮二無二だった。

今日も6時間程度FastestやShortestを漁っていた。昨日mmapで取ったFastestのうちいくつかが埋め込みで取られていたので、こちらも対抗し、atcoder_testcasesから落としてきた入出力ファイルを食わせると入力の先頭を必要なだけ読んで場合分け+出力するPascalコードを生成するコードを書いた。これを使ってまたいくつかFastestを取った。

週記(2022/03/14-2022/03/20) - kotatsugameの日記

以下お気持ち表明。正直な話、このアカウントに対する印象は悪い。特にゴルフされていなかった問題で、当時最短の数百Bytesのコードを中途半端に縮めてShortestを取っていたのが強烈に印象に残っているからだ。縮めるならちゃんと1問に数時間費やす勢いで粘着してほしい。当然そのようなコードにはいくらでも縮める余地があったので、AtCoder ProblemsのListで検索して、このアカウントが最短コードを保持している問題を狙い撃ちして縮めていたこともある。最近は上に書いたようにFastestでも似たようなことを行った。

しかしまあ、そのようなことをやるにあたっては僕も既存の最短コードを参考にしていることだし、それ以外にも普段から1Bだけの更新で最短コードを取ることも多い。埋め込みもやってしまったので、完全に同じ穴の狢である。だから、このアカウントの行動を批判するということはできない。ブーメランとなってしまう。ということもあって、これまでは最短コードを奪い取ることで気晴らしをしていたわけなのだが、今TLで晒されているのを見て、本音で言えばちょっと胸がすく思いがした。

ただし、明確に悪とされることは何もやっていないことに注意しなければならない。先ほども述べたように、自分は決して批判できないのだ。そして、ひとたびこのアカウントが明確に悪とされたならば、自分もまたそうなるという危機感がある。

以下のようなツイートを昔したのだが、この言説が受け入れられると個人的には非常に都合がよい。自分の行いをかなりの部分まで正当化できるからだ。本家ゴルフ場であるanarchy golfでは、そのような改善は元になったコードを書いたユーザ名を自分のユーザ名の後に括弧でくくって付け足すという文化がある。anarchyとは言いつつかなり治安が良い。AtCoderにはそのようなリスペクトを示す方法がないので、こんなことになっていると言えなくもないか?自分にそのようなリスペクト精神が育まれているかについては、怪しい。

以上、お気持ち表明。

布団でしばらく淫夢実況を見て時間を溶かした。思ったよりたくさん投稿されており、さすがに3本くらい見たら正気に戻れて切り上げることができた。

www.nicovideo.jp

学食に行って食事。今年度初めてである。まだ入学式も終わっていないのにかなり人がいてびっくりした。大学院生になったという自覚からくる微妙なアウェー感を抱えつつ、普段と変わらないメニューを注文。ご飯の特大も通常通り提供されていて助かった。

その後生協に寄り、注文していたラノベを9冊受け取って帰宅。今日は僕の前後に1人ずつ並んでいたくらいの込み具合だったので良かったが、これから教科書販売が本格化すると考えれば、受け取りのタイミングは考える必要がありそう。

ブラックサンダーも箱買いしてきた。ブラックサンダーの箱に元からついているバーコードはブラックサンダー単品に割り当てられており、これまで箱買いするときには、レジで読み取ったそれを20倍することで対応されていた。最近、箱買いのためのバーコードが新しく用意され、シールとして貼られ始めたらしい。およそ1年半で20箱以上購入した僕のせいだろうか?それとも他に何人も箱買いした人がいたのだろうか?

帰宅してからはずっと先週の週記を書いていた。土日の分を溜めたまま、昨日は寝落ちしてしまった。週末はコンテストが多く文章量が増えがち。

午後4時半からインターン先の定例会。先週の進捗は、すでに出来上がっていたものを微調整してデプロイしただけ。あとは次に書くコードの構想を練っているという感じで発表した。構想を練っているのは嘘ではないが、実際に書き始めてみないことにはどうにも決めきれないと思ってしまったので、そちらもカスみたいな進捗しかない。

勉強会が一段落した頃合いで、書き上げてチェックまで済ませた日記を投稿した。先週はコンテスト8個に加えJOIG春合宿の問題を解いた感想も書いたのでかなり長くなり、普通に書き終わった段階で28000文字を超えていた。せっかくだから30000文字の大台に乗せようということで途中に適当に追記した後、推敲しつつ微調整を加えて、ちょうど30000文字ピッタリにしてある。

食事した後はラノベを読んだりYouTubeを見たりしていた。しばらくして、椅子の上で少し意識を飛ばしてしまったので布団に移動。なおもラノベを読み続けるつもりでいたが、眠気に耐え切れずそのまま就寝。午後10時前だった。

04/05(火)

午前3時半起床。

ラノベを1冊読了した。「Vtuberってめんどくせえ!」。面白かった。女性Vばかりの箱に主人公が男性Vとして一人だけデビューし大炎上してしまうところからスタートする。その描写は正直かなり辛かった。しかしそれにも耐えて活動を続けた結果、ハプニングなども上手く作用して主人公の人柄が知れ渡り、受け入れられていく話。終盤のデマを完全否定する配信のシーンは、主人公の訴えでコメントの流れがどんどん変わっていく様子が劇的で良かった。

このラノベはカクヨム発である。ハーメルンVtuberモノは結構チェックしていたつもりだったが、カクヨムのほうは全く見向きもしていなかった。探せば他にもいろいろあるだろうし、楽しみである。とりあえずこのラノベの続きも連載分がたくさんあるので、読んでみたいと思っている。

ゴミ出しして、午前7時半からインターン関連のコーディングを始めた。昨日言及していた構想をとりあえず形にしようと書き進めていたら、良さそうなアイディアが浮かんできたので、とりあえず実装してみた。実際の効果のほどは実データで実行してみないことには何とも言えないが、設計的には満足感がある。考えている設計をまとめて、実装できていない部分を洗い出し、また書き進めて……と繰り返していたら興が乗り、正午くらいまでコーディングを続けていた。

チュウニズムのバージョンアップ情報が流れてきた。今回は「ロシェの宝物庫」以外にマップも消えないし、削除曲も少なめで、あんまり大きな変更はないなという印象。ただこれに伴って終了するイベントがちょっと問題。

グッズプレゼントキャンペーンというのがあって、デジタルグッズのキャラクター4種類を集めておきたかった。1種類に30ポイント=30クレが必要なので、キャンペーン期間中に120クレプレイすればよい。さて今はどれくらい溜まっていたかなとチェックしてみると、直近2回スーパーノバに行った分のポイントがないことに気づいた。どうやら開店からキャンペーン終了まであまり間がないこともあって、キャンペーンの参加店舗となっていなかったらしい。ということで現在76ポイントしか溜まっていないため、バージョンアップまでの一週間ちょっとでさらに44クレプレイする必要があるようだ。2日ほど行けばよいだろうか?頑張りたい。

布団に入って、カクヨムで今朝読んだラノベの続きを読み始めた。午後2時くらいに寝落ちして、午後6時半にまた起床。明日は朝から入学式があるので、また早めに寝る必要がある。しかしカクヨムを読むのがやめられず、深夜までダラダラ読み続けてしまった。

電子レンジで4分から5分温めろと書いてある冷凍食品を食べた。万が一にも冷たいままだと困るから5分温めようと思って時間をセットしたら、見事に焦げ付いてしまった。他に同じものが2食あるので、そちらは4分でセットするようにしたい。

午前0時からSRM827があった。Stage3でTCO R4に進出が決定しているのであまり出るつもりはなかったが、せっかく起きているのだしということで参加を決めた。Appletはまだ証明書チェックに失敗していた。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19131

Easyは不快。単純な算数をさせる問題なのに、制約の上限が何もかも10^{18}になっていてオーバーフローにめちゃくちゃ気を遣う必要がある。Pythonに切り替えて解くのが一番楽なのかもしれない。1周期に解く問題数を最初に求める方針を取り、掛け算がオーバーフローしないことを割り算に変形して確かめることで解いた。チャレンジフェーズで見た解法で、まず最初に1周期以内に答えが求まるかどうか調べ、求まらなかったと分かった時初めて1周期に解く問題数を計算する方針は賢い。この場合分けを入れることで問題数がオーバーフローしないことを保証できるし、チェックと実際の答えを求めるプログラムが同じなので関数を再利用できる。

Medは謎。bit全探索した後bool値のdpをして復元するだけで、とても500点とは思えない。行数の制約が列数の制約より極端に小さいことを利用して、そちらでbit全探索を行うというのは、昔のJOIの「おせんべい」という問題で見た印象が強い。

Hardも謎。ROYGBIV1234560マッピングしてから実験すると、i番目の人は\sum_{k=0}^S\binom{S}{k}C_{i-k}\bmod 7が答えになるとわかる。これは数列Cの母関数に(1+x)^Sを掛けていると考えられる。次数|C|以上の部分はまた次数0に戻るように、つまり\bmod x^{|C|}-1で計算してよいので、二分累乗法で計算すれば長さ|C|の列をO(\log S)回畳み込めればよいことになる。愚直に書いても間に合うだろうと考えていたら微妙に間に合わず慌てた。冷静になると、扱う数の最大値が6なのだから畳み込んだ直後の配列の値も十分小さく、NTTだけで直接計算できる。SRMでは当然ACLのconvolutionは動かないので、かなり久しぶりに自作ライブラリのNTTを引っ張り出してきた。ビットシフトと加減算の優先順位について、いちいち括弧をつけないと警告が出るのが少し癇に障った。

ほかのRoomに比べ、僕がいたRoomはチャレンジでほぼ落ちず平穏だった。そのままシステスも全部通り、全完6位でレートは2613→2655(+42)。highest。今回の上位6人は全員日本人だったらしい。

SRMが終わって午前2時。そこからすぐ寝れば睡眠時間が6時間確保できたのに、再度カクヨムを読み始めてしまった。まだ大丈夫、もうちょっと、と読み進めているうちに午前7時くらいになって、このまま起きていることに決めた。

午前8時前に布団から出る。食事してシャワーを浴びたりちょっと日記を書いたりしていたらいい感じの時間になった。そこからひとしきりネクタイと格闘した結果、予定より少し遅れて午前9時過ぎに出発。地下鉄を乗り継いで会場に向かった。到着したのはギリギリの時間で、運営も急いでいたのかチェックなしでホールに入れてしまい、せっかく用意してきた合格通知書の出番がなかった。

式は30分程度で終了。感染対策も何もあったものじゃないすし詰め状態で座っていた。式の中盤くらいからスマホの回線が不安定になって、終わってホールから出るまでインターネットに接続できずかなり不安になった。外に出て自撮りした。

何とか連絡のついたたいぺーと、その友人と合流。また地下鉄に乗り、仙台駅で降りて駅ビルの地下で食事した。正午ちょっと前という時間帯でしばらく待ったのだが、ウェイティングシートに書いた名前を読み落とされて初っ端から暗雲が漂っていた。その後店に入って出てきたお冷のコップがかなり汚れていたり、ご飯茶碗の底に乾いた米粒がくっついていたり、食事と一緒に持ってくると言われたドリンクが食べ終わって店員に確認するまで出てこなかったり、かなり悪い体験をした。

眠気からゲーセンに行くのを諦め、また地下鉄に乗って帰ってきた。これから研究室に行くらしい2人と別れて帰宅。

やっと重い腰を上げて担当教員にメールを出した。特に書くことも思いつかなかったので、メールが遅れたお詫びと挨拶しか書いていない。

大学院に合格した後すぐ担当教員にメールを出している人が多く、かなり焦った。

週記(2022/03/21-2022/03/27) - kotatsugameの日記

布団に入ってちょっとカクヨムでも読もうかと思っていたら即座に寝落ちした。午後2時だった。

04/06(水)

午後7時半起床。寝る前に出したメールに返信があった。研究室に伺って自己紹介などをする日程を決める必要があるらしい。

Twitterの通知で、アカウントを作ってから9年が経過したことを知った。

午後8時にまた寝た。

04/07(木)

午前1時半起床、午前10時半までカクヨムを読み続けてまた就寝。

次に午後6時半起床。午後7時、火曜日に読んだラノベVtuberってめんどくせえ!」の続きとして最近ずっと読んでいた作品の最新話に追いついた。500話以上あってかなり時間がかかりそうだと思っていたが、1話1話が短く文字数としては130万文字ちょっとだったので、数日かかり切りになっただけで済んだ。

kakuyomu.jp

ラノベから変わらず面白かった。以降の章もずっと炎上を題材にしていたが、1巻部分とは違い主人公を擁護する側の意見が描写されることも多く、安心して読めた。その意味では主人公が受け入れられていなかった最初が一番辛かったのかもしれない。主人公は問題のある人間ではないので、話が進むにつれだんだん本人が炎上するというより巻き込まれて炎上することが多くなってきていた。

「炎上」それ自体について、初めのころのキツい描写の印象が薄れ、慣れもありなんだか軽く扱っているような感覚を得てしまったものの、実際は非常に重い話なのだと自分を戒めつつ読んでいた。メインの話はそうやって大変なことも多く描かれていた一方、間に挟まれる短編はひたすら安穏としていて、主人公たちの関係性に集中して読むことができた。

起きて担当教員からのメールに返信した。自己紹介の日程について、明日金曜日はガイダンスで山に登る用事があったので、その時ついでにできればなと思っていたのだが、メールを返信するタイミングを逃してしまった結果前日夜となり、さすがに明日の予定を今メールで知らせるのは不味かろうと思って、来週火曜日の午後でお願いした。

シャワーを浴びたりして午後8時。夜は天気が悪いらしいのでゲーセンに行くのを諦め、布団に戻って今度は「Vtuberってめんどくせえ!」の没話・零れ話集を読み始めた。午前0時頃寝落ち。

04/08(金)

午前4時起床。

少しして、昨日読み始めたカクヨムを読み終えた。誕生日配信の話が特に気に入った。誕生日という制約から短編を配置できる時期が決まり、しかしその時点での作中における仲としては進みすぎた2人を描いてしまったため没になったらしい。最新話まで読んだ以上その辺りの整合性はあまり気にならず、非常に高い糖度が大変良かった。主人公のタイミングの良さもまさにヒーローという感じで格好いい。

kakuyomu.jp

チュウニズムのバージョンアップに伴う新機能で非常にありがたいものが発表されていたのを知った。キャラクターを育てて手に入るスキルシードが筐体で確認できるというもの。これまで、目的のスキルシードを獲得できるキャラを育てる際は逐一wikiを調べて選択していたのだった。

さらにハーメルンを開いて1作読み始めた。30話弱と一口サイズだったので、午前8時半ごろに読了。「魔法科高校の煌黒龍」。

syosetu.org

良かった。クロスオーバーでやってきた主人公アルバトリオンが最強でありつつも、原作主人公の司波達也の出番があまり減っておらず、両立できている感じがする。最初数話を読んだ感じでは原作主人公を放って暴れ回るタイプの話かと思ってしまっていた。アルバトリオンが感情が薄いタイプの男性として描かれているのも良い。

布団から出てシャワーを浴びたり洗濯機を回したりしつつ、日記を少し書いた。午前10時過ぎに家を出る。今日は午後3時までゲーセンにいて、移動して午後4時から山で大学院のガイダンスに出席するという予定。まず生協に寄って食事し、クリーニング屋に卒業式・入学式で着たスーツ一式を預け、正午を少し回ったあたりでゲーセンに到着した。

今日の成果は新曲を埋めただけ。グッズキャンペーンのポイントは16クレ分増えて、92ポイント。Elemental CreationのULTIMAでSSSを出せたのはかなり驚き。低速地帯の前までで0-2出してしまい諦め気味でプレイしていたのだが、終盤は擦りも鍵盤もあり得ないくらい上手くいって耐えた。もっと上のスコアも狙えたということになり、返す返すも前半のミスが惜しい。その後も数回プレイしてみたものの、あれほど上手いプレイはもう出ないだろうということを再確認するだけに終わった。

一旦帰宅し、自転車から原付に乗り換えて山に登る。前を走るトラックに邪魔されて信号が見えず、黄色信号で交差点に突入してしまった。対面で右折待ちがおり、さらに申し訳ない気持ちになった。途中生協でラノベを受け取りつつ到着し、それからガイダンスの部屋を確認した。普段講義を受けていた数学棟でガイダンスだと思っていたのに、合同棟というちょっとよくわからない建物を指示されていたらしい。原付を停めた場所から少し歩いてようやくたどり着いた。

ガイダンスの間は眠くて目を閉じていた。就活の話をされていた記憶がある。自己紹介タイムが始まったので目が覚めた。僕の番が回ってきたので、学年と専攻分野と担当教員を述べ、あとは趣味の競技プログラミングについて少し触れた。競技プログラミングが趣味で~す、だけだとなんだか物足りなく感じたので、追加で一言考え、「4年生のときにいいところまで行ったのでモチベが消え気味」と述べた。思い返せば、モチベが消えているというよりは、他にやりたいこと(ネット小説漁り)ができたというのが正しい気がする。

ガイダンスが終わってから、自己紹介の時に見つけた僕と同じ担当教員の人に挨拶しに行った。その人は別大学から来られたようで、その関係かこれから研究室に呼び出されているらしいので、試しについて行ってみることにした。数学棟の玄関は既に施錠されており、前で同級生が何人かたむろしていたが、後ろから来ていた先生が通用口を開けてくださった。そのままトントン拍子で話が進み、2人そろって担当教員に挨拶することになった。代わりに、火曜日午後に挨拶に伺うという予定はキャンセルを申し入れた。

1時間ほどかけて、これまで学んできたことを説明したり話を聞いたりした。先生が僕らをどのように指導するかを決めるためらしい。そうすぐに決まるものでもないようで、また来週木曜日に集まって、今度はセミナーを行うことになった。自分が取り組んだことをちょっと準備して説明する。院試の面接のときに取り上げようとしたSliding Window Aggregationについて話そうと思っている。面接のときは僕のまとまっていない話ぶりがまずかったのか、それとも一人にそんな時間をかけていられないからか、かなり最初のほうで制止されてしまったので、リベンジ。

午後7時前に終了。この時間に学食の夜の部が営業していることを覚えていたので、そのまま2人で行った。すると数学科の友人がほかに数人いたので、合流してしばらく駄弁った。そういえば彼らはガイダンスのとき自己紹介していなかったなと思って聞いてみると、盛んに自己紹介していたのは教室の前のほうに座った人間ばかりで、後ろのほうはあんまりそういう雰囲気でもなかったらしい。全員分回していたらかなり時間がかかっていただろうし、それもやむなしか。

午後8時を回って帰宅。即座に布団に入り、就寝報告をする間もなく寝落ちした。午後8時半過ぎだった。

04/09(土)

午前5時頃起床。二度寝できず午前9時半までハーメルンを読んでいた。起き上がり、午前10時からGCJR1Aに出た。

https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5

1問目は文字列の先頭から考えれば、見ている文字とその直後の文字を比較することで2倍するべきか否かがわかるはず。ただ同じ文字だった場合はさらにその後ろを見ることになるので、それなら最初からランレングス圧縮しておけばよい。

2問目は2^0,2^1,\dots,2^{29}を用意しておけばよい。残り何を出力しようと、Bと混ぜて貪欲に選ぶだけで目標値との誤差を10^9未満にできるので、あとは2べきを適切に当てはめればピッタリに合わせられる。そういう証明はつけていたものの、ビビり、貪欲に選ぶ前に降順ソートした。ローカルテスターを回してみると何も言わず即座に終了してしまったので、何かエラーでもあったのかと思ってしばらくコードを眺めていた。デバッグ出力を挟んだことでちゃんとケースが実行されていることを知り、何も言わずに正常終了するのがACの合図だと気づけた。ちょっと不親切。

3問目は少し難しい。適当に貪欲を書くとサンプルで落ちる。最初から最後までつけたままの重りを取り除いて考えると、機械にセットした重りをすべて取り外すタイミングがどこかで発生する。貪欲に操作した結果のタイミングと最適なタイミングが異なっているらしい。では、そのタイミングを全探索してみるのはどうだろうか?考えてみると、こうやって分割することで元と同じ形をした2つの部分問題に分割できていると分かった。なので区間dpができそう。

適当に書くと、まず区間O(E^2)通り、その分割がそれぞれO(E)通りで、さらに計算の度に「最初から最後までつけたままの重り」を求めるのにO(EW)かかる。一番最後の共通する重りを求めるループについては、区間を決めたときにやることにしたらよいのではないかと思ったが、そうするとこれまでの分割の様子によってdpの値が変わるので答えが正しく出なかった。遅延セグメント木でEの代わりに\log Eを付けてみるも、定数倍の影響かさらに遅くなった。しばらく考えて、分割を決めるO(E)のループと共通する重りを求めるO(EW)をまとめて行うことにした。累積minを計算する感じ。これで全体O(E^3 W)になって、定数倍も6分の1くらいつく。手元では十分高速に動作したので、投げた。

1時間半ほどで解き終わり、その後は日記を書いていた。全完123位。1問目について、文字列の後ろから見るS\leftarrow\min(c+S,c+c+S)とする方法をTLで見てびっくりした。この問題の制約ならこれが一番シンプルで簡単そう。3問目は、初めにO(E^2W)かけてすべての区間に対して共通する重りの総数を前計算しておけば、分割を決めるO(E)のループだけで計算できるようになる。共通する重りが区間を広げるごとに単調に減少するので、minの差の和とminの和の差が一致するようになったと言える。

また布団に戻り、午後3時頃までハーメルンを読んで就寝。午後7時起床。今日は今年度初めての冷凍弁当が届くと思っていて、1時間おきに目覚ましをかけて深く眠らないようにしていたのだが、受け取った記憶がない。すわ寝過ごしたかと焦ってインターホンを見て、来客がなかったことを確認し、配達が来週開始であることにやっと気づいた。目覚ましのかけ損で眠い。

しばらく布団でハーメルンを読み、起きて日記を書き、午後9時からARC138に出た。

Daiwa Securities Co. Ltd. Programming Contest 2022 Spring(AtCoder Regular Contest 138) - AtCoder

Aは、ij(ただしi\le K\lt j)を入れ替えようとしたとき、最初にiK番目に持ってくることで合計j-i回の操作で達成できる。ここから1要素だけ入れ替えるので十分であるということもわかる。よって、加えてA_i\gt A_jを満たすようなペア(i,j)に対してj-iの最小値を求めればよい。何かデータ構造を使いそうになったが、冷静になれば値でソートしてjを舐めつつiの最大値を管理するので十分。Bは操作を逆から見る。操作Bは行える限り貪欲に行ってもよいことがわかるので、あとはシミュレートするだけ。かなり簡単。

Cは大きいほうから\frac N 2枚取れそうなことが直感的に分かった。証明できなかったがいかにも正しそうだったので、そのまま書くことにした。取りたいカードを+1と、取りたくないカードを-1としたとき、右からの累積和が常に-1以上になればよいとわかる。累積和と途中の最小値のペアはセグメント木に乗るので、すべてのkに対してチェックできる。

Dは謎。隣接項のXORとしてありうる数を全列挙したあと先頭から全探索するコードを書いて、小さいケースの出力を眺めていた。N=1のケースを除けば、N=KまたはKが偶数の場合明らかにNo。それ以外は構築できそうだ。特に、隣接項のXORを取ってみると1個おきに2^K-1が出現しているので、かなり規則性がある。それらを取り除くとより小さいケースに帰着できそうだったので、何とか法則性を見つけようと格闘していた。残り1時間になったくらいで少し手詰まりになり、順位表を確認すると、もう100人以上に解かれていてひっくり返る。そこでふと、先ほど書いた全探索のコードが一瞬で答えを出してきたのが気になった。試しに大きなケースで試してみると、再帰が深すぎて手元ではセグフォしたものの、コードテストでは相変わらず爆速で終了する。慌てて提出したら50msちょっとで通った。

残り時間はE問題を考えていた。1\dots A_{i_1}-1の決め方とそれ以降の決め方で分けてdpするのだと思い、前者はO(N^2)になったものの、後者がO(N^2K)から落ちずコンテスト終了。ノーペナ4完で78位だった。Cの証明は、全体の和が0であることを考えると、累積和Sが最小になる点からスタートすることでS\rightarrow S-\min S\ge 0になることからわかる。

A問題だけ適当にRubyコードゴルフして、午後11時半からECR126に出た。

Dashboard - Educational Codeforces Round 126 (Rated for Div. 2) - Codeforces

Aは直前をswapしたかを持ってdp。Bは32768=2^{15}なので2進数で考えようと思ったが面倒。0から操作を逆向きに行うBFSができるので、それで最初に全通りの答えを求めて解いた。Cはそろえる高さを\max h\max h+1両方試せば十分。高さを揃えるときは、とりあえず貪欲に2を足してみて、あとから回数を調節すればよい。Dは後ろから見れば貪欲に取ってよいとわかる。前からではできない。加算する値とその差分を管理することで、データ構造を持ち出さずともシミュレートが行える。先頭k項は直接見て、\max\lceil (b_i-a_i)/i\rceilを答えに足す。Eはセグ木。区間に対して両端の情報、具体的には端のどのマスとどのマスが連結であるかの情報を持つとマージできる。マージ関数は気合い。迂回して連結になるようなケースを間違いなく処理するためにはUFを持ち出すのが安全。ただマージ関数内でいちいちUFの初期化などしていてもよいかかなり不安だった。何とか600msちょっとで通った。

Fは解けなかった。長さl区間をテレポーターでk個に分割すると、そこを抜けるのにq=\lfloor l/k\rfloorとしてq^2\times(l-(l\bmod k))+(q+1)^2\times(l\bmod k)だけコストがかかる。kを動かしてこのコストの変化をみると、qが一定の間は変化も一定であることに気づいた。そこで、各区間に対して商列挙を行い、変化が大きいところから取っていくようなコードを書いた。しかし35ケース目でMLEやTLEが出てしまい、結局通せなかった。それもそうで、長さ\sqrt N程度の区間\sqrt N個ある場合、全部商列挙すると合計O(N^{3/4})になってしまう。正解は、コストの変化をどこまで使うかで二分探索することらしい。

5完までは速かったし、Fはあまり解かれなかったので18位。

そこから朝までは淫夢実況を見つつ日記を書いていた。午前8時頃、切り上げて布団に入りカクヨムを読み始めた。途中で今日のARC-Eが解けた気になって、起き上がって実装してみたものの全然計算量が落ちていなかったため、記録としてTLE解を提出しておき、また布団に戻った。午前11時過ぎに寝落ち。

04/10(日)

午後4時半起床。午後5時からOpenCupで、シャワーを浴びていたら数分遅れてしまった。

チームではAJDBCFGをこの順に解いた。僕はADBの考察と実装をした。

最初、少し遅れてAを読み始めた。見た目は厳ついが、よく見ると問題文の状況にかなり制限があって考えやすいことに気づく。適当に考察しつつ順位表を見るとどんどん通されていたので、慌てて書き始めた。一発で通った。次にJが解かれていて、これはチームメイトが考察して書いたもののTLEが出ていた。そこから1時間くらい格闘して通ったらしい。

その間、僕はCを考え、諦め、Dに進んでいた。順位表で大量にペナがついていたので、慎重に考察したつもり。n\ge 3頂点の単純グラフであって、頂点1\dots kは次数がちょうど1、それ以外は次数が2以上であり、グラフの直径が2以下であるようなもののうち辺の数が最小のものを構築せよという問題。k\ge 1の場合は簡単で、ウニグラフにならざるを得ないので、残りは次数の条件を満たすように置くだけ。k=nまたはk=n-2の場合はその条件を満たせないため、作れない。

k=0の場合が難しかった。n\le 5では大きなループを作るのが最適なので、n\ge 6でもそこに対角線を張ることで構築するのかなと思った。しかしn\ge 7ではウニグラフに辺を追加する方法が安上がりなようだ。n=6では辺の数が8本で一致したので、そのあたりで処理を切り替えることにした。しかしこれを投げるとWA。n=6でしばらくいろいろグラフを作っていると、なんと7本で構築することに成功してしまった。5頂点のループ1-2-3-4-5-11-63-6を足すというもの。この調子でn=7も減るかと思ったがそんなことはなかったので、とりあえずこのケースだけ対応して投げなおしてみたら、通った。パズル。

次にBを読んだ。頂点数がn\times 2^mで各頂点から辺が高々mn+m+2本出ているグラフで、全点対間最短距離を求めるという問題。しかしさすがに辺数はもっと減る。最悪ケースが思いつかないので、PCも空いていることだし実装してしまうことにした。実装して適当なケースを試してみるとそれなりに高速に動く。ここから効きそうな考察が全然わからなかったためとりあえず落ちてから考えようと思って投げてみると、3.3secくらいで通った。

残り時間はFに口出ししたりGを考えたりしていた。あまり良い働きができないまま、午後9時になったのでABC247に出た。

ABCのことを書く前にOpenCupの残りについて書いておこう。Cは僕が離脱する1時間前に通っていた。僕が離脱してから20分ぐらいして、FとGが立て続けに通ったようだ。GはML 16MBという空間計算量が制限された問題だったので、かなり大変そうだった。FもTLEに苦労していたようだ。僕が諦めたC問題だが、\max(x_1,x_2,x_3)-\min(x_1,x_2,x_3)=\frac 1 2\left(|x_1-x_2|+|x_2-x_3|+|x_3-x_1|\right)という式を使ったらしい。見覚えがないことはない、気がする。

ABC247について。

AtCoder Beginner Contest 247 - AtCoder

AはVim。Bは面倒そうだったので先にCを解いた。Rubyで、配列を足し算していく方法。次にB問題もRubyで解こうとした。文字列の出現回数をカウントしてチェックしようと思っていたのだが、s_i=t_iのケースに対処できないことに気づいてC++で解くことにした。以降もC++。Dは値と個数をペアにしてqueueに入れる。Eは各iに対し、直前のXYXより大きな数・Yより小さな数の出現位置を記録して、R=iとしたときに可能なLの個数を求めた。これらの出現位置は、dequeにスライド最大値・最小値を求める感じで値とインデックスをpushすることで取得した。後から整理してみれば、変数を用意して書き換えるだけでよかったとわかる。

Fは、同じ数が書かれたカードに辺を張るとグラフ全体が複数のループに分解できる。それぞれのループにおいてどの頂点を選ぶか決める。決めるときは隣接する2頂点のうちどちらかを必ず選ぶという制約があり、これは1点決め打って1周dpする方法で解ける。Gは重みを無視するとマッチング問題になるので、同様にフローで解けないか考えたら解けた。最小費用流を流量を変えて何回も解くことになったので、ACLslope関数を使って実装した。

Exは転倒数の偶奇など考えていたが、入れ替える2人は隣接している必要がない。このような操作で1,2,\dots,NP_1,P_2,\dots,P_Nに並び替えるのは典型的。iP_iを辺で結んだfunctional graphを考えれば、長さlのループはl-1回の操作で実現できるとわかる。つまり連結成分ごとに操作回数が1ずつ減るとみなせるので、Nから連結成分数を引いた数がK以下になればよい。また最初うまく題意を取れていなかったが、入れ替えるときに選ぶijは異なる必要があるようなので、偶奇も一致している必要がある。いずれにせよ、連結成分数ごとに順列の数を数え上げられれば解ける。

連結成分上ではc_iが一致する必要があるので、以降は数列cの頻度配列cntだけ扱うことにする。各cの出現回数n=cnt_cについて独立に考えてよい。長さnの順列(から作ったfunctional graph)を連結成分数ごとに数え上げたい。挿入dpを考えると、0\le i\le n-1を列に追加するときは「これまで作ったループのどこかに入れる」のがi通り、「一人だけでループを作る」のが1通り。多項式で表現すれば、dp\leftarrow dp\times(x+i)とわかる。つまりdp=\prod_{i=0}^{n-1}(x+i)である。

それぞれのcについてこのような多項式を作れば、それらの積を取ることで全体の数え上げができる。具体的に書くと\prod_{c=1}^N\prod_{i=0}^{cnt_c-1}(x+i)となり、これは1次式N個の積である。そのような積はセグメント木っぽくマージしていくことで全体でO(N(\log N)^2)で計算できるので、解けた。実装は多項式をqueueに詰め、queueのサイズが1になるまで「先頭から2個pop」→「積をpush」を繰り返すのが簡単。

ノーペナ全完3位。

Gで、ACLslope関数が流量とコストの関係の折れ線グラフを返すという部分に引っかかってWAになっていた人を観測した。すべての流量が出現するわけではないので、手作業で間を補完する必要がある。この実装は最小費用流の実装、つまり「コスト最小のパスに流せるだけ流す」ということを思い浮かべれば自然に感じられると思っている。そうやって流せるだけ流した時の流量はちょうど1とは限らないわけで、そのパスを使い切るまではコストが同じペースで増えていくことになる。折れ線の線分にあたる。

コードゴルフ。Aは最初に提出したVim 7Bが最短。取れてよかった。Bはs_it_iを混ぜた多重集合を作り、\{s_i,s_i,t_i,t_i\}という多重集合を含むかどうかチェックすればよい。RakuのBagを使った。Cは1,2,\dots,2^N-1lsbに1を足したものを出力すればよく、Rakuで24Bになったのだが、dcで再帰関数を書いたほうが短くなった。DはRubyで負け。EはAWK。残りは手付かず。

昨日のARC138-AとCのコードゴルフを少しした後は朝まで日記を書いていた。今週もひたすら溜めてしまい大変だった。あとは、ネット小説を読みながらの寝落ちが多くて、最近就寝・起床報告のツイートができていないのも気になるところ。