06/07(月)
先週の週記を投稿してからの話。ちょっとハーメルンを開くことがあって、面白そうなものを1つ見つけたので読んだ。ターニャ・デグレチャフがダンブルドア世代のホグワーツに入学する話で、設定に惹かれたのだが、すでにエタっていて涙。
いろいろな人の週記・日記を漁っていた。僕の友人の一人もサイトを自作して週記を書こうとしているようだ。サイトにこの「kotatsugameの日記」のリンクを貼ってくれているようなので、こちらからもここで紹介しておきたい。
ABC204Dが縮んだ。縮んだというか、実は解法がAGC020C-Median Sumと全く同一らしく、そちらのコード(ABC204の元最短コードより短い)をコピペしてきただけ。問題文だけ聞いても同じであるとは思いにくいが、コードを見れば解法が全く同じであることは直ちに理解できる。
大学の課題をする。まず数理統計学のレポートを終わらせた。こちらはちょっとした課題を解くだけなので、簡単。問題は数学基礎論特選のレポート。
「数学基礎論特選」という講義のレポートを書いていた。3回分の講義資料を読んで、途中にある問題からいくつか選んで解く。
週記(2021/05/10-2021/05/16) - kotatsugameの日記
この日から1か月経過したということで、また3回分の講義資料が溜まり、同様に問題を選んで解く課題が出された。3回ごとに1区切りつくらしいので、前回の講義資料の最後のほうは全然わからないまま放置していたのだが、どうやらその後も続きの話をしていたらしく、慌てて前回格闘した記憶を呼び覚ましながら講義資料を読んでいた。ただ、前回ラストで僕の頭を破壊したゲーデル数や証明可能性についての記号などが、今回は様相論理として□に吸収されている(?)ので、それをそういうものと捉えることで何とか講義資料を読み進められている。
しかし3回分のスライドのうち1回目の半分まで読んだ段階で嫌になってきてしまい、布団に寝っ転がってなろうを読み始めてしまった。
かなり眠気があるが、せっかく起きているのだしということで学食に行くことにした。
平常時はご飯(特大)を注文していたが、今日は提供されないらしかったので、迷った挙句ご飯(大)とご飯(中)を購入した。ちょっと多かったので、次回は中サイズを2つ注文することにしよう。
週記(2021/05/10-2021/05/16) - kotatsugameの日記
— こたつがめ (@kotatsugame_t) 2021年6月7日
店頭の表示ではご飯の特大がありそうだったが、注文する場所に掲示されているものを確認すると、そちらでは特大は存在しなかった。やはり提供されていないのだろう。
帰ってきてまた布団にダイブしてなろうを読んでいたが、すぐ力尽きて寝落ち。午後1時半から午後8時まで寝ていた。
起きてすぐ典型90問の今日の分を解く。今日は左右からLISをする。Rubyで書いてニコニコしていたが、すぐ大幅に縮められた。よくわからない。
解いてからまた布団に戻り、なろうを読んでいたら寝落ちした。午前1時だった。
06/08(火)
午前7時半に目を覚ます。寝落ちばっかりで自分の体調がよくわからず、なんとなく眠さを感じつつ午前11時半まで布団でなろうを読んでいたが、今日もまた起きているのだし、と学食に行くことにした。
— こたつがめ (@kotatsugame_t) 2021年6月8日
昨日の写真でも確認できるが、ご飯はシートをかけた状態で提供される。「最近はこうなのか」という指摘があったが、これは別にコロナ対策とかではなく、僕が入学した当初からこのようにされていた。特にお昼時、混雑する時間帯のご飯の提供はすでに盛られたものが棚に並べられているため、乾燥を防いでいるのだろう。
選考プロセスが遅れるかも、という話があったものの、今日聞いた感じだともう来週には会議にかけて下さるらしい。
週記(2021/05/31-2021/06/06) - kotatsugameの日記
このインターンに内定が出た。ありがたい限り。手続きはすぐに行うが、実際に働き始めるのは僕の院試が終了してから、つまり9月くらいからになるようだ。
1333話!
1333 pic.twitter.com/ErOli9b1Uh
— こたつがめ (@kotatsugame_t) 2021年6月8日
今日の典型90問が投稿されていたので、解いた。コードゴルフとしては、配列の両端を変数で持っておいて左右に伸ばす実装がよい。として持つとアクセスがになるが、]として持つとでアクセスできる。工夫としてはそのくらいだろう。
また昨日のレポートの続きに取り組む。昨日はある程度講義資料を読んでから問題に取り組もうと考えていたが、そんな余裕はない。何とか解読できた問題に全力を注ぐと、ちょっと怪しいところはあるが、とりあえず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時まで起きていられたので、今日も学食に行った。
— こたつがめ (@kotatsugame_t) 2021年6月9日
毎日同じものを食べるというのは一種の儀式でもあるわけですよ
— こたつがめ (@kotatsugame_t) 2021年6月9日
今日は結構早くに家を出たので、午前11時過ぎには食事を終えられた。昼休みが始まる前、人が少ないうちに床屋に行っておくことにした。かなり眠くて、髪の毛を切ってもらっている間はほとんど意識がなかったが、今日担当してくれた人がかなり威勢がよく、ジョキジョキ音を立てて鋏を動かしていたことを覚えている。というか鋏に髪の毛が挟まってかなり痛かった。しかし出来上がりは良さそう。髪の毛の生え方の左右非対称性などを説明されたが、それを考慮して長さを調節しているらしい。
床屋を出て家に帰ろうとしたが、横断歩道がない箇所で道路を横断しようとした際、近づいてくる車に気づけなかったらしい。前から車が来ているのにフラフラ車道に自転車を漕ぎだしてしまい、かなりヒヤッとした。確実に見えているはずの近さだったが、寝ぼけていたのだろうか。
床屋で待っている間に典型90問が投稿されたことは確認していた。今日の問題はグラフを作ってBFS。Rubyで書いたらPerlに取られたが、ちょっと格闘したら取り返せた。BFSで使うキューを@0
にすることで、グラフを作るのとBFSの始点をキューに入れるのをほぼ同じコードでできたのがよかったのではないだろうか。
また布団に戻ってなろうを読んでいたが、午後3時くらいに寝落ちした。
06/10(木)
06/09 午後8時に起床。
今週月曜日の典型90問についてはRubyでかなり負けたと書いた。その問題は数列の左右からLISを計算するが、数列の左右から同様の処理をした後にマージするという意味で似たような問題が存在し、そちらも縮んでいる。その最短コードを見ることによって、月曜日の問題がどのように短縮されたのかが少しだけ窺い知れていた。その問題のコードゴルフはちょっとだけ取り合いが発生していて、火曜日にもちょっと縮んでいた。今日も少し縮んだ。
似たような処理を2回行うということで、以前はproc
を作成していたのだが、コードを文字列として2回繰り返すほうが短いらしい。毎回reverse!
することで、数列の左右から処理を行うこともできている。
コードゴルフした後はまたなろうを読み続けていたが、午前1時半から午前4時半までまた寝落ちしていた。
起きてからもなろうを読み続け、午前11時半になったので学食に向かった。
— こたつがめ (@kotatsugame_t) 2021年6月10日
帰ってきてしばらく週記を書きつつ、今週のゼミに参加した。ビッグオーの記法が導入されたが、と書くと等号なのに推移律が成り立たないということが言われていた。これは僕にはない着眼点ですごいなあという気持ち。という記法もあるらしいという指摘をした。等号に右から左への向きがある、という考え方もあるらしい。あとは、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はa
とb
の素因数の個数がk
以上ならばよくて、k=1
の場合がコーナーケース。コーナーケースには気づいていたのに、a
を素因数分解するコードをコピペした時の修正ミスで1WAしてしまい赤っ恥。Eは長さと"haha"
の個数と左右3文字ずつを保存しておく。面倒。Fはと変形する。桁ごとにみるととわかる。半信半疑で出したら通った。
Gはfloorがからむ最小値で、線形計画法のような図を描いてみると三分探索できそう。ただfloorがついたそれには最近煮え湯を飲まされたので、ABC204Eと同様floorを外してから三分探索した。TLを見ていると、多いほうから優先的に引く貪欲でもよいらしい。x
とy
が近づくまでは割り算で一気に計算し、あとは2回ずつペアにして引くことを考える。
全完してからは布団に入り、眠気をこらえつつなろうを読んでいた。午前5時半就寝。
06/11(金)
今日はぜひとも学食に行きたいと思ったので、目覚ましを午前11時と午後0時半にセットしていた。午前11時の目覚ましは、止めた記憶こそあるものの、瞬時に二度寝してしまったらしい。目を瞑った次の瞬間再度目覚ましが鳴り響いたと感じた。
今日の典型90問が投稿されていた。最初は遅延セグメント木を書いてしまったが、これは明らかに寝ぼけている。ほとんど同様の問題が僕の参加したJOI本選の第1問目だったことを覚えていて、その解説を見て、データ構造など必要ないことに思い至った。とりあえずそれで通しておき、午後1時くらいに学食に行った。
今日も納豆ご飯を食べようとしたが、お昼過ぎとあって大したものは残っていなかった。納豆も一見売り切れかと思ったが、よく見ると普段とは別のところに2個だけ残っていたので、これ幸いと確保。サラダ類は売り切れていたので、適当な副菜を購入した。
— こたつがめ (@kotatsugame_t) 2021年6月11日
これで5日間毎日ほとんど同じものを食べていたことになる。水曜日にも言及したように、これは儀式の一種であるが、とはいえ別に何か念願があるわけでもない。毎日同じものを食べていたら面白いかなと思ったが、反応は全然ないので、結局自分の行動を常に追いかけている人、つまりは自分にしか通じない面白さだったということ。
帰りに購買に寄って新刊の短編集を購入した。米澤穂信さんの手になる短編も収録されているとのことで確認すると、見覚えのないタイトルだったため、書籍には初収録であると判断したのが購入の決め手。奥付を見たところ、この判断は正しかった。
ほかにもカロリーメイトを購入して帰宅。
15段 pic.twitter.com/78p2vqZT9t
— こたつがめ (@kotatsugame_t) 2021年6月11日
帰ってきてしばらく今日の典型90問のコードゴルフをし、そのあと布団でなろうを読んでいた。ちょっと寝なおそうかとも考えたが、なろうを読んでいるうちに時間は過ぎていき、結局寝ないまま午後6時半になった。サークル解説会の準備をする。
今日はABC204の解説会の予定。F問題の解説を書いたらもうかなりいい時間で、E問題の解説も書けるかと思ったが、微妙に間に合わなかったのでかなり適当なスライドになってしまった。今日はこの2問だけの発表で、参加者も3人。僕がひとしきり喋って、終了した。先週の記事をふと見ると、日付がコピペ元のまま変わっていなかったので、直しておいた。
2021/06/11 定例会 | puzzleknot 公式サイト
そういえば昨日のCFのシステスが終了していた。全完10位。ちゃんと通ってよかった。
yukicoder 299に出た。滑り込み全完。
yukicoder contest 299 (BANNED CONTEST) - yukicoder
Aはよい。入力を加工してdcに流し込む方法で現在の最短コードを持っている。Bは面倒だが拡張ユークリッドの互除法で解いた。解説を見るとを全探索するのでもよかったらしい。Cは赤字の制約が怪しいが、実は全部同じコードで解ける。復元が怠い。Dは係数を求めると1乗、2乗、3乗の和になるので、公式を使って和を消す。
Eは最初勝敗が決まるまで延々ゲームを続けるのだと思っており線型方程式を解こうとしていたが、よく見るとただの行列累乗。さすがにもう行列累乗は飽きた。謎のREが出てしばらくコードとにらめっこしていたが、入力に制約違反があったらしい。
Fはなんちゃらモーメントなるヤバそうな単語が見受けられるが、よく見ると偏差を乗して足しているだけ。の時は0での時はいわゆる分散、つまり2乗の平均引く平均の2乗。もしかしてのときも……?と思って計算してみると、3乗や4乗の平均まで計算しておけば求められることが分かった。遅延セグ木に5個くらい値を載せる。列が円環なのも面倒ポイント。
Gは包除原理。愚直にやれば、の時はのdp配列を作って計算したくなる。これにはおおよそくらいの計算が必要になる。つまり全体で。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に参加した。
5完31位、パフォーマンス2955、レートは2724→2749(+25)。D問題までは非常に良かっただけに、E問題での失速が気になるところ。まあレートはいい感じに上がったので良かった。
Aは普通に考えれば最後の文字を持つdpだが、新しく足すの寄与を計算する必要があるため、値だけではなく場合の数を求めるdpも同時に行う必要がある。見た瞬間に解けた。FA。
Bはちょっと計算するとになる。これは下に凸な関数なので、すべて足した値も下に凸となり三分探索できるが、コンテスト中の僕は三分探索を信用できなかったため、もうちょっと考察した。はで最小値を取る。グラフを書くと、そこを境に傾きが-1から1になっているわけで、これは絶対値関数の平行移動である。つまり、そのmaxいくつかの和は、の最小化と同様に考えれば、いずれかのについてで最小値を取る。これで探索すべき値が個になり、左と右で和をもつことですべての場合について計算できる。さらに考察を進めれば候補の中央値を取ればよいこともわかるが、コンテスト中はすべて試す方針で通した。
Cは難しい。ちょっと手で計算してみると、値を大きく増やすにはx+=y
とy+=x
でフィボナッチ数列を作るくらいしか手段がなさそうだとわかる。フィボナッチ数列から適当に要素を選んで和を取ると任意の非負整数が作れる、というのは(それが値の大きいほうから貪欲に取って良いことも含めて)競プロでよく見る定理。今回も、適当なタイミングでx
かy
を1増やしてやることによってフィボナッチ数列を途中から始めて合流させる感じにできそうなので、方針としてはこれでよい。ただ実装が面倒。とりあえずフィボナッチ数列が何項目まで必要かとどのタイミングで増やすかだけ確定させて、偶奇は最後に帳尻を合わせることにした。出力を見ていてもよくわからないが、ランダムテストを回した感じではよさそうだったので提出、AC。解説だと、使うフィボナッチ数列の長さを決め打つことで偶奇を決め打てるようにしていた。
Dはかなり簡単だった。まず最上位bitで場合分けするのはすぐわかる。0と1が両方偶数個あるならそれぞれで再帰し、1つ下のbitを見る。奇数個ある場合を考える。現在見ているbitが0であるような要素a
と1であるような要素b
についてのa^b
の最小値を求めると、実はそれが答えになる。なぜなら、Aliceがa
かb
を選んだタイミングで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だが、こちらはVimでRubyコードを書くテクでさらに縮んだ。
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=4
、K=3
という入力の時に聞く回数が3,1,1,1
のような列を使ってしまい、1WA。クエリ回数が2回のはずなのに聞く回数が3の要素があるとダメということだ。
つまり、項の非負整数列とがかつを満たすとき、個の要素を選んで同時に1引くことを繰り返しての値をすべて0にできるという事実と、実際の方法は値が大きな要素から貪欲に個ずつ選ぶことで構成できるということ。何回かこの事実を用いる問題を解いた覚えがあるが、証明は覚えていない。TLを見る限りに関する帰納法が回るらしい。
コンテスト後のTLでもいろいろ解法が流れてきた。僕のようにできるだけ均す方法やフローを流す方法もあったが、一番すごかったのはSSRSさんの、聞いた回数が奇数回のものの個数をもってグラフを作成しBFSする方法。
E: 「n 個の電球があり最初はオフになっている。一回の操作で k 個の電球の状態を変更する。電球を最小回数すべてオンにする操作手順を構築せよ」という問題に帰着。電球の個数を状態として持つ n+1 頂点のグラフ上で BFS を行い経路復元
— SSRS (@SSRS_cp) 2021年6月13日
F1は連結成分をまとめた後辺を張ってSCCし、入次数が0の頂点を数えた。後から考えてみれば、連結成分をまとめる必要はなかった。F2は、SCCした後のDAGにおいて到達できなければならない頂点がいくつか指定され、それらすべてに到達できるような頂点集合の最小サイズを求める問題になる。DAGの道被覆というワードで調べたりしていたが、よく考えるとこれは違う。グリッドからグラフを作成したので、それによってグラフが持つことになる特徴を利用するのだと思ったが、わからずに終わった。
どうやら、入次数が0の頂点を抜き出してグリッドの左から順に並べておくと、ある頂点に到達できる入次数0の頂点は区間になるらしい。つまり、区間がいくつか与えられるので、それぞれの区間に含まれる頂点が1つ以上存在するように頂点を選ぶ問題になって、これは区間スケジューリングで解ける。かなり頭が良い。
CF後にABC-Fのゴルフもした。Cythonとnetworkx。行と列に対応する頂点は、駒の条件を表すのに必要な分だけ用意しておけばよい。DiGraph
は何回も同じ辺を張ると最後に張ったものが使われるようなので、それを利用して必要になるたびに行と列の頂点を用意してみた。
そういえば、今日のABCのdifficultyは灰-灰-灰-茶-黄-黄らしい。かなりすごいことになっている。
日記を書いていたら昨日のARC-Bが縮んだ。だったが、とするほうが短かった。