週記（2021/02/08-2021/02/14）

02/08(月)

先週の週記を投稿してから、また橙diffを少しやっていた。CFのレート更新が来て、predictorの通り-42であった。布団に入ってからなろうを少し読んで、午前8時就寝。

午後4時起床。幾何学概論Bの教員から「レポートを提出した学生は全員合格しています」というコメントが出ていた。ちょっと喜んだものの、このレポートが何を指しているか明確でないため予断は許されない。講義の途中で挟まれる問題に回答するレポートを指していた場合、半分しか出していない僕はまずいかもしれない。

DDCC2021の予選申し込みが始まっていた。今年はAtCoderから完全に独立してやるらしい。この状況下で30人規模のオンサイトを予定してもいるようだ。ただ、本選が装置実装部門のみになって、コード部門は行われないらしいので、残念。とりあえず申し込みをしておいた。

www.discoverychannel.jp

通販で買い物をする。まずAmazonで500mlペットボトルのお茶24本のケースを買う。注文履歴によれば、1/13にも同じものを注文している。日記には該当する記述がなかった。1月も持たずになくなってしまったので、再度購入した。

次に大学生協のサイトでラノベを探す。最近本屋に全然行けていないので、買っていない新刊がかなりある。リストにまとめてあるので、それを見ながら在庫にあるものをドンドン注文していく。最後に、最近Twitterで流れてきた「数学者の夏」を加えて注文を確定させた。

bookclub.kodansha.co.jp

合計1万円ちょっとで、大学生協で受け取る時に割引が効く。金額だけ見れば常に生協経由で買ったほうが安上がりだが、やはりリアルの本屋で手に取って確認する体験は捨てがたい。

サークル解説会の準備をする。スライドを作成している途中、キーボードが変な感じになった。最近頻発しているので、どういう挙動をするのか動画に撮っておく。今回は半角・全角の切り替えもうまくいっていないことに気づいて、それを直そうと奮闘していたら一緒に直った。

サークル解説会はつつがなく終了。来週もやるが、そろそろ春休み期間なので、どうするか決めなければならない。

また橙diffを進める。計算機の進化によって、ナイーブにやっても間に合うようになってしまった問題があったので、適当にゴルフしておいた。

atcoder.jp

dp配列の初期化は、最初memsetでやっていたが、testestestさんによって「ローカル変数にして宣言と同時に初期化するのを繰り返す」方法が提案された。5000回も3e5要素の配列を宣言するのは脳筋。それで間に合ってしまうのだから面白い。冷静になれば、もともと5000回3e5イテレーションのループを回していたのだから、最悪ケースではほとんど影響がないのか。

1e9+7の埋め込みにも新手が出た。順に59,154,202,7という文字コードの4文字をシングルクォートでくくると、整数型の1e9+7になる。以前は何かint型の変数に代入してから使っており、%=a=1e9+7でmod部分に7Bかかっていたのが、今はシングルクォート含め6B。これを適用して別の問題を2問ほど縮めておいた。

午前3時くらいに眠くなって布団に入る。午前5時くらいまでなろうを読んでいたが、眠気がすごいことになってきたので、就寝ツイートをして寝た。洗濯物を干さなければならなかったのだが、諦めてしまった。

02/09(火)

午後2時くらいに目を覚まし、なろうを読む。再度の眠気が来なさそうなので、午後3時半くらいに起床報告しておいた。さらになろうを読み進め、一作読了。

https://ncode.syosetu.com/n6204l/

これも東方古代スタート。なんと言ったらいいのかわからないが、印象としては江戸時代の町人が使ってそうな感じの言葉遣いをしようとして変なことになった文章で書かれていて微妙に気になる。が、ストーリーは非常に良かった。第一章では幻想入りする前、原作キャラとの絡みを描いて、第二章でいざ幻想入りして久しぶりの再会を描く、その途中でエタっている。

布団から出て、また橙diffを進める。布団に入っている間に解けたはずの問題の実装をするが、全然合わない。ある程度ナイーブにやって解法が正しいか確認しようと提出してみたが、ほとんどのケースでTLEして使い物にならなかった。ここで、ランダムケースを生成してテストすることにした。ランダムケースのジェネレータと全探索のジャッジ解を用意して、ojでケース生成・アウトプット生成・一斉テストをやる。改めてかなり便利であると感じた。実際WAのケースも見つかって、変数の意味に関するミスだったことが発覚。無事ACできた。

別の問題を解き始めて、数回のWAの後にようやく最後のコーナーケースを見つけたあたりでサークルバチャが始まったので、いったん避けておいてバチャのほうに参加する。

今日はCF #559 dvi.1。4完してかなりいい感じ。Aはサンプルの意味が分からなかったので合わないまま提出したところ、当然のようにWAだった。ただサンプル1で落ちたのでペナルティにはならなかった。冷静になると、minが「ちょうど」ある値でなければならないので、全部ひとりでつじつまを合わせようとすると「ちょうど」ではなくなってしまう。これがサンプル1。Bはいったん飛ばしたが、Cを解いてから戻ってきて実験したらすんなり解けた。k=1がコーナー。

Cは、大小関係に関する条件に直してトポロジカルソートすればよい。たくさん辺を張る必要がありそうだが、だいたい同じ形の辺の張り方をしているので、前に張ったやつを再利用すればよい。Dは面白かった。残っている点のうち一番極端なやつ（右に振り切っているか左に振り切っているか）のどちらかをLとRに応じて選べばよい。そうすると、次にどの点を選んでも条件が満たせるので、そこで再度一番極端なやつを取る。この「次にどの点を選んでも条件が満たせる」状態を維持して点を減らしていけるので、必ず構成可能。偏角ソートの必要がありそうだが、点は必ず2直角の間に収まってくれるので、外積の符号で判断できる。

Cまで解いてからしばらく、さっきまでやっていた橙diffに戻って通していた。Dは正直解けるとは思っていなかったが、やってみたら解けてうれしい。バチャ中に諦めるという行為はバチャを無意味なものに貶めているので、気を付けたい。

yukicoderで3問ばかり通してsolvedランキングの3位に浮上しておいた。

もうそろそろRating Historyで確認できるsolvedが6000問になりそう。

布団に入って、ハーメルンを読もうとしたが止めてすぐ寝た。午前6時半だった。

02/10(水)

午後2時、起きる。二度寝しようと思ったが、生協に注文した本が届いたらしいので、起きて向かうことにする。閉店は午後3時。学食はすでに閉まっており、また購買のパン類も全滅しているだろうし、どこで食べ物を得るか迷う。今日はAmazonからの荷物も届くらしいので、家にいなきゃならないよなあ……と考えていたが、午前中の間に宅配ボックスに届いていたことを知ったので、家にいなくてもよくなった。ということで、食事は街に出て行うことにした。とりあえず生協で本を受け取る。

13冊注文したはずが11冊しかなくて、よくよくメールを読み直すと、2冊はまだ出荷されていなかったらしい。別々に来るのを知らなかった。ラノベばっかり生協のデスクに並べられて、一つ一つチェックしていたのだが、後ろに人が並んでいて少し恥ずかしかった。精進が足りない。10%引かれて合計で8000円くらいになった。

いったん家に戻って本を置き、軍手などを用意してゲーセンに向かう。地下鉄の駅の広告で、仙台駅前でトムとジェリー展をやっていることを知った。行ってみたい。

www.khb-tv.co.jp

途中の立ち食いそば屋で食事していざゲーム。最近また曲が追加された。同時に古いマップの課題曲が解禁されてもいる。マップを進めるのが遅すぎる。

この後はホスフィンが来てずっとマッチングしていたので、SSSは出ていない。出る前に癖がつきそうで怖い。

午後8時くらいに一緒にラーメン屋に行って食事。そのあと地下鉄に乗って帰宅した。シャワーを浴びて、サークルのバチャに臨む。今日はCF #539 div.1。ABCDが解けた。

AはZero-Sum Ranges。Bは答えが1または2または"Impossible"で、全探索して1の判定をする。Cは遅延セグメント木に区間の幅・区間の変化量・区間内における変化量の最小値の3つを乗せて二分探索する。TLが1.5secで、二分探索にlogを2つつけると落ちそうな制約だが、ACLはちゃんとlog 1つでやってくれるので、本当に実装するだけの問題。これはACLが公開されたことで難易度が大きく下がった問題であると考えられる。1点罠があって、回答クエリに答える前に[l,r)範囲外からスタートして範囲内に入り込んでいるクエリをキャンセルしておかなければならない。これに気付かず2WA。

Dはケイリーの公式で数え上げ。必死に頑張ったら解けて成長を感じる。頂点aとbを結ぶパスの辺の本数をkとしよう。このkについてループを回し、答えを足し合わせる。以降、kは固定されているものとする。

まず辺の重みについて。abパスに乗る辺の重みは、辺も区別するので単にcomb(m-1,k-1)になる。写像12相における、箱を区別する・ボールを区別しない・各箱に1個以上ボールを入れる、場合の数だ。残りの辺n-k-1本の重みはどうでもよいので、m^(n-k-1)通り。

次に頂点のラベルについて。abパスに乗るaとb以外の頂点はP(n-2,k-1)通り。で、このabパスを1頂点に圧縮することを考えると、全体はn-k頂点のグラフになるので、ありうるラベル付き木は(n-k)^(n-k-2)通り……とはならない。なぜなら、圧縮した頂点のどこに辺が生えているかは区別されなければならないからだ。これを区別するためには、圧縮した頂点の次数それぞれで計算して和を取ればいい、とも考えたが、これは閉じた式にできなかった。そこで、Wikipediaのケイリーの公式の証明を見る。

ケイリーの公式 - Wikipedia

プリューファーコードを用いた証明の節において、木の葉を削除しつつその親のラベルを記録する、ということが書かれている。このとき、ラベルに関しては圧縮前のものを見ればよいのではないか？つまり、圧縮後の頂点のラベルの代わりに圧縮前のk+1個のラベルのどれかを使うことにして、今考えているようなラベル付き木の集合と1以上n以下の記号n-k-2個の列は一対一対応するのではなかろうか。これは実際そうであった。係数が少し違って、圧縮後の頂点のラベルがn-kであったとすると、圧縮後の頂点はプリューファーコードを作る過程において必ず最後まで残ってくれるが、このとき残る2点のうちもう片方が圧縮前のどこに接続しているかでさらにk+1通りあって、結局全体で(k+1)n^(n-k-2)通りになる。n-k==1のときは特別扱いで1通り。これでサンプルが合い、通った。

考察としてはこのようなステップを踏んだが、今整理しなおせば「圧縮」という操作を考える必要はあまりなかった。プリューファーコードを作る過程でabパスに乗る頂点を残すようすれば、自然と1以上n以下の記号n-k-2個の列ができて、最後に残るk+2頂点のうちabパスに乗っていない頂点がどこから生えているかでk+1掛かる。

D問題のsolvedがC問題に比べてめちゃくちゃ多くてびっくりした。コンテスト後のupsolveで増えたなら理解できるが、コンテスト中からドンドン通されていてびっくり。

また橙diffを進める。

atcoder.jp

桁DPで解いた。復元する代わりに、答えとなる文字列を陽に持っても十分間に合うような制約。更新は、+で繋がれるような新たな数（ループのインデックスによって桁数は確定する）を後ろにつなげるか、あるいはすでにつなげてある数の特定の桁を変更するか。新たに数を後ろにつなげるときは暫定的にゼロ埋めしておいて、そこを変更していく。変更する場所は、数の間に+記号を入れてあるので、そこから数桁後ろに戻るような感じで特定する。難易度的に復元は必要だったのだろう。あるいは、当時は桁DPがそれほど人口に膾炙していなかったのかもしれない。

布団に入ってTLを眺めていると、次の問題がboostの多倍長浮動小数点数で解けたという話が流れてきた。

atcoder.jp

添付されていた提出URLのコードを読んでみると、cpp_dec_float_100を使っている。これは10進数で100桁の精度を持つらしい。似たようなことがdcでもできると思い、100kなどとしてみて数回提出したが、どうにも合わない。おそらく、dcの精度は小数点以下の桁数が固定されるのに対して、boostのそれは有効数字で決まっているからだろう。しかしだ。精度を高くすればACできるわけではない、ということはすでに知っているが、それでも有効数字100桁で計算すると用意された20数個のテストケースに「たまたま」通った、ということは間違いないわけである。

では、小数点以下n桁で計算すればたまたますべて通るような、そんなnは存在するだろうか？

テストケースが公開されていたので、dropboxから落としてくる。これをojで使用できるようにして、プログラムで精度の値を変えながら順番に試していくようなコードを書いた。bashでループを回し、ループ変数の値をdcのコードに埋め込んで、それをoj tで試す。oj tは全ケースに通った時正常終了してくれるようなので、ACの検出はかなり楽である。ACできた精度は、画面に出力してもよいが、念のためファイルにも書き出しておくことにしよう。

そんなコードを回しておいて、午前6時過ぎに就寝した。

02/11(木)

午後3時起床。わくわくしてパソコンのスリープを解除しようとしたところ、キーボードもマウスも認識してくれない。焦る。ぶん回して寝たプログラムが重すぎるのだと思い、パソコンの物理ボタンでいったんシャットダウンした。念のためACできた精度をファイル出力しておいて良かった。しかし、再起動しても認識してくれなかった。

普段はUSBハブを机の上まで出してきて、そこに無線の受信機を入れてキーボードとマウスを接続している。無線の調子が悪いのかと思い、有線キーボードを出してきてUSBハブに差し込んでみたが、これもダメ。パソコンの前面にあるUSB口に入れてみると、認識してくれた。どうやらUSBハブの調子が悪いようだ。よく見てみると、作動ランプがついていないではないか。

今差し込んだ有線キーボードにはいわゆる「乳首」が付いているので、とりあえずパソコンの操作はできる。問題はいったん後回しにして昨夜回したプログラムの結果をチェックすると、なんとたった1つだけACできる精度が発見されていた。879桁であった。どこまで探索したのかはわからないが、いかにも「たまたま全て通りました」といった感じの結果だ。とりあえず提出して最短コードとなった。

atcoder.jp

さて、USBハブの問題を解決しなければならない。Windowsが認識しているデバイスの一覧を表示すると、USBハブらしき項目に「デバイス記述子要求の失敗」と書いてある。これを直せばよさそう。そのままググると、対処法がいくつも書かれたブログ記事が出てきたので、そこにある対処法を上から順に試していく。

……解決しなかった。ノートパソコンを取り出してそちらにUSBハブを差してみると、今度は認識されているようだが、しかしハブにさらに別のUSB機器を差し込んでも認識してくれない。寿命か？そこそこ高かったんだよなあ、と思いつつ、いったんコード類をすべて取り外して再接続してみると、今度は認識してくれた。これまでもコードの抜き差しは繰り返していたが、「いったん全部外す」のが良かったのかもしれない。デスクトップのほうに差しなおしてみると、確かに作動ランプが点灯している。良かった～。

こういう謎の現象が起こった時のために、キーボードやマウスは有線のものを含む2台以上保持しておくのがよいだろう。動作チェックができたので、パソコンが2台あるのもよかった。

成績を確認したところ、新たに1つ講義の評価が出ていた。月曜日に書いていた「レポートを出した学生は全員合格」の講義で、僕もBで浮いていた。うれしい。結局期末レポートが手書きである必要もなかったようだ。

ラノベを読む。まず前日の夜から読んでいた「幼馴染で婚約者なふたりが恋人を目指す話1」。主人公とヒロインがそれぞれ企業経営者の子供であるという設定。自分たちのプライベートな話をクラス全体に話して聞かせているのには結構違和感を覚える。主人公とヒロインが上流階級であるという設定は、婚約者だったり半同棲だったりの理由付けになっているだけで、実際の恋愛模様などは一般人と変わらない感じで描かれる。

主人公が上流階級の人間の話で特別に覚えているのはこれだ。かなり好きなのでリンクを貼る、が、この小説投稿サイトは3月初めで終了してしまうらしい。4年くらい前にも終了するという話があったな、と思って調べたところ、運営を移管して延命したらしい。槻影さんこれどこか別の場所に投稿してくれないかな……。

storie.jp

2021/04/18追記：終了していた。題名も見えないので、ここに書いておく。「天才美少女ストーリーテラー笹宮明と僕の愉快で退屈な日常」というものだった。

2021/12/29追記：復活していた。

次に「日常ではさえないただのおっさん、本当は地上最強の戦神7」。本編読了後あとがきを読むと、どうにもシリーズ完結みたいな雰囲気を出している。慌てて調べたところ、完結だった。どのように読んでもストーリーの途中でぶつ切りになっているようにしか思えない。書き上げてから打ち切りが決まったのかもしれないが、もう少しちゃんとまとめようとは出来なかったのだろうか。なろう版でもちょうど今日最終話が投稿されているようで、そちらを見る限りは本来7巻後も数十話くらい続くようだった。なんとも後味の悪い終わり方。

正直文章も突っ込みどころが多い。似たような立場・設定の人（「八神輝」とか、女性複数人で構成されたパーティーとか）が一気に出てくるシーンが多いが、セリフだけで発話者を区別するのはハナから諦めているらしく、セリフの直前か直後に発話者の名前を書くような感じの文章でかなりテンポが悪い。

もう1冊。「継母の連れ子が元カノだった6」。非常に良かった。ところどころネットのネタやミステリに関するネタが挟まっていて、前者は微妙だが後者はニヤニヤできる。個々のシーンもかなり好みで、ストーリー全体として見ても面白い。良いです。

良すぎて途中途中休憩を挟まないと読めなかった。休憩としてCF Div.3を埋めていた。Contest Maniaというサイトで埋め状況を確認しつつ、最近のコンテストから順に解いている。Div.2とDiv.1に共通する問題でうまく認識してくれないという欠点はあるようだが、Div.3を埋めるにあたっては影響しない。

午前6時くらいに橙diffを埋める作業に戻って、「部屋割り」という問題を開いた。通すのに5時間かかった。

atcoder.jp

最初考えていた場合分けはヤバいケースがあって、それを直すのに非常に苦労した。愚直を書いて、ランダムケースを500個くらい作った。解説を読むとシミュレーションと書いてあって、初手から全然違うんだなあという気持ちに。場合分けにも少しだけ言及されていたが、お勧めはしないと書いてあって涙。

結局通しきることができたので満足。さらにもう1問開いたところ、今度は一瞬で解けてさらに気分がよくなった。続けてCF Div.3からまた少し解き、6000ACに到達した。

午後1時、就寝。

02/12(金)

午後8時起床。yukicoderに出て、4完だった。

Aは数列の総和が与えられていることに気づかず迷走。BはUF。Cは、1倍する区間は一つながりになることを利用して、区間を全探索した。区間を固定した後は、それぞれの端点を調べた後、1倍する区間で三分探索。関数の値を計算するラムダ式を作っておくとかなり簡単に書けた。DはDPのD。包除原理は使わず、ループごとに始点と同じ頂点にいる・いないをキーに持った。

Eはのいみさんのツイートを見てupsolveした。

直後にこどふぉ。全完してシステス後15位。

Aは、bを小さいほうからいくつか試す。Bは真ん中の自由度を累積和で求めて両端は毎回計算した。よく見るとa_r-a_lとr-lだけで決まるらしい。Cは非常に難しい。bを固定することを考えると、sqrt(Y)以降は商でまとめるやつをすれば解けることは解ける。実はa%bを固定すればよかったらしい。Dはわからなかったのでいったん飛ばした。

Eは気合い。absのために、ソートして左からの累積と右からの累積を持ったりしたが、実は|a-b|=max(a-b,b-a)を利用すればそんなことしなくてよかったらしい。ソートしたのにソートする前の値を使ったりして2WA生やしてしまった。FはZero-Sum Rangesみたいな感じ、だけ考えて実装を始めたが迷走。ちゃんと紙の上で考えてから解こう！Dに戻って、唐突にLCM(1..16)=720720を確認したところ、解けた。市松模様にして、片方を720720に、もう片方を720720-a^4にすればよい。

さらにCF Div.3埋めを進める。今日は2コンテストぶん+αくらいだった。1コンテストに1時間弱かかるので結構面倒であるようだ。ただ、簡単な問題をなぎ倒すのは楽しい。

午前9時、就寝。

02/13(土)

午後3時くらいに生協の弁当を待ち構えるため目覚ましで覚醒。その後寝たり起きたりを2回くらい繰り返して午後4時になる。寝ているのはマズいと感じたため、スマホを触っていたら午後4時半くらいに弁当が到着した。そのあとも少しスマホを触っていて、午後5時くらいに再度入眠。

ARCを寝過ごさないため、午後7時くらいから30分おきに目覚ましをセットしている。その前の午後6時半あたりでも意識があったような気がするが、結局起きたのは午後7時半だった。生協の弁当を待ち構えるのも含め、細切れの睡眠になってしまった印象があって、どうにも頭がぼやけている。今日のコンテストは寝過ごさなかったが、明日は昼からICPC練習の予定があり、そちらは少しまずいかもしれない。

昨日手を付けたCF Div.3のF問題を通して食事したりしていたらARCの時間になった。今日は5完38位でパフォーマンス2878、レートは2690→2710(+20)で久しぶりに（微妙に）highestを更新した。

Aは頭が回っておらず、最初にCをL..Rで全探索するコードを提出したところ、マルチテストケースにやられてTLEした。CFをやっていると、こういう場合はsum R-Lにも制約がついているように見えてしまっておかしなことになる。幸い、よく見たら定数時間で解けるので、すぐ再提出してAC。直後にdcの31Bコードを書いて通しておいたが、これは5完後に30Bに縮んだ。

Bはいくつかの区間が組み合わさった形になる。AでWAを生やし、自分の頭を信頼できなくなったので、区間の重複を省いたりするのには座標圧縮＋imos法を用いた。

Cは部分木ごとに再帰的に考えてよいやつ。プレイヤーのスコアはPとN-Pになるので、Pの最大化の代わりにP-(N-P)=2P-Nの最大化を考えてもよい。相手は2P-Nをできるだけ小さくしようとしてくる。こうやって差の形にしておくと、部分木ごとに「差の増減」と「先手後手が入れ替わるか」を持ってきて適当に貪欲すればよくなる。これらの考察は書きながら考えていたら整理されていったのであって、最初のあまり整理されていない状態のまま設計したコードで書き上げて無理やりサンプルを合わせてしまった結果、1WA。これはどうしようもない。サンプルがすべてあったコードは、提出しちゃうだろ。

Dは、結局隅からすべてのマスを通れないといけない。最初は隅からBFSして通れないマスが存在する行の個数と列の個数のminを出力したが、これは誤り。実際は1つ地面を増やすことでいくつかの行・列が一気に通れるようになる。これを反映するためにはUFを使うとよい。Eは、「まだ動かしていない区間」の両端を持つDPをO(N^2M)で書いてみると、サンプルが合う。DPをよく見ると区間の幅だけ持っていてもよさそうに見えるが、動かしていない区間として適切でないものを省くのに、結局区間の始点終点が必要に見えてしまう。ここでぐっとこらえて遷移を観察すると、区間の幅を減らすときは左から1個取るか右から1個取るかしかないので、この操作を何回したかの情報（これは区間幅から復元できる）さえあれば、あとは二項係数で区間の始点終点に応じたDPの値が復元できる。これはかなりすんなりACできた。

結局ACDでそれぞれ1WAずつ出してしまった。Cを通したあたりではかなり辛くなっていたが、順位表を見たところ全然通っていなかったので復活し、そのあとも気分よく解いていけた。

コンテストが終わって少し後に地震が来た。かなり大きめであった。机の下にもぐっていると、本棚がグラグラ揺れているのに気づき、思わず押さえに行ってしまった。突っ張り棒は設置してあるものの、多少ゆるみがあったようだ。これは良くない行動であったらしい。

シャワーを浴びて食事をし、SRM800に出た。今日は250-400-550-1000の4問。うち最初の3問を解いて、challengeも1件成功し、16位でレートは2404→2481(+77)、最高値を更新した。記念すべき第800回ということで、いくつかの基準に従ってTシャツが配られるらしい。僕は上位25人という基準をクリアしているので、Tシャツが届くようだ。

250は適当にBFS。400は両端のminもしくはmaxが答えになる。証明も自分なりにつけておいた。小さいケースは手で試すとわかる。より大きなケースでは両端を変えずにサイズを1小さくするのが最適。両端を変えようとすると、小さくしたい人は大きく、大きくしたい人は小さくしかできない。550は二分探索。「a秒までに着手しなければならず、b秒かかる課題」の最適な並べ方はa+bの昇順である。

例えば(a_1,b_1)と(a_2,b_2)を並べるとしよう。これまでt秒経過しているとして、t+b_1\le a_2かつt+b_2\gt a_1ならば、(a_1,b_1)は(a_2,b_2)より先に来なければならない。変形してa_1-b_2\lt t\le a_2-b_1\Leftrightarrow a_1+b_1\lt a_2+b_2である。つまりa+bの昇順に並べても損しないということ。こういう比較関数ネタは、いちいち覚えてはいられないので、導き方だけ覚えておいて毎回式変形している。

400に再帰全探索のコードが提出されていたのを落とした。TLEなのでジャッジに時間がかかったのだが、その間心拍数がすごいことになっていた。

朝方布団に入り、しばらくハーメルンを読んでから午前9時頃に就寝。

02/14(日)

午後2時少し前に起床。すぐICPCチーム練に突入。今日はこのセットらしい。同じく東北大から横浜大会に進んだ、Aobayama_sugarstepの練習に便乗させてもらっている。

https://codeforces.com/contest/1250

相変わらずこどふぉは人が多いので、solvedが増えてきた問題を順になぎ倒していくのが最も良い戦略となる。今日はチーム参加なので、solved数がmaxの問題はチームメイトに任せて、ちょっと少なめのものから解いていった。結果はABCEFGHJLMNの11完で、僕はそのうちNJCEBMGを、この順で解いた。全体的に解の復元を要求する問題が多くて嫌になった。

Nは気合い。連結成分でBFSするときに、最後に訪れた頂点とそこに行くのに使用した辺を保存しておいて、その終点を変えて別の連結成分につなげればよい。この問題だけはsolved数を見ずに開いたのだが、すんなり解けてちょっと不安になった。Jは二分探索。Cは最初実家DPをしようとして失敗したが、区間の終点を全探索する方針に変えて解けた。累積和のようなものを考えると、更新は区間addで、取得は区間minでできる。

Eは少し難しい。2-SATが見えるが、trueを割り当てる個数の最小化はどうもできそうにない。ここでグラフを出力してよく見ると、a⇒bという辺があるときは常にb⇒a、￢a⇒￢b、￢a⇒￢bも存在することに気づく。つまり、弱連結成分ならば常に強連結成分となり、各要素の真偽を反転した別の強連結成分と1対1対応するということがわかる。こうなると、この対応する強連結成分2つの組のうちどちらをtrueにするか、を個別に定める問題になるので、真偽の割り当てに応じて小さいほうか大きいほうを選べばよい。

Bはsとしてありうる値をO(K^2)で列挙して、自明に不要なものを除いたり重複を削除したりした後、各候補sについてO(K)でrを探索したら1200msで通った。rを全探索するのが正しい解法のようだ。Mは、まず3x3マス置きに埋めて真ん中のブロックを縁取れることに気づき、あとはそれのサイズを倍々（本当は横は縦より長くする）にしていきながら同様に斜めにずらして埋めていくことで作れた。Gは差分とAの累積和を持ちながら尺取り法のようにして更新。これも最初は実家DPを考えていたが、差分が負のときの扱いがうまくいかなかった。冷静になると、更新のために区間からもらってくる必要はなくて、常に区間の一番左端の要素を持ってきてよいので、尺取り法が適用できると分かった。

19時に終了。その後30分程度オンライン通話アプリで感想を言い合って、Div.3を少し埋めていたらyukicoderの時間になった。

今日は3問で、最初の2問を通して終了した。TROCがあったので残り20分あたりで抜けはしたものの、それがなくても3問目は通せなかっただろう。Aは大体何でもできて、BはLCM(1..N)からある素数の指数を1少なくすることしかできなさそうなので、N以下で最大の素数を抜けばよい。N/2..Nに素数が存在することについては何となくで飛ばしてしまったが、ここにはベルトラン・チェビシェフの定理が使えるようだ。Cは……。

TROC #19に出る。6完4位で2528→2602(+74)。どんどん上がっているが、何気に現在全体ランキングの9位らしい。毎回参加することが重要。今回から制約が問題文の直下に置かれるようになったらしく、非常に便利になった。

Aは書いている途中で常に-1になりそうなことに気付いたが、そのまま書ききった。Bは全体の半分だけ作れる。Cはbitを減らしていく。制約が優しくて、必ず先にKのbitが消える。ちょっと書き間違えて1WA。Dは難しいが、[1,i]と[i,1]を順に聞いて、その差を見るとわかる。片方だけだと微妙なものが残るが、両方からやるとマズいものはちゃんと消えてくれる。Eはやるだけ。Fは非常に難しいと思っていて、根を決め打ち、子を0・1・任意の3種類に分けて場合分けを頑張ると木DPできる。もっと頑張ると全方位木DPできるので、それで通した。めちゃくちゃ自由度が高いことはわかっていたが、実際にAが全部0のパターンとサンプル2のケース以外はYESらしい。許せないな？Gは諦めた。

DはFAだった。touristと一緒のところに書かれていて非常に誇らしい。touristはCの後Eに進んだようだ。

Gを諦めてからは、今日のyukicoderのC問題と格闘していた。だいたい午後11時にスタートして、ACが午前5時半だったので、コンテスト本番で少しやっていた分も含めれば7時間に及ぶ壮絶な戦いであった。

方針としては、連結成分に番号を振りつつ行ごとに見るDPをする。壁と空きマス（本当はチョコレートだが、ここではこう呼ぶ）は最大でそれぞれ3つずつの連結成分があるので、1マスの情報は6通り、6進数で情報を保持する。よって計算量はO(R 6^C 2^C CN)のようだ。冷静になるとこれで通そうとするのはイカレていた。ちなみに、空きマスの連結成分も考えなければならないことに気づくのに3時間くらいかかった。次のようなケースを数えられていなかった。

#####
#...#
#.#.#
###.#

前の行の情報と現在の行の壁・空きマスの配置から連結成分によって再度壁・空きマスに番号を振り直し、頂点の個数を数えて次の行に更新する。このとき、マスの外側にたどり着けないまま壁にふさがれてしまう空きマスや最後まで連結にならなかった壁の組などを検出して適宜飛ばしておく。連結成分0は必ずマスの外側にたどりつける空きマスにだけ割り振られるようにしておくことで、空きマスがマスの外側にたどり着いたかどうかを判定する。各行の両端が空きマスだった場合はそこを連結成分0に直すことにすると達成できる。

最初にサンプルが合ったとき、最大ケースは手元で19secだった。そこから、途中O(C^2)のループがあったのをなくして12secくらいになった。そのあとは定数倍バトルで、何回も回していたループをまとめたり、不必要な分岐を減らしたり、UFをベタ書きしたり、find関数の戻り値を配列に取って置いたりして計算時間を減らしていった。結局手元で7.5secくらいになったのだが、yukicoder上では相も変わらず10秒オーバーのようであった。最後にCを定数6にしたところ、手元で6secとなり、yukicoder上でも10secギリギリでACできる速度になった。C<=6という小さなループが頻発するので、キャッシュヒットや並列化はあまり考えられない。その代わり、その小さなループを定数回のループに直したことで、ループアンローリングなどができたのではないかと考えている。