週記(2021/06/07-2021/06/13)

06/07(月)

先週の週記を投稿してからの話。ちょっとハーメルンを開くことがあって、面白そうなものを1つ見つけたので読んだ。ターニャ・デグレチャフダンブルドア世代のホグワーツに入学する話で、設定に惹かれたのだが、すでにエタっていて涙。

syosetu.org

いろいろな人の週記・日記を漁っていた。僕の友人の一人もサイトを自作して週記を書こうとしているようだ。サイトにこの「kotatsugameの日記」のリンクを貼ってくれているようなので、こちらからもここで紹介しておきたい。

YASUTAROのホームページ

ABC204Dが縮んだ。縮んだというか、実は解法がAGC020C-Median Sumと全く同一らしく、そちらのコード(ABC204の元最短コードより短い)をコピペしてきただけ。問題文だけ聞いても同じであるとは思いにくいが、コードを見れば解法が全く同じであることは直ちに理解できる。

C - Median Sum

大学の課題をする。まず数理統計学のレポートを終わらせた。こちらはちょっとした課題を解くだけなので、簡単。問題は数学基礎論特選のレポート。

数学基礎論特選」という講義のレポートを書いていた。3回分の講義資料を読んで、途中にある問題からいくつか選んで解く。

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

この日から1か月経過したということで、また3回分の講義資料が溜まり、同様に問題を選んで解く課題が出された。3回ごとに1区切りつくらしいので、前回の講義資料の最後のほうは全然わからないまま放置していたのだが、どうやらその後も続きの話をしていたらしく、慌てて前回格闘した記憶を呼び覚ましながら講義資料を読んでいた。ただ、前回ラストで僕の頭を破壊したゲーデル数や証明可能性についての記号などが、今回は様相論理として□に吸収されている(?)ので、それをそういうものと捉えることで何とか講義資料を読み進められている。

しかし3回分のスライドのうち1回目の半分まで読んだ段階で嫌になってきてしまい、布団に寝っ転がってなろうを読み始めてしまった。

かなり眠気があるが、せっかく起きているのだしということで学食に行くことにした。

平常時はご飯(特大)を注文していたが、今日は提供されないらしかったので、迷った挙句ご飯(大)とご飯(中)を購入した。ちょっと多かったので、次回は中サイズを2つ注文することにしよう。

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

店頭の表示ではご飯の特大がありそうだったが、注文する場所に掲示されているものを確認すると、そちらでは特大は存在しなかった。やはり提供されていないのだろう。

帰ってきてまた布団にダイブしてなろうを読んでいたが、すぐ力尽きて寝落ち。午後1時半から午後8時まで寝ていた。

起きてすぐ典型90問の今日の分を解く。今日は左右からLISをする。Rubyで書いてニコニコしていたが、すぐ大幅に縮められた。よくわからない。

解いてからまた布団に戻り、なろうを読んでいたら寝落ちした。午前1時だった。

06/08(火)

午前7時半に目を覚ます。寝落ちばっかりで自分の体調がよくわからず、なんとなく眠さを感じつつ午前11時半まで布団でなろうを読んでいたが、今日もまた起きているのだし、と学食に行くことにした。

昨日の写真でも確認できるが、ご飯はシートをかけた状態で提供される。「最近はこうなのか」という指摘があったが、これは別にコロナ対策とかではなく、僕が入学した当初からこのようにされていた。特にお昼時、混雑する時間帯のご飯の提供はすでに盛られたものが棚に並べられているため、乾燥を防いでいるのだろう。

選考プロセスが遅れるかも、という話があったものの、今日聞いた感じだともう来週には会議にかけて下さるらしい。

週記(2021/05/31-2021/06/06) - kotatsugameの日記

このインターンに内定が出た。ありがたい限り。手続きはすぐに行うが、実際に働き始めるのは僕の院試が終了してから、つまり9月くらいからになるようだ。

1333話!

今日の典型90問が投稿されていたので、解いた。コードゴルフとしては、配列の両端を変数で持っておいて左右に伸ばす実装がよい。[l,r)として持つとアクセスがl+x-1になるが、(l,r]として持つとl+xでアクセスできる。工夫としてはそのくらいだろう。

また昨日のレポートの続きに取り組む。昨日はある程度講義資料を読んでから問題に取り組もうと考えていたが、そんな余裕はない。何とか解読できた問題に全力を注ぐと、ちょっと怪しいところはあるが、とりあえず1問解けた。

もう無理!とばかりに布団にダイブし、またなろうを読んでいたが、午後7時に寝落ちした。

06/09(水)

06/08 午後11時に起きた。生活リズムがヤバい。

昨日一昨日とやってきたレポートは、06/09 午後1時が提出締め切りである。つまり、今日。全然終わっていない。3回分の講義資料があると言っていて、一昨日第1回の半分まで進めたものの、昨日は問題を解いてしかいないため一切進まなかった。つまり、残り半日で2回半進める必要がある。しかも謎の生活リズムで、自分がこれから提出期限までどの程度眠ることになるのかもわからない。

とりあえずまた講義資料と格闘する。講義資料の第2回の序盤まで読み進め、問題をさらに2問解くことに成功した。提出するには10問用意されている問題から5問以上解くことが求められている。まだ3問しかできていないが、実はそれだけ提出しても許されるのではないだろうか。とにもかくにも疲れ果てたので、布団に戻ることにした。

なんとなく眠気を感じていたので、布団でなろうを読みつつ寝る体勢を作っていた。もちろん提出期限には遅れないよう目覚ましをセットしてあった。しかししばらく待っていても眠れそうになかったので、あきらめて布団から這い出し、またレポートと格闘することにした。

Topcoderからメールが来ていた。今日はSRMらしいが、よく見るとdiv.2 onlyらしい。SRMでdiv.2 onlyなのは初めて見る。

午前3時からまたレポート。よくわからない箇所はもうすっぱり諦めて、少しでもわかる部分の周辺を何とか読んでいく。前回の課題の際によく読まないまま放置した箇所の進化系みたいな命題をバッサリ読み飛ばしてしまったが、何とか解けそうな問題を選んで解いていき、午前5時に5問の回答が完成した。すぐに提出。

前回のレポートについていたコメントを読んでいた。かなりボコボコで厳しい。講義資料で導入された関数を使用した箇所で、関数の定義がないという理由で減点されていたので、そこについてはClassroomのコメントから異議を申し立てておいた。布団に戻ってなろうを読んでいたが、午前6時にコメントにTAからの返信が来た。どうやら点数を付けなおしてくれるらしい。朝早くからありがたい話である。

またずっとなろうを読んでいたが、午前10時まで起きていられたので、今日も学食に行った。

今日は結構早くに家を出たので、午前11時過ぎには食事を終えられた。昼休みが始まる前、人が少ないうちに床屋に行っておくことにした。かなり眠くて、髪の毛を切ってもらっている間はほとんど意識がなかったが、今日担当してくれた人がかなり威勢がよく、ジョキジョキ音を立てて鋏を動かしていたことを覚えている。というか鋏に髪の毛が挟まってかなり痛かった。しかし出来上がりは良さそう。髪の毛の生え方の左右非対称性などを説明されたが、それを考慮して長さを調節しているらしい。

床屋を出て家に帰ろうとしたが、横断歩道がない箇所で道路を横断しようとした際、近づいてくる車に気づけなかったらしい。前から車が来ているのにフラフラ車道に自転車を漕ぎだしてしまい、かなりヒヤッとした。確実に見えているはずの近さだったが、寝ぼけていたのだろうか。

床屋で待っている間に典型90問が投稿されたことは確認していた。今日の問題はグラフを作ってBFS。Rubyで書いたらPerlに取られたが、ちょっと格闘したら取り返せた。BFSで使うキューを@0にすることで、グラフを作るのとBFSの始点をキューに入れるのをほぼ同じコードでできたのがよかったのではないだろうか。

また布団に戻ってなろうを読んでいたが、午後3時くらいに寝落ちした。

06/10(木)

06/09 午後8時に起床。

今週月曜日の典型90問についてはRubyでかなり負けたと書いた。その問題は数列の左右からLISを計算するが、数列の左右から同様の処理をした後にマージするという意味で似たような問題が存在し、そちらも縮んでいる。その最短コードを見ることによって、月曜日の問題がどのように短縮されたのかが少しだけ窺い知れていた。その問題のコードゴルフはちょっとだけ取り合いが発生していて、火曜日にもちょっと縮んでいた。今日も少し縮んだ。

atcoder.jp

似たような処理を2回行うということで、以前はprocを作成していたのだが、コードを文字列として2回繰り返すほうが短いらしい。毎回reverse!することで、数列の左右から処理を行うこともできている。

コードゴルフした後はまたなろうを読み続けていたが、午前1時半から午前4時半までまた寝落ちしていた。

起きてからもなろうを読み続け、午前11時半になったので学食に向かった。

帰ってきてしばらく週記を書きつつ、今週のゼミに参加した。ビッグオーの記法が導入されたが、f(x)=O(x)と書くと等号なのに推移律が成り立たないということが言われていた。これは僕にはない着眼点ですごいなあという気持ち。f(x)\in O(x)という記法もあるらしいという指摘をした。等号に右から左への向きがある、という考え方もあるらしい。あとは、PDFファイルをMicrosoft Edgeで表示していた人のURL欄にWindowsのユーザ名=本名が表示されているのでどうにかしたほうが良いのでは、と言われていたため、F11キーを押して全画面モードに入ることで副次的にURL欄が見えなくなる、という話もした。

別の人がPARI/GPの紹介をして、それでコーディングして条件を満たすものを全列挙したりしていた。コードを詳しく読んでいる暇はなかったが、チラリと見えた限りではif文やfor文の記法が独特。if(条件,真,偽)という風に関係する式をすべてかっこでくくり、複数の文章を書く場合はセミコロンで区切る。セミコロンとコンマを演算子のようにとらえたとき、セミコロンのほうがコンマより優先度が高いと言えるのが独特に感じられた。これは僕の触れたことのある言語ではImageMagickと同じだが、for文は競プロの文脈で言うrepのようになっているようだ。

途中で今日の典型90問を解いたりもした。まああからさまな制約。

ゼミが終わって布団に入りなろうを読もうとしたが、即座に寝落ちした。午後5時から午後9時まで寝ていた。

起きてからもしばらくなろうを読んでいたが、午後11時半からCF #725 div.3に出た。とりあえず全完だが、システスは明日。

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

Aから面倒。最大・最小のインデックスを見てなんやかやする。Bは平均値以上の要素を数える。Cはlower_boundとかupper_boundを使う。Dはabの素因数の個数がk以上ならばよくて、k=1の場合がコーナーケース。コーナーケースには気づいていたのに、a素因数分解するコードをコピペした時の修正ミスで1WAしてしまい赤っ恥。Eは長さと"haha"の個数と左右3文字ずつを保存しておく。面倒。Fはf(r)-f(l)と変形する。桁ごとにみるとf(n)=\sum_i \left\lfloor\frac{n}{10^i}\right\rfloorとわかる。半信半疑で出したら通った。

Gはfloorがからむ最小値で、線形計画法のような図を描いてみると三分探索できそう。ただfloorがついたそれには最近煮え湯を飲まされたので、ABC204Eと同様floorを外してから三分探索した。TLを見ていると、多いほうから優先的に引く貪欲でもよいらしい。xyが近づくまでは割り算で一気に計算し、あとは2回ずつペアにして引くことを考える。

全完してからは布団に入り、眠気をこらえつつなろうを読んでいた。午前5時半就寝。

06/11(金)

今日はぜひとも学食に行きたいと思ったので、目覚ましを午前11時と午後0時半にセットしていた。午前11時の目覚ましは、止めた記憶こそあるものの、瞬時に二度寝してしまったらしい。目を瞑った次の瞬間再度目覚ましが鳴り響いたと感じた。

今日の典型90問が投稿されていた。最初は遅延セグメント木を書いてしまったが、これは明らかに寝ぼけている。ほとんど同様の問題が僕の参加したJOI本選の第1問目だったことを覚えていて、その解説を見て、データ構造など必要ないことに思い至った。とりあえずそれで通しておき、午後1時くらいに学食に行った。

atcoder.jp

今日も納豆ご飯を食べようとしたが、お昼過ぎとあって大したものは残っていなかった。納豆も一見売り切れかと思ったが、よく見ると普段とは別のところに2個だけ残っていたので、これ幸いと確保。サラダ類は売り切れていたので、適当な副菜を購入した。

これで5日間毎日ほとんど同じものを食べていたことになる。水曜日にも言及したように、これは儀式の一種であるが、とはいえ別に何か念願があるわけでもない。毎日同じものを食べていたら面白いかなと思ったが、反応は全然ないので、結局自分の行動を常に追いかけている人、つまりは自分にしか通じない面白さだったということ。

帰りに購買に寄って新刊の短編集を購入した。米澤穂信さんの手になる短編も収録されているとのことで確認すると、見覚えのないタイトルだったため、書籍には初収録であると判断したのが購入の決め手。奥付を見たところ、この判断は正しかった。

books.bunshun.jp

ほかにもカロリーメイトを購入して帰宅。

帰ってきてしばらく今日の典型90問のコードゴルフをし、そのあと布団でなろうを読んでいた。ちょっと寝なおそうかとも考えたが、なろうを読んでいるうちに時間は過ぎていき、結局寝ないまま午後6時半になった。サークル解説会の準備をする。

今日はABC204の解説会の予定。F問題の解説を書いたらもうかなりいい時間で、E問題の解説も書けるかと思ったが、微妙に間に合わなかったのでかなり適当なスライドになってしまった。今日はこの2問だけの発表で、参加者も3人。僕がひとしきり喋って、終了した。先週の記事をふと見ると、日付がコピペ元のまま変わっていなかったので、直しておいた。

2021/06/11 定例会 | puzzleknot 公式サイト

そういえば昨日のCFのシステスが終了していた。全完10位。ちゃんと通ってよかった。

yukicoder 299に出た。滑り込み全完。

yukicoder contest 299 (BANNED CONTEST) - yukicoder

Aはよい。入力を加工してdcに流し込む方法で現在の最短コードを持っている。Bは面倒だが拡張ユークリッドの互除法で解いた。解説を見ると1\dots NMを全探索するのでもよかったらしい。Cは赤字の制約が怪しいが、実は全部同じコードで解ける。復元が怠い。Dは係数を求めると1乗、2乗、3乗の和になるので、公式を使って和を消す。

Eは最初勝敗が決まるまで延々ゲームを続けるのだと思っており線型方程式を解こうとしていたが、よく見るとただの行列累乗。さすがにもう行列累乗は飽きた。謎のREが出てしばらくコードとにらめっこしていたが、入力に制約違反があったらしい。

Fはなんちゃらモーメントなるヤバそうな単語が見受けられるが、よく見ると偏差をk乗して足しているだけ。k=1の時は0でk=2の時はいわゆる分散、つまり2乗の平均引く平均の2乗。もしかしてk=3,4のときも……?と思って計算してみると、3乗や4乗の平均まで計算しておけば求められることが分かった。遅延セグ木に5個くらい値を載せる。列が円環なのも面倒ポイント。

Gは包除原理。愚直にやれば、q=iの時は(i+1)\times(T_i+1)のdp配列を作って計算したくなる。これにはおおよそ\sum_{j=1}^i jT_i=\frac{i(i+1)}2 T_iくらいの計算が必要になる。つまり全体で\sum_{i=1}^Q \frac{i(i+1)}2 T_i\approx \frac 1 2 \sum_{i=1}^Q i^2 T_i\approx \frac{Q^3 \max T}6\approx 5\times 10^8。TL 4secなので間に合う。2500ms。

日記を書いてから布団に入りなろうを開いたが、眠気に耐えかねてすぐ寝た。午前3時半だった。

06/12(土)

午前9時に目を覚ましてしまう。

Twitterで今日の典型90問を確認し、さて寝なおそうと思ったが、考えているうちに眠気が覚めてきてしまった。星7ということで気合を入れてしばらくあれこれ考えていたが、ただの畳み込みであることに気づいてびっくり。解けたはよいが眠れなくなってしまったので、なろうを読んでいた。

午前11時半くらいになって、AtCoderのほうで問題が公開されたことを知り、布団から起き上がってコーディングした。C++ACLで書くのが一番短いだろうと考え、269Bのコードを作成したが、以前ALPCのConvolutionの最短コードをRubyで更新したことを思い出して、そのコードを流用したところ、13B縮んだ。ALPCにおいては4000msくらいかかっていたので、畳み込みを2回行うこの問題で間に合うこと自体かなり驚きなのだが、やはり数列の長さが短いことが効いているのか、それともALPCのほうは入力の読み込みがかなり遅いのか。

ALPCのConvolutionでゴルフをしていた。Ruby多倍長整数を使って、16進で20桁ごとに数値を埋め込むと、掛け合わせても20桁から溢れないので、復元できるということらしい。

週記(2021/05/17-2021/-5/23) - kotatsugameの日記

さらにVimを使ってRubyのコードを作り、実行するテクを用いて、さらに15B縮んだ。これが現在の最短コード、241Bである。元のRubyコードのほうもまだ縮みそうなので、こちらもそれに応じて更新される予感があるが、今はわからない。Vimのインサートモードで<Ctrl-@>を入力したかったのだが、文字コードでどれに対応するのかわからなかったため使えなかった。一応ASCIIコードのnon-printableな文字はすべて試したので、これ以上はUnicodeで2B文字になり、<Ctrl-A><Esc>と同じ長さになって縮まないだろう。

そんなことをしていると午後2時になってしまった。布団に戻る。今日は生協の弁当配達があるので午後3時には起きていたいが、目覚ましを信じ、訪れた眠気に身を任せて寝ることにした。

午後3時と4時にかけていた目覚ましによって浅い睡眠状態だったのがよかったのか、今日も何とかチャイムに気づくことができた。午後4時半だった。受け取って再度就寝し、午後7時半に起床。

かなり眠い。うつらうつらTwitterをしていたら、ホスフィンから書いた文章に間違いがないか確かめてくれというDMが来たので、それを読んでいた。途中で午後9時になったのでARC122に参加した。

Tokio Marine & Nichido Fire Insurance Programming Contest 2021(AtCoder Regular Contest 122) - AtCoder

5完31位、パフォーマンス2955、レートは2724→2749(+25)。D問題までは非常に良かっただけに、E問題での失速が気になるところ。まあレートはいい感じに上がったので良かった。

Aは普通に考えれば最後の文字を持つdpだが、新しく足すA_iの寄与を計算する必要があるため、値だけではなく場合の数を求めるdpも同時に行う必要がある。見た瞬間に解けた。FA。

Bはちょっと計算すると\max(A_i-x,x)になる。これは下に凸な関数なので、すべて足した値も下に凸となり三分探索できるが、コンテスト中の僕は三分探索を信用できなかったため、もうちょっと考察した。\max(A_i-x,x)x=\frac{A_i}2で最小値を取る。グラフを書くと、そこを境に傾きが-1から1になっているわけで、これは絶対値関数の平行移動である。つまり、そのmaxいくつかの和は、\sum |A_i-x|の最小化と同様に考えれば、いずれかのiについて\frac{A_i}2で最小値を取る。これで探索すべき値がN個になり、左と右で和をもつことですべての場合について計算できる。さらに考察を進めれば候補の中央値を取ればよいこともわかるが、コンテスト中はすべて試す方針で通した。

Cは難しい。ちょっと手で計算してみると、値を大きく増やすにはx+=yy+=xフィボナッチ数列を作るくらいしか手段がなさそうだとわかる。フィボナッチ数列から適当に要素を選んで和を取ると任意の非負整数が作れる、というのは(それが値の大きいほうから貪欲に取って良いことも含めて)競プロでよく見る定理。今回も、適当なタイミングでxyを1増やしてやることによってフィボナッチ数列を途中から始めて合流させる感じにできそうなので、方針としてはこれでよい。ただ実装が面倒。とりあえずフィボナッチ数列が何項目まで必要かとどのタイミングで増やすかだけ確定させて、偶奇は最後に帳尻を合わせることにした。出力を見ていてもよくわからないが、ランダムテストを回した感じではよさそうだったので提出、AC。解説だと、使うフィボナッチ数列の長さを決め打つことで偶奇を決め打てるようにしていた。

Dはかなり簡単だった。まず最上位bitで場合分けするのはすぐわかる。0と1が両方偶数個あるならそれぞれで再帰し、1つ下のbitを見る。奇数個ある場合を考える。現在見ているbitが0であるような要素aと1であるような要素bについてのa^bの最小値を求めると、実はそれが答えになる。なぜなら、Aliceがabを選んだタイミングでBobがもう一方を選ぶことでa^bが作れ、Aliceがそれ以外の要素を選んだときは、それと現在見ているbitが同じ要素をペアにあてがうことでa^b未満になるから。結局Aliceは何もできないということらしい。a^bの最小値を求めるフェーズだが、これはbinarytrieで解ける。ライブラリを貼り付けてAC。10分で解けてしまい、かなり全能感を感じた。

Eは迷走してしまった。106までの素因数を求めておくと、1018素因数分解が必要なだけできる。109オーダーの素数2つの積と素数を区別するのが問題だが、これは素因数分解する値同士でgcdを計算して出てきた素数だけ考えればよい。これで出てこない素数2つの積は、今回の問題だと素数と同様に扱っても構わないため。実はこれで問題が解けて、あとは指数を見ながら数列の最後の項から貪欲に構築していけばよかったのに、何か難しいステップがあると思い込んでしまい、気づくのにかなり時間がかかった。さらに素因数分解のミスで2WA。解説を読んで気付いたが、指数を見ながら構築するというのは指数のminとmaxの話になって、これは元の数においてはgcdとlcmに対応するため、素因数分解する必要はなかった。つまり後ろから貪欲に取ってよいことさえ考察できればよく、素因数分解の具体的な方法を考えるのは後回しにしておいてもよかったのだ。

コードゴルフをする。Aはよくわからないdcコードが最短。BはOctaveだったが、謎のabsを噛ませていたのに気づかず、取られてしまった。これは非常に悔しい。EはRuby。Cを書こうとしたがすでにdcで縮め切られており、しばらく考えてもこれ以上縮まなさそうだったので諦めた。

ホスフィンの文章を読む作業に戻る。最後まで読んで、わからなかった部分を質問し、いくつか誤植を指摘した。扱っている問題に対する興味がなかったので、詳しい部分は理解していない箇所も残っているが、誤植を見つけるくらいなら十分だった。

朝方、布団に入ってなろうを読んだ。午前10時に寝落ちした。

06/13(日)

午後6時半起床。ABCまでずっとなろうを読んでいた。始まる直前になろうのバトルシーンが終了して一段落ついた。ABC205に出る。

AtCoder Beginner Contest 205 - AtCoder

Aはdc。精度を設定してから100で割るより、0.01を掛けたほうが短い。割り算では精度は必ず設定した値にされるが、掛け算はオペランドの精度に合わせた結果が得られる。

Bは最短コードがどのようになるかよくわからなかったのでとりあえずRubyで書いたが、putsとしなければならないところをpにしてしまい1WA。コードゴルフsed。基本は/\<\(.*\) .* \1\>/で、テストケースハックなどを行い縮めておいた。

Cは普通に多倍長整数を使うとどのようにしてもTLEする。仕方なくC++で場合分けを大量にして通しておいた。Dは適当に二分探索で、サンプルを合わせたら通った。

Eは非常に難しかった。dp[i][w-b]のようなdpを考えると、遷移は±1なのでいつもの括弧列とか格子を進む場合の数の図が思い浮かぶ。ジグザグの図を考えると、問題の条件は、特定の高さ以上に進めないことを表す。これはカタラン数を求めるのと同様にグリッドを折り返すことで求められる。答えが0のケースで値を引きすぎて1WA。カタラン数の下りは見覚えがあったが、TLによれば数学ガールらしい。

Fはいつもの行と列を結ぶグラフのマッチングだと思って二部マッチングのライブラリを貼ったが、サンプルが合わない。それはそうで、駒に対して扱える辺が決まっている。この条件を表現しようと思い、条件をどのように並べるかいろいろ試してみると、行-条件-列で表現できることが分かった。フローを流してAC。

コードゴルフをする。A、Bは最初のほうにACしたものでよい。

Cは、適当な数でmodを取ったりしてみていたが、ここでCは偶奇さえ合っていれば問題ないことに気づく。例えばC%2+2としておけば累乗した数を直接比較できる。答えを出力する際の場合分けも難しいが、BC-ACからd2^v/で符号を取り出し、61から引くことで答えの文字コードを得るのが良さそう。本当はAC-BCを使って61を足したいところだが、どちらにせよrの1Bがかかる。……と思っていたが、Pコマンドは値の絶対値を取ってくれるらしい。つまり61から引く=61-xではなく61を引く=x-61でも正しい出力が得られる。これで-1B。

DはRuby。EもRubyだが、こちらはVimRubyコードを書くテクでさらに縮んだ。

Fのコードゴルフをする前にCodeforcesに出た。今日はcombined。

Dashboard - Codeforces LATOKEN Round 1 (Div. 1 + Div. 2) - Codeforces

6完62位、2839→2842(+3)でhighest。途中詰まってなろうを読んでいたが、終盤になって気づきを得て考察が進んでしまい、通せず悔しい思いをした。しかし解法を聞く限りまだ遠そう。

Aは市松模様に塗るしかない。Bは幅1の突出している部分を縮める。Cは一緒にflipしなければならない列がグラフの連結成分として表せる。答えは2の連結成分数乗。Dは、まず適当な頂点を1回聞いて、そこからの距離が偶数の頂点と奇数の頂点のうち少ないほうを全部聞く。辺の復元は面倒だと思ったが、距離1の頂点を全部つないだ後重複を除けばOK。インタラクティブのくせに入力を2e6個ほど読む必要があって、1500msくらいかかっている。

Eもインタラクティブ。非常に難しい。すべての値を同じ回数だけ聞くことを考えていたが、そんな必要はない。結局、聞く回数として最初1,1,1...という列を用意し、順に2ずつ足しながら総和がKの倍数になるのを待った。復元については、毎回ソートして残り回数が多いものからK個ずつ使う。これでよいことは自明ではないが、コンテスト中は気づかなかった。N=4K=3という入力の時に聞く回数が3,1,1,1のような列を使ってしまい、1WA。クエリ回数が2回のはずなのに聞く回数が3の要素があるとダメということだ。

つまり、N項の非負整数列A0\lt K\le N\sum A\equiv 0\bmod{K}かつ\max A\le \frac{\sum A}Kを満たすとき、K個の要素を選んで同時に1引くことを繰り返してAの値をすべて0にできるという事実と、実際の方法は値が大きな要素から貪欲にK個ずつ選ぶことで構成できるということ。何回かこの事実を用いる問題を解いた覚えがあるが、証明は覚えていない。TLを見る限り\frac{\sum A}Kに関する帰納法が回るらしい。

コンテスト後のTLでもいろいろ解法が流れてきた。僕のようにできるだけ均す方法やフローを流す方法もあったが、一番すごかったのはSSRSさんの、聞いた回数が奇数回のものの個数をもってグラフを作成しBFSする方法。

F1は連結成分をまとめた後辺を張ってSCCし、入次数が0の頂点を数えた。後から考えてみれば、連結成分をまとめる必要はなかった。F2は、SCCした後のDAGにおいて到達できなければならない頂点がいくつか指定され、それらすべてに到達できるような頂点集合の最小サイズを求める問題になる。DAGの道被覆というワードで調べたりしていたが、よく考えるとこれは違う。グリッドからグラフを作成したので、それによってグラフが持つことになる特徴を利用するのだと思ったが、わからずに終わった。

どうやら、入次数が0の頂点を抜き出してグリッドの左から順に並べておくと、ある頂点に到達できる入次数0の頂点は区間になるらしい。つまり、区間がいくつか与えられるので、それぞれの区間に含まれる頂点が1つ以上存在するように頂点を選ぶ問題になって、これは区間スケジューリングで解ける。かなり頭が良い。

CF後にABC-Fのゴルフもした。Cythonとnetworkx。行と列に対応する頂点は、駒の条件を表すのに必要な分だけ用意しておけばよい。DiGraphは何回も同じ辺を張ると最後に張ったものが使われるようなので、それを利用して必要になるたびに行と列の頂点を用意してみた。

そういえば、今日のABCのdifficultyは灰-灰-灰-茶-黄-黄らしい。かなりすごいことになっている。

日記を書いていたら昨日のARC-Bが縮んだ。\max(x,A-x)だったが、\frac{A+|A-2x|}2とするほうが短かった。

週記(2021/05/31-2021/06/06)

05/31(月)

午前7時、目覚める。午後3時までなろうを読んでいた。yukicoderに問題が追加されたらしいが、今は気にせず放置することにした。午後3時に再度寝落ちして、次に午後7時半に起床。

まず典型90問を解いた。今日は超頂点。うっかり01BFSをしたが、別に辺の重みをすべて1にして最後に2で割っても同じ値が出る。こちらはBFSでよい。コードゴルフはよくわからないのでしなかった。

昨日のABCのC、Eが縮められていた。このうちCはテストケースハックに成功してしまい縮んだ。Eはとりあえず放置。またA問題の最短コードも更新されていて、Vimの単語検索・移動を巧妙に使ってうまいことパターンを区別するコードが登場した。ABC155A-Poorでも同様のコードを見たし、コンテスト中もそれなりに考えていたのだが、どういう思考でこの操作を生み出すのか全然わからない。

atcoder.jp

atcoder.jp

典型90問の004は、これまではPyPyが最短になっていたが、Crystalで更新されていた。自分でも書いてみると確かに縮んで、また取り返すことができた。ロジックは変わっていない。

先週の週記を書き上げて投稿した。先週の平日は本当に一切の予定がなくて、一歩も家から出ずに思う存分生活リズムをぶち壊しながらずっとなろうを読んでいたらしい。振り返ってみればとんでもない一週間だった。またやりたいぜ。

AHC003の参加記を書こうと思って、下書きに初日の分だけ書き残しておいたのだが、結局それから1度もコードを書かずに終了してしまったので、内容は少しだけ週記に移して、記事のほうは削除した。

またコードゴルフをする。mapが頻発するコードは、無理やり同じ形をくくりだしてjoinしてからevalすると短くなるらしい。多分適用できるコードはいくつかあると思うが、このテクが使えるコードというのはおしなべて手順が多いアルゴリズムを採用しているため、その他の点でもまだまだ縮む余地があるだろう。ということで、探して縮めることは今回はしないことにした。

atcoder.jp

昨日のABCのE問題を見る。解説と同様の方針だが、わざわざX座標が同じ値を同時に処理しなくても、直前に見た点とそれによる集合の変化さえ覚えておけばよいらしい。これでRubyのコードが最短になっていたが、Perlでも書けたので縮んだ。その後取り返された。シェルスクリプトで各行に2つ値が書かれたものを数の組としてソートするとき、基本的には-k1n -k2nと書く必要があるようだ。ここで-nk1 -k2とすると、最初のオプション-n-k2にも適用されるということで先と同じ意味になり、-1B。しかし-nとだけ書くと組の2つ目は辞書順ソートされてしまうらしく、ダメだった。かなりいびつに感じられるが、ここは縮まないのだろうか。

AHC003のシステスが終わったらしいので見に行くと、0点になっていた。びっくりして自分の提出欄を確認したところ、コードゴルフしていて最後に出したTLE解がシステス対象になってしまっていたらしい。これはかなりショック。自明解なので順位的には下のほうだが、しかし0点はちょっと恥ずかしい。

日付が変わってから午前5時くらいまでなろうを読んでいた。そのあとシャワーを浴びてゴミを出し、帰りしなに宅配ボックスから届いていた荷物を受け取った。

昨日Amazonで注文した商品が宅配ボックスに配達されたことを知ったが、取りに行くのは面倒だった。

週記(2021/05/24-2021/05/30) - kotatsugameの日記

また布団に戻って学食の麺コーナーが開店する午前11時半までなろうを読んだ。そろそろいい時間かな、と思って学食に行こうとしたが、ふとAtCoderを確認すると今日の典型90問が投稿されていたので、通してから行くことにした。とりあえずC++で全探索するコードを書いて提出したが、700msくらいあって嫌な予感がする。Rubycombination(5)を使って書いたら案の定TLEしてしまった。それではCrystalならば、と持ち出してきたが、こちらもTLE。PyPyもTLEした。

この時点でそう簡単にゴルフ出来ないことに気づき、先に学食に行くことにした。昼休みに入ると人だらけになって待ち時間が嫌なので、その前に食べ始める必要がある。なんとか昼休み10分前に学食にたどり着けた。食事して購買でブラックサンダーを箱買いし、帰宅。

典型90問のコードゴルフを続ける。mapでまとめてdpすることも考えたが、こちらも間に合わない。どうやら全探索するしかなくて、C言語を持ち出す必要がありそうだ。5重ループなど書いていられないから、再帰関数で実装することにする。入力部をまとめたり関数呼び出しのところで頑張ったりreturnを書かないようにしたりして、121Bのコードが出来上がった。相変わらずC言語はよくわからない。このコードは手元では動かないので、毎回コードテストで試すことになるが、ちょうど出力の末尾に改行が必要だったというテストケースのミスを修正した後のリジャッジと被って、実行は毎回かなり待つことになった。

月が変わったので、5月ぶんの読書記録の集計をした。

まだパソコンにかじりついているつもりだったが、椅子の上で少し寝てしまったこともあり、しょうがなく布団に移動した。午後3時、就寝。

06/01(火)

午後9時くらいに少し目を覚まして、午前0時まで布団でなろうを読み、また寝た。

06/02(水)

午前4時半、目を覚ます。二度寝するつもりだったが、実際は午前9時まで布団でなろうを読んでいた。今日は応募したインターンの2回目の面接の予定なので、もう二度寝できない時間になってしまった。仕方なく起きる。

午後1時からAtCoderJobsで応募したインターンの1次面接があった。

週記(2021/05/17-2021/-5/23) - kotatsugameの日記

生協の購買が開くのを待ってから学食に行こうと思って、それまではコードゴルフをしていた。昨日の典型90問がCrystalによって縮められていた。combinationsがTLEすることを確認してもう無理だと考えていたが、普通に再帰をするとよい。これは、毎回掛け算していたのが再帰1ステップで1回だけに抑えられた結果、定数倍の5が消えたことによるものだろう。また、普通のcombinationsだと最初にすべてArrayに溜めてしまうので、each_combinationsを使用してイテレータを用いるとよいのではないか、とも考えたが、こちらも結局TLEしてしまった。

それで、再帰関数を使う方法でしばらく格闘していたら、現状の最短である101Bと同じ長さのコードが完成した。かなりびっくりなことをしているので、もしかしたらもっとシンプルなコードなのかもしれない。とりあえず今はこれ以上縮められなさそう。

そのようなことをしていたら、午前11時半になってしまった。面接は正午からなので、それまでに大学に行って学食で食事する、というのは難しそう。ギリギリ購買で買い物するくらいはできると考え、自転車を一所懸命に漕いで向かった。思ったより早くついたので問題なくパン等を購入し、帰宅。急いで食べて、歯に食べかすがついていないことを確認し、Zoomに入った。

30分くらいCEOから会社の説明を受け、残りの時間はエンジニアの方々と質疑応答を行った。せっかくCEOから直々に会社の説明をしてもらったのに、特に質問などをひねり出すことができず、しばらくカメラの前で唸っていた。また、途中で自分の将来像のようなことを聞かれたが、こちらもすぐには思い浮かばず、恥じ入るばかり。エンジニアの方々に対しても特に聞きたいことなど用意しておらず、そういう面談があることは知らされていたのだから、準備しておけばよかったなあとひとしきり後悔していた。こちらは質問をひねり出すことができて、1日の流れであるとか、コーディングスタイルについてを聞くことができた。比較対象がないわけではあるが、まあ良さそう。

1時間ちょっとで終了。かなり感触が良い。前回の面接のときには、応募者がかなり多いため働ける日程に余裕がある僕は選考プロセスが遅れるかも、という話があったものの、今日聞いた感じだともう来週には会議にかけて下さるらしい。これどのくらい日記に書いていいのかわからないな。前回(1回目)の日記では怖がって具体的なことは何も書かなかったが、今回はいろいろ書いてしまった。マズかったらこっそり教えてほしい。

布団に倒れこんでしばらくなろうを読んでいた。眠気が襲ってきたが、振り払い、ゲーセンに行くことにする。

今日はかなり調子が悪かった。特に最初のほうは1曲ぶん集中が持たず、ノーツは見えているのに手が動かない、エアーでミスを出す、など散々だった。最後のほうはちょっとだけ持ち直して、新曲の99AJ埋めは一段落ついた。

午後7時を回ったあたりで食事しようと思い、ゲーセンを離脱。どこのラーメン屋に行こうか考えながらうろうろしていたらたいぺーからDMが来て、一緒に食事することになった。

仙台駅まで行って待ち合わせ、駅前のラーメン屋に入った。「味噌乃屋 田所商店」という店で、かなり昔に1回だけ入ったことがあった。その時どうだったかは覚えていないが、今日はあまり口に合わなかった。味噌ラーメンは好きなはずだが……。

ラーメン屋を出て本屋に入った。駅前の丸善は棚の配置の変更やらの真っ最中らしく、今日はラノベコーナーに行けなかった。仕方なく文庫コーナーだけ見て、前に買った本の続刊1冊と、新作1冊を買った。

本屋を出て、さてゲーセンに戻ろうかと思ったが、たいぺーはもう帰るつもりらしい。帰りしなに僕の自転車のチェーンに油を差してくれるそうなので、僕もゲーセンに行くのをあきらめてついていくことにした。たいぺーと別れて家まで自転車を漕いだわけだが、油の威力はすさまじく、力を入れてペダルを踏んでも音が全然しない。ありがたいことだ。

帰ってきて、今日の典型90問を解いた。bitsetを使うと書きやすい。Ruby多倍長整数を使い縮めておいた。

米澤穂信さんの新刊が出るらしい。

しばらくなろうを読んだりしていたが、やはり眠気がすごい。午前1時就寝。

06/03(木)

正午、起床。ゼミがあるからと念のため目覚ましをセットしていたが、まさかそこまで爆睡するとは思っていなかった。危ないところだった。

今日の典型はすでに投稿されていたようだ。コードゴルフしていたらゼミの開始時間を見逃してしまった。2分遅れで慌てて入室したら、ちょうど僕がどうしたのかを話しているところだったようだ。急いで謝ろうとしたがマイクをオンにしたりミュートを解除するのに手間取った。

ゼミを聞きつつ今日の典型90問を解く。今日はいつもの\mathbb{F}_2線形代数コードゴルフで基底を取る操作は、基本的にnoshi基底を使っておけば間違いない。

1度は取られたものの、入力を読みつつ溜めずに毎回基底に入れていく感じのコードを書いたらかなり縮んだ。bitの入力が2通りあるのがかなり厄介で、これはどうしようもなさそう。

ゼミが終わった。学食の夜の部が開く午後5時を待って学食に行き、そのあとまたゲーセンに行くことにする。チュウニズムのマップが全然終わらない。来週のアップデートで終了するイベントについては今日で終わらせておく必要があるというわけだ。昨日食事のあとゲーセンに行かなかったが、もし行っていたとしても昨日のうちには終わらなかっただろう。

このグルグルはずっとただの曲線だと思っていたが、アットマークらしい。びっくり。

しばらくなろうを読んでいたら午後5時前になったので、学食に行った。閉店直前の購買で飲み物を買い、学食で夜ご飯を食べて1日ぶんのミールカード1200円を使い切ろうとしたが、最後にダメ押しで買ったシュークリームが完全にはみ出てしまった。学食のシュークリームは硬くて不味い。正直、お金が余っていたとしても買わないほうがいい。買わないほうがいいことは分かっているはずなのに、レジ前に置かれているから、ミールカードの残額が微妙っぽい場合などについつい買ってしまいがち。今回もそれだが、実は微妙じゃなくてすでに使い切られていた……ということだった。

ゲーセンに向かっていたら街中でクラスメイトに会い、挨拶をした。学食とかでよく会う人。

今日の成果はまあまあ。マップやイベントは何とか限定アイテムをすべて集め終えることができた。また、12+の未AJが1個減り、ついにラスト1個になった。12+の未AJが減るのは本当に久しぶりな気がする。この譜面は今日たまたま選曲したものだが、一発でAJを出すことができた。ラストの鍵盤は相変わらずよくわからないが、指は動いてくれた。

ほかにも5譜面くらい13のAJを99AJにしたりなど。低難易度譜面で脱力を意識していたらエアーで赤をたくさん出すようになってしまい、困った。高難易度については、HAELEQUINの前半がかなりうまくなっていることが分かったが、結局ラストのホールド鍵盤地帯ゲーなのでどうしようもない。

じっくり午後11時までゲーセンにいて、さて帰ろうと思ったところ、駐輪場が閉まっていた。

昨日は(別に深夜まで止めていたわけではないが)別の駐輪場に止めていたが、そこはゲーセンから少し遠かった。そこで別の駐輪場があったことを思い出し、今日はそちらを使ったわけなのだが、24時間営業ではないことをすっかり忘れていた。どうしようもないのでまた明日来る。明日来れなければさらに追加料金が必要になってしまう。

今日は徒歩で帰る。帰りに夕食を食べることにする。いつもの立ち食いそば屋は空いているかわからず、24時間営業らしいマクドナルドを見つけたのでそこで食べた。僕が来たタイミングだけかなり忙しかったらしく、注文するまでも結構待った。日付も変わろうとしているのにUber Eatsの配達員が来ていてびっくりした。ビッグマックのセットを満腹になりつつ食べて、そこから30分以上歩いて家に帰ってきた。かなり疲労困憊。明日の行きは電車にしよう……。

シャワーを浴びて僕がゲーセンにいる間に縮められていたコードの粗探しをし、日記を書いたら、朝方になってしまった。布団に入ってすぐに寝た。午前5時半だった。

06/04(金)

午前11時半に目を覚ました。自転車を取りに行こうと思ったが、外は雨が降っていた。明日からまた晴れるらしい。駐輪場は1日60円で、さらに回数券を買っているので実際のところ1日あたり50円しかかからない。2日や3日でどこかへ移動されるわけでもなし、今日は取りにいかないことにした。

起きた時点ですでに典型90問が投稿されていたが、今日はそんな短くなる気がしなかったので、放置して布団でなろうを読んでいた。午後4時半になって布団から出て活動を開始し、まずはその典型90問を通しておいた。

ダブリングで解く方法と周期を検出して解く方法の2つが考えられる。このうち周期を検出する方は似た問題を以前ゴルフしたことがあった。確認するとちょっと縮む余地を見つけたので、そちらも更新しておいて、ほとんど同じコードで今日の問題も解いた。

atcoder.jp

と思っていたらPerlに抜かれてしまった。いろいろ奮闘した結果、桁和と元の値の和を求める部分がうまくいって縮んだ。桁和を求めるのは、単純に考えればeval s/\B/+/grとなる。あるいはmap 1..$_,/./gでもできることはできるが、長さも同じだし、今回は使わなかった。さて、s/\B/+/grの部分であるが、これをs//+/grにすると文字列の先頭と末尾にも+がくっついてしまう。このうち先頭は問題ないが、末尾につくのが困りどころ。そこでs//+/gr.$_としてみると、ちょうど末尾の+を使って元の値との和も一緒に求められるようになった。ここが最短を奪取したときの更新ポイントだった。

今日のサークル解説会の準備をする。yukicoderが午後8時スタートになった影響で、こちらも開始を1時間早めて午後7時スタートにしている。先週もずれたし、どうやら来週もずれそうだ。毎週金曜日に活動する上での宿命と言えよう。とりあえずF問題のスライドを作って、ほかの問題をどうしようか悩んでいたところ、祖母から仕送りが届いた。

仕送りの片づけをしていたところ解説会の時間になってしまったので、今週は僕のF問題と、もう一人E問題を解説してくれた人の発表だけになる。解説会には結局3人しか来なかったが、予定通り行った。

2021/06/04 定例会 | puzzleknot 公式サイト

終わってからしばらく院試について調べていた。まだ何も決めていないし考えようともしていない。困った……。出願までは残り1か月くらいしかないようだ。

yukicoder 298に出た。5完。

yukicoder contest 298 - yukicoder

Aはよい。BはNが偶数なら明らかで、奇数の場合は3 6を先頭に入れたりしておけばよい。N\le 5の場合は、N=1ならOKで、それ以外は構築不可能。Cは素因数ごとにカウントして最大値を求める。カウントについては、エラトステネスの篩っぽくやれば十分間に合いそうで、実際最大ケースでも間に合う。

Dを読んだがわからなかったので、solvedが多かったFに移った。大きな値と小さな値に分けて全探索することを思いついてしばらく格闘していたが、最大ケースとして10^{10}ではなく10^9を使っていたので2回ほどTLEを出してしまった。ここで気づいて、全然間に合っていないことが発覚。さらに奮闘して、なんとか手元では間に合うくらいの速さになったが、yukicoderのジャッジでは間に合わないようだったので、もうちょっと頑張る必要が出てきた。最終的に、小さな値は43までをmapを使って全探索し、それ以降は5重ループで全通り試すことで3500msくらいで通った。43まで探索するという根拠は、44\times 45\times 46\times 47\times 48\times 49\gt 10^{10}であるから。

Dに戻った。popcount(ab)%2には特に良い性質はないらしい。ここで、1からNを2つに分割するとき、まず数列Xにすべて入れておいてからYに要素を移し替えることを考えて、このときのf(X)-f(Y)の差分を見ることにした。試しに計算してみると、どうやら差分は要素ごとに独立な値になるらしい。a!=bなるabについてpopcount(ab)%2==0であったとすると、abがそれぞれXからYに移動する際にf(X)-f(Y)から1ずつ引かれることになるわけだが、まずf(X)から1引かれて、さらにabが両方Yに所属した段階でf(Y)が1増えると考えると納得できる。a==bの場合もちょっと注意すれば同様にできて、結局差分のうちいくつかを選んで足し合わせることで目的の値が得られるか?という部分和問題になった。

Eに進んだ。しばらく実験していると、1が書かれたマスが互いに影響しないなら綺麗な形になることが分かったが、影響し合うときにどうなるかが全然わからない。解けずに終わった。Gは見もしなかった。

upsolveはせず、そのままECR110に出た。全完。

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

Aはよい。Bは偶数をより先頭に持ってくるのがよくて、このときもともと互いに素でなかったペアに加え、偶数と奇数のペアであって互いに素であるようなものの個数だけ良いペアが増える。Cは...010...101に分けて数えるが、...???はどちらにもカウントされてしまうので引いておく必要がある。ちょっとインデックス周りが怖かったが、サンプルを合わせたら通った。

Dはセグメント木のように自分の子の値から自分の値を計算する。セグメント木の中間ノードごとに処理を変える必要があるので、自分でベタ書きした。普段使うセグメント木のインデックスと入力される文字列のインデックスでちょっと混乱したが、入力された文字列を全部反転して意味も反転してやるとうまくいった。

Eは、LCAをダブリングで求めるときに使うような親の列を動的に構築する。これは11+11+1+2、……のように作れる。この上で、クエリに答える際はどこまで使い切ったかを探し(二分探索してもよいが、BIT上の二分探索のようにすることでlogが1つ落とせる)、そこから1歩ずつ降りていくようにして使っていく。毎回1番上まで登ってしまい1TLE。

Fは難しい。文字列abについて、それぞれに含まれる文字を多重集合として見たときに一致していない場合はf(a,b)=1337。さらに文字列がすべて異なるという条件からa\ne bなのでf(a,b)\gt 0で、しかも文字列を両方ソートしてしまえば必ず一致するからf(a,b)\le 2となる。よって、f(a,b)=1となるような組だけ数え上げればよい。L=|s_1|として\min(n^2 L,26nL^2)くらいの計算量で解いた。

n^2Lのほうは簡単で、すべてのペアに対して先頭と末尾からできるだけ一致させた上で、残った真ん中の部分を考える。ペアのどちらかでその部分がソート済みであればよい。

26nL^2のほうは難しい。ローリングハッシュを使った。各文字列に対してソートする区間を決め打つと、それより前とそれより後ろは適当に前計算できる。ソートする区間については文字ごとの出現頻度を管理し、同じ文字が連続するハッシュを累積和などで計算しておけばよい。ここに定数倍の26がかかっている。そのようにして1つの文字列から複数のハッシュを作り、その他の文字列の(区間をソートしない)ハッシュであって今作ったハッシュたちに含まれるものの個数を数える。f(a,b)=1ならばaをソートするかbをソートするかのどちらか一方でしか作れないから、重複を気にする必要はない。

ローリングハッシュは、素数1000000993を使い、基数はランダムな値2つを使用した。一発で通ってハッピー。

今日の典型90問が大幅に縮んでいた。実験してみたところ、毎回周期を検出する必要はないらしく、どこかで必ず周期4735のループに入るようだ。では毎回K \bmod{4735}を使用すればよいかというとそうでもなくて、ループに入る前に終わってしまうのはマズい。4735の倍数を順に試していくと、33145でACできた。その方針で縮めていくと何とか現在報告されている最短を更新することができた。

午前6時就寝。

06/05(土)

午後2時起床。今日の典型は全然わからなかった。まともに解けないと思って検索してみると、そのものズバリなライブラリが出てきた。

Offline-Dag-Reachability(DAGの到達可能性クエリ) | Luzhiled’s Library

さて、今日はいよいよ自転車を回収しに行く日だが、その前に生協の弁当を受け取ったり典型90問を通したりしておきたい。ということで出かけるのを待っていた。生協の弁当は早くに届いたが、典型90問の公開はかなり遅かった。なろうを読みながら待っていたが、結局出かけるのは午後7時過ぎになってしまった。

地下鉄に乗って仙台駅まで出る。水曜日に入った本屋は、今日はラノベコーナーにたどり着けた。よくよく考えるとこのコーナーは水曜日も存在して、ただ見つけられなかっただけにも思える。その後別の本屋もはしごしてラノベの新刊を買いそろえた。大学生協で注文しようと思っていたが、せっかく本屋に来たので、という感じ。また、水曜日に言及した米澤穂信さんの新刊も購入した。その後食事して駐輪場に向かった。

駐輪場に入る際、管理人さんがいたので挨拶しておいた。それが効いたのかわからないが、延滞分の駐輪券を1日分おまけしてもらえた。非常にありがたい。浮いた1日分を使って別の駐輪場(24時間営業)に移動し、そこに止めて今日もゲーセンに行った。

今日は「小悪魔の遊園地」でSSSを出した。追加されたときにSSSを出せなかったので敬遠していたが、やってみると今日はかなり上手く、すぐに乗った。特に中盤の意味不明な鍵盤地帯が意味不明ながらあんまり崩れなかったのがよかった。基本的に四鍵のように押そうとしているが、手の位置がずれることもあって実際は押せていない。グチャっとなっている。

今日はよくわからない鍵盤がうまい日かと思ってGiselleを選曲してみたが、こちらは全然ダメ。GCJR3もあるので早々に帰宅した。今日買った本を写真に撮ってツイート。

GCJR3に出た。Abdで183位。

Code Jam - Google’s Coding Competitions

通過可能性はないと思っていて、そんな精神状態でA問題を読んだので、即座に逃げ出したくなった。文字数が偶数の場合が難しいが、同じ文字が4個以上あれば2個組にして消してもよさそうだと思ったのでそのようにし、さらに2個以上残った文字を組にして消すかどうかをbit全探索した。0の扱いなどでミスっていたが、文字数8の入力を全通り試して愚直解と比較してデバッグしたら通った。

bはこれまたbit全探索。\binom{6}{3}^6くらいになる。dは座標圧縮後の数列を全探索して、そこでいったんゲームをプレイし、その結果に応じて組み合わせを使い元の値を復元する感じ。

このあたりでもうわからなくなったので諦めてしまった。Bは基本的に最大流で、うまいことコストを設定することで特定の位置から順に使われるようにしたり、あるいは四角形が存在する限りそれをflipし続ける、というアルゴリズムでも構成できるらしい。どちらもよくわかっていない。cは実は全探索できる、らしいが、こちらもあんまり考えていない。

へのkさんが25位で通過していてすごい。本当に強い。

布団にダイブしてなろうを読んでいたら寝落ちしてしまった。午前2時半だった。

06/06(日)

午前7時、目を覚ます。午前9時くらいまでなろうを読んで、また寝た。

次に目を覚ましたのは午後6時だった。yukicoderでお誕生日コンテストが開催されているようだが、見送ることにした。昨日のECR110はシステスが終了しており、全問通って8位だった。

昨日の典型90問は、昨日の時点でRubyの120Bが報告されていた。64個ごとに分割する以外の解法があるのだろうと思って解説の公開を待っていたのだった。公式解説自体は64個に分割するものだったが、drogskolさんが別の解法をツイートしていた。

i8vV5r - Online C++0x Compiler & Debugging Tool - Ideone.com

昨日はうしさんのライブラリを参考にして解いたため、(A_i,B_i)というクエリを処理するときにはdp[A_i]|=1<<iとしていた。そうではなくdp[u]|=1<<uとし、すべてのペアについて問題を解くことにすれば、頂点番号uに対しては1..uに対応するbitしか保存しなくてよいため、必要なメモリが\frac{N^2}2くらいになるらしい。またこれを多倍長整数で扱うとより簡単になるようだ。確かにRubyで書くとTLEもMLEもしなかった。その方針でちょっと頑張ってみたところ、何とか119Bを達成でき、最短を奪取した。

2時間くらいなろうを読んで、午後9時からABC204に出た。全完9位。

A問題はif文を書くのは長そうだったのでちょっと考えていた。どうやら(-x-y)%3で良いらしい。Bもdcだろうなとは思いつつ、こちらは時間を気にしてとりあえずRubyで書いた。CからはC++を使用した。Cは各点からBFS。Dは大体半分になる部分和を探せばよい。

Eは難しいが、コストが下に凸っぽいので三分探索できると思い、書いた。しかしWA。コスト関数t+C+\frac{D}{t+1}微分してみると1-\frac{D}{(t+1)^2}になるためt=\sqrt{D}-1で最小になるらしい。これを直接計算し、その周り10個くらいを調べたら通った。Fは行列累乗。

Eはfloorを取ると傾きが0になる箇所が出てきて三分探索できないらしい。逆に、floorを取らない値で三分探索すれば通る。floorを取る・取らないでargminが変わらないことも簡単に証明できるが、一応TLで見た言及ツイートのリンクを貼っておこう。

コードゴルフ。Aはよい。Bはdcで書いたが、コンテスト後に縮められた。数列の要素数が少ないので、毎回zを使ってチェックしても間に合う。dcのテクがまだあまり発達していないころはループといえばこの形だったが、今は105オーダーのループを回すためにそれ以外の方法がいろいろ得られており、そちらに気を取られてしまった。

CはPerl。2200ms超えで全然間に合っていないようだった。mapで書いていたのをforに直しつつ別の個所も弄って通したのだが、コードは少し長くなってしまった。ふと気づいて答えを保存する変数を$\から$%に変えたところ、たった+2Bでかなり速くなってくれた。それでも2050msほどだったが、このくらいなら十分実行時間のブレで説明がつくということは知っていたので、同じコードを何回か投げて通した。$\は基本的に文字列を保存する変数なので、数値としてインクリメントしたりするのは遅い。DはRuby。EFは手つかず。

CF #724 div.2に出た。5完52位。

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

Aから難しかった。僕は条件を満たすか数列の要素数が300を超えるまでめいっぱい要素を追加する方法で解いたが、pretestで1400msくらいあってかなり不安だった。システスも問題なく通ってくれたが、冷静になって考えるともっとちゃんと解ける。まず負の数がある場合は数列の要素がどこまでも大きくなるので必ずNOで、負の数がない場合は数列全部のgcdを取り、その倍数を現在の最大値まで埋めておけばよい。また数列の要素の最大値が100以下なので、もっと単純に0..100を出力するだけでも解ける。

Bは全探索。答えは必ず3文字以下になる。Cは難しかったが、各文字列に対して文字列全体の'D'の個数と'K'の個数の比で分割しなければならないことに気づくと解ける。具体的には、各prefixに対して'D'の個数と'K'の個数の比を計算し、mapでカウントすればよい。

Dは毎回2要素しか増やせないので、中央値としてはすでに存在する要素のうち1個までしかずれることができない。逆に追加する値の絶対値を十分大きく取っておけば、以前に中央値として出現した値以外を考慮しなくてよくなる。よって、その以前に中央値として出現した値をsetなどで管理し、直前の中央値と現在の中央値の間に別の要素が挟まっていればNOとなる。

Eは面白かった。まず0は盤面のどこにでも置ける。0を置く場所を決定すると、1を置く場所も決定してしまう。なぜなら、1の隣には0がなければならず、また逆に0の隣でまだ決まっていないマスには1しか置けないからだ。1を置く場所が決定すると、なんと2を置く場所も決まる。これも先ほど同様、2の隣には1が存在しなければならないことと、まだ決まっていないマスには2以上の値しか置けないため、特に1の隣には2しか置けないことからわかる。このようにして、0を置く場所を決定するだけですべてのマスが決まってしまう。つまり、現在未定のマスから0を置くマスを決める場合の数を答えればよい。1点、注意として、0を置くマスは必ず1つ以上なければならない。

Fは全然わからなかった。実は後手必勝らしい。終了した盤面を適当な位置から切り開いてみると、おおよそABABAB_ABA_Bのような形になっていなければならない。つまりABは合わせて偶数個あるので、最後に行動できたのは後手、というわけだ。とはいえこれが分かったところで、何をどう数え上げるのかについてはいまだわからないまま。

週記(2021/05/24-2021/05/30)

05/24(月)

先週の週記を投稿してから寝るまでの話。

サークルの継続関係の作業を一気に終わらせることにした。大学に提出する書類自体は昨年度も同様のフォーマットで作成したのでそちらから引き写してくれば済む。今年は去年のものがさらに洗練されており、スプレッドシート1つにすべての書類がまとまっていて、同じ内容を1回記入すると、別の欄にも自動で反映されるようになっていた。かなり便利だった。

問題は、サークル活動に使用しているサービスのアカウントの整理で、具体的にはGoogle DriveとSlackからすでに在籍していない人のアカウントを解除する作業があった。できるだけ余計な情報を入手しないという思想の元、サークルメンバーのメールアドレスは入部届にしか書いてもらっていないため、過去数年分の入部届の記録をひっくり返して誰がどのアカウントの持ち主か特定する作業に邁進した。とはいえ、ほとんどのアカウントは本名が表示名になっているので、思っていたよりはすんなりチェックできた。最後に対応が取れなかったアカウントが数個残ったので、しばらくSlackで持ち主を探してみて、現れないようであればこれも解除する。

「レーゼンシア帝国繁栄紀」を読んだ。古本を大量に買ったときの1冊。設定は良さそうだったが、内容はあまり面白くなかった。ひょんなことから帝国皇帝に成りすまして政務を執ることになった主人公が、知識と持ち前の機転を活かして活躍する話。ラストシーンはラノベ冒頭のカラーイラストにもなっていて、それを見る限りは騎士団を鼓舞する勇猛な主人公、という感じだったので楽しみにしていた。しかし本編を読んでみると、別に何かの合戦というわけでもなく、帝都の公園で一騒動巻き起こすために嘘の演説を行うというシーンだったらしく、かなりがっかりした。

布団に入ってから、先週の週記にTCB36のことを書くのをすっかり忘れていたことに気づいた。日付としては05/21(金)、日記を書いてから真夜中に参加したもので、入力の受け取りミスで理論値を逃してしまった。長方形領域の与えられ方が、A B C Dで「左下の点(A,B)と右上の点(C,D)」を表すと思い込んでいたが、実際は「A<=x<=BかつC<=y<=Dなる点」の意味だったらしい。それ以外問題に関しては何も覚えていない。30分くらいで全完した(負け惜しみ)。

布団で少しなろうを読んで、午前11時半就寝。寝る直前に、今日の典型90問のコードを書いて、問題が追加されたら自動で提出されるように設定しておいた。

午後6時くらいに目を覚ました。典型90問の問題自体は追加されているものの、コードが提出されていない。パソコンがスリープしてしまっていたようだ。失敗。とりあえず再度出しなおした。これはRubyのコードだったが、Perlで書いてみるとさらに縮んだ。Rakuではもっと縮むはずだったが、実際にはTLEしてしまったので、現在はPerlのコードが最短となっている。

そのあと布団に戻ってちょっとうつらうつらしたりなろうを読んだりしていたが、本格的に寝ることはできず、午後9時半になってしぶしぶ起きた。食事してシャワーを浴び、1月前のサークルバチャのupsolveをしたが、出したコードが落ちてしまった。もうすぐこどふぉのコンテストが始まるので、放置して参加した。

この回のD問題は解説自体もかなり難しかったが、理解は済ませている。残りは書くだけなので、そのうちupsolveしたい。

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

CF #722 div.1。4完51位でレートは2821→2839(+18)、highest。

https://codeforces.com/contest/1528

Aは簡単。直感的には、木を2部グラフと見て、それぞれ最大値を取る点と最小値を取る点に分けることが思い浮かぶが、簡単な反例が構築できた。[0,1]-[1,1]-[1,2]。冷静になると木DPでよい。

Bはちょっと怯むが、しばらく実験してみると、外側に同じ長さのペアをたくさん重ねてより小さい値の通り数に帰着するか、全てを同じ長さのペアで埋めるしかない。具体的には、f(N)Nに対する問題の答えだとすれば、f(N)=d(N)+\sum_{i=1}^{N-1}f(i)。ここでd(N)Nの約数の個数を表す。

Cは、Soroushの木を元に考えれば、求めるクリークの頂点は全てSoroushの木における根からある頂点へのパスに乗る。よってSoroushの木でdfsをし、そのパスを全探索する。パスを1つ固定すると、Keshiの木に関する条件は、選んだ頂点たちが互いに親子関係にないということだから、Keshiの木において深いところにある頂点から貪欲に取ってよさそう。実際には毎回パスの頂点を全部見るわけにはいかないので、暫定的に頂点を選んでおいて、より深い場所に頂点があったらそれに入れ替えるということをすることになる。ある頂点が別の選んだ頂点の部分木であるか、またある頂点の部分木に別の選んだ頂点が含まれるか、ということは、Keshiの木でオイラーツアーした列を区間setの遅延セグメント木に乗せれば判定できる。さらに、今見ている頂点が選んだ頂点のうちどれの部分木に含まれているかという情報も、区間setの値を頂点番号にすることで得られる。

Dは、dijkstraの頂点に到達時刻\bmod{N}の値の情報も持たせたくなるが、ちょっと考えるとできる限り早く着いてから待つのが最適であることがわかる。よって頂点数N、辺数N^2dijkstraN回行う問題に落ちる。最も内側のループでNによる剰余演算が行われるとかなりパフォーマンスに影響するらしく、僕は何となく安全側に倒してif文を書いていたのでpriority_queueのlogをつけても900msくらいだったが、そうでなければO(N^2)dijkstraをした人でも2000msを超えたりしていて、かなり怖い。

Eに1時間くらいかけたが、解けなかった。そのままコンテスト終了。

「レーゼンシア帝国繁栄紀」の2巻を読んだ。ここで打ち切りらしい。相変わらずあまり面白くなかった。伏線回収とはいえ、行き過ぎて主人公が最初から全部わかっていたという結論になってしまい、主人公視点で綴られてきた話との印象が合わない。しかし、こう言語化すると、よくある話のように思えるから、この作品が面白く感じられなかった理由としては弱そう。結局打ち切りだということをわかって読んでいるのが一番ダメだった。同様のことを以前の週記でも言及したなと思い探したところ、案の定あった。人はそう簡単に変わらない。

「打ち切りになってしまった」という情報を念頭に作品を読んでもあまり楽しめないということに気づいた。

週記(2020/11/23-2020/11/29) - kotatsugameの日記

E問題のn=3における答えを教えてもらい、しばらく格闘していたら、解けた。コンテスト中の考察には間違いがなく、数え上げのミスだった。解法をここに書こうとしたが、さすがにちょっと長すぎたため個別に記事を立てた。

kotatsugame.hatenablog.com

コンテスト中のコードは、上の場合分けのうち最後のケースの計算が誤っていたようだった。

コンテスト直前に解いて落ちてしまっていた提出を修正し、通した。

https://codeforces.com/contest/1019/submission/117265532

これもかなり難しい。与えられた点から3点選んで三角形の面積がSになるような組を探せ、という問題で、解法は2点決め打って3点目を探索。この探索が非常に頭が良い。決め打った2点P_iP_jの法線ベクトルとしてP_j-P_iを反時計回りに90度回転したもの\overrightarrow{n_{i,j}}を考えると、三角形の面積は、その法線ベクトルと3点目の位置ベクトルの内積について1次関数の関係にあるらしい。頑張って計算すると分かったが、かなりびっくりな性質。

計算についても一応書いておく。a(\vec{a})=P_ib(\vec{b})=P_jc(\vec{c})の3点によって作られる三角形の(符号付き)面積を求める。\vec{n}=\overrightarrow{n_{i,j}}とおく。点cから直線abに下ろした垂線の(符号付き?)長さをhとすると、tを変数として\vec{c}-h\cdot\vec{n}=t(\vec{b}-\vec{a})+\vec{a}が成り立つ。両辺に\vec{n}内積として掛けると\vec{c}\cdot\vec{n}-h|\vec{n}|^2=\vec{a}\cdot\vec{n}。よってh=\frac{(\vec{c}-\vec{a})\cdot\vec{n}}{|\vec{n}|^2}

よって定数をkk'としてまとめるとS=\frac 1 2|\vec{b}-\vec{a}|h=k(\vec{c}-\vec{a})\cdot\vec{n}=k\vec{c}\cdot\vec{n}-k'と書ける。

従って、点を法線ベクトルとの内積の値によってソートしておけば、二分探索で3点目を探せるようだ。このソートの方法も頭がよい。考えられる法線ベクトルをすべて列挙し、偏角ソートしておく。それを順番に見ていくとき、ある点P_iP_jについて順番が入れ替わる瞬間というのはこの2点によって作られた法線ベクトルが出現した瞬間に限られるらしい。このことは\overrightarrow{n_{i,j}}\cdot \overrightarrow{P_i}=\overrightarrow{n_{i,j}}\cdot \overrightarrow{P_j}であることと法線ベクトルを偏角ソートしていることからわかる。

日記を書いた。texにおけるvecoverrightarrowの使い分けが難しい。問題の解説を念入りに書いていたら1日分で5000文字にもなってしまった。マズい。

布団に入ってから新しいなろうに手を出した。午前11時半就寝。

05/25(火)

午後6時半起床。

典型90問が投稿されていたので提出した。問題自体は昨日寝る前に確認していて、ほとんど同じ(に見える)問題が記憶に強く残っていたので、これもすぐわかった。

kotatsugame.hatenablog.com

寝ている間に縮められていた問題と合わせてコードゴルフ。前者は勝てたが後者は負けている。3時間くらいずっとバトルしていた。PerlのUnion-Findで新手らしきものが出た。配列の代わりに${-1}${-2}……を使用するというもの。それはそう、という感じだが、結構効いた。ほかにもPerlでUFを書いているコードを探して睨んでいた。

atcoder.jp

TCB36は理論値を逃してしまい、10位以内には入れなかったが、代わりに特別賞が当たった。運が良い。僕が初めて参加したTCB31からこれまで毎回賞金・賞品を得られていて、Streakは何とか続いてくれたようだ。

布団に戻って3時間くらいなろうを読んでいたら、先ほど縮めた問題がさらに縮んだと報告された。Vimのコード。慌てて起き上がりパソコンに向かった。削る余地のあるコマンドは少ないように見えるが、Vimのコマンドには1文字のものも多いため、ちょっとの隙が命取りになる。実際、しばらく試行錯誤していたら相手と同じ長さのコードが完成してしまった。非常に悔しいのでさらにごちゃごちゃしていたところ、テストケースハックができて1文字縮んだ。

昔の週記をちょっと読み返していた。当時、自分の裡に激しい感情があったことは覚えているが、もう

寝る前にと思ってメールを確認すると、インターンの面接日程についての話が来ていた。前回1回目の面接の結果、2回目の面接に進ませてもらえるようだ。会社のCEOが出てこられるらしい。特に対策する気もない以上なるようにしかならないので、失礼のないようにだけ心がけておきたい。

布団に戻って昨日寝る前に読み始めたなろうを読んでいた。およそ6時間くらい読み続けていた。非常に面白い。

https://ncode.syosetu.com/n5534co/

午前11時に寝た。

05/26(水)

午後6時半起床。

今日の典型90問を通しておく。かなり簡単だし、あんまり縮まなさそう。実際、すぐに得られる46B解から更新がない。おそらく提出時間の関係で誰かに負けているだろう。

すぐに布団に戻ってなろうを読み続けていたが、今日は皆既月蝕なので、せっかく見えるらしいし見ておこうと思う。下だけジーパンに着替えて、上はパジャマにパーカーという格好。後ろの裾からパジャマの緑色が見えていてなんとも言えないが、まあすぐ戻るだろうと思って出た。

月を探して少し歩くと、道端にぽつぽつ人が立っている道路があった。確かにこの辺りは満月がよく見える。僕が出て行った時間はすでに蝕の最大であり、もしかして月がどこに行ったか分からない!?と思っていたが、全然そんなことはなかった。左上のあたりはいくらか光が当たっていたし、そうでなくとも全体が紅くぼんやりと光っていて、これを見逃すことはあり得ないだろう。

スマホで写真を撮ってみた。4倍くらいにズームして夜空にレンズを向けた。シャッターを切ってから撮影が完了するまで、これはその時々で発される効果音によって判別しているが、が非常に長かった。露光時間が長いことが関係しているのだろうか、それとも撮影自体は一瞬で、光量の補正処理に時間をかけていたのだろうか。びっくりしてかなり手を揺らしてしまったが、写真になってみるとそれほどブレているようには見えない。いや、僕が4倍ズームの影響だと思っているぼやけは、実際にはこの手ブレによるものだったのかも。

写真だと紅さがより感じられるように思える。非常にエモーショナル。レイリー散乱という言葉を初めて聞いたのは、何かのクイズ番組だったと思う。

しばらく見ていると雲に隠れてしまった。蝕の最大を目の当たりにできたのはかなり幸運だったらしい。周りの人たちはそそくさと帰っていったが、僕はしばらく残っていた。せっかくだし月が半分くらい光を取り戻すまで待って地球の影が丸いことを見てやろう、と思っていたのだが、よくよく調べると月が地球の影を脱出するのにはまだ1時間半ほどかかるらしい。そんなには待っていられない。また雲から顔を出した月を最後にもう一度眺め、帰った。

PerlのUnion-Findに、昨日とは別の新手が出ていた。

atcoder.jp

pop$_[0]を使い分けることで、1つの関数でUniteとFindの両方を実現してしまっているらしい。すごいコードであると感じる。ただ、1回Uniteするだけならば直接書いたほうが短い……はず。試していない。PerlのUnion-Findはいろいろ方法があって、local$_を利用してみたり、ちゃんとmy$x=popとしてみたり、どれが短いかは直ちにはわかりにくい。

布団に戻ってまたなろうを読み続ける。途中SRMがあったが、前回のEasyの問題文がひどかったこと、またなろうが面白すぎて読むのが止められないことの2点をもって見送ることにした。しばらくしてSRMを終えた人たちがTLに現れたが、その感想を聞く限り今回はかなりまともだったらしい。

明日は木曜日で、毎週のゼミがあると思い、生活リズムをどうしようか悩んでいたが、先週お休みを言い渡されていたことを思い出した。これで思う存分生活を破壊できる。午前10時まで読んでいた。

途中でTCB34のアマギフ1000円分が届いた。

午前10時、寝落ちした。

05/27(木)

午後4時起床。今日もまた1日の初めに典型90問を通す。今日は半分全列挙で、そうやすやすと短くはならないから、適当にC++で書いておいた。

月曜日にほとんど終わらせていたサークル継続届に関する作業の、最後の詰めを行う。継続届に関する顧問の先生のチェックは、月曜日に書いてすぐ依頼したので既に終了していたが、実際のところは携帯電話番号がまだ不明な人がいる。ひとまず連絡先を持たないということにして、本人に確認を取ろうとしていたが、結局数日たっても音沙汰なしだった。仕方ないのでそのままにして、今日の日付に直した継続届を大学に提出した。次に、誰のものかわかっていないアカウントについて。それぞれSlackでDMを送ったり、アカウント名を公開して身に覚えがあるか問いかけてみたものの、どちらも自分のものであるという人が現れなかったため、これも解除した。これでスッキリ掃除が完了し、現在残っているアカウントはすべて持ち主との対応が取れている。取れているはずだ。

今日の典型がRubyで縮められていたので、自分もやってみる。半分全列挙なのであまり短くなるようには見えない。combinationbsearch_indexなど、便利なメソッドはたくさんあって、そういうものを利用するのが一番短くなることは試行錯誤の結果わかっているものの、やはり長いメソッド名が気に食わない。あまり縮む余地はなさそうだが、何とかひねりだして現在の最短を持っている。

布団に戻ってなろうを読んでいた。午後7時くらいに何とか学食に行こうとしたが、家を出てみると雨が降っていたので今日は行かないことにした。閉店時間的にもギリギリで、自転車で行くなら間に合うだろうが徒歩だとちょっと厳しいのもあった。

布団に戻ってまたなろうを読んでいると、明日のyukicoderが1時間早まるという情報が流れてきた。こちらの解説会と被る恐れがあるため、前日で申し訳ないが30分早め、午後7時半から行うことを周知した。

PythonのコードがCythonで縮められたので、起き上がってパソコンの前に向かう。Cythonを適用するとわかっていればこちらも同様の変更をすればよく、多少手間取ったはものの取り返せた。Cythonの実行環境が手元にないのがちょっと辛いが、ほとんどPythonと同じでfor文を短縮することにしか使っていないため、まだ何とかなっている。

布団に戻ってなろうを読み続けていたが、午後11時半くらいに寝落ちした。

05/28(金)

午前3時くらいに目を覚ます。この日は午後5時までほとんどずっとなろうを読んでいた。

昨日の典型がさらに縮んでいるらしい。もう全然わからないので、放置。

午前10時くらいには、今日の典型問題を解いて提出するスクリプトを書いた。今日の問題は非常に簡単で、制約もかなり緩い。最初はRakuがよいと考え、そのコードを提出するよう設定していたのだが、しばらくしてからdcで書いたほうがよほど短いことに思い当たる。慌てて書き直した。25Bで、午後2時少し前に無事提出されたようだ。問題なくACでき、全体で2番目のACだし、それ以降縮んだという報告もないので、最短は取れているだろう。

午後5時になって、眠気に耐え切れなくなった。解説会が2時間半後にあるが、かなりどうでもよくなってしまい、自分が起きられなかった時のことをホスフィンに託して寝た。そこから30分おきに目覚ましを設定しており、何とか午後7時に布団から這い出ることに成功した。

解説スライドの用意も何もできていない。幸い今日も熱心なサークルメンバーが2問くらい発表してくれるようなので、最悪それだけでもよいか、と考えていたが、思い直して簡単な問題を1問だけ解説することにした。スライド4ページを適当に書いた。

解説会は、前日に30分前にずれ込んだものの、いつもと変わらない数の参加者が集まってくれてありがたかった。問題なく終了し、そのあとの処理、つまりスライドの公開作業なども終了。ホスフィンには解説会の代理を頼むならもっと早くに連絡してほしいと怒られてしまった。かなり申し訳ない。勝手になろうを読んで生活リズムが限界になっていた。

僕が少しだけ寝ている間に、昨日のCythonのコードがさらに縮んでいたらしい。これはもう全然わからないため、諦めの境地にある。

またもう1つ縮められたコードがあって、そちらはかなり面白かった。いや、自分のコードが縮められているので悔しさのほうが大きいが。

atcoder.jp

odというコマンドを使って、入力をなんらかの数値にマッピングする。これをdcで加工することで望む出力を得る。以前のコードはRubyで同様のこと、つまり入力を適当な数値にして加工する、を行っていた。同様の手法で得られた最短コードは他にもあるが、そちらはどうも縮みそうになかった。

yukicoder 297に参加した。7完。

yukicoder contest 297 - yukicoder

Aはx=0x=dの場合のみを考えればよい。これを式に起こしてみるとdadbだった。意味を考えれば当たり前で、d min(a,b)と書ける。Bはよくわからなかったのでいったん飛ばす。Cはまあ、できる。未証明AC。Dもわからなかったので飛ばした。Eは行列累乗やるだけ。

FはAを降順ソートしてdp[N][M]動的計画法だろうというのはわかるが、遷移がちょっと難しそう。2個組にして遷移したいが、できない。ここでよく考えると、奇数番目にある要素を選んだらソートした数列Aにおける次の要素も必ず選ぶことになる。選んで損しないからだ。これで遷移も定数時間で書けてハッピー。気を使ってdp配列を使いまわそうとしたが、2個先の配列にアクセスする必要があることに気づいたため、泣く泣く書き直した。

Bに戻る。種類数がkの通り数を考えていたが、これは全然ダメ。そもそも着眼点が違っていて、1からNのそれぞれの値が得られた数列に含まれるかを見ればよい。これもいわゆる主客転倒か。これがすぐに見えなかったのは反省。Dは得られていた式をWolframAlphaに投げたら閉じた式になった。

Gは、パスグラフのみを考えればよいとして、一番先頭に1e9-1を置いて、K-1番目に-1e9を置き、あとは周期Kで同じ値を繰り返すことにしたら通った。これは(N-1)%K==0のときだけNoになる。しかしコンテスト後に落ちてしまった。解説を読むと信じられない場合分けが書いてあって、かなり信じられなかったので、落ちているのも今は放置することにした。

Hは解けなかった。マージテクを思いついたと思って書いたが全然答えが合わなかった。

CF div.2があったが、見送ることにして、日記を書いていた。なろうをずっと読んでおり、溜めてしまっていた。

その後Amazonでお茶と黒コショウを注文し、GCJ Tシャツを受け取る手続きも済ませた。GCJ Tシャツのサイズ表記はSM、MD、LGなどと書いてあって何のことかよくわからなかったため、胸囲と身長の対応など調べてSMにしておいたが、どうやらこれらはSMall、MeDium、LarGeの意味らしい。これまでは確かMサイズを注文していたので、間違えてしまったか?

午前2時、布団に入ってなろうの続きを読んだ。そのまま午前10時まで読み続け、明日のことを考えて就寝した。

05/29(土)

午後3時と午後4時に目覚ましをかけていて、午後4時のほうで起きる。生協の弁当を受け取りたい。起きた時点ではまだ到着していなかったようだが、うつらうつらしていたらすぐに届いた。受け取って、そのあとちょっとなろうを読んだが、さすがにまずいと思いなおして午後4時半に寝直した。

午後7時半起床。眠すぎたのでしばらく布団でなろうを読んでいた。ARCまで残り40分くらいになったあたりで出て、食事した。その後今日の典型90問を解いていた。何をさせたいかはわかっているはずだが、実装が悪いのかクエリ回数が全然足りていない。

午後9時からARC121に出た。

NOMURA Programming Contest 2021(AtCoder Regular Contest 121) - AtCoder

3完189位、パフォーマンス2329、レートは2761→2724(-37)。DとEの両方を解けるべきで、解けなかった結果。しかし今はなろうが面白すぎて特に思うこともない。

Aは、xyそれぞれで大きいほうから2個と小さいほうから2個を取り、その高々8個の点の組を全探索した。ちょっと慎重に解いたが、問題なくAC。

Bは、異なる体色の犬のペアの個数が小さいことにはすぐ気づいた。しかし、RGGBのペアを考えているとき、なぜか2つのGが同じかわいさを持っていると考えてしまって、RBGGに組みなおしたほうがよいと勘違いしてしまった。これで2WA。逆に、RGGBをそれぞれ計算するときに同じGの犬を使ってしまう場合を考えなくてよいことはすぐわかった。

Cはよくわからない。1手で転倒数を1少なくできる場合はその動作をしてよくて、できない場合は4手使って転倒数を2少なくするか、5手使って転倒数を1少なくするかのどちらかをすることになりそう。前者はよいものの、後者が頻発するとちょっとまずい。操作回数の制約から、平均的に2手で転倒数を1少なくしたいからだ。しばらく考えていたがよい方法が思い浮かばなかったので実装したところ、フラグの管理ミスで1WAしたが通った。よくわかっていない。

そのあとsolved数を見てEに行った。自分の子でまだ決まっていない頂点の個数を持ち2乗の木DPをすることを考え、そのあとずっと格闘していたが、コンテスト終了間際に愚直なコードを書いたら合わないことに気づいてしまって、絶望。そのまま解けず終了した。

Eは解説の1行目だけ読んだ。1行目からよくわからなかったが、逆順列を考えると自分の子についての条件になって扱いやすくなるらしい。確かに、問題の定義をそのまま使っていたが、うまく木DPできなくて苦労した。Dは、一応問題分だけ読んでいて、TLで0を増やすということを耳に(目に)した。これは天才。

今日の典型90問の続きをする。させたいことというのは、黄金分割探索だろう。クエリの様子を出力してみると、どうやら途中から幅1で探索をしてしまっているらしい。Wikipediaで調べた通り、x1<x2<x3を持った状態で次に調べる箇所をx1+x3-x2に設定していたが、最初に区間黄金比で分割する際の誤差が影響してどんどん変わってしまっているようだった。ならば、ということで区間の幅を広げるような補正をかけてみたが、まだクエリ回数は指定された15回より5、6回くらい多い。

次に調べる箇所を単純な計算で求めるのはあきらめ、毎回区間黄金比に分割することにした。すると、クエリ回数が17回になった。誤差が怖かったが、毎回手作業で補正しているよりはマシ……ということだろうか。

この段階で、初手で区間の両端を聞いていることに注目する。ここはなくてもよいのかもしれない。そうしてやってみると、確かにほとんどのケースでは15回のクエリで特定できたが、端を区別できなくなってしまい、k=1,2のケースなどでは16回のクエリを使ってしまった。最後に、区間の両端として1Nではなく0N+1を持つことにしたら、すべてのケースに対し15回のクエリで特定できるコードが完成した。

コードゴルフ。どうやら1500回クエリを投げるコードでもACにはなるらしい。dcで45Bを書いたが、すぐさま44Bに縮められた。45Bはかなり素直なコードだが、微妙に同じことを2回ほど書いているので、そのあたりが縮むのだろうなとは予測がつくものの、実際どういう風に縮められたのかはわからない。

日付が変わったあたりからまたなろうを読み始めて、午前7時くらいまで読んでいた。ここでいったんシャワーを浴びる。パソコンの前に座って、初日以来一切手を付けていないAHCのコードを書こうと思ったが、やろうとしていたことが案外面倒なことに気づいて諦めた。なろうが面白すぎるのが悪い。日曜日が期限のミニットペーパーを提出して再度布団に戻り、午後1時半までまたなろうを読んでいた。

途中で今日の典型の解説が投稿された。初期の区間幅をフィボナッチ数1597としておくと、すべての分割点がうまく整数点となってくれるらしい。なるほど……。

また、寝る直前に昨日Amazonで注文した商品が宅配ボックスに配達されたことを知ったが、取りに行くのは面倒だった。午後1時半就寝。

05/30(日)

午後7時半起床。布団でごろごろしているとAHCが終了した。僕が考えていたことというのは、乱数が加えられる前の縦横の辺の重みの元となる数をどうにかして推定すればよいだろうということで、これは焼きなまし法でも使うのではないだろうか、と考えていたが、TLに流れてきた解法を見ると、機械学習モデルなどを使用した人が多くて怯んだ。

初日に少しだけやっていたときはテスト実行が動かなくて困惑したが、コマンドを指定する部分で自分で定義したaliasを使っているのが悪かったらしい。また、RubyString#*に負の数を与えるとREになってしまうらしく、ここで1WAした。

最短コードについては、1B差で勝っていたものの、相手のRakuはもう少し縮んだので、出しておいた。出してからさらに縮むかもしれないことに気づき真っ青になったが、30分待って再度提出してみるとそちらはWAになった。手元だとうまく動いているようだが、よくわからない。

午後9時からABC203に参加した。全完21位。

AtCoder Beginner Contest 203(Sponsored by Panasonic) - AtCoder

Aはどう書いていいかわからなかったので、とりあえず非ゴルフ解を出しておいた。Bは適当に式変形してdc。CはとりあえずRuby

DからはC++で書いた。Dは二分探索することは一瞬で分かったが、実装にはかなり苦労してしまった。中央値となりうる値の最小値を求めたいが、判定関数として「x以上の中央値をとる場所が存在する」を使うのはダメだった。「x未満の中央値をとる場所が存在する」という判定関数を使用し、そのようなxの最大値を求めて、それに1足したものが答え。

Eは実装は面倒だったがちょっと面白く感じられた。Y座標ごとに見て、例えば(X_1,Y)(X_2,Y)(ただしX_1\lt X_2)があったら([X_1,X_2),Y)をグラフの頂点として見ることで、ある点から別の点に移動できるかということをグラフの有向辺として捉えることができる。この上でBFSをした。

Fは両者の行動を混ぜて考えてもよい。青木君が草を抜く本数に対して高橋君が何回操作するかを考えたくて、これはAlienDPかと思ってしばらく調べてみたが、どうやらAlienDPの条件は満たせなさそう。そこで考え直すと、高橋君の操作回数がかなり少ないことに気づく。高橋君が操作した回数をDPの1つの次元で管理することで解ける。わかってみればかなり簡単だった。

ゴルフ。Aは現状sedが最短。sで置換した後tで分岐していて、これは仕様を完全に忘れていた。Bは全完後にちょっと縮んだので残念な思いをしたが、時間差で最短になっていた。CはPerl。DFは手つかずで、Eは適当にRubyで書いてある。Enumerable#partitionを初めて使った。

CF combinedがあったが見送ることにして、また布団に戻ってなろうを読んでいたが、午後3時半に寝落ちした。

今週はこの「影の勇者の再冒険 ~~Re-Tale of the Brave~~」にすべてを破壊されてしまった。毎日少なくとも10時間くらい読んでいたらしい。

https://ncode.syosetu.com/n5534co/

月曜日から読み始めて、寝落ち時点でだいたい700話だった。このペースだと、外伝も含めてあと3週間ほどは身動きが取れなくなるだろう。最高困った。

Codeforces Round #722 Div.1 E Mashtali and Hagh Trees

codeforces.com

問題概要

以下の3つの条件を満たす有向木を数え上げてください。

  • 最も長い(有向)パスの長さが n

  • すべての頂点の次数(=入次数+出次数)が 3 以下

  • ある頂点対が friends であることを、2頂点を結ぶパスが存在することとして定義したとき、すべての friends でない頂点対 (u,v) について、ある頂点 w が存在し、(u,w)(v,w) がそれぞれ friends となる

解法

準備

説明のため、長さ n のパスを1つ固定し、先頭(パスがスタートする頂点)から順に 0,1,2,\dots,n と番号を振っておきます。このもとで条件を整理してみます。

まず1つ目の条件は、この長さ n のパスがそれ以上伸ばせないということに相当します。つまり、番号 0 の頂点は入次数0で、番号 n の頂点は出次数0です。

2つ目の条件からは、固定したパスから辺を生やすとき、番号 1,2,\dots,n-1 の頂点からは1本ずつしか生やせないことが言えます。

3つ目の条件について、パスに合流する辺とパスから分岐する辺を考えてみます。例えば、番号 2 の頂点に合流する辺と番号 1 の頂点から分岐する辺があったとき、それぞれの先の頂点は当然 friends ではありませんし、さらに3つ目の条件を満たすような頂点 w も存在しません。より一般に、ある値 L が存在して、L 未満の番号の頂点にはパスに合流する辺のみが、L 以上の番号の頂点にはパスから分岐する辺のみが生えることになります。

下の図のようなイメージです。

f:id:kotatsugame:20210525080030p:plain

さて、パスに合流する辺とパスから分岐する辺は、向きこそ異なるものの、パターンとしては同一のものになります。よって、とりあえずパスに合流する辺として考えてみることにします。具体的には、番号 i までのパスに合流する辺をくっつける場合の数 v_i を求めます。v_0=1 です。

番号 i の頂点から辺が生えていない場合は v_{i-1} 通りあります。生えている場合は、その先にあるパスの長さによって、現在固定しているパスとの区別がつくかどうかを考える必要があります。パスの長さが i-2 以下のときは、区別がつくため、固定しているパスへの辺の生やし方と掛け合わせて v_{i-1}\sum_{j=0}^{i-2}v_j 通りあります。区別がつかない場合は重複組み合わせになり、{}_{v_{i-1}}\mathrm{H}_2 通りです。合わせると以下のような式が成り立ちます。

\displaystyle v_i=v_{i-1}+{}_{v_{i-1}}\mathrm{H}_2+v_{i-1}\sum_{j=0}^{i-2}v_j

特に、番号 i の頂点から辺が生えている場合の数は v_i-v_{i-1} となります。

パターン1

パスに合流するような辺とパスから分岐する辺の両方が存在するようなグラフを数え上げます。この際、番号 0 の頂点と番号 n の頂点は次数が1となることに注意しておきます。

パスに合流するような辺がつながっている頂点のうち、最も番号が大きいものの番号を l\ge 1 とします。対応して、パスから分岐するような辺がつながっている頂点のうち、最も番号が小さいものの番号を l\lt r\le n-1 とします。そのようなグラフの場合の数は (v_l-v_{l-1})(v_{n-r}-v_{n-r-1}) となります。

このままでも累積和を取ることによって計算できますが、もう少し進めてみます。l を固定したとき、l\lt r\le n-1 について v_{n-r}-v_{n-r-1} の和を求めます。

\displaystyle \sum_{r=l+1}^{n-1}(v_{n-r}-v_{n-r-1})=(v_{n-l-1}-v_{n-l-2})+(v_{n-l-2}-v_{n-l-3})+\dots+(v_1-v_0)=v_{n-l-1}-1

意味としては、n-l-1 番目までの頂点に辺を生やす場合の数から、1本も辺を生やさない場合を引いたことになります。

パターン2

パスに合流する辺しか存在しない場合を考えます。パスから分岐する辺しか存在しない場合もパターンとしては等しいため、全く同じ値になることがわかります。番号 n の頂点の次数(=入次数)は1から3の3通りありますが、このうち1または2の場合は、合わせて以前に計算した v_n となります。よって次数が3の場合のみを新たに考えればよいです。

3本の辺それぞれが区別できるかどうかを考えます。これは、その先にあるパスの長さによって決まるのでした。パスを1つ固定しているので、少なくとも1本には長さ n-1 のパス(辺の生やし方 v_{n-1} 通り)がつながっています。その他の2本について、その先のパスの長さがどうなっているかで場合分けします。

  • すべて n-1 の場合

どれも区別できない可能性があります。重複組み合わせを用いて {}_{v_{n-1}} \mathrm{H}_3 通りと書けます。

  • 1本が n-1 の場合

もう1本についての場合の数は \sum_{i=0}^{n-2}v_i なので、{}_{v_{n-1}} \mathrm{H}_2 \sum_{i=0}^{n-2}v_i 通りと書けます。

  • どれも n-1 未満の場合

長いほうの長さが i であるとき、短いほうの長さが i かそれ未満かで式が異なり、{}_{v_i} \mathrm{H}_2+v_i\sum_{j=0}^{i-1}v_j=v_{i+1}-v_i 通りと書けます。あとは 0\le i\lt n-1 についてこれの和をとればよく、最後に長さ n-1 のパスの場合の数を掛けて v_{n-1}\sum_{i=0}^{n-2}(v_{i+1}-v_i)=v_{n-1}(v_{n-1}-v_0)=v_{n-1}(v_{n-1}-1) 通りになります。

最後に、パスから分岐する辺しかない場合のために値を2倍するのですが、この際パスに一切辺が生えていない状態を2回カウントしてしまっているため、1引く必要があります。

実装

ACLmodintを使用しています。

https://codeforces.com/contest/1528/submission/117271924

#include<iostream>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
mint H(mint a,int k)
{
    mint ret=1;
    for(int i=1;i<=k;i++)ret=ret*(a+i-1)/i;
    return ret;
}
int n;
mint v[1<<20];
int main()
{
    cin>>n;
    v[0]=1;
    mint sv=0;
    for(int i=1;i<=n;i++)
    {
        v[i]=v[i-1]+H(v[i-1],2)+v[i-1]*sv;
        sv+=v[i-1];
    }
    mint ans1=0,ans2=0;
    for(int l=1;l<n-1;l++)
    {
        ans1+=(v[l]-v[l-1])*(v[n-l-1]-1);
    }
    ans2+=v[n];
    ans2+=H(v[n-1],3);
    ans2+=H(v[n-1],2)*(sv-v[n-1]);
    ans2+=v[n-1]*(v[n-1]-1);
    cout<<(ans1+ans2*2-1).val()<<endl;
}

週記(2021/05/17-2021/-5/23)

05/17(月)

先週の週記を投稿してから、また寝ずに月曜日を過ごした。

まずALPCのConvolutionでゴルフをしていた。Ruby多倍長整数を使って、16進で20桁ごとに数値を埋め込むと、掛け合わせても20桁から溢れないので、復元できるということらしい。そういうテクの存在は認識していたが、以前確認した時には何やらTLEが取れていなかったはずだった。今見るとACできていたので、自分も同様のアルゴリズムで書いて、縮めておいた。わざわざ16進数で埋め込んでいるのは、.to_iより.hexのほうが短いという理由だ。

atcoder.jp

転生したらスライムだった件」の本編を読了した。

https://ncode.syosetu.com/n6316bn/

非常に面白い。累計ランキング1位は伊達ではない。これから数十話ぶんの番外編があるので、非常に楽しみである。本編完結後の、何の憂いもなく無双できる番外編は、非常に体に良いことで知られている。

眠気をこらえて典型90問の公開を待ち、解いた。今日は単純なdpで、Perlで縮めていたのだが、一瞬でdcの38Bが出て勝てなかった。現状自力では43Bにとどまっていて、大きく差をつけられている。この長さで5B差がついているのは、何かアルゴリズムの違いがあるのだろうか。スタックにdpの履歴をためているが、最初に9個以上の0を入れたり、また引き算した後のmodを取ったりするところが長ったらしく感じられる。引き算はどうしようもないか?

その後別の問題の最短コードを眺めていたが、眠気に耐えかね、布団に移動。ラノベを読んでいたが、午後8時半就寝。今週からサークル活動の曜日が変更になり、解説会は金曜日に移動した。

05/18(火)

午前3時半くらいに目を覚ましてしまう。典型90問のコードゴルフが更新されていたようなので、縮め返した。これで目がさえてしまったので、なろうを読み進めていた。

転生したらスライムだった件」の番外編を読了した。相変わらず面白かった。ただ、2つの中編はどちらもリムルの本領がクライマックスまで発揮されないタイプの話だったので、そのぶんのカタルシスはあったものの、やや物足りなかった。もっと読みたいものだ。書籍版を買えばいいのかもしれない。

その後布団から出てコードゴルフしたり、サークル宛てに来ていたメールに返信したり、ゴミを出したりした後、午前10時半に再度寝直すことに成功した。

午後3時半起床。夕方からたいぺーと外食する予定があるので、寝なおす必要があったというわけだ。学食は今の時間開いていないが、購買はやっているので、そこでカロリーメイトをしこたま買い込み、ついでに以前注文した本のうち届くのが遅れていた最後の1冊を受け取った。大学近くの郵便局で原付の軽自動車税を払おうとしたが、窓口が午後4時で閉まってしまうらしく、これには失敗した。

夕方、ラノベを読んでいたら、たいぺーが家に来た。本来はすぐ外出するはずだったのだが、今日の分の典型90問がまだAtCoderに出題されていないため、それを待つことにする。たいぺーを放置してしまうことになるが、僕の本棚を眺めたりして暇をつぶしていたようだ。

待っている間にラノベが読み終わった。「恋は双子で割り切れない」。最近Twitterでよく広告ツイートを目にする。そんなにプッシュされるということは面白いのだろう、と期待して読んだが、正直期待外れだった。双子がいて、両方に好意を寄せられている幼馴染が主人公で、その3人の関係性を描く話。設定はそのような感じだが、キャラ付けのつもりだろうか、視点人物によって地の文に含まれる語彙がかなり難しくなって、ストーリーに集中できなかった。他のラノベから固有名詞を借りてくるとかなら同じラノベとして面白く読めるだろうが、僕の知らないSFとか海外の古典の固有名詞を持ち出されても困る。そういうのは一般書でやったら良かったのではないだろうか。わざわざラノベでする必要性は感じられない。固有名詞だけではなく日本語の語彙でも知らないものがあったが、それは僕の落ち度なので頑張って調べながら読んだ。

読み終わるのとほとんど時を同じくして、典型90問がアップロードされた。サクッと解いてAC、ゴルフは面倒そうなので放置していよいよ外出。仙台レジャーランドが閉店してしまったので、違うゲーセンに行くことを念頭に、その近辺でラーメン屋を探してみたが、どれもピンと来なかったので、結局駅前までズルズル歩いてつけ麺屋に入った。僕は結構来ているが、たいぺーは初めてらしい。なんとなく2玉ぶん注文してみたら、思ったより多かった。つけ汁が早々に冷え切ってしまったが、つけ汁温めサービスがあるのか謎だったので、結局冷たいまま食べていた。熱盛にしてもらえばよかった。

店内で最近話題のアニメOPが流れていたが、歌詞に聞き覚えがなかったので、さては2番だな?と思い、たいぺーにそのことを話した。この際、歌詞の2番のことを方言で「2題目」と言ったところ通じなかったので、大変びっくりした。こういう方言っぽくない(と感じられる)方言はわかりにくいし、使いがち。例えば小説など読んでいても、特にキャラが方言を喋っていることを意味せず「腹がくちくなる」「物を(あるべきところに)なおす」というのが出てくることがあるが、意図せず出てしまった作者の方言だなあと感じながら読んでいる。

食事して少し本屋に寄ったあとゲーセン。しばらくたいぺーとマッチングして、フルチェインが出たりした。たいぺーが帰宅してからはアップデートで追加された曲を埋めていた。Lv.12のOPが99.50%に乗ったほか、追加された13+の両方でSSSを達成できた。運指が固まっていないうちに出てしまい、スコア的にはあんまり納得がいかないが、特にWizdomiotについては発狂が信じられないくらい上手くいった結果のスコアだから、これ以上はそうそう伸びないだろうという予感がある。

Lv12のスコアを詰めていた。スコア的には全体で1000点以上増えたはずだが、OVER POWERのパーセント表示は微動だにしない。99.50%を目指しているが、数値的にいくつになればよいのかが全然わからない。

週記(2021/04/26-2021/05/02) - kotatsugameの日記

午後11時半、閉店時間になったので帰宅。途中で仙台レジャーランドの跡地に寄った。いつもならこの時間でも遊べたのに……。

今日買った本はこれ。

夜中から朝方にかけて、ずっとコードゴルフをしていた。午前6時半就寝。

05/19(水)

午後4時ごろ、ふと目を覚ましてAtCoderを確認したら、典型90問の今日のぶんが公開されていたので、起きて縮めた。RubyだとunshiftpoprotateするのはTLEしてしまったので、まずCrystalで書いた。Crystalのdequeには、swaprotate!というそのものズバリなメソッドが存在するようだ。その後、先頭インデックスを持つ想定解を思いつき、Rubyで通した。最後に、Perlだとunshiftpoprotateしても間に合うようだったので、それで書いたのが現在の最短となっている。午後6時に再度寝直した。

午後9時半起床。

「雪中の花は、軍神を偽る」を読んだ。かなり面白かった。異世界に転生して軍師となり、自軍を勝利に導くという話。異世界といっても中華風の異世界で、この辺りは富士見L文庫らしさを感じる(富士見L文庫は最近「あやかし」と「中華っぽい話」しか出してない気がする)。似たようなストーリーの話としては「数字で救う!弱小国家」というのを思い浮かべられるが、転移したらたまたま国の王女と懇意になって軍師になるか、軍神に憑依して軍師とあがめられるか、どちらが自然に感じられるだろうか。どちらも不自然と言われたらそうかもしれない。そういう設定上の不自然さはともかく、ストーリーは面白かった。主人公が男装女子であるという点も僕にとっては目新しく、新鮮。

続いて「才女のお世話」を読んだ。これも良い。まずみわべさくらさんのイラストが良く、これを目当てに購入したが、作品自体も面白かった。自活能力があまりないヒロインがかわいらしい。ラストでは財閥令嬢という設定が実態を伴って現れ、ハラハラした。

コードゴルフをしつつ、さらにもう1冊。「クラスの大嫌いな女子と結婚することになった」2巻。非常に良い。外面としては嫌いあっている2人の軽妙な掛け合いが心地よい中、内心で互いに惹かれあっていく様がもどかしく、微笑ましい。高校生夫婦という設定にも描写から現実味が感じられる。

さらにコードゴルフを続けていた。朝になって、典型90問の今日の解説が公開され、dequeが想定でなかったことを知った。dequeのランダムアクセスを定数時間で行うというのは難しいことらしい。僕はリングバッファによる実装を念頭にしていたため簡単だろうと思っていたのだが、実はC++においてもリングバッファではない実装をしているらしく、かなり謎だった。ちょっと調べたところ、STL一般についての要件を満たすための実装らしいが……。

午前9時就寝。

05/20(木)

午後0時半起床。目覚ましを3回くらい見送ったうえで気合の起床に成功した。ゼミがある。

先週の続きからということで、僕が先週終えられなかった分の発表をまず行うことになった。スライド自体はすでに完成しているので、今週はな~んにも準備をしていなかったのだが、するとスライドを作りながら話そうと考えていた内容が頭から吹き飛んでおり、ところどころ口が回らなかった。発表自体は何とか終えられたが、先週と同じページ数のスライドに先週の倍の時間がかかっている。これには、スライドの内容が少し難しくなったことも関係している。

今日の典型90問は最初、0から2\times 10^{18}を二分探索する中で部分集合のdpO(2^N N^2+N^3)を行って解いた。C++でも1.2secくらいかかっていて、スクリプト言語でのACは難しそう。ここで、TLによれば指数の底を2にできるようだったので、その方針で考えてみる。補グラフのK彩色問題に言い換えられて、これは検索するとO(N 2^N)で解けるらしい。包除原理を活用する、と書いてあったが、具体的にどのように解くのかわからなかったため、さらに検索していると、解説しているスライドが出てきたので、それを見ながら実装した。さらに二分探索をやめ、答えの候補となる点対の距離O(N^2)通りのそれぞれについて計算するようにしたところ、100ms以下と爆速になってくれたので、Rubyでの実装に移った。(実は、答えの候補を絞ったうえで二分探索することでO(\log N)回彩色問題を解けばよくなるようだ。)

現在の計算量はO(N^3 2^N)で、N=15で計算してみるとまだマズい。実際N=15のケースではかなり時間がかかってしまうことが確認できたので、オーダーを落とすことになった。実は包除原理の箇所ではメビウス変換を行っており、このせいでO(N 2^N)だったのだが、実際は配列の最後の値にしか興味がないため、適当に係数\pm 1を前計算して足し合わせることでも同様の結果が得られ、結果O(2^N)K彩色問題が解けた。……解けているように見える。Wikipediaに書いてあるオーダーよりも良いものが得られてしまい困惑したが、Nビットの整数演算がO(N)であると考えると、計算量は確かにO(N 2^N)になる。そういうことだろうか。

コードゴルフすると253Bになった。

学食に行き、帰ってきて、すぐ布団に横になったところ、耐え難い眠気が訪れた。実際耐えられず、午後8時半に寝落ちした。

午前0時半起床。サークルのバチャを吹き飛ばし、CF div.2が始まってしまっていた。仕方ないのでベッドでゴロゴロしつつずっとなろうを読んでいた。この生活リズムの乱れ、つまり朝のほうに寄ってしまっている状態はあまり望ましくないため、無理矢理にでも寝ておく必要がある。午前5時くらいに眠気が来たので、すかさず寝た。

05/21(金)

午前11時起床。

syosetu.org

章題が「東方靈異伝」になっていた。ついに旧作突入らしい。感慨深い。

学食に行って、帰りに軽自動車税の支払いもしてきた。今日は成功した。

午後1時からAtCoderJobsで応募したインターンの1次面接があった。1次というのは、ここでは第一回というくらいの意味合いで言っていて、実際には異なる名前がついている。初めての面接なのにかなり主要なエンジニアらしい方に面接していただいて恐縮の限り。面接自体は好感触だったが、相変わらず自分が何をやりたいかということがよくわかっていないため、その点はあいまいで腑抜けた回答をしていたと感じる。そういうのは一回働いてみないとわからないと思っているので、何の準備もしていなかったが、こういう甘えた考えはいけないのかもしれない。直す気は……まだない。

予定通り1時間みっちりお話していただいて、終了。典型90問の今日の分が公開されていたので、とりあえず通して、少しだけ縮めてから午後3時くらいに家を出た。青葉山のキャンパスに向かう。卒業アルバムの写真撮影を行うためだ。事前にTLで質問したところ、顔面しか映らないためTシャツとジーパンで何ら問題ないらしい。

家を出てしばらく歩いてから、ひげを剃ろうと思って剃っていないことを思い出したが、後の祭り。しかしカメラマンさんはあまり気にならないと言ってくださったし、実際撮られた写真を確認してもあまり見えなかったので、卒業アルバムになったら解像度の狭間に呑まれて潰れるだろう。

この行き帰りはずっとスマホとにらめっこして典型90問のコードゴルフをしていた。方針がよかったのか、現状で(報告された中では)最短らしい。M=46とすると、最初はO(N+M^2)で解いていたところをO(MN)で解くようにしたら、大変短くなった。

帰ってきてatgolferを確認すると、以前Perl6でTLEしていた解がRakuで出すことで高速になりACする、というやつで1問縮められていた。慌てて、これまでPerl6でTLEしたコードをすべて探し、縮められるものを縮めておいた。

サークルバチャの時間になったので、参加する。今日はCF #492 div.1。サークルの活動する曜日が変更され、解説会は金曜日、バチャは木・金曜日になった。木曜日は午後9時からだが、金曜日は解説会に押し出されて午後5時半から。

https://codeforces.com/contest/995

A問題は解けなかった。B問題は、貪欲に左端から揃えていってよさそう。

C問題は、|x|\ge|y|なる点だけを抜き出し、|x|の降順にソートして2つ組にする。(x_1,y_1)(x_2,y_2)が組になったとすると、|x_1+x_2||x_1-x_2|の小さいほうが得られるように符号をつけることにする。こうすると、あとは組ごとでどのように反転しても|\sum x|\le 10^6となるようにできる。例えばx_1+x_2となるように符号をつけたとすると、y_1+y_2が残るが、これの絶対値の降順にソートして貪欲に足したり引いたりすることで(組にした点の符号をずらさないようにしながら)|\sum y|を最小化でき、具体的には|\sum y|\le \sqrt 2\times 10^6になる。この\sqrt 2|x|\ge |y|から出ている。

同様に|x|\lt |y|なる点も処理し、最後にそれぞれからできた2つのベクトルを足したり引いたりして、答えとして適切なら出力するようにしたら、通った。しかしこれには反例があって、処理の後にできるベクトルが(10^6,\sqrt 2\times 10^6)だと当然ダメ。具体的にそのようなケースも構築できてしまったが、コンテスト中なので気にしないことにした。バチャだとフルフィードバックであるということもある。

Dは面白かったが、かなりエスパーが効きやすそうな問題に見える。答えは値すべての平均値になる。自由度が小さいケースで確認してみよう。残り1bitが確定していない状況を考えると、先手は値が大きくなるように定め、後手は値が小さくなるように定める。この2つは一致しないため、残り1bitが確定していない状態の期待値は、含まれる2通りの場合の平均値になる。

残り2bitが確定していない状態から1bitを定めるというのは、残り1bitの状態の期待値は含まれる2通りの状態の平均値であるということを鑑みると、候補を2x2のマスに並べて1x2(あるいは2x1)マスを選ぶことに等しくなる。先手は、ここに含まれる値の総和が大きいものを選べばよい。逆に後手は、先手が選ぶのと真逆の状態を選ぶことになる。たとえば??から先手が0?にするとしたら、後手は?0でも?1でもなく1?を選ぶのが最適である、ということだ。これは、それより期待値が小さくなるような後手の選び方(例えば?1)が存在するとしたら、先手が逆にそれと真逆な状態?0を選ぶことで、0?より期待値を大きくできる(2種類の期待値の総和は必ず2x2のマスの総和に一致するため、min=sum-maxという要領でそのようなことが言える)ということからわかる。結局、残り2bitが確定していない状態の期待値も含まれる4通りの場合の平均値であることが分かった。

このことは、確定していない残りのbit数がいくつであっても成り立つ。結局、一番最初の状態の期待値は、含まれる2^n通りすべての平均値になる。

解説を読んでAを通し、Cの正しい解法を実装した。Aは、中央の2xNマスをターンテーブルとみてぐるぐる回すことで、目的の駐車場と隣接する瞬間が来る。一度も回せなければ答えは-1だ。

Cは、長さがr以下のベクトル3つがあると、適当に2つ選んで足したり引いたりすることで長さがr以下のベクトルを作れる、ということを利用して、すべてのベクトルの長さが10^6以下であるという条件を満たしたままベクトルの個数を減らしてくことで答えが得られるようだ。実装はちょっと面倒。

バチャに参加する直前と直後で、サークル解説会の準備をしていた。今日は解説に立候補してくれた人が2名、計3問の解説役が決定しているので、かなりありがたい。自分もF問題のスライドを作成した。

2021/05/21 定例会 | puzzleknot 公式サイト

yukicoder 296に出た。全完。

yukicoder contest 296 - yukicoder

Aはよい。Rubyで書いて、提出前にぐっとにらむとxorだとわかったので、慌ててRakuで書き直した。Bも面倒だが、文字列の先頭と末尾と長さだけ保存しておいて最長経路のようなことをすると解ける。Cはすぐに直前2数を持つdpが思いつくが、書いてみるとO(NK^3)になっていてびっくりする。累積和で書き直すことができて、数列の総和についても新しく足された分は通り数のdpと掛け算することでわかるので、OK。

Dは各数の平方因子をエラトステネスの篩の要領で計算し、square-freeとなった数の出現頻度をカウントすれば求まる。EはABCで見た、dp配列はK\times Kだけど毎回の更新がO(K)箇所で済む、というやつ。各次元に沿ってmaxを計算しておくのもABCで出たものと同じ。FはCと問題設定が同じということだけ先に言われていて、C問題を数学で高速化するのかな~と嫌な気分になっていたが、ふたを開けてみれば行列累乗だった。微妙に遷移行列で混乱したが、問題なくAC。

そういえば、昨日の典型90問はk-meansで解けないだろうかと思っていたのだった。そのことをツイートしたところ、実際に試してダメだったという報告が寄せられた。小さいケースだから厳密解が求まってもおかしくないと思っていたが、そもそも重心との距離はあんまり関係ないのかも。

日記を書いた。今週はなんとこれまで5日分を溜めており、真夜中から朝方までかけて書くことになった。書き終えてからちょっとコードゴルフをして、布団に入り、開いているいくつかのなろうを適当に読んで、午前7時就寝。

05/22(土)

午前11時57分の目覚ましで起床。正午からのAHC003に備えたものだ。このとき具体的に何をしていたかというのは、まだコンテスト中であるから書けない。20分くらいパソコンの前に座っていたが、そのあとすぐ布団に入った。少しだけTLを眺めていたが、またすぐ寝た。

午後4時くらいに再度起床した。生協の弁当受け取りを念頭に置いた起床時間だったが、それ以外にも典型90問が投稿されたことを確認したという理由もある。今日の典型は、適当に文字を置換して足し、Zalgorithmをする。星7がつけられていたが、かなりすんなり解けた。実装も簡単。ただコードを縮めようとすると、どう実装したものかわからなくなる。

C++ACLを使うコードを書いていたら、Rubyで通せたことが報告された。自分もRubyでZalgorithmを書いてみたが、実行時間が全然お話にならない。考え直して、ローリングハッシュを用いることにした。Zalgorithmで行っていた判定というのは、つまるところ文字列のprefixとsuffixで一致するものを数えていたのだから、引き算すら存在しないかなり単純な実装で書ける。手元で動かすと2secを微妙に超えてしまうようだったが、AtCoder上では1sec前後で安定した。ローリングハッシュに用いるmodについても考える必要がある。長さが10^6文字の文字列を区別する必要があるため、基数の位数の関係でmodは7桁以上にする必要がある。そこで7桁の素数を大きいほうからと、基数として1桁の数を選んで投げまくってみたところ、99999712で通った。コードの書き方によっても通る素数と基数の組は変わるらしく、文字列の判定方法が変わるコードの改善があるたびにそういう組を見つける作業が発生して、大変だった。ほかにも、理論的に通らない6桁の素数を試したりもしていて、かなり無駄な提出が多かった。

そういうことをしていたら夜になった。ちょっとラノベを読んだり食事したりして、ABC202に参加した。19位。

AISing Programming Contest 2021(AtCoder Beginner Contest 202) - AtCoder

Aはよい。何とか最短を取れた。逆にBはrevを忘れてWAを出してしまい、速度差で最短を取れなかった。CからはC++で書いていた。Cは特に言うことなし。Dも自明だと思ったが、なぜか3回もWAを出してしまって大変な目にあった。Kと比較する値とKから引き算する値が異なっている提出を繰り返していたようだ。Eはオイラーツアーを考えるとわかる。

Fは大変。まず点はXの昇順→Yの昇順でソートしておく。ccw(i,j,k)で「\overrightarrow{P_iP_j}\times\overrightarrow{P_iP_k}\gt 0」を表すことにする。反時計回りになっているということを判定する関数だ。凸包だから、直前の2点i,jを持っておいて、次の点kccw(i,j,k)であるように決めれば作れる。面積が整数であるという条件も、外積の偶奇を見ていけばよい。これでO(N^3)のdpが書けるが、しかし凸包の内部に含まれる点を考慮するのが難しい。

ここで、凸包の隣接する3点i,j,kについて、それぞれ点P_lであってccw(i,j,l)\land\neg ccw(i,k,l)となるような点の個数を数えると、その総和が凸包の外側にある点の個数になる。外角ごとに外側にあるとわかる点を数えている。このことを用いると凸包の内部に含まれる点を考慮できるが、ただし凸包をスタートする部分のカウントが難しい。最初は1点決め打ってスタートしていたが、これだと外側の点を漏れなく数えることができない。1周して戻ってきたとき、最初に使った辺の情報を復元できないから、決め打った1点の外角を考えられないため。そこで、仕方なく2点(つまり1辺)決め打ってスタートすることにした。

結局、O(N^3)のdpをO(N^2)回行うことになった。最初の提出ではTLEしてしまったが、直前の2点i,jからkを選ぶループのためにi,jに対してccw(i,j,k)を満たすようなkを事前に列挙しておいたり、またccw\overrightarrow{P_i}\times\overrightarrow{P_j}を最初にすべて計算して配列に保管しておいたりといった改善を加えたところ、2回目の提出でACできた。1500ms。ccw(i,j,k)を満たすような組i,j,kの個数はそんな多くはならないだろうから、5乗といっても定数倍が小さくなるだろうと考えてはいたものの、TLEした後の改善中は、実際にはどれくらい惜しいのかがわからなかったため、大変に怖い思いをした。

Fの想定解は、1点決め打ったあと各辺との三角形を作って内部の点を数えており、頭が良い。これだと2点の情報だけでカウントできるので、最初に決め打つ部分がO(N)になって、合計で4乗になる。

コードゴルフ。ABはコンテスト中に出したものが最適であろう。

CはPerlで書いていたが、AWKで書くとかなりいい感じになって、縮んだ。3行目と4行目を一気に読みこんだのがミソで、1つのループを使いまわし、2行目においては1..Nの集計を、3・4行目においてはN+1..2Nを回して答えを求めている。このインデックスの連続性により、ループ変数の初期化が必要なくなって、処理が無駄なくまとめられている。会心の出来。

atcoder.jp

DはRubycombination.sizeで二項係数を計算するやつ。EもRubyで、よくわからないが少しばかりのバトルが発生して縮んだ。Fは手つかず。

TCO21 R2Aに出た。以下のリンク先は、この日記を書いている段階ではまだ表示されない。

TopCoder Statistics - Match Overview

EMの2完で33位、レートは2556→2567(+11)でhighestを更新した。赤が多いのでこんな順位でもレートが上がった。

Easyはカス。問題文が5400文字くらいある英文で、題意を把握するのにかなり苦労した。

台座が3つある。駒A、B、Cと武器グー、チョキ、パーがあり、各台座に駒と武器が1つずつ並べられている(重複はない)。この並び順はずっと不明。

"AB"と宣言すると、駒Aと同じ台座にある武器が駒Bと同じ台座にある武器に勝つ(もちろんじゃんけんの意味で)、という表明になる。失敗する(宣言が誤りである)こともあるが、この宣言を80%以上の確率で成功させたい。

具体的には、次のようなゲームが進行する。まず自分が1度宣言を行い、それが成功したかが知らされる。これは入力で与えられる。その後、これも入力される文字列に従って、「駒の入れ替え」「武器の入れ替え」「駒か武器の入れ替え」「宣言」が行われる。入れ替えの具体的な内容は知らされない。「宣言」のタイミングで宣言を行い、ゲームを通しての成功率を80%以上にせよ。

解法は簡単で、最初の宣言である2つの駒の間の勝ち負けがわかるが、そのあと駒や武器が入れ替えられると勝ち負けも毎回逆転するので、それを見て答えるだけ。ちょっと面白く感じるが、それを圧倒的に上回る問題文の難読さで、非常に嫌な気持ちになった。

Medは、DAGが与えられるので、ある頂点uであって、それ以外のいかなる頂点vに対しても「uからvにたどり着ける」か「vからuにたどり着ける」のどちらかを満たすようなuをすべて求めよ、というもの。解法はいろいろあるようだ。以下は僕の解法。

トポロジカルソート順で、uであってuより先にあるすべての頂点にたどり着けるようなものを求められれば、辺の向きを変えつつ2回計算することで答えられることがわかる。よってこれを考える。トポロジカルソートの逆順にみていき、今見ている頂点よりも先にあるすべての頂点にたどり着けるために到達しなければならない頂点の集合を管理する。ある頂点uを見ているときは、u\rightarrow vなる辺について集合からvを削除し、最後に集合にuを追加して、集合の要素がuただ1つだった場合に条件を満たすとわかる。

集合はbitsetで管理した。bitset.count()==1だと最大ケースで1secくらいかかったが、集合にuを追加する直前に判定することにしてbitset.none()を使うと爆速になった。

Hardはわからず。ラプラシアン行列を書いて行列木定理を考えていた。

ラノベを1冊読んだ。「午後九時、ベランダ越しの女神先輩は僕だけのもの」2巻。

内容は……よくわからない。良いか悪いかでいえば、良い。ヒロインの描写がなんとなく淫靡でドキドキした。

週記(2020/10/19-2020/10/25) - kotatsugameの日記

1巻は確か、恋愛ものとしてはちょっと異色のイベントがあって衝撃を受けており、評価がよくわからなくなっていたが、2巻は(紆余曲折あったものの)真っ当に恋愛しており、非常にエモーショナル。はっきり良いと言える。ただ、情緒を増すための表現かもしれないが、時系列を頻繁に前後させて書かれた文章はちょっと読みづらかった。

日記を書いてシャワーを浴び、布団に入り、ちょっとだけなろうを読んだがすぐに寝た。午前8時半だった。

05/23(日)

午後5時起床。

昨日の典型90問の解説が投稿されていたので読んだが、ローリングハッシュが想定解らしくびっくり。自分の中で、ローリングハッシュというのは、文字列の中途半端な位置同士をマッチングする羽目になったときに渋々持ち出す信用ならないアルゴリズムというイメージだから、Zalgorithmで解ける以上これが想定だろうと信じ込んでいた。

昨日のコードも縮められていた。解説を読みつつちょっと考えてみると、どうやら文字を入れ替えるところで無駄な場合分けがありそう。RGB012を対応させる(正確には文字コードを3で割ったあまりを見て120と対応させる)と、文字cdについて(c+d)%3がすべてのインデックスで一致していることを判定することになる。これはd-d..2-dのどれかに入れ替えることで文字列の一致になって、d==R ? R : G+B-dみたいな場合分けが必要なくなる。あと、昨日必死に素数をいろいろ試していたが、別に素数じゃなくても通るようだ。適当な数を適当に累乗すると、そこそこ大きな数が7Bよりも短く書ける。

テストケースがなくなっていたらしい。

夜は本を読みつつARCを待とうと思ったが、緊張からあまり読めないまま時間になった。ARC120。

AtCoder Regular Contest 120 - AtCoder

5完28位でパフォーマンス2929、レートは2741→2761(+20)でまたも最高値を更新した。実は次回赤チャンスらしい。今日は結果としては良かったが、他がよかった分Cで詰まりまくって50分もかけたのが残念でならない。

A問題は、操作した数が新たな最大値になることに気づけばあとはいろいろ和を持つだけ。持つだけだが、紙に書かずフィーリングで実装したら合わせるのに手間取った。合ってからもまだ怖いので別のケースを試したりしていた。サンプルの数列が昇順に並んでいるのが怖いポイント。Bは、斜めに文字がそろっているのが必要十分っぽいことは見た瞬間わかって、証明もすぐつく。グリッドを斜めに走査するのになぜか手間取ったが問題なくAC。

Cは、適当に隣接項の和・差や先頭からの累積和を取ってみて操作の影響を確かめていたが、全然わからなかった。そこで一度操作そのものを純粋な気持ちで眺めると、項の元の値に左に移動した回数が足され、右に移動した回数が引かれていくことに気づく。また4 3という2項に操作しても値が変わらないことを確かめると、先頭から順にどん欲に合わせて良さそうであるとわかった。最初に、最大まで左に移動したときの値としてA_i+iを考えておいて、B_1と一致するもののうち最も左にあるものを除いてそれ以外を右にずらす……ということができればよい。この右にずらす操作は、全ての値から1引くことになるので容易に実現可能なはずが、コンテスト中はB_1のために持ってきた値より左にある要素にしか影響がないと勘違いしてしまっていた。これだと区間加算・値の検索をする必要が生じる。どうにもまともな方法ではできそうになかったので、仕方なく平方分割を書いたが、サンプルが合わない。ここで初めてサンプルを手で試し、勘違いに気づいた。自分に失望しながら書き直してAC。コンテストは残り65分で、順位表を見ると300位、さらにD問題もすでに100人以上に通されていて、顔が真っ青になった。

翻ってDは一瞬で解けた。上界を考えると、数列の値の大きいほうから半分と小さいほうから半分をうまく組にできればよくて、大きいほうに必ず(を割り当てるなどするとかっこ列が対応しなくなるが、折れ線グラフで下にはみ出た分を折り返すことを考えるとできる。

EはかなりWAが出ているようだったが、通さないと命がないため考える。幸いDを瞬殺したので時間は1時間くらい残っていた。まず、移動するなら左か右に全速力で動いたほうがよいことがわかる。二分探索することにして判定問題として見ると、まず人1はずっと右に全速力で移動し、その次の人2は途中まで行って、戻って、パーティーが終わる瞬間人1と会う。人3は人2が途中まで行くのに合わせて会い、残った時間は適当に右に進んでいればよい。ここまでは良いが、人4がどのタイミングで人3と会うのかについて、2通りある。つまり、人3が人2と会う前か、後か。とりあえず2通り考えることにすると、人5は4通りあり得ることになりそうだが、実は「できるだけ右に進んでからパーティーが終わる瞬間に人4と会う」か「人4がパーティーが終わる瞬間に人3と会う前のどこかで会う」の2つ、つまり最も極端なものだけを考えておけばよいだろうと感じた。この直感が順位表で散見されるWAの原因か、とも思いつつ、丁寧に実装して提出したら通った。快哉を叫びそうになったがぐっとこらえ、指パッチンにとどめた。後から電車のダイヤグラムみたいな図を描いてみたが、どうやら他のケースは、確実により右に進めたり、最終的な位置が同じになったりして、この2ケースのどちらかに吸収されてしまうようだ。

Fを開いて自明なdpを書いてみると、以前似たようなdpを頑張って高速化したような覚えがあったが、よくわからなかったので放置して、残りの時間はコードゴルフをしていた。

コードゴルフ。Aは負け。Bは久しぶりに#!perl -pで対応しないかっこを書く見た目が奇妙なテクが使えて嬉しい。DはRubyで書いておいた。

atcoder.jp

本を1冊読んだ。「犯罪社会学者・椥辻霖雨の憂鬱」。主人公のキャラが好み。主人公が准教授として在籍する大学の生徒で、重要そうな感じに登場するキャラがいたが、結局話の本筋には関わってこずじまいだったので、次巻があれば期待したい。ミステリパートはあまり面白くなかったが、吉川線の話で、トリックに関係する器物から受ける印象に対し、それを用いた殺人が行われたというギャップにちょっとゾッとした。

週記(2021/05/10-2021/05/16)

05/10(月)

先週の週記の最後の部分で、ARC118-Aの最短コードに使われている式を導いた。これについて、よりシンプルに見える手法がTLに流れてきた。

実は周期ごとに分けて考える必要はなく、A=\left\lceil\frac{100N}t\right\rceilN回目の番号が飛ぶことになる。ceilとfloorが入り混じることになるが、結論から迎えに行こうとすればそれほど難しくなさそうだ。

布団に入ってなろうを読みつつ寝る準備をしていたが、大学生協に注文していた本がちょうど届いたらしいので、受け取りに行くことにした。また、かなり毛が伸びてきたので、床屋にも行く。昼休みとかち合うとまずいので急いだ結果、正午になる前に食事を終えて床屋に入店することができた。それでも昼休み直前だから結構混んでいた。3つ座席があって、ここ1年は真ん中を飛ばして使っていたのだが、今日は全部埋まった。

ほとんど寝そうになりながら髪の毛を切ってもらっていた。今日担当してくれた人は、すべての工程が終了した段階で微調整しようとしたのかバリカンを再度使用したりしたため、服に細かい髪の毛がついたりして大変かゆい思いをした。帰宅までつけたマスクにもかなり多い毛が残っていた。

生協で本を受け取った。これは完全に昼休みとかぶってしまい、今日受け取る11冊をレジに通してもらっている間に後ろに結構人が並んでいてびっくりした。

研究室に配属されたということで、安全教育の案内が来た。Classroomで動画と資料を見て、フォームの小テストに回答する必要があるらしい。適当に30分くらい動画を流しながらWikipediaで世界一の一覧を読んでいたが、それも読み終わってしまったので、小テストを確認してから動画のそれっぽい場所を探す作戦でサクッと完答した。

買ってきた本をさっそく1冊読んだ。「元スパイ、家政夫に転職する」2巻。やはり主人公が強いとよい。半ばにある模擬戦の描写がよかった。クライマックスのほうは敵役がかなりへなちょこだし、物語のピントもヒロインに集中していたので、バトルという観点から見れば消化不良気味。次巻へ続く引きもあったが、後書きはこれで完結かのような書かれ方をしていてビビる。打ち切りだろうか。

典型90問を解いた。今日はOctaveがよさそう。N行2列行列における各行(x,y)(x+y,x-y)に変えるのは、右から[1,1;1,-1]という行列を掛ければ一気に行える、が、WA。このWAの原因は分かっていないが、以前の経験から行列を転置して左から掛けるとACできることが(僕に)知られている。以前の経験というのはこれだ。

atcoder.jp

今日のサークル解説会の準備をする。また何一つ始まっていない状態でこの日を迎えてしまった。これまで3回新歓イベントとして外部に解説会を公開してきたが、今日で最終回の予定だ。なのでそれなりに頑張る必要があると思ったが、頑張れなかった……。

ZONeプロコンの問題を取り扱った。今日は結局B問題とC問題のスライドを作成した段階で時間切れだったが、C問題の解説スライドは結構熱を入れて書いたつもりなので、解説会自体は結構喋ることがあって30分以上続いた。解説スライドは↓にある。

2021/05/10 定例会 | puzzleknot 公式サイト

布団に入ってからしばらくなろうを読み、午後11時就寝。

05/11(火)

午前10時起床。

書類を送ったインターン先から返信があって、とりあえず面接をしてもらえるらしい。1度書類選考で落とされた経験から、これも大変にありがたいことだという感覚がある。どこの馬の骨かもわからない輩のために面接官の1時間を使うのはありえないはず。

学食に行く。昼休み直前くらいの時間に入店してしまい、食べている間に周りの席がどんどん埋まっていて、感染症対策~!という気分になった。一言たりとも喋らないでほしい。

家に帰ってからは夜までずっと「数学基礎論特選」という講義のレポートを書いていた。3回分の講義資料を読んで、途中にある問題からいくつか選んで解く。かなり疲れた。特に最後のほうでは「数」と「数項」と「ゲーデル数」が入り混じるのも辛いし、だいたいゲーデル文「自分自身を証明できない」だったり対角化だったりは脳にめちゃくちゃ負担をかける。昔数学ガールで読んで挫折したが、今になっても満身創痍であった。

ずっと、といっても途中途中で集中が切れたりなんだりして別のことをやっていた。まず今日の典型90問のゴルフ。C++で遅延セグメント木を使って書いたが、反省してスライド最小値を実装した。こちらだとRubyでもちょっと余裕がある。

ノクターンノベルズを読んだりもしていた。

https://novel18.syosetu.com/n1848fz/

https://novel18.syosetu.com/n4476gq/

https://novel18.syosetu.com/n2204eu/

午後11時になって完成。普段考察用紙に書きなぐるのとは違ってレポートは丁寧に書くべきではあるが、なぜか字を丁寧に書けなくなってしまっていて、非常な悪筆。連絡が来ていて、東北大学感染症警戒レベルの引き下げに伴いこの講義では対面講義をしようとしているらしい。意味が分からない……。対面になったら行かないと思う。せめて講義資料のアップロードは続けてほしいが、どうなるだろうか。

勢いづいて数理統計学の課題も解いた。今週は簡単なものを1問だけ。数値計算でもないので、計算機を使う必要もナシ。

木曜日のゼミはいよいよ僕の発表の番である。これの準備を(今更)始めることにした。少し教科書を読んだが、まあまだ難しくはなさそうなので、どのように発表するかに意識を割く。これまで2回、他の人の発表を見てきたが、皆手書きのノートをスキャンして映しているようだ。しかし僕の悪筆を人に見せるのはためらわれるし、どうやら丁寧に書く能力も失われてしまったようなので、LaTeXを使う。Beamerというヤツでスライドを作成することにした。

最初はdefinitionやらのblockが表示されなくて頭を抱えていたが、適当に調べたチュートリアルに従って\documentclass{beamer}\documentclass[dvipdfmx]{beamer}に変更したら表示されるようになった。枠で囲まれていなかったのでblockとは……?という気持ちにもなったが、これはテーマによって変わる部分で、デフォルトだと枠で囲まれないらしい。なんとなくよく見る気がするorchidを選択しておいた。数式のフォントもデフォルトだとかなり垢抜けない感じだったので、変えておいた。

4時間くらいスライドを作成していたが、どうやらまだ発表範囲の半分も進んでいないらしい。しかも出来上がったスライドを見てみると、ただ教科書を翻訳しただけにも見える。そのような発表は唾棄すべきである、という言説は「数学 ゼミ」等で検索すればいくらでも目にできるが、実際自分がやる段になるとどうしていいかわからない。今読んでいる教科書は、ほとんどの事項を丁寧に解説していて、僕が気付けるような行間はない。

朝方日記を書いて布団に入り、少しだけなろうを読んで就寝。午前5時だった。

05/12(水)

正午、起床。今から学食に行くとちょうど混雑とかち合うので、ちょっとだけ二度寝し、午後1時過ぎに家を出た。学食は午後1時半にいったん閉まってしまうので、あまり時間の余裕はない。

帰ってきて、今日の典型90問の回答コードを作った。今日の問題も簡単なので、できるだけ早く提出できるようにしたい。また15秒おきに提出を試みるスクリプトを書いて、提出できるまでずっと動かしておくことにした。それはそのまま放置して、昨日の続きでスライドの作成を進める。

スライド1ページでは証明が終わらないようだ。そこをギュッと縮めて簡潔に記述する必要性を生じさせるのもスライドという媒体の醍醐味かもしれないが、今は普通に困っている。調べたところ、\end{proof}の直前に\let\qedsymbol\relaxというのを書いておくとよいらしい。確かに証明終わりの記号が消えていた。

さて、早くもスライド作成がいやになってきたため、ラノベを読んだ。「魔王2099」2巻。1巻の時点で非常に面白いと感じていたが、この巻を読んでさらにその思いを強くした。帯にも書いてあったことだが、笑えるシーンもシリアスなシーンも含まれていて、どちらもそれぞれこの作品らしさが(主に主人公のキャラがぶれないという意味で)あって、良い。

ストーリー的には、この巻では主人公の一行が学園に少しだけ通うことになる。これも非常に好みのシチュエーションだ。これに関しての僕の考えというのは以下のようなツイートのものだ。

「科学の力使いまくって隠居生活」の更新があった。ホスフィンに教えてもらった。やはりいつ見ても変わらない安心感がある。

www.youtube.com

僕は一時期Minecraftをプレイしていて、そのときは工業化MODを大量に導入していたが、それは主にこの実況シリーズの影響を受けてのことだった。このシリーズに限らずほかの工業化MODの実況者のような、機械や配管であふれた拠点にあこがれて、とりあえずクアーリーで掘りぬいて巨大な箱を作ったは良いものの、モチベが続かず途中で技術を進めることができなくなり、スカスカなまま終わる……ということを経験した。どうやら早い段階で大量生産をしようとするとダメらしい。そのような段階で資材を溜め込むことにはあまり意味がない。まあもうMinecraftはしないはずなので、今となってはただの思い出。

ラノベを読んだり動画を視聴したりする間にもスライドは少しずつ進んでいて、ついに日付が変わるころ完成。句読点を。、から. ,に置換したりしてそれっぽい雰囲気は出ている。発表範囲的には昨日で半分弱のスライドが完成していたはずだが、後半はちょっと計算が多く、ページ数では今日は昨日の倍くらい作った。出来上がったので興奮してホスフィンに送り付けたところ、微妙にはみ出しているのはフォントサイズを変更することで対処できる、という指摘を受けた。それはそうすぎる。

夜、別のラノベを読んでいた。非常に良いシチュエーションがあった。

途中で眠気に耐えかね就寝。午前4時だった。

05/13(木)

午前11時起床。起きた瞬間感覚的に寝坊を感じ取ったので非常に焦っていたが、時計を見れば全然そんなことはなかった。学食に行く。

「個数制限なしナップサック問題の解」と言われた。確かに、胃袋をナップサックと思えば、僕の満足度を最大化できている。平常時はご飯(特大)を注文していたが、今日は提供されないらしかったので、迷った挙句ご飯(大)とご飯(中)を購入した。ちょっと多かったので、次回は中サイズを2つ注文することにしよう。

家に帰ってTwitter Web Appを開いたら、autocompleteが暴発してキーワード検索の欄に自分のメアドが入力されるようになってしまっていた。Chromeを再起動すると直ると聞いたが直らず。設定から手動でChromeの更新を行うと修正されたが、まだDMのあたりで暴発しているように見える。

午後1時、ゼミが始まる。また今週もゼータ関数の教科書は手に入れられていない。今日の内容としては、先週証明したゴツい公式をこねこねして解析接続を行うらしい。正直ゼミ後でもあんまりよくわかっていない。というかそれはそうで、途中で今日の典型90問のコードゴルフを始めていてはわかるものもわからなくなるだろう。資料を見直してキャッチアップしていきたい。

その後、僕が使っているほうの教科書の発表に移る。まず先週の残りがあるため、それが発表された。今日はそれだけで1時間くらいかかった。その後僕の出番が来た。30分くらいだと予想して、なんとかオタク早口を駆使してキリのよいところまで進めた。内容的にはそう……というものしかやっていないので、あんまり質問も来ないし、突っ込みもなかった。今日は15ページまで発表して、残り19ページあるので、来週は僕が残りを発表するためまた次の人がずれていく……。もうそろそろ1周すると思うが、このずれは初回にどのような感じかわからないまま1人が大量に担当してしまったためなので、担当範囲については気を付けたい。

僕が作ったスライドは以下に公開しておこう。読んでいる本は「Introduction to Analytic Number Theory (Apostol)」だ。

Apostol_Chapter2_2.8-2.11.pdf - Google ドライブ

終わってからラノベを読んだ。「隣のクーデレラを甘やかしたら、ウチの合鍵を渡すことになった」2巻。良かった。あとがきによれば、1巻で知り合って、2巻で仲を深めて、3巻で合鍵を渡すという構成だったらしく、無事に2巻が出るどころかすでに3巻まで決定しているのは安心感がある。

夜、サークルのバチャに出た。#522 div.1。4完して非常に良い出来。

Dashboard - Codeforces Round #522 (Div. 1, based on Technocup 2019 Elimination Round 3) - Codeforces

Aは、まず直接向かう場合を試して、そのあとスタートから縦または横に進んで直線に乗り、どこかで降りて縦または横に進んでゴールにたどり着く、というのを2x2通り調べればよい……はずだった。直接向かう場合の計算でオーバーフローして1WA。

Bも難しい。同じ重さのものだけ抜き出す必要があって、抜き出し方の通り数をdpで計算する。ところが、全体で重さが2種類しかない場合は、片方の重さを全部抜き出すことでもう片方も判別できるようになる、というケースが存在する。これに気付くのはかなり難しかった。

Cも難しいと思ったが、それっぽいことを書いたら通った。木なので端から詰めると最大マッチングが達成されるらしく、このとき頂点が「マッチングで使われた」、「マッチングで使われていない」、「その1頂点のみ孤立している」の3状態に分けられて、木dpできる。1頂点が孤立している場合は、素直に考えると「マッチングで使われていない」に該当しそうなものだが、1頂点だけ切り離すことが可能なため、このように分けて考える必要があった。

Dは基本的にはダブリングで、各階層でテーブルをセグメント木に乗せておく。円環における区間の端の扱いに気を使って実装したが、45ケース目でWAした。最大値の単位元が大きすぎるのでは?とか、以降探索しなくてよいと示すためのヤケクソな値が小さかったのでは?とか考えていたが同じケースでWA。結局ランダムケースを生成して試すことになったが、WAの原因はN=1の時だけ答えが0にならなければならないというものだった。正直愚直解の実装を少しでも違ったものにしていたら検出できなかったのではないかと思う。まあ通せたのでセーフ。

Eは時間を巻き戻すという機能を持つesolangで足し算を行う問題だった。まず2数の桁がそろっていないのがヤバそう。

夜、ラノベを読みながら眠気に負けそうになっていたら、Rubyで新手が出た。splitはブロックを取れるらしい。

atcoder.jp

日記を書いてすぐ就寝。午前5時だった。

05/14(金)

午後5時起床。12時間睡眠でいい感じ。

今日の典型が解けない。布団にうずくまって考えていたが、埒が明かないので学食に行った。夜の部はあまり行かないので混雑状況が読めなかったが、午後6時はかなり混む時間らしい。

帰ってきてまたずっと考えていたが、さらに1時間くらい経ってようやく解けた。燃やす埋めるであることに気づくのにこれだけかかったということ。コードゴルフC++ACLを使うくらいしかできることはないと思っていたけど、普通にNetworkXでよい。そもそもC++で書いている段階で辺の張り方がよくなかったらしい。鍵を開けるのにW円かかり中でA_i円得られる、というのを+A_i-Wと一本の式にして考えており、この場合負のペナルティを表現するために先に足しておいてから引くことになるが、実際は先にA_iの総和を求めておいて、鍵を開けるなら-W円、開けないなら-A_i円というふうに書ける。これで結構縮んだ。

NetworkXのグラフの頂点はかなり無茶苦茶できる。今回は使わなかったが、sourceとsinkを表現するのは0N+1でなくてもよくて、例えば-1とかG.add_edgeが使える。何回も呼び出す関数を変数に入れることで縮めるテクの副次的な効果。また、今回は使わなかったが、NetworkXのクソ長関数名を使う代わりにeval(dir()[])を使うテクニックを思い出した。

ラノベを1冊読んだ。「辺境都市の育成者」3巻。設定が非常に良い。「弟子がたくさんいて、皆大変に偉くなったが、まだ師匠を慕っている」というのも僕の好みの1つらしい。他にも同様の設定のなろうはいろいろあると思う。一点気になることがあって、これはこの作者の作品を読むたびに触れている気がするが、ひたすらセリフが読みにくい。「Aについて喋る。Bについて喋る。」「Aについて答える。Bについて答える。」というのはテキストによるコミュニケーションでありがちだが、これをセリフで一生やっているのは何とかしてほしいところ。

作品同士であまり関係はないが、同作者の「公女殿下の家庭教師」とは世界を共有している(ただし年代は全く異なる)ようだ。今巻ラストでは、「公女殿下」のほうで最近出てきたキャラと同じ姓の人が出てきてオッとなった。

2021/04/22に参加したバチャのupsolveを1つ進めた。

Cは二部グラフのように塗ってみてダメなところを少し修正するもWA。

週記(2021/04/19-2021/04/25) - kotatsugameの日記

https://codeforces.com/contest/1019/problem/C

解説を見てあーあとなるタイプの構築問題。今日書こうとしたら、解法だけ覚えていて問題を全く覚えていなかったため、有向グラフなのに双方向に辺を張っていた。この回のD問題は解説自体もかなり難しかったが、理解は済ませている。残りは書くだけなので、そのうちupsolveしたい。

yukicoder contest 295に出た。5完。

yukicoder contest 295 - yukicoder

Aはよい。BはA=1の点が重要。Cは余事象を考える。ここまでは一瞬で解けた。Dは、後ろから見て「ここにいたらマズい」という範囲を管理した。移動前にここにいたらマズいのか移動後にここにいたらマズいのかを取り違えていたらしく、4WA。

Eはいつもの偶置換・奇置換かと思ったが、ちょっと計算すると全部奇置換だとわかる。A<=Bとすると、まずmod Aが等しいインデックスの順序は自由にできて、このA個の自由に入れ替え可能なブロックをBで繋げるかという話になる。gcd(A,B)==1はよいとして、すべてのブロックから別のブロックに辺が生えていればよいと考え、1..N-BB+1..Nにすべてのブロックが含まれるかを見たが、WA。左と右のブロックで同一の組を繋いでいるとまずいのかと考えるも、A<=N-Bだと例えば4 2 36 3 4でWAになるので、ではA+1<=N-Bではどうかと投げてみると通った。繋げるということを考えると、グラフの連結性の話になって、辺がA-1本以上ないといけないというのがわかるらしい。ひたすらWAを生やしまくった。8WA。

Fはダメ。WolframAlphaでエスパーしようとしたが、Aがdistinctでない場合にゼロ除算が発生する。通分することでゼロになる項が消せるらしかったが、計算不可能だった。どうやら留数定理でも解けるらしい。試してみたが、微分するパートがわからなかった。

もう1冊ラノベを読んだ。「両親の借金を肩代わりしてもらう条件は日本一可愛い女子高生と一緒に暮らすことでした。」2巻。あんまり合わなかった。1巻読了時点では文章が合わないということを書いていたが、今回はさらにストーリーにも合わなさを感じた。どうやら性的なスキンシップを伴う恋愛ものがダメらしい、と言葉で書いてはみるが、正直自分でもよくわかっていない。なぜこのラノベのお色気シーンは受け付けなくて、「お隣の天使様にいつの間にか駄目人間にされてしまった件」のそれはオールOKなのか。

題名・あらすじ・イラストに惹かれて買った。「ラノベのプロ!」によれば、これはラノベのパッケージングが僕に刺さったということ。ただ文章がどうにも合わなかった。

週記(2020/12/21-2020/12/27) - kotatsugameの日記

日記を書き、布団に入って少しなろうを読んで寝た。午前7時半だった。

05/15(土)

午後3時起床。

今日はGW明けて初めての生協の弁当配達の日なので、起きておく必要がある。普段は生活リズムが完全にぶっ壊れていて、弁当を受け取ったら即座に二度寝するような体制で配達を待っていたが、今日はいい感じなので普通に起きていることにした。

弁当を受け取りつつ、午後6時までコードゴルフをしていた。最近更新が活発で10個以上取られている。勝てない。信じられないことに自分のモチベーションがあまりないらしく、古いコードを探して縮められているのを目にしながら、自分もそれをしようという気にならない。

今日の典型90問を解く。格子点だけを整数で扱う幾何ライブラリを整備していて、凸包も貼るだけ。あとはピックの定理で適当にやる。典型だなあという感じ。コードゴルフRubyComplexで、climpetさんに負けていたが何とか追いつき、変なことをして1Bだけ抜いた。

ABC201に出た。全完2WAで26位。適当にやりすぎ。

Mynavi Programming Contest 2021(AtCoder Beginner Contest 201) - AtCoder

Aはコードゴルフがどうなるかわからないので、Rakuで適当に書いた。FA。BはBashだと思ったが、挙動がよく分かっておらず2WA。そのあとしばらく時間を使ってVimで縮めていたが、結局負けている。Cはo?の個数をカウントしてどうにかするのかと思っていたが、冷静になると暗証番号のほうを全探索できる。Dは適当にDP。Eは、パスのxorが親とのxorから計算できることも、数列から2つ選んだxorの総和を計算するのも、それぞれ既出。組み合わせるだけ。Fは番号の小さいほうから何人かが左端に移動し、番号の大きいほうから何人かが右端に移動すると考えてよい。どちらかの人数を全探索して、もう一方をデータ構造で持つ。適当に書いてみるとRange AddとRange Minができればよいことが分かったので、遅延セグメント木を使う。

コードゴルフ。Aは3つの数の中にsum(A)/3が存在することを見るという解法がすごい。Bはなぜかd}が頭からすっぽり抜けており、負け。この2つは取れなくてかなり悔しさを感じる。CはRuby 73B、Perl 72B。よくわからない。DとEは適当にRubyで書いておいた。Fは僕のコンテスト中のC++が現状最短。

そのあとすぐGCJ2021 R2に出た。全完103位。Tシャツを得た。

Code Jam - Google’s Coding Competitions

Aは、単純に[1,N][2,N]、……を順に聞いて最小値を先頭に持ってくることが思い浮かぶ。さすがにこんな簡単なわけないだろ……と思いつつ試しに計算してみたが、どうやらこれでよいらしい。訝りながら出したら通った。Bは一番内側の多角形の辺数を全探索する。これが例えばkだったとすると、Nについて問題を解くのが(N-k)/kについて問題を解くことに落とし込まれるので、再帰的に解ける。実装して大き目のケースを試してみると爆速だったので提出、AC。

Cは難しく感じたが、頑張ったら解けた。stackを使ってシミュレートすることで、パンケーキの大小関係をグラフにできる。このグラフのトポロジカルソートを数え上げたい。一般のグラフでは難しいらしいので、グラフに何か良い性質があるのだろうと思ってじっくり睨んでみると、「すべての頂点の入次数が高々1」であることがわかる。合流しない、と言い換えてもよい。この場合は各頂点についてその子らをマージする通り数を二項係数で数えれば解ける。ほかにも「出次数が高々2」というのもわかるが、解法には関係ない。

最大のパンケーキを固定して分割する方法でも同様の解法になるが、そちらのほうが見通しがよさそうだった。

kkt89.hatenablog.com

dは、隣り合うマスをswapする以外は1点flipで済むので、どのペアをswapするかで二部マッチング。Dもフローで考えることにする。swapが連鎖するのが怖いが、ちょっと計算してみると、まずswapするペアは必ず「どちらも色を変える必要があること」「ペアの最終的な色が異なること」の2点を満たす必要があり、このときうまくswapをつなげることで(x,y)(z,w)だけを|x-z|+|y-w|回のswapで入れ替えられることがわかる。例えばGGMMGGMMの両端を入れ替えようとすると、GGMMGMGMGGMMGMMGGGMMMGMGGMGMMGMGGMMGMGMGGMMMGGMGMGMMGGMGと7回でできる。書き並べるとわかりにくいが、Gが右に動くのとMが左に動くのを繰り返すことでうまくほかの位置を変えないようにしている。

さて、ここまでできればあとは辺を張って最小重みマッチングをすればよい。いろいろググってハンガリアン法などを見ていたが、最大マッチングである必要はないので使えない。流量を変えつつ何回も最小費用流をしたくなるが、これは実はACLslopeという関数を使えばよい。

今年のGCJ R3進出ボーダーはABC3完だったようだ。CもDもかなりがっつり考察することになって、難しい問題だと感じたから、ボーダーはかなり高めに見える。年に一度古強者が集まるGCJと、普段のコンテストとでは、かなり感覚が違うのだろう。

日記を書いてから布団に向かったが、ふと思い立ってラノベを1冊読んだ。「株では勝てる俺も、カワイイ女子高生には勝てない。」という作品。あまり面白くなかった。株とかでお金持ちになる話は好きだが、この小説ではすでにデイトレードで成功した主人公がヒロインと関わって「人間らしさ」を得ようとする話で、実際の取引は(描写こそあるものの)本筋ではない。そのことはタイトルからも想像がついていて、まあそれならそれで良いのだが、話の本筋にもあまり身が入らなかった。主人公の人間味のなさというのが、すべてをお金で解決しようとすることで描かれていて、あまり受け入れられなかった。

もう1冊ラノベを開いたが、100ページくらいで眠気に負けた。午前8時就寝。

05/16(日)

午後4時起床。二度寝しようと思ってはいたが、布団でなろうを読んでいるうちにARCまで2時間を切ったので、そのまま起きていることになった。そこからコンテスト開始まではコードゴルフをしていた。

atcoder.jp

(0..59).sumのかっこを削るため、dfs関数の最後で0..59をreturnして使っている。これは僕の知る限りでは新手で、そこそこ適用範囲が広そうだったが、探しても縮むものは見つけられなかった。この問題自体も後にさらに縮められている。

ARC119に出た。5完30位でパフォーマンス2933、レートは2717→2741(+24)でhighestを更新した。

AtCoder Regular Contest 119 - AtCoder

Aはよい。Bはかなり迷走して20分かけた。最初は左から貪欲だと思ったが、これは全然違う。1の塊を丸ごと1マス横にずらすのが1手で行えて、その塊のイメージで考えていたが、何も得られなかった。頭を切り替えようとして順位表を見るとかなり通されておりビビるが、戻ってきてすぐ1と1の組を無視することを思いついた。すると隣接swapだけでそろえる問題になる……と思って実装したがサンプルが合わない。実際には、間にはめ込んだ1を乗り越えて進むのも1手でできるので、その分手数が少なくなる。結局、左から見て、Sにある1の塊とTにある1の塊のどちらかを管理しながら進めていくようにした。1発で通ったのだけはよかった。

Cは、区間の左右を0としたときに階差を1個飛ばしで足し合わせた値2つがどちらも0になることが条件。インデックスの偶奇で分けて先頭からの和を持ち、端の補正をしつつmapでカウントすればよい。これが見えるのは一瞬だが、実装で偶奇に神経をとがらせる必要があってつらかった。解説はかなりシンプルで、階差をとる必要がなかったのかと愕然。

Dは典型考察として、縦H個と横W個の頂点を作り、グリッドの点は頂点間の辺に変換することで2部グラフを作る、という方針が思い浮かぶ。問題設定をグラフに落とし込んでみると、連結成分ごとにある頂点を選んで、それ以外をすべて消すという操作ができ、最後に縦と横で残った頂点の個数の積を最小化することになる。辺を1本以上含むような連結成分だけ考えれば、縦と横どちらの頂点を残すかはどの連結成分でも自由なので、貪欲に決定することができる。復元もdfsで可能。辺を含まない連結成分も考えていたこと、ABを最小化するときはmin(A,B)を最小化しなければならないのに、逆に最大化してしまったことで2WA。

Eは最近こどふぉで見た気がする。しばらく時間を使って週記から該当する記述を探したが、当時の考察は結局意味をなさなかった。

https://codeforces.com/contest/1513/problem/F

Fはつらい。差分を計算する。

週記(2021/04/05-2021/04/11) - kotatsugameの日記

当時大苦戦したことを覚えていた。45分程度で正確に実装しきれる方針を選ぶ必要がある。どうやら当時は値でソートすることでうまくデータ構造を使ったようだが、今回は区間の両端という位置関係が重要なので、ソートはできない(後から知ったことだが、実はこれは大間違いだった)。A_r\le A_{r+1}なるrに対して、l\le rかつA_{l-1}\le A_lかつA_{l-1}\le A_rとなるようなA_lの最大値を求めるセグメント木と、l\le rかつA_{l-1}\le A_lかつA_l\ge A_{r+1}となるようなA_{l-1}の最小値を求めるセグメント木を書き、列の符号反転やreverseを4通り試して必ず2つのうちどちらかで差分が拾えるようにして解いた。これは、当時の日記における簡単だったほうのケースを無理やり拡張して難しいケースを解いたということ。

Eを通したら残り10分しかなく、Fがほとんど通されていなかったので、あきらめてA問題のコードゴルフをしていた。

Eの解説を読んで知ったが、ii+1の大小関係が等しいlrを選んだとき、l\lt rだろうがl\gt rだろうが同様に扱って計算した差分が達成可能であるようだ。コンテスト中はl \le rとなるように選んでいたが、その条件がなくなると話はさらに簡単になり、区間のオーバーラップを計算するだけなのでセグメント木も必要なかったらしい。というかこどふぉの解説でも同じことが書かれていた。コンテスト中は英語を読むのを嫌がってすぐページを閉じてしまったが、なんともったいないことをしたのか。

コンテストとしては、DもEも順当に解けたなあという印象。思ったより通されておらずびっくりした。B問題でかなり詰まってしまったが、パニックにならなかったのは良かった。

コードゴルフ。Aはループ条件をNの値に応じて決める必要がなく、一律で100回くらい回してよいことに気づかずに取られた。そこから6時間くらい試行錯誤して1B短縮できたのだが、よく見るとただのテストケースハックだった。b=1となるようなケースが入っていないらしく、例えばN=6で落ちる。ただテストケースハックしているだけなので、わざわざ方針を変えたのは長くなっているだけであり、もともとの最短コードを書き直すとさらに-2Bした。

BはPerlchar s:Schar t:Tを同時に見ていったとき、s-tの累積和をcとすると、s==0&&(t==1||c!=0)なる点の個数を答えればよい。$/=\1とすると1文字ずつ読めることを使って解いていたが、getcを使うほうが短いことに気づいて冷や汗が出た。CはAWK

週記(2021/05/03-2021/05/09)

05/03(月)

先週分の週記を投稿したのは正午くらいだった。今日は午後8時から競プロサークルで解説会があるし、準備も相変わらず手つかずなので、寝ないことにする。まあそれでなくても日曜日の起床時間は午後11時だったのだ。

昼食を手に入れるため、買い物に行くことにした。これまでは大学近くのコンビニまで行っていたが、より近くに小さめの店があることをGoogle Mapで確認したので、散歩がてら出向いてみることにした。店は小さく、品ぞろえもよくない。僕が入店したら爺さんが奥から出てきてレジに陣取るという、なんともいたたまれない感じ。確かにコンビニより近いし、標高差的にもこちらのほうが通いやすそうだが、これから先利用するかというと……うーん。まあ種類を選ばなければ食べ物は買えるから、利用してもいいのだが、いたたまれなさがすごいのが自分の中では一番の問題だったようだ。

帰ってきて、解説会の準備を始めるにも中途半端な時間であるから、ラノベを1冊読むことにした。「ルミナス☆アイドル」。主人公が幼馴染3人組をアイドルユニットとしてプロデュースするという話だ。設定は非常に好みであったが、話の展開の仕方があまり良くなかった。IKUTOという現役トップアイドルかつ学園の非常勤講師が、ことあるごとに主人公たちにアドバイスを与えたり助力をしたりするのだが、その頻度が高すぎるように感じられた。何もかもIKUTOにおんぶにだっこであるような状態では、プロデューサーとしての才能があるとされている主人公のそのすごさというのもよくわからない。IKUTOがすごいのは十分伝わってくるのだが。シリーズが続いていけば主人公の主人公らしさというのも徐々に明らかになっていったのかもしれないが、残念ながらこのラノベは1巻打ち切りであった。

解説会の準備をする。今日は僕だけが発表者になるらしい。ABC199のBCF問題のスライドを作成した。かなり時間に余裕があったので、解説会が始まる前にすでに今日の解説会の記録を公式サイトにアップロードする準備が整っていた。

さて、解説会が始まった。今日は見学2名、ホスフィン、僕の4名らしい。やはり連休の半ばであるというのは効いているようだ。今日はかなり気を付けて丁寧にしゃべっていたつもりだが、自分でそう思っているだけで普通に早口のままかもしれない。このF問題を全くの初心者に解説してもどうしようもないので、せめてもと思い二分累乗法について喋っていた。F問題の解説も終わりかけた頃合いで見学の2名が相次いで抜けてしまった。タイミングを見計らっていたのだろうか、だとしたら申し訳ない気持ちになる。入退室自由とは謳っていてもやはり気になるのは仕方ない。また終わる時間を明確に決めていないのもあんまりよろしくなさそう。

結局Meetはホスフィンと1対1になったので、サークル運営について話していた。いつかどこかでサークルが用意したセットをyukicoderで出題したいから、音頭を取ってくれ、といったことを言われた。僕は誰かの提案に便乗する気だったので、自分が主体となるらしくびっくりしていたが、それもサークル長の務めである。

午後10時くらいに布団に入ってスマホでなろうを開いたが、即座に寝落ちした。

05/04(火)

午前4時半、目を覚ます。布団で少しだけコードゴルフした。

例えばRubyは文の区切りとしてセミコロンと改行のどちらを使用してもよい。僕はこのような場合、自分の美意識に従ってできるだけ改行を使っている(しかし、この仕様はAWKでも同じだが、そちらはセミコロンを使っている)。改行を含むソースコードを提出するときは、CRLFではなくLFとして文字数を減らすため、特殊な提出方法を行う必要がある。特殊といってもUserScriptがあるので、それを導入するだけで済むのだが。

github.com

しかしこの提出方法は現状スマホからだと行うことができない。そういう理由があって、Rubyなどでコードゴルフする必要がある場合は毎回パソコンの前に座っているのだが、この時はPerlでゴルフしていたので、布団からでも提出できたというわけだ。Perlは、文の区切りはセミコロンのみである。

そのあとはなろうを読んでいた。午前5時から午前7時半までかけて、この作品を最新話まで読んだ。

https://ncode.syosetu.com/n6285gw/

最近はある方のツイートを見てなろうを漁っており、TSものが多くなってきている。この作品にはほかにも配信者要素、掲示板要素があって、好みだ。

午前8時から午後0時半まで、再度寝ていた。

yukicoderに問題が追加されていたので、解いた。

No.1498 Factorization from -1 to 1 - yukicoder

105までの素数は104個くらいしかないが、そのすべてで試し割りしていると微妙に間に合わなさそう。そこで、素因数分解する対象の数がi^2+1という特殊な形をしていることに着目し、必要となる素数を絞り込むことにした。素因数分解する対象を全列挙して、そのどれか1つ以上を割り切るような素数だけ抜き出してみると、個数はだいたい半分になった。抜き出すプログラムも手元では2secくらいで実行できたので、そのまま提出してみたのだが、見事にTLEした。オンライン実行で試してみたところ、手元では2secだったのがyukicoderのサーバ上では3secになっていてたまげた。

そこで、必要な素数と不必要な素数それぞれの特徴を調べてみることにした。4で割った余りが3でなければ必要な素数となるようだ。i^2+1\not\equiv 3 \pmod{4}ということから類推したが、どういう原理なのかは知らない。ともかくも、全探索によって正しいことはわかっている。これで素数を抜き出す箇所の大幅な高速化がなされ、AC。

しかし、抜き出した素数すべてで試し割りして失敗するような入力が続くとかなり時間がかかるらしい。そういうケースを作成してチャレンジしておき、改めて一度素因数分解した数値をメモしておくようなコードを書いて通した。解説を見たところ、もっとちゃんとした解法があったようだ。

コードゴルフのつもりでfactorコマンドに投げてみると爆速だった。最短コードについては、問題が追加された深夜の時点で%20さんがコードゴルフしていたようだった。

vectorの途中の要素が、一番後ろの要素とswapしてからpop_backすることで削除できるという話を聞いた。言われてみれば当たり前だが、かなり盲点。

外に遊びに行こうと思っていたが、今日の典型90問・031が追加されたのでコードゴルフすることになった。climpetさんとバトルしていたら夕方になってしまったので、今日は外出するのを諦めた。

atcoder.jp

dijkstra法を使用する問題でコードゴルフするため、Pythonを使っている。頂点の情報として2つの整数を組にして持つ必要があった。以前のコードだと数値2つをくっつけて1つの整数にしていたが、ここをtuple<int,int,int>にしたところ、TLEしてしまった。Pythontupleは遅い、という話は何度か耳にしていたので、仕方ないかと思いつつも、試しにtuple<tuple<int,int>,int>で持ってみたところ、これまでと変わらない速度でACしてしまった。かなり面白い。

レトルトのパスタソースを使用する際、これまではわざわざ別の器を用意して電子レンジにかけていたが、今日ついにパスタと一緒に茹でる決心がついた。テク自体は以前から知っていたが、パスタを茹でる時間とレトルトを湯煎する時間が合わず、断念していた。別にきっちり時間を守らなくてもよさそうであることに気づいたので決行。

何もすることがないので、以前の典型90問のコードを見直していた。7問くらい縮んだ。

夜中、CF div.3に出ようと思ったら、1日延期されていた。仕方ないのでコードゴルフ続行。典型90問・023はO(HW2^{W})で通したっきりになっていたが、ちゃんと想定解で出しなおしておいた。状態を圧縮して事前に番号を振るのをサボり、mapで処理していたのだが、以前に出した「dpテーブルの値が0のところから遷移しない」高速化をしたコードに負けてしまった。そちらの解法も、確かに圧縮こそしていないものの想定解の計算量と言えるのかもしれない。そのあとRubyに移植してコードゴルフした。

Array#max (Ruby 3.0.0 リファレンスマニュアル)

現在の実装では、先頭2つをまず比較して、そのうち大きいほうと3つ目を比較……というのを続けていく実装になっているらしい。おおよそeach_cons(2)のようなことができる。これまではreduceを使用して書いていたはずだから、縮むコードが存在するはずだ。そう思ってずっと探していた。1つだけ見つけることができた。

atcoder.jp

探している間も寝そうになっていたから、とりあえず一通り目を通したと思った段階で布団に入った。布団でなろうを開き、「転生したらスライムだった件」を読み始めた。主人公がなかなか人型にならなくてもどかしい。10話ちょっと読んだ段階で寝落ちした。午前6時だった。

05/05(水)

午前11時半起床。

テストケースハックでコードが短縮されていた。もともとVimだったのがsedになっている。[a-z][a-z]があってかなり縮みそうな予感がするので、Vimに戻して\lを使ってみたが、出力するために書いておいたYesesに反応してしまいダメだった。テストケースをダウンロードして、2つある[a-z]のどちらかがもっと短くならないか試していたら、なんと[a-z][ah]で通ることを発見した。左右どちらかを1文字にしてしまうとダメで、さらに2文字+2文字もすべてダメなようだから、この方針だと[a-z][ah]が最も短い。

今日こそ遊びに行こうと思って準備していたところでちょうど典型90問・032が追加された。このままだと昨日と同じことになるので、適当に縮めてすぐ切り上げた。

まずミスドで腹ごしらえして、ゲーセン。今日は「真千年女王」でSSSを達成した。2021/04/28に縦連が間に合わないと言及していたもの。前半の縦連は、今日やってみると普通に間に合った。後半は真ん中にノーツが増えて、それをカバーするために手を広げると間に合わなくなるようだった。このような場合は真ん中3鍵の連打を片手で処理することにしていたが、今日はこれが信じられないくらい下手くそで辛かった。ラストの4鍵は普通に難しいが、事前に家で再生速度を落とした譜面動画をじっくり見てきたので、そこそこうまくいくことが多かった。

ほかにも、13+のスコアがいくつか伸びたのと、13のAJが3つ増えた。明らかに速い鍵盤についていけるようになっている。

ゲーセン頻度的に考えれば、2021/05/09に閉店する仙台レジャーランド一番町店に来るのは、今日が最後の日になりそうだ。そこそこ感慨深くなりつつ帰宅した。今後はセガ仙台に行く。チュウニズム、より一般にセガ音ゲーをするにはここが最適だろうが、ボルテや弐寺の民はどこに行くのだろう。他人事ながら大変そうだ。

シャワーを浴びてCF #719 div.3に出た。全完。

Aは適当に書いたがちょっと怖かった。Bは桁を全探索する。テストケースごとに毎回計算してよい。Cは非常に難しかったが、4x4を手で構成している最中にひらめくことができた。連続する数を斜めに置いていけばよい。Dは超典型問題、非可算無限回見た。

Eは左端を全探索する。左端を1つ右に進めるとき、コストが1増える羊と減る羊がいるので、それを管理する。コンテスト後に知ったが、これはi番目の羊の位置をA_iとして\sum |A_i-i-x|の最小化となる。そういう言い換えをすると、AtCoderに全く同じ問題がある。

C - Linear Approximation

F1は二分探索。F2も二分探索で、1度聞いたクエリの答えはメモしておく。この時、クエリを聞く前・聞いた後に0から1になったものを補正するためにBITを使った。聞く区間の候補は218くらいあるが、答えるクエリが少ない以上、あまり細かいところを何種類も聞くことはない。GはスタートとゴールからBFSする。高々1回使用するワープポイントをどれとどれにするかは独立に決められる。

Gの入力が4e6個あるうえ、テストケースが120個以上あったので、ジャッジが詰まりまくった。scanfcin高速化より遅いので戦々恐々としていたが、ふたを開けてみれば1800msくらいで収まった。自前の高速入出力を使うと260msになった。

布団に入ってちょっとした競プロ関連の記事を読んでいたが、耐えられず寝落ちしてしまった。午前4時半だった。

05/06(木)

午前11時起床。大型連休を挟んで久しぶりに学食に行き、食事した。帰ってきてから、大学生協のオンライン書籍注文サイトで本を注文した。

午後1時からゼミ。

先々週のゼミの顔合わせの時には教科書を注文しようかとも考えていたが、なんとなく放っておいているうちに2週間が経過してしまった。

週記(2021/04/19-2021/04/25) - kotatsugameの日記

まだ買っていない。今日も無の状態でゼミに臨むことになった。今日のゼータ関数は、最初はフーンという感じだったが、途中で出てきた公式がものすごい形をしていてあえなく轟沈した。僕がメインにしているほうは少しだけ難しくなったような感じ。少し先にFormal power seriesという単語が見えてかなり興奮した。最後まで質問も発言もせず終了。

「プニキとはじめるリーグ運営 ~野球ゲーム?作って運営します~」が完結していた。

https://ncode.syosetu.com/n4212eh/

非常に面白かった。一気読みしたのでまだ細部の記憶が残っているが、その状態でエピローグとしてその後十数年の話をダイジェストのような形で見せられ、心がしばらく囚われてしまった。作者のブーブママさんの別作品であるVtuberものも、本編完結後定期的に小噺みたいなのがずっと入っていたが、本当に終了するらしい。いったん充電期間に入るとのことで、また新作が読めるのを楽しみにしている。

昨日のCF div.3のシステスが始まっていた。G問題のscanfはTLEしてしまい、なんとなく出しておいた高速入出力が通って何とか全完が保たれるという状態になっていた。ペナルティ的には1WAのカウントも含めて+24だが、僕より上にいた人も数名Gをシステスで落としたようで、順位は8位に上がった。dijkstra解を落としたかったらしいが、入力サイズはなんとかならなかったのだろうか。

AtCoder Jobsに登録し、インターンに応募してみた。

週記(2021/04/12-2021/04/18) - kotatsugameの日記

書類選考で落ちた。どうやらかなり人が集まっているらしく、僕のように内容が薄いエントリーシートは落とされる運命にあるようだ。自分に自信があるフリをしてそれっぽいことを書いておかなければならない。何もできないからと言って何もできないと書くとダメらしい。ともかく、インターンには行きたいので、また別の会社に応募してみた。AtCoderJobsでボタンを押すだけ。

大学の課題をする。まず2週溜めていた論理学の講義を視聴し、ミニットペーパーを提出した。初回・第二回はイントロのような感じだったが、今回から本格的に証明が始まる。導出規則が最初に並べられて、例題を通して扱い方を確認していく形式らしい。第三回はMPP、MTT、DNで、第四回はCPだった。CPはもう使い方からして面白い。今はまだ証明した命題が感覚的に何を意味しているのか理解できるが、もうそろそろ限界だろう。

次に数理統計学。課題はただの計算問題だが、3x3行列の逆行列を求める必要があるし、わざわざ注釈で計算機を使ってもよいと書いてあるから、遠慮なく使うことにした。これまではOctaveで書いていたが、浮動小数点数をそのままレポートに書いて提出するのはちょっと具合が悪い。そこで今回はRubyを持ち出してみた。やっぱり有理数型はいい。逆行列有理数型で求めてくれたのはありがたかった。冷静になると当たり前か。

夜、div.3のシステスがやり直されていた。かなり謎。

ほかにやっておくべき課題はまだ残っていたが、典型90問のコードゴルフを始めてしまった。まったく成果が得られないまま3時間くらい経過したところで、眠気に耐え切れず就寝。午前0時半だった。

05/07(金)

午前8時半起床。ゴミを出した。

そのあとはずっと布団にこもってなろうを読んでいた。最近は「転生したらスライムだった件」を読んでいる。やはり超人気作だけあって面白い。

https://ncode.syosetu.com/n6316bn/

以前TLに流れてきたファンアートが非常にかっこよかったので、そのシーンを読むのを楽しみにしていた。思っていたより早い段階で出会えて、すでに満足。

www.pixiv.net

能力のルビ振りについて気になったことがある。「英雄覇道」と書いて「エラバレシモノ」と読んでいるが、このように熟語の読みに熟語を噛み砕いて言ったような日本語をつけるのは、一時期流行ったのだろうか?他には「デスマーチからはじまる異世界狂想曲」でも見たことがある気がする。

結局昼間も布団から出られず、学食には行けなかった。夜になってようやく空腹がなろう欲を上回ったため、布団から出て学食の夜の部に行った。

途中でAtCoderJobsを確認したところインターンに応募した会社から返信があって、履歴書などを送る必要があるらしいことを知った。慌ててコンビニで調達しようとしたが、データでの提出ならネットにフォーマットが転がっているという話を聞いたので、とりあえずそちらを探してみることにした。

帰ってきてまたなろうを読み、時間になったのでyukicoderに出た。

yukicoder contest 294 - yukicoder

Aはかなり面倒そうだが、AWKで一発だった。Bは非常に難しい。90度回転しても手も足も出ず、実験してOEISに投げても何も得られなかったが、実験した盤面を出力してみると、N=3以降は中途半端な部分が全部埋まっているようだったので、その範囲を数える数式を気合で求めた。小さいところは埋め込むことになる。Cは飛ばしてDに移った。

Dは、やるべきことはわかるので丁寧に実装。連結成分ごとに見ると、1点の値をxと置いたときに他の点はA_0+xA_1-xのどちらか、または両方の形で表せることになる。これでxが一意に定まるならばよし、そうでないならば可能な範囲を求めて、またさらにmax<Kとなるような値も求めておき、最後に引く。

Eは解法ガチャに成功して良い方針を一発で引けた。公式解説は残念ながら読めなかった。公式解説のような方法で考察できれば強いのだろうが、できないものは仕方ないので、どのようにして解いたか記録しておく。

まず、数列Aをまとめることを考える。bitwise ANDが重要なのだから、まとめ方はゼータ変換と呼ばれるようなヤツで、自分を含む集合すべてについての和を求めておく。これを数列Sとしておこう。C_5を例に取り上げて実験してみる。

まず、Bの添え字としてありうるのは5の部分集合である0,1,4,5である。B_5に掛けられることになるAの和というのは、i \;{\rm AND}\; 5=5、つまり5を部分集合に含むようなi全てについての和であるから、S_5である。

B_4に掛けられるのは、同様にしてS_4とな……らない。S_5B_5のほうに吸収されるので、S_4-S_5である。同様にB_1に対してはS_1-S_5B_0に対してはS_0-S_1-S_4+S_5となる。

すべて足すとC_5=B_5S_5+B_4(S_4-S_5)+B_1(S_1-S_5)+B_0(S_0-S_1-S_4+S_5)。この状態でもかなり綺麗な形をしているように見えるが、実際のところSについてはめちゃくちゃ中途半端な和のため、扱えない。そこで、今度はSに注目して整理してみることにした。C_5=S_5(B_5-B_4-B_1+B_0)+S_4(B_4-B_0)+S_1(B_1-B_0)+S_0B_0

これはかなりきれいである。ちゃんと添え字が0まで出てきているし、符号の反転も規則的だ。これはいわゆるメビウス変換と呼ばれるものらしいが、そんなことは知らなくても適当に__builtin_parityを見て符号反転し、ゼータ変換してもう一回符号反転することで全て求まる。それを数列Tとしておこう。T_5=B_5-B_4-B_1+B_0だ。

C_5=S_5T_5+S_4T_4+S_1T_1+S_0T_0となった。添え字がそろっているのもうれしい。詳しく証明したわけではないが、もう見るからにC_k=\sum_{i\subset k}S_iT_iだろう。STに対し点ごとに積を取ってゼータ変換するとACした。

Fを結構長い間考えていたが、解けなかったので、Cに戻った。左から順に見ていくことで、各マスの確率が自分の1つ右についての1次式で書ける。ここで右から順に見ていくことでどんどん確定させていける。有理数が怖かったのでRubyを使った。そのあとまたFを考えていたが、結局解けずに終了。

Fは、まず畳み込みで'i''n'の間に何マスあるペアがいくつ、というのが数え上げられる。ここで止まってしまったのだが、コンビネーションを分解することでまた片方の列をreverseした感じの畳み込みにできたらしい。言われてみれば本当にそうなんだが……。

直後にCF #720 div.2。4完。かなり難しく感じた。

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

Aから1WAした。B>1が条件で、ABAA(B+1)を出力すればよい。ABで割り切れる、ではなくABで割り切れるだと思っていて、A%B!=0が条件だとしていた。

Bも非常に難しかった。ずっと隣り合うペアに対して操作することだけ考えていた。冷静になると、数列の最小値を選べばもう片方はやりたい放題。僕はminとmin+1を交互に並べたが、TLでは1e9+7を1つおきに挟んだ人もいたらしい。なるほど。

Cは、クエリ回数の制約が二分探索をしなさいと言っているので、判定できそうな質問を探した。結果t=2でx>=p_iが判定できるようだったので、それを使って1つ求める。残りの数字は、今わかったものと組み合わせてt=1でmaxを得たりt=2でminを得たりする。maxになるものとminになるものどちらが多いか確認しておけば、全体の高々半分しか再チェックに回らないため、クエリ回数の制限に通る。微妙に眠い頭でminとmaxと変数が入り混じった式を扱うことになって大変だった。

Dはただの木DFSだと思ったけどWA on pretest 2。「工」みたいなグラフは、真ん中の棒を切るのが一番良いが、適当にDFSすると足の片方を切ってしまう。Eは解けず。

夜中はずっとコードゴルフをしていた。Perlに新手が出た。

atcoder.jp

無向グラフの読み取りにはこれまでmap{push@$_,$_[--$|]for@_=glob}<>という決まりきったイディオムを使っていたが、自己ループの存在が問題にならない場合、@_ごとpushしてしまってもよい。これはかなり適用範囲が広い。

布団に入ったら即座に寝落ちした。午前8時だった。

05/08(土)

午後4時起床。

寝る直前に今日のぶんの典型90問の問題を読んでいたが、まったくわからないまま眠ってしまった。起きて再度考えてもすぐにはわからない。結局実装を含めて1時間半くらいかかった。

解法はこうだ:dfsの行きがけ順に頂点に番号を振り、それでソートして隣り合う頂点のLCAを求めておく。このLCAが深い順に隣り合う2つのペアをマージしていき、グループの代表の点は元の代表の点2つのLCAにしていく。以前までの代表の点と新しい代表の点との間の距離を答えに足す。

今日は午後8時くらいからへのkと一緒にちょっとした配信をする予定だ。VSCode拡張機能で画面共有して行うらしいので、手元にセットアップすることになった。適当にインストールしてC++シンタックスハイライトとVimのコマンドを入れたが、操作性はVimのままGUIの特徴も兼ね備え、さらにIDEっぽいこともしてくれる、かなり便利な環境になった。しかしてIDEではないのだから、コンパイラインタプリタについてはこれまで自分が使ってきたcygwinが対応するというのも嬉しい点。これから競プロを始める人はVSCodeを使うのが一番良いだろう。僕はかたくなにcygwin+Vimで続けるつもりだが。

昨日のPerlコードがさらに縮んでいた。argmaxがかなり上手いが、なんとなく既視感があるので、一度見たけど忘れていただけのテクニックかもしれない。忘れちゃ意味ないよ。

atcoder.jp

そうこうしているうちに配信が始まった。15分くらいで終了。

事前に少しだけ打ち合わせみたいなことをして流れは決めておいたが、セリフはほとんどアドリブであった。改めて聞き直すと、2人が一緒に喋っている瞬間や、僕がそれを恐れて無言だったりボソボソ喋っていて聞き取れなかったりしたセリフがあった。またやはり全体的に滑舌に難がある。せっかく人前で喋るのだから、そういうこともちょっとは考えておきたかった。

ABC200に出場した。全完17位。

KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200) - AtCoder

A、Bはよい。Cは親の顔より見たタイプの問題。Dはdpして復元した。Eは、まず3つの値の総和が特定の値になる場合の数を包除原理を用いて計算し、これを利用して求める組の3つの値の総和がいくつになるか計算した。これはO(N)で、残り1つずつ決めるのにもO(N)かけた。

Fは0と1が切り替わる回数に注目すればよい。この回数がk回のとき、操作回数は\lfloor\frac{k+1}{2}\rfloorとなる。kの偶奇で分ける必要があるが、これは両端の文字が異なるかどうかを見て足す値を制御することで通常の除算にできる。両端の文字としてあり得るものを最大4通り探索して、それぞれに対し0と1が切り替わる回数を計算する。実装の都合上文字列Sが1文字だと面倒なことになるようだったので、この場合だけ先に処理することにした。S="0"S="1"の場合は明らかで、S="?"の場合は愚直に計算した結果をOEISに投げてK2^{K-2}となる。

Dは微妙に噓解法だったらしい。同じインデックスから2通りの列を作成するのが難しそうだったので、2つの列の最後のインデックスが異なる値にできると思って実装していたのだが、これは200 1という数列が反例となって成り立たない。

コードゴルフ。Aはdcで8Bを書いて暫定的な最短だったのだが、Vimに負けた。Vimの8Bは確認していたが、不必要なコマンドがあることに気づかなかった。数値をインクリメントすると、カーソルはその数値の末尾に移動するため、わざわざ$する必要はない。

Bはdc。場合分けを減らすため、2種類の値を両方用意して、適当にスタックの深さをいじってrしている。N%200という値で割り算を試みることで、0の場合はそのまま、そうでない場合はスタックトップの値を潰せる。これはかなり上手かった。Cもdc。

Dは想定解の鳩ノ巣原理がかなり賢い。探索する回数はかなり少ないので、Rakuでも間に合うようだ。またRubyのcombinationは取り出す要素の個数を指定する必要があるが、Rakuは指定しないことで2N通りすべてを(lazyに)列挙してくれるので、その点でも縮んでいる。EFは手つかず。Fは現在の最短コードがアルゴリズム的にかなり上手いようだが、読解していない。

深夜、SRM805に出た。EMの2完で11位。Eが落ちまくったので、コーディングフェーズ終了直後から見たら順位が半分くらいになった。

https://community.topcoder.com/stat?c=round_overview&rd=18678

Eは気合い。端っこで動けなくなるケースは自力で気づけたが、サンプルに入っていて安心感がある。intの3つ組をmapに入れるのはかなり恐怖なので、2つ組に留めておいて、代わりにmapを9個くらい持った。入力を乱数で生成するが、生成方法の疑似コードと一緒にC++等の実装が提供されていたのもありがたかった。

Mは桁DPで、使える数字のうち最も左にあるものを使うという条件を入れることで重複を省ける。実装上は以前に出現したときのdp配列の値を引けばよいらしい。細かいことは考えずに実装したら大体のサンプルがあって、0始まりのケースを抜き忘れていたので抜くと全て合った。……簡単に言ったが、最初の段階で空文字列を抜くために答えから1引いていたのを忘れていて、サンプル1(答えが1になるケース)がずっと0になっていて困っていた。もっと別のケースを見ると1引いているのに気づけただろうが、答えが0になっているのを見るとどうしてもdp遷移のバグを疑ってしまう。

Hも読んだ。中点を列挙してどれだけ覆えるかbitsetで持ち、2つの中点ですべてを覆えるならマッチングみたいなことをして復元できそう、までは考えたが、中点と完全に重なる点の存在・マッチングの結果片方の集合が空になってしまう場合の検出がよくわからなかったので実装せずに終わった。後からkmjpさんの解説記事を読んだが、二部マッチングでよい理由も、片方の集合だけで完全に覆える場合をもとから考えなくていい理由もよくわからなかった。

TopCoder SRM 805 : Div1 Hard TwoGalaxies - kmjp's blog

朝方、しばらくコードゴルフをしてから布団に入り、「転生したらスライムだった件」を読み進めた。午前7時から午後1時半までかけて80話くらい読んで、さすがにまずいと思い就寝。

05/09(日)

午後8時半起床。今日はARCだが、開催時刻がいつもより1時間ちょっと遅いので、ゆっくりしていられた。

昨日の典型90問は、dfsの行きがけ順にソートした後両端をつなげて隣り合う2頂点間の距離を求めると、その半分が答えだったようだ。また、ソートして隣り合う2頂点のLCAを求めておくと、それ以外の点が必要になることはないらしい。これは、ある連続する3頂点をマージするとき、左の2頂点のLCAと右の2頂点のLCAはどちらも真ん中の頂点の親なので、その2つの間にも親子関係がある、ということを一般化するとわかる。

ARC118に参加した。4完で48位、パフォーマンス2762、レートは2712→2717(+5)で1だけhighestを更新した。

AtCoder Regular Contest 118 - AtCoder

Aから難しい。税抜き価格が100円増えると税込み価格は100+t円増えて、その間に被りはないので、t種類の金額が税込み価格として現れない。これを利用して探索範囲を狭め、残りを愚直に計算する。微妙に合わせるのに失敗し、10分くらいかかった。

Bはほとんど明らかなように感じられた。最初はB=\left\lfloor\frac{AM}{N}\right\rfloorとしておいて、足りない分どこに1足すかは足す前と足した後の差を見てソートして決める。しかし今書いていて気付いたが、一つの要素に補正として2以上の値を足すことがない、という事実については証明していなかった。

Cは、3*5*7*112*32*52*72*11を用意して、ほかに偶数かつ35711のどれかで割り切れるものを列挙した。

Dは、まず原始根を取って言い換えることで単純な足し算引き算の問題になることに気づいて興奮したが、実際はほとんど意味なし。a,bそれぞれの位数を{\rm ord}_a,{\rm ord}_bとしたとき(これは原始根を取らなくても計算できる)、{\rm lcm}({\rm ord}_a,{\rm ord}_b)\lt P-1ならば答えはNo。そうでない場合は、100マス計算みたいにして{\rm ord}_a \times {\rm ord}_bマスを埋めてみると、適当な長方形の範囲に重複なく全て出現していることがわかるので、そこをジグザグに辿る。この辿る部分は原始根を取ったところで見えるものではなかった。

提出するとREとWAが出た。オーバーフローを見つけたので、WAもこれだろうと思って提出しなおしたら、普通に間違っていたらしく再度WA。ジグザグに辿っても1に戻ってこれない場合があって、これは取った長方形を高さが奇数になるように置いて横にジグザグに辿ったときに発生する。P=2の場合を特別扱いすることにすると、P-1は必ず偶数になるから、長方形を取り直すことで必ず高さを偶数にできる。その処理を加えてAC。

Eは、サンプル1の2種類のマス目に経路数を書き込んで足し合わせてみたりしていたが、何もわからなかった。解説を読んだが、結局、順列を考えるというよりは、縦と横に被りがないような障害物の置き方と考えるほうがよくて、このとき自分の縦と横を見るdpが出てくるようだ。

コードゴルフ。Cは2*32*53*5のどれかで割り切れる数を列挙するだけでよく、RakuのJunctionがかなり効く。Bは適当にRuby

Aは面倒だと考えていたが、\left\lfloor\frac{100N-1}t\right\rfloor+Nという単純な式で書けてしまうらしく、気づいた時にはdcで提出されていた。この式について考えてみる。

まず、解説の周期100+tについて、そのうち具体的にどこがスキップされるのか考えると、\left\lfloor\frac{tA}{100}\right\rfloorの値が動いたところだと分かる。よって1\le k\le t番目のスキップはA=\left\lceil\frac{100k}{t}\right\rceilによって達成される。ここで、本来A円だったのが税込みでk円増えたということだから、実際にスキップされた金額はA+k-1=\left\lceil\frac{100k}{t}\right\rceil+k-1円となる。

さて、N番目にスキップされた値というのは、まずそこに至るまでに周期が\left\lfloor\frac{N-1}{t}\right\rfloor回繰り返されて、その次の周期における(N-1\bmod{t})+1番目のスキップによるものである。q=\left\lfloor\frac{N-1}{t}\right\rfloorr=N-1\bmod tと置いて立式してみよう。そこまでの周期による(100+t)qと、今注目している周期における\left\lceil\frac{100(r+1)}{t}\right\rceil+r+1-1を足せばよい。tq+r=N-1であることを考えると100q+\left\lceil\frac{100(r+1)}{t}\right\rceil+N-1になる。

\displaystyle 100q+\left\lceil\frac{100(r+1)}{t}\right\rceil+N-1=\left\lceil\frac{100tq+100r+100}{t}\right\rceil+N-1=\left\lfloor\frac{100(tq+r)+99}{t}\right\rfloor+N=\left\lfloor\frac{100N-1}{t}\right\rfloor+N

よって確かに答えが\left\lfloor\frac{100N-1}t\right\rfloor+Nとなることが分かった。

今週木曜日に応募したインターンだが、選考書類を提出するよう言われていたのだった。履歴書のwordファイルを落としてきたりして何とか錬成し、メールで送った。