06/20(月)

午後1時半起床。ここ最近覚えがないくらいスッキリとした目覚めだった。あとは今日中に週記を書き上げて投稿できれば完璧。

今週のチュウニズムのアップデート情報が流れてきた。「泥の分際で私だけの大切を奪おうだなんて」が追加されるらしい。少し前にMVを再生してドハマりし、数日ずっとループしていた記憶がある。歌が良いのは当然として、イラストの女の子の表情もどれも非常に良い。嫉妬したり、見下したり、憔悴したり。三つ目はもう少し別の表現もありそう。ジャケットやサムネになっている堕天後のイラストの表情を言っている。

【6/23(木) 「ツユ」コラボイベント開始！】
23日(木)より『くらべられっ子』『あの世行きのバスに乗ってさらば。』『泥の分際で私だけの大切を奪おうだなんて』の3曲がチュウニズムに登場！イベントマップではキャラクターやアイテムがゲットできるので、ぜひ遊んでみてね！https://t.co/2OHGGB6Wc1 pic.twitter.com/YFA5DPUeU5
— チュウニズム公式@6/23(木)『ツユ』コラボイベント開催！ (@chunithm) 2022年6月20日

www.youtube.com

生協に行ってパン類を買い、帰宅して午後3時半からミーティング。最近ペアプログラミングをしていた人が学習の進捗を報告するのを聞いていた。その人からかなりお褒めの言葉を頂いて嬉しい。自分からもいくつか意見や懸念点を伝え、これからどうするか話し合っている途中で1時間が経過したため、話を切り上げて定例会に移った。

定例会では特筆することはなし。最近ずっと少しコードを書き換えて学習を回すのを繰り返していただけなので、報告すべき進捗がない。ただここでも先ほどの方の進捗報告で僕の名前が出てきたので、それに便乗する形で少しコメントを加え、内容をかさ増しした。勉強会は自然言語処理の話。以前AlphaCodeの論文を読んだときもよくわからなかったし、今日の発表を聞いて理解が進んだかというと、あまり……という感じ。もちろん発表ではなく僕に問題がある。理解したければ手を動かす必要があるのだ。

課題レポートを錬成する。今日期限で残っているのはゲーム理論だけ。教科書の今回の章は前回同様発展的な内容が多く、課題の問題が発展的ではない部分、つまり章の残りカスみたいな部分からしか出ていなかったので楽勝。パパっと終わらせて日記を書き始める。午後11時を回って何とか完成し、投稿した。

先週日曜日のOpenCup代理コンテストの解説を読んだ。ただし取り組んだ問題だけ。特にA問題はいろいろ知見が得られたので、ここに書いておきたい。「頂点数 $N$ で辺が $2NK$ 本（以上）の無向グラフから、その部分グラフであって二部グラフかつ各頂点の次数が $K+1$ 以上になるようなものを構築せよ」という問題。今の表現は先週の週記に書いたものよりわかりやすくなったはず。

自分のアプローチは、各頂点の次数が $2K+1$ 以上になるようにグラフの頂点を削除した後二部グラフにするというものだった。逆で、二部グラフにしてからグラフの頂点を削除するのがよかったらしい。まず事実として「 $M$ 辺の自己ループを持たないグラフは『辺を $M/2$ 本以上持つ二部グラフ』を部分グラフに持つ」ということがあって、こうして作った辺が $NK$ 本以上ある二部グラフから次数 $K$ 以下の頂点を削除していくと、いつか全頂点の次数が $K+1$ 以上になっている。この操作でグラフが空にならないことは先週の週記でも書いた。Diestel Prop 1.2.2。

さて、先ほど登場した事実を示そう。といっても実は簡単。頂点をランダムに塗り分けると各辺が二部グラフに含まれる確率が一律で $1/2$ であるため、すべての塗り分けについて辺の数を数えたものの平均が $M/2$ 本となり、特に $M/2$ 本以上の辺を持つ塗り分けが存在することが言える。つい最近、次数に関してこうやって $\max\ge{\rm mean}\ge\min$ という議論を行った記憶がある。さらに $M\gt 0$ のとき $M/2$ よりstrictに大きくできること、また $M$ を固定していろいろグラフを変えたとき、「二部グラフとして持てる辺の数の最大値」の最小値が $M/2+O(\sqrt M)$ オーダーであることを熨斗袋さんに教えてもらった。以下のツイートとそのリプライ。あくまで $\Theta$ ではなく $O$ であるはず。

辺の数の評価ですが、全て片側に寄せるカットが大きさ 0 なので、M ≥ 1 のとき M/2 を超えるというのは言えると思います。
漸近的には M/2 + O(√M) で抑えられるはずです。2n 頂点の完全グラフのうち、辺の本数が M 以上となる最小のものを取ってくると示せます。
— 寝る (@noshi91) 2022年6月20日

そのような二部グラフの構築について、解説では乱択して適当に頂点を塗り分けた後1点flipを繰り返していた。しかしもっとオーダー良く決定的に解けるらしい。これまた熨斗袋さんのツイートによる。すでに集合に振り分けられた頂点への辺だけ考えると必ず半分以上を二部グラフに含めることができて、全部終わった時には $M/2$ 本以上になっているということ。

というのも、二部グラフを取るところで乱択ではなくて v = 1, 2, … の順に貪欲をしていけば deterministic に半分以上の辺を含む塗り分けを得られるため。
— 寝る (@noshi91) 2022年6月20日

来週月曜日午前中が期限の、ハードウエア基礎の課題レポートを錬成する。講義スライドは電気回路の計算を入念にやっていて、高校物理を忘却してしまった自分では何を言っているのか理解できなくなってきた。しかし練習問題と解答がいくつか載っていて、それをガン見しつつ手を動かすと課題で出るレベルなら何とかなった。スライドを眺めながら絶望していた時間が長く、課題を解くのはすぐできた。僕の理解では必要ないパラメータが問題文で与えられていたのが不安。

シャワーを浴びて2時間ほど日記を書き、布団に入った。TLでDMOJというコンテストサイトの話題が出ていて、ちょうど今Ratedのコンテストが開催されている様子。期間には余裕があるので、明日あたり出ようかなと考えた。午前7時就寝。

Home - DMOJ: Modern Online Judge

06/21(火)

午後1時半起床。

チュウニズムのアップデート情報がまた流れてきた。ありえないくらい最高すぎる。まず「フォニイ」の追加が嬉しい。ただそれよりも「BlackFlagBreaker!!」の追加に驚いた。音ゲー界隈と関わりの深い人たちが作った曲なのでいずれは追加されると思っていたが、さすがにちょっと速すぎて信じられなかった。もちろんこれも非常に嬉しいことである。

【6/23(木) 楽曲追加！】
6月23日(木)より、大人気niconico楽曲や、最新のPOPS&ANIME楽曲が合わせて3曲チュウニズムに登場するよ！ぜひ遊んでみてね！
「吉原ラメント / 亜沙」
「フォニイ / ツミキ」
「BlackFlagBreaker!! / 社築 × https://t.co/7H0EPjpRsQ」https://t.co/7Z0JyEHT0B pic.twitter.com/pFuUA4qTFE
— チュウニズム公式@6/23(木)『ツユ』コラボイベント開催！ (@chunithm) 2022年6月21日

昨日寝る前に見たDMOJにアカウントを作り、少し問題を解いてみた。CodeChefのとき日記に書いたような確認をここでもやってみたが、正直もう細かい仕様を覚えていられないので、AtCoder以外ではいつもlong longを使うし、main関数の型もしっかり書くようになっている。

今日はCodeChefのコンテストがあるらしい。先週気になっていると言ったばっかりだし、また今日はコンテスト尽くしの1日にしてみようという思いから、アカウントを作った。練習問題を3問ばかり解いて、どんな感じなのかを探る。main関数の型がなくてもCEにはならず、longは64bit整数らしい。
週記（2021/09/20-2021/09/26） - kotatsugameの日記

いったん大学生協に行って買い物。入荷メールが届いていたラノベを受け取ろうとしたら1冊が見つからなくて、しばらく探してもらっていた。オーバーラップ文庫。途中でこのレーベルが毎月25日発売日であるということに気づいたため、入荷メールの間違いということになった。最近予約でばかり買っているのでレーベルごとの発売日が頭から抜けてしまっている。

「奴隷」とか「ギルド」とか「Sランク」が含まれたタイトルを目の前で読み上げられ確認されてヤバかった。心臓に毛を生やしていなければ死んでいた
— こたつがめ (@kotatsugame_t) 2022年6月21日

帰宅し、午後6時ぐらいからBCI Programming Contest 1 Seniorに出た。4日間の期間が用意されていて、その中から適当な3時間を選んでコンテストに参加することができる。参加終了まで順位表は見られない。想像していたよりかなり難しかったし、順位表が見えないので本当に今取り組んでいる問題が難しいのかにいまいち自信が持てず大変だった。

BCI Programming Contest 1 Senior - DMOJ: Modern Online Judge

S1はまず $a_1$ を決定する。これまでに決定した数で作れるペアの和を全部削除しておくことで、その時々で最小のものが $a_1+a_i$ の形をしているとわかる。あとは繰り返し。

S2からもう難しい。 $0$ と $x$ の距離が $x$ に等しくなるような最大の $x$ は、 $p$ の小さいほうから二つを $p_1$ と $p_2$ として $L=\lfloor(p_1+p_2)/2\rfloor$ となる。また、 $0$ と $L+1$ の距離を聞いて $L-1$ か $L$ か判定することで、 $p_2-p_1$ の偶奇を特定できる。 $p_2-p_1$ が偶数のときは $L-1$ と $L+1$ が、奇数のときは $L$ と $L+1$ がそれぞれ $0$ から等距離にあるとわかる。もっと言えば、 $0$ から $p_1$ までの地点からは等距離にあって、 $p_1$ より右で2点より左（2点を含む）の位置からは等距離にない。よってこの範囲を二分探索することで $p_1$ が特定できる。 $p_1$ と $C$ の距離を聞くことで、 $p$ の最大値もわかる。

あとは内側を探索。ある開区間 $(l,r)$ について、その左右で最も近い $p_l,p_r$ がわかっているとして、 $(l,r)$ に別の $p$ があるかを判定するには、 $m=\lfloor(l+r)/2\rfloor$ と $p_l$ の距離 $a$ を聞けばよい。 $p_l$ または $p_r$ から直接向かうよりも短くなるなら $m-a$ または $m+a$ が $p$ の一つとなり、 $(m-a,m+a)$ には $p$ がないこともわかる。これで $(l,r)$ が二分割されるので、それぞれで再帰的に解く。1時間くらいかかった。

S3が初手から全く分からなかったので、S4に進んだ。 $A\oplus B$ と $0$ を場合分けしてXORする方針。 $A\oplus B$ のMSBと、 $A\cdot(A\oplus B)$ （ただし $\cdot$ はbitwise AND）のMSBが比較できれば良い。MSBを検出するため、ある数を右・下・左にずらしてbitwise ORしまくることでMSB以下のビットをすべて立てた数を作った。数 $X$ に対してそのような操作をした後の数を $f(X)$ とおくと、 $f(A\oplus B)\oplus f(A\cdot(A\oplus B))$ が非ゼロになるのとMSBが等しくないのは同値。こうして得られた数にさらに $f$ を作用させ、 $A\oplus B$ とのbitwise ANDを取ることで、 $A\lt B$ なら $A\oplus B$ になって $A\ge B$ なら $0$ になるような数が得られる。つまり、 $f(f(A\oplus B)\oplus f(A\cdot(A\oplus B)))\cdot(A\oplus B)$ 。

さて、 $f$ は計算用にレジスタを一つ破壊する。 $A$ と $A\oplus B$ を保存しておいて、さらに $f$ を同時に二つ持つ必要があるので、レジスタは五つ必要になって90点までの部分点が得られる。これを実装して提出。しかしWA。自前でチェッカーを書いても全然落ちなかったので、試しに $f$ の計算を賢くやっていたつもりの部分を愚直にやったら通った。ずらしてbitwise ORするときに $16\rightarrow 8\rightarrow 4\rightarrow 2\rightarrow 1$ と幅を狭めることで効率的に全部埋められると思っていたところを、 $1\dots 31$ を全部行う方針に。何がダメだったのかわからない。

残り20分もないため、ほかの問題は無視してこのまま満点を考える。まず $f(A\oplus B)$ を作り、適切にずらしてbitwise ORを繰り返すことでこれのMSBだけ下ろした数を得る。その数を $X$ とし、また $Y=A\cdot(A\oplus B)$ とする。 $Y\oplus(Y\cdot X)=Y\setminus X$ を計算した結果が非ゼロになるのと、 $A\oplus B$ と $Y$ のMSBが等しいことが同値になる。あとは先ほどと同様にすれば、 $A\gt B$ なら $A\oplus B$ になって $A\le B$ なら $0$ になるような数が得られる。こちらのアルゴリズムはレジスタ四つで実装できる。

残り時間が少ない。サッと書いてチェッカーに投げると合わず、焦りながら何度も読み返したものの結局合わないまま終わった。直後に、先ほどは $A\lt B$ なら $A\oplus B$ になっていたところが今は $A\gt B$ なら $A\oplus B$ になるということに気づいた。非常に悔しい。

公開された順位表を見に行くと現時点で9位。自分より上の人は全員S3で満点を取っているので、実は解けなければならない問題だったらしい。今考えてみても全然わからない。S4の満点は二人しかいないので、余計に悔しくなってきた。総じて良い結果ではない。コンテストが難しかったこともあってしばらく放心状態だった。

終えてから日記のコンテスト部分を書き、戻ってS3のupsolveをした。あまりに無理すぎて途中椅子で寝入ってしまったが、何とかひらめきを得ることができた。

最初に $X\leftarrow X\bmod{\sum_i a_i}$ としておく。まず、バスもバス停も同じ色のものが固まって同じ順番で並んでいるのが最適とエスパーする。固まっているほうが明らかに嬉しくて、バスとバス停が列として一致する瞬間があるとさらに嬉しそうだから。あとは時刻 $0$ の時点でいくつずれているかの問題になって、部分点はずらす幅を全探索してバスごとに寄与をカウントしても通る。ここまではコンテスト中に考えていたこと。ただし実装はしなかった。

最大の非自明ポイントとして、このずらす幅はおよそ $X/2$ と決め打ってよいらしい。考え方としては、全くずれていない状態のとき答えに対する寄与が最も大きくなり、そこから左右に行くごとにどんどん減っていくはずだから、時刻 $0$ から $X-1$ の間に達成するずれ幅の区間を $[-\lfloor X/2\rfloor,\lceil X/2\rceil)$ などとして $\pm 0$ を含みつつその左右がだいたい同じ長さになるようにしたくなる、というものだった。部分点のコードを書き換えて提出してみると当然のように通ってひっくり返った。

あとは答えを求める部分の高速化。気合いが必要。ある色について、その色のバスが時刻 $0$ から $X-1$ の間にどの位置をどれだけ通るかの分布は台形になるため、傾き $+1,\pm 0,-1$ の部分に分割して、それぞれその色のバス停と重なる部分を求めて答えに足す。もう見るからに面倒そうなことを言っているが、実装してみると案外すらすら書けた。一発でAC。確かにこれは解けるべきだったかもしれない。しかしこれを通していたらS4は部分点も間に合わなかっただろう。

upsolve後はYouTubeに気を取られつつ昼間までおすすめのなろうまとめを書いていた。朝あたりに指導教員の先生からメールが来て、今週木曜日のセミナーがキャンセルになった。よって思いっきり生活リズムを乱すことができる。正午就寝。

そういえば今日は夏至だったらしい。コンテストへの参加が終わったあたりでTLを見て気づいたが、日記のその部分に割り込ませるのが不自然だったのでここに書いておく。

今日夏至！？
— こたつがめ (@kotatsugame_t) 2022年6月21日

06/22(水)

午後9時起床。ICPCの誓約書を提出した。また昨日参加したコンテストが終了していた。16位まで落ちて、最初のレーティングは2320。

YouTubeのチャンネルにコミュニティ投稿ができるようになったと通知が来た。登録者数500人で開放される機能らしい。思いがけない特典があって嬉しい。最近、YouTubeの動画の共有ボタンを押すと「投稿で共有」という謎の表示が出るようになっていたが、これもコミュニティ投稿が可能になったことによるもののようだ。

おすすめのなろうまとめを書く。昨日と同じくらい進められれば今日終わりそうということで頑張っていた。午前9時になってついに完成し、投稿した。

kotatsugame.hatenablog.com

前の記事から継続して紹介しているのが21作品、ここ1年で読んだものから26作品選んだ。ジャンル分けについては、二次創作が多いし、どうしても全部主人公最強モノという観点で見てしまっているので、今回はすっぱり諦めることにした。

こうして改めておすすめできるものをまとめてみると、一般にも評価が高い作品ばかり集めてしまったなという感想になる。ではこの記事の意義はどこにあるのかという話だが、ジャンルを問わず一人の人間が好きなものを集めたという点にあると考えている。特定のジャンルの作品を読みたいなら自分で検索して評価順に並べればよい。そこから離れ、別のジャンルなりあまり知らない作品の二次創作なりにこの記事を読んで手を出す人がいれば嬉しい。

学食で食事し、帰宅してからはしばらくラノベを読んでいた。午後2時就寝。

06/23(木)

午後10時起床。しばらくYouTubeを見ていた。

www.youtube.com

周央サンゴさん、かなり面白い。普通にやっていても面白いうえ、上手なのに題材が意味不明な声劇が最高。また朗読の際の声を人間が発音していることに驚くし、イラストとまったく合っていないように思えて笑ってしまう。

ラノベを2冊読んだ。まず1冊目、「灰原くんの強くて青春ニューゲーム」2巻。1巻に引き続き非常に良かった。当時日記に「微妙な緊張感がある」という感想を書いて、たぶんこれは態度を取り繕っている主人公がボロを出さないかドキドキする状態を指していたと思うが、1巻ラストの展開を受けて2巻ではかなり緩和されていた。依然としてまだあまり関わりのない人からは完璧超人という扱いを受けているものの、主人公はこれを不思議がりつつ軽くスルーするため、素直に主人公を引き立てるシーンとしてニヤニヤできた。この巻からは仲間内の恋愛模様について焦点を当てている。特に、心に決めた人が1巻から変わっていない主人公に対して積極的にアプローチを掛けるヒロインの話。まあこの人に対してはラストで一段落ついたため、不安定な状態は脱したように見える。しかしその過程で周囲の様々な関係が表出してきて、次の巻はどれだけ思惑が入り組むのか楽しみである。

2冊目、「才女のお世話」3巻。面白かった。幼馴染であるヒロインがようやくメインを張る。その幼馴染が抱える問題を解決しようと奮闘しているうちに、主人公も入学以来いつの間にか生じていた自身の問題点に気づく。後者については、別に叙述トリックというわけではないもののラノベ読者から見ると結構盲点な気がして、そういう展開になるのかと驚いた。ラストシーンは多少テンプレ展開に見えるが劇的でよい。しかし剣道の試合の最中に大声で声援を送るという描写は受け入れ難かった。それなしでは確かに味気ないので展開上の要請はありそう、とはいえもう少し気を使ってほしいところ。

日記に本の感想を書き、学食で食事して、それからなろうを読み始めた。午後3時半寝落ち。

06/24(金)

午後11時起床。実は明日土曜日は昼からICPC模擬国内予選らしい。完全に生活リズムが合っていない。大学から出る予定なので、とりあえず何も考えず注文した生協の冷凍弁当の配達を月曜日に振り替えてもらえるようメールを出した。

今日は横たわったまま過ごすことでできるだけ早く寝ようとし、布団でなろうを読み始めた。午前3時くらいになって1作読了。「隣に住んでる聖女様は俺がキャラデザを担当した大人気VTuberでした」。

https://ncode.syosetu.com/n5518hm/

非常に面白かった。そもそもとして、「Vtuber」と「半同棲」という僕が好きな題材を合体させているのだから気に入らないはずがない。特にVtuberパートが好み。タイトルにもある通り主人公はイラストレーターで、担当したVtuberに誘われて親娘コラボを繰り返し人気となっていた。二人が思いがけずリアルで対面することから話が始まるのだが、それ以前の設定だけで自分のストライクど真ん中。ファンに認められているくらい仲の良いVtuberの男女コンビは最高。

設定の話ばかりして内容に触れていなかった。Vtuberモノとしての配信パートと半同棲モノとしての恋愛パートをそれぞれだけ見ても十分面白い。前者については主人公がLive2Dの肉体を手に入れるくだりが好み。後者については学校、つまり他者の目があるところでも二人が距離を近づけていく様子が良い。いずれ二つのパートが大きく交わる展開もありそうで期待している。すでに描かれた部分としては、オフコラボのシーンがそれの一例になるだろうか。今のところおおむね独立して進んでいるように思う。

DMOJでまたRatedのコンテストが開催されていることに気づいた。金曜日から月曜日までの日程だが、土日はコンテストで埋め尽くされているし、月曜日はインターンだったり課題だったりでこれまた予定を入れたくないので、今日参加しておく必要があったらしい。明日の予定を鑑みて今からでもギリギリ大丈夫だと判断し、午前3時半から3時間で参加した。内容や感想については、今日の日記を公開する時点でコンテストが終了していないので来週の週記に書こうと思う。

DMOPC '21 June Contest - DMOJ: Modern Online Judge

公開するのは来週だが、文章は今日作成する。書き終えるともう午前8時を回っていた。布団に入り、そこから何を思ったかなろうを2時間以上読んで、午前10時半就寝。

06/25(土)

午後1時起床。死にそう。ノロノロ準備して出発し、学食で食事しつつ山に登った。信じられないくらい暑かった。

ホスフィンが大学の演習室を確保してくれたので、そこからICPC模擬国内予選に参加する。午後2時から3時間のコンテスト。これについては参加記を書く予定なので、日記ではあまり触れない。投稿したら以下にリンクを貼っておこう。全体3位だったことだけ、かなり嬉しいのでここにも書いておきたい。

07/01追記：投稿した。

kotatsugame.hatenablog.com

午後6時前に帰宅。即座に布団に横たわってABCまで仮眠を取ろうとした。しかしうまく眠れず、結局2時間横たわっただけになってしまった。ずっと目が冴えていたので、肝心の頭が休まった気が全然しない。シャワーを浴びて眠気を少しでも取り、午後9時からABC257。

NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257） - AtCoder

Aはパッと見よくわからなかったので実際に文字列を作って解こうとし、C++で書き始めたところで $\lfloor(X-1)/N\rfloor+1$ 番目のアルファベットを出力すればよいことに気づいた。そのままC++で書き上げ、ACを確認した後、dcでも提出しておいた。Bは愚直に。Cは $S_i$ と $W_i$ を組にして $W_i$ でソートし、区切りをずらしつつ差分更新する。同じ体重の人を区別できないことに注意。このあたりの問題にしてはちょっと難しいなと感じた。

Dも難しい。 $i\rightarrow j$ と $j\rightarrow i$ でジャンプするための $S$ の下限が異なり得ることを見落とし、最小全域木を求めようとした。無向辺ではなく有向辺だと思わなければならないと知り、考察をやり直す。始点を1点決めると、そこから各点に到達するための $S$ の下限がdijkstraで計算できる。辺の数が $O(N^2)$ なので $O(N^2\log N)$ のdijkstraを $N$ 回行った。実装途中で答えが最大 $4\times 10^9$ とint型の最大値を超えることに気づき、コストの変数をlong longに修正したのだが、し切れていなかったようで1WA。

Eは最初に $9$ を連打することを考えて、それより桁数を増やすほうが得だと気づいた。桁数の最大値は $\lfloor N/\min C\rfloor$ になるので、これを達成できる限りで最上位桁から数字を大きくしていくのがよい。実装も簡単で、D問題のACから2分ちょっとで通った。見た目からdpっぽさも感じていたので拍子抜け。Fは、結ぶ街の片方が未定のテレポーターを超頂点 $0$ に繋がる辺だと見なしてグラフを作ればよい。頂点 $0$ と $i$ を同一視したときの $1$ から $N$ までの最短距離を求めることになって、 $1\rightarrow N$ と $1\rightarrow 0\rightarrow i\rightarrow N$ と $1\rightarrow i\rightarrow 0\rightarrow N$ の距離の最小値となる。 $1$ 、 $N$ から各頂点への距離をそれぞれ前計算すればよい。GはZ-Algorithmとrange chminで実家dpができる。range chminのほうは優先度付きキューで、今見ている要素への作用素を持つことで実装した。

Exは難しい。kyopro_friendsさんの解説と全く同じ式変形によって、 $\left(\sum x\right)^2+\sum y$ を最大化する問題に帰着した。よくわからないので適当な貪欲を試してみる。 $(x,y)$ の降順にソートして値を順に追加し、 $K$ 個を超えたら取り除いたときの値の減少量が最も小さいものを取り除く貪欲を書いてみると、70ケースくらいまで通った。もしかしてACかと思いかなり興奮したものの、蓋を開けてみると6ケースWA。次に $(y,x)$ の降順にソートして同じことをすると、5ケースWAに減った。最後に、 $(x,-y)$ の降順にソートして連続する $K$ 個を選ぶコードを追加してAC。

Editorial - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

最後の場合分けは、 $\sum x$ をいろいろ試しつつ $\sum y$ を最大化しようとしている。これまで値を1個だけ交換してきたが、2個交換するときどうなるか計算してみると、 $x$ が交換したペアの両方で増えているか減っていれば1個だけ交換するのよりよさそうだったので、積極的に $\sum x$ が減る方向に動きたかったのだ。

80分弱で全完、Dの1WAとExの4WAで5ペナ、4位。Dの想定解は二分探索だったらしい。考えもしなかった。Exの解説は大変そうなことが書いてあって、僕のコードに正当性がないことしかわからない。

コードゴルフ。A問題はAC直後に提出したdc 9Bが最短でよく、ちゃんと速度でも勝てていた。BはPerl。CはRubyで書いたがPerlに大敗。EはRubyで負け。他は手付かず。

眠気をこらえ、午後11時半からCGR21に出た。

Dashboard - Codeforces Global Round 21 - Codeforces

Aは $\max_i (a_i\mid z)$ が答え。Bは2手で必ず可能なので、0手と1手の判定ができればよい。0手は自明で、1手は両端から続く $0$ を削除したとき $0$ が残らないことを確認する。Cは逆の操作が可能なので、 $a$ と $b$ に操作を施して何らかの正規形にし、一致するか判定すればよい。具体的には1番目の操作で分解できるだけする。一応ランレングス圧縮して保持したが、普通に持っても間に合うくらいの長さにしかならないようだ。Dは右にしか進まなくてよいと思い込んで貰うdpをした。左向きの累積max・minを持って、それが更新される点だけdpの値をセグ木に乗せておく。あとは区間MINで今見ている点までの距離が求まる。

Eは各マスに対してそこに置かれた人形を消すのに何手必要かを手計算してみると、寄与の流れが見えてきた。 $i+1$ 行目の手数の列から $i$ 行目の手数の列を求めるとき、長さが $a_i$ になるよう $0$ 埋めし、全体に $+1$ したあと右から累積和を取るという操作をしていることがわかる。この $+1$ がマス $(0,0)$ にたどり着くときいくつになるか考えればよくて、これはマス $(x,y)$ から左と上への移動を繰り返してマス $(0,0)$ に到達する方法だから $\binom{x+y}{y}$ となる。よって求める値は $\sum_{x=0}^n\sum_{y=0}^{a_x-1}\binom{x+y}{y}$ となり、内側の総和がよく見る形。Wolfram|Alphaに投げたらちゃんと閉じた式になった。

Fはまず各頂点 $k$ について頂点たちを $k$ からの距離が同じものでグループ分けしておく。次に根を1点固定し、その子、つまり根から距離 $1$ にある頂点の集合を考える。どれかわからないので全探索する。実は、ここまで決めると木としては高々1通りになる。なぜなら、親 $p$ と子 $u$ の組が与えられたとき、 $u$ の子は $u$ からの距離が $p$ と同じになるからである。先ほど分けたグループから $p$ を含むものを見つけ、 $p$ 以外を $u$ の子とすることでBFSのようにして木を下っていける。途中ですでに見た頂点が出現したらダメだったということ。最後まで決めきれたら、改めて条件をチェックして出力する。グループ分けするときUFを使っていて、 $d(u,k)=d(v,k)$ かつ $d(v,k)=d(w,k)$ なのに $d(u,k)\ne d(w,k)$ であるようなケースに引っかかってしまい1WA。

残り1時間ちょっとはGを考えていて、端から決めるときの計算を関数だと思ってセグメント木に乗せられそうだったのだが合成が書けず終了した。

システスは全部通って速めの6完で21位。レートは2875→2964(+89)。あと1回上振れすればLGMだが相変わらず遠く感じている。

Dの右にしか進まなくてよいというのはあまり正しくない。解説では「常に右の最も遠い点に進むのが最適」という事実が紹介されていて、これを含んでいるからたまたま正しくなっていたようだ。右にしか進まなくてよいことを証明するためには、途中で左に進むような経路を取ってきて右にだけ進む経路で再現するのが一般的だが、かなり難しそう。少し取り組んでみたところ左に何回進むかなどで場合分けが大量発生し、早々に放り投げた。

Eは各マスに何個人形が置かれるかカウントするのでも答えが求まる。マス $(x,y)$ に置かれる人形の数を求めるときは、上に書いたのと全く逆の $(0,0)$ から右と下だけに進んで $(x,y)$ にたどり着く方法だと見れて、値は同様に $\binom{x+y}{y}$ になる。Fは根と子を一つ、つまり1辺決めてもよかったらしい。そもそもグループ分けが正しくないことに気づかず使っていたのが問題。計算量的には余裕があるので、子を探索するときに入力を直接見る方法で $O(n)$ かけてもよかった。

かなり眠い。布団に入って少しなろうを読み、午前4時半就寝。

06/26(日)

午前9時半に起きてしまった。かなり眠気が残っていたのにうっかりスマホを取り、TLを見て、二度と眠れなくなった。布団に横たわったままずっとなろうを読んでいたが、一向に眠れる気配がないので、午後2時半に布団から出て、しばらくICPC模擬国内予選の参加記を書いていた。

午後4時からOpenCup。今週も代理コンテストで、ARCと被せないため開始をこの時間にするということで合意が取れていた。今日のコンテストタイトルはPTZ 2021 Summer Day 2, NAC 2021。ちなみに代理コンテストは五つしかなく、これが最後である。

Petrozavodsk Summer 2021. Day 2. The American Contest - Dashboard - Contest - QOJ.ac

チームとしてMFLDJCEAGを解いた。僕は最初2時間をAに費やし、解けず、次の2時間半でGを解いた。ずっと椅子を温め続けていたので非常に苦しいコンテストだった。Gが通ったのもよくわかっていないので消化不良気味。Aは考察の初手が違っていて、後半は僕が考えていたことと同じことをやるようなので少し悔しい。チームメイトが通してくれたので感謝。

Gについて。クエリを $a$ の昇順に並べ、先頭から数列を展開していく。展開後の長さは前計算できるので、クエリに関係ないならスキップする。このとき、展開後の列に含まれる $k$ の個数というのをすべての $k$ に対して求めたくなる。値 $n$ を $s$ 回展開するとすれば、 $k\le n$ に対して展開後の個数が $k$ の $s-1$ 次式になる。 $s$ は非常に小さいので、多項式をBITに乗せれば区間和を取得することで個数が求められるようになる。

ただし $a\le 10^9$ なので、途中をスキップしたとしても何項見ることになるのかがよくわからなかった。残りの展開回数が $0$ 回になってからようやくクエリの計算をしていたらTLEだったので、残り $1$ 回の時点で求めるようにしたら通った。このとき固定された順列に対して区間内の $k$ 以下の要素数が知りたくなったので、 $\log$ が2個つく重めのライブラリを持ち出したが、さすがに全部展開するよりは速かったのだろう。

直後、午後9時からARC143に出た。

AtCoder Regular Contest 143 - AtCoder

Aは、 $A\le B\le C$ としてまず $B=C$ となるように操作したい。つまり $A$ と $C$ から $1$ 引くのを $C-B$ 回繰り返すため、 $A\ge C-B$ である必要がある。一度 $B=C$ になりさえすれば、後は $B$ 回の操作で全部 $0$ にするのが最適。

Bは少し難しい。まず1番目の条件を満たさない数は各列の最大値である。列 $i$ の最大値を $M_i$ とおいて、 $M$ の最小値が $i=i_m$ で達成されるとしよう。すると $i\ne i_m$ について、 $M_i$ と同じ行の $i_m$ 列目の数は $M_{i_m}$ 以下になる。今 $M_i\gt M_{i_m}$ なので、 $M_i$ と同じ行により小さい数があることが分かった。したがって2番目の条件も満たさないようなマスはあるとすれば $M_{i_m}$ だけである。あとは $M_{i_m}$ を全探索して適当に組み合わせ計算。

Cも難しい。最初、選ぶ山がちょうど一つだと勘違いしていた。少しの勘違いもあり解けたと思って実装し、サンプルが合わず、誤読が判明して絶望。ただし、相手の操作を真似することを考えて $A\leftarrow A\bmod{(X+Y)}$ としてよいという考察が変わらず適用できたので軽傷だった。そのような操作をした後 $A_i\ge X$ なる $i$ がなければ先手負け。まずこれでサンプルが通って提出し、WAだった。もうちょっと考えて、 $X\gt A_i\ge Y$ なる $i$ があると自分に手番が返ってくる可能性があることに気づいた。この条件を追加すると通った。

Dは案外あっさり解けた。 $(A_i,B_i)$ を辺と見たときに出現するループは、 $A_i\leftrightarrow B_i+N\leftrightarrow B_i$ と展開することで問題のほうのグラフでもループにできる。これを $A_i\rightarrow B_i$ という有向辺だと思うと、二重辺連結成分だったものが強連結成分となるよう向き付けられれば最適で、実際dfs木を使えば達成可能。これは日記を書きつつ整理したうえでの表現で、コンテスト当時どのような閃きでdfs木にたどり着いたのかは記憶があいまいで再現できなかった。ともかく実装し、提出すると1ケースだけWAで絶望したが、頂点番号を0-indexedにしていなかっただけだった。すぐ出しなおしてAC。ちなみに実装テクとして、0と1のどちらが $A\rightarrow B$ かということには注意を払わなくてよい。全部逆にしても橋の本数は同じになるからだ。

Eは初手が完璧で一瞬で解けた。葉の石をどのタイミングで取り除くか考えると、親より前か後かという話になって、初期状態を見ることで決定する。またこれに応じて親の石の初期状態が変わったと見なせて、さらに以降その葉は無視してよくなる。このように葉を順に削除していき、最後に残る1点の状態を見ることで判定問題が解ける。また各辺についてどちらの端点の石を先に取り除くかという条件だけが操作列に要請されるので、辞書順最小の構築はトポロジカルソートを優先度付きキューで行うという典型問題になる。実装も特に手間取ることなく一発AC。

この時点で2位。Fに80分残すことができて、初の全完もあり得るかと思ったが、その後ずっと考えていても解けずに終了した。最後のほうは愚直と比較していて、 $N=7$ で $\{1,2,3,5,7\}$ と $\{1,2,3,6,7\}$ が数えられていないことに気づいたものの、最後に $7$ を入れるかどうかの判定が難しいことに気づいて絶望。いや、 $N=7$ ならまだ何とかなっていた。しかしもっと大きな数になるともっと盛大に破綻していることに気づいて、今度こそ諦めてしまった。

結局Fは誰にも解かれず最終順位も2位。ARCでは最高。かかった時間がそれぞれ3分、7分、12分、8分、7分と、DEが自分でも信じられないくらい速かった。2ペナ出してしまったのが惜しいなと思っていたが、1位とは12分差なので惜しくもなんともない。3位とは10秒ちょっとの僅差だったので危なかった。

Eの判定問題は、初期状態における表が白い石の個数の偶奇を見るだけで解けるらしい。なるほど、葉から削除していくとその偶奇が変わらないことから確かめられる。コンテスト中は考えもしなかった。こういう顕著な性質が必要なく、むしろ想定解から外れていく罠になってしまう問題というのも面白い。

コードゴルフ。Aは $2\times\max(A,B,C)\gt A+B+C$ なら $-1$ 、そうでなければ $\max(A,B,C)$ なので、dcで実装。Bは解説にある閉じた式をさらに整理し、 $(N^2)!-\frac{N!^2(N^2)!}{(2N-1)!}$ をRubyで計算する、コードをVimで書いている。さすがに $(500^2)!$ は厳しいため $\bmod$ を取った値を使うことになり、割り算が面倒だが、 $\frac{(N^2)!}{(2N-1)!}=\prod_{i=2N}^{N^2}i$ と求めることにするとかなり縮んだ。CはPerl。シンプルな条件に見えて結構面倒で、うまい表現が思いつかず微妙に長そうなコードを書いている。以降は手付かず。

もうあり得ないくらい眠い。しかし今週末出たコンテストはどれも非常に良い成績を残しているため、午前1時からのSRM832にも出ることにした。

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

Easyは面倒。まずcommandsを1回実行したとき各点を何度訪れるかカウントする。最初はcommandsの要素がめちゃくちゃ大きいことに気づかず愚直を書いていた。後から気付いて修正。周期が $N$ なので、 $1\le i\le N$ に対して $i$ 個先を通るのが何回かそれぞれ数えるのが楽だった。次に、commandsを1回実行するたびに進む数が求まるので、これを $R$ 回繰り返したときどの地点から何回commandsを開始することになるか数えた。こちらは元に戻る周期が $N$ より小さくなる可能性があるが、 $N$ だと思って計算しても問題ない。最後に $O(N^2)$ かけて畳み込むと答えになる。始点に $+1$ することを忘れずに。

Medも面倒。 $A=0$ の場合に解ければ差を取ることで答えになる。まず、 $S$ の長さが $B$ になるとき何桁の数を追加しているのか調べる。 $n$ 桁のgoodな数は、 $1\dots n-2$ 桁のgoodな数に対して $n$ 桁目のbitを立てたものになるから、その個数や含まれる $1$ の個数が順番に求まる。桁数 $n$ を確定したら、「その桁が立っている状態で」下の桁が $1\dots n-2$ 桁のどれに該当するか調べていく。再帰的に繰り返すことで上位桁からどこが立っているか順に求まっていって、最後に中途半端な部分を調べる。非常に怖いので小さい値で愚直と比較したり、途中で桁数が大きくなりすぎたりしないか調べたり（58桁の数まで追加されるようだ）してから提出した。

Hardは簡単。 $i=1\dots N$ の順でループし、 $A$ を $i$ 番目から左に見ていったときに初めて出現する値の位置を差分更新で列挙する。 $H=i$ なるクエリ $[L,H)$ について、列挙した数であって区間 $[L,H)$ に含まれるものの和を求めることで、必要なtmaxの和が求まる。これは1点更新区間和のセグ木で実現できる。 $i=N\dots 1$ として同様のことを行えばtminも得られる。解法はすぐ出たものの実装に手間取って900点中600点くらいになった。