04/05(月)

午前9時半起床。

二度寝するべきだとは思っていたが、寝落ちする前に読んでいたノクターンノベルズの続きを読み始めてしまい、そのまま止まらなかった。正午、読了。

https://novel18.syosetu.com/n7640gf/

主人公とハーレムメンバーのバランスのとり方とか、主人公の優しさが良さげに描かれていて良かった。

そのまま他の作品を漁って、2つ読んだ。こちらは完全にエロに振り切っていてストーリーなどないようなものなので、特に感想もない。題名も書かないので気になる人はリンク先（R18サイト）に飛んでほしい。

https://novel18.syosetu.com/n6275gw/

https://novel18.syosetu.com/n8082gs/

午後1時半ごろ寝落ちして、午後8時ごろに目を覚ました。ツイートを確認すると午後6時頃に少しだけ覚醒していたようだが、特に何もせずまた寝たようだった。

食事して週記を書いた。また数日分溜めていたので、午後9時から作業に入って投稿したのが午後11時半だった。

ECR2を埋めた。Aは不快。BCは普通。

Dは幾何で、2円の共通部分の面積を求めよという問題だった。ライブラリになっていなかったので、この機会に作っておくことにした。2円の交点を求めるライブラリはあったが、その点から角度などを復元するよりは処理自体をコピーしてきたほうがよさそう。それぞれの円に対し、2円の交点と円の中心からなる扇形の中心角が求まれば、そこから扇形の面積と三角形の面積が計算できて……というやつだ。

ところが落ちてしまった。テストケースを見ると、ほんの少しだけ重なるときに誤差で落ちているようだ。そこで、以前は角度を求めるのにacosを使用していたところを、asinで求めることにした。asinのほうが精度が良い、という話を最近のICPCで聞いた気がする（が、実際のところはよくわかっていない）。ほんの少しだけ重なっているという仮定、より一般にacosで求めたい角度が直角より小さいことが分かっていれば、3辺の長さから求めた三角形の面積（仮定から、角度を使用して求める符号付き面積と一致する）を使用することでsinの値がわかる。これで試してみると、確かに少しだけ誤差は減ったようだが、まだACにはならない。

最終的にdoubleをlong doubleにしたらacosのままで通った。つまらない。今回はdoubleをlong doubleに置換したが、より汎用的にするべく幾何ライブラリにusing Real=doubleと書いてdoubleだった箇所をすべてRealにしておいた。今回のような場合はusing Real=long doubleに書き直すことになる。

Eはマージテクで、Fは解けなかったので解説を読んで通した。二部グラフであることを巧妙に使っていて面白かった。

そういえば、汎用的なグラフ構造体というのはいつか作りたいと思っていたライブラリの一つである。これの設計に関して考えていた。メンバ変数の名前が決まっていて、ほかに必要な情報も持てるようなedge構造体だけ毎回書いて、グラフ構造体自体は常にvector<vector<edge>>で持つ、というものを考えたが、kimiyukiさんによればこれは汎用的なグラフ構造体とはならないらしい。具体的には、辺を陰に持ちたかったり、隣接行列で持ちたかったりする場合に困るようだ。それはそう。

上の設計ではedgeについて抽象化していたが、ここをvector<edge>について抽象化する（隣接リストを舐めるイテレータを作る）というのが良さげならしい。そういう方針で作成されたグラフ構造体についての議論は以前TLで見たことがある気がする。

ECR3を埋めた。ABCDは普通。Eは見た瞬間最小全域木+オイラーツアー+LCA+RMQの解法が思い浮かぶが、実装が嫌でしばらく逃避していた。RMQ以外はライブラリになっていない。そういったことをツイートすると、第2回PASTのO問題ではないかという指摘が来た。見てみると全く同じ問題だったので、コピペしてAC。並列二分探索による解法は当時感動していた気がするが、時が経ち、すっかり忘れ去っていた。Fはセグメント木上で二分探索。

Problem - E - Codeforces

O - Variable Spanning Trees

ECR4のAからEまでを解いた。ABは普通。Cはかっこの対応が一意に定まる。Dは幅0の区間をわざわざ削除してしまい1WA。Eはどこかで見たことがある。

Fを開いて、解法自体はすぐわかるものの、復元があって実装が辛そうだったので今日は止めておくことにした。布団に入ってまたノクターンノベルズを読んでいたが、午前11時ごろ寝落ちした。

04/06(火)

午後4時半起床。そのまま夜まで布団でノクターンノベルズを読み続けていた。

https://novel18.syosetu.com/n9485dy/

↑これはたこノすけさんにオススメされたものだが、50話くらい読んで放棄してしまった。

https://novel18.syosetu.com/n8462gt/

サークルのバチャに出た。CF #516 div.1。途中30分くらいこどふぉが落ちていて非常に厳しい気持ちになった。問題はvjudgeから見られるが、実装まで済ませた問題が提出できないのは辛かった。

Aはギャグ。未証明で通した。バチャ後の反省会で知ったが、回文の両端の文字が等しいことに着目すれば証明できる。文字列の文字をソートしたものが答えだが、これは回文の両端の文字になりうるペアすべてが、実際に回文の両端の文字になっているので、最大。

Bは左右の移動が打ち消しあった回数を持っておけば、どちらにどれだけ余分に移動しているかはスタート地点と現在地の座標の差から計算できる。打ち消しあった回数で01BFSをした。ほかの人は左右に移動した回数の和で01BFSしていたようだ。min(L,R)*2+abs(y-sy)=L+Rが成り立つから、L+Rで01BFSしようとmin(L,R)で01BFSしようと変わらない、ということだろう。他にも、LとRでそれぞれ01BFSした人もいた。変に遠回りすることでLを増やしてRを減らす、なんてことはできないから、これも正しい。

Cは二分探索っぽくやる。2^29<10^9<2^30なので、最初の1点だけは一番端に固定する。また、X軸から少しだけ浮かせておくことで、座標が1しか離れていない2点の間を通るような直線が簡単に引けた。

コンテスト後にDをupsolveした。答えとなる値を決め打つと、それがminとかmaxの1つの引数になるので、探索する区間を適当に分割してminやmaxを消し、あとは頑張る……というようなことを考えていたが、どうにもならなかった。特に単調性があるわけでもないし、割り算が出てくるのでその商ごとにまとめて見ることでさらに区間に分割しようとしたが、floorはともかくceilのほうがよくわからなかった。解説はかなり頭が良い。O(min(n^2,k/n))だが、僕の実装だとO(k/n)のほうにlogがついてしまった。k/n<1e7という場合分けだとTLEして、n>2e4にしたらACした。

このlogは、(d+1)a+db=1なるaとbを1組見つけるために使った拡張ユークリッドの互除法によるものだが、冷静になれば(d+1)-d=1なのでa=1とb=-1が必ず解である。これでちゃんと線形になって、試してみるとk/n<1e7の場合分けでも通った。サボりすぎ。

最近はレトルトカレーを食べている。実家でよく母がやっていたように、カレーの皿を洗う前にはティッシュで汚れをある程度拭き取っている。実家では不要になった肌着などを使っていたが、そんなものは保管していない。カレーに限らず、汚れが多い皿は拭き取ってから洗う、というのは重要な典型テク。

またノクターンノベルズを読んだ。

https://novel18.syosetu.com/n5258gt/

昨日放置したECR4のFを実装した。そもそもの実装がつらかったのと、さらに円周上をどちらに移動するかの符号を合わせるのに苦労したが、サンプルが通ったものがそのまま一発ACだった。

ECR5を埋めた。ABCは普通。Dは尺取り法。Eは商ごとにまとめて見るやつ。Fは文字列を'$'などを間に挟んですべて連結した文字列を作り、それの接尾辞配列と高さ配列を計算して、高い順に要素をマージしていく感じでできる。ただこれだと全体で2回以上出現する文字列に関してしか計算できないので、1回だけ出現する文字列に関しては別に計算する必要がある。ここの計算を間違えて2WA。

ECR6のAからEまでを解いた。ABCは普通。Dはオーバーフローで1WA。10⁹を4倍してしまった。2倍して2倍する、という形で書かれていたので気づけなかった。Eはオイラーツアーして区間set区間bitwise ORの遅延セグメント木。

せっかくなのでオイラーツアーのライブラリを作っておくことにした。今回必要なのは辺属性ではなく頂点属性。昨日考えていたグラフ構造体をいよいよ実装して、それを使って作ろうかと思ったが、何回もクエリに答えるため構造体が必要で、結局ほかのライブラリと同様オイラーツアー構造体にadd_edgeを作ってグラフを作る形になった。

library/euler_tour_vertex.cpp at master · kotatsugame/library · GitHub

Fは解けない。布団に入ってノクターンノベルズを読んでいたら午前7時半ごろ寝落ちした。

https://novel18.syosetu.com/n8141gc/

04/07(水)

午後2時半起床。寝落ちする前に読んでいたものをそのまま読み続けて、読了した。

https://novel18.syosetu.com/n8141gc/

かなり歪んでいて、心情的には理解できないが、そういうものに触れてみるという点では良かった。

他の作品をいくつか漁ったが、だいたいは少し読んで投げ出してしまった。1作だけ読了。

https://novel18.syosetu.com/n9412dj/

そうこうしているうちに夜になったので、サークルバチャに参加した。CF #511 div.1。

Aは誤読して1WA。削除しなかった要素のgcdが、削除した要素のどれよりも大きくなる必要がある、という風に読んだ。正しくは、削除しなかった要素のgcdが最初の全要素のgcdよりも大きくなること。こちらだと、最初に全体をgcdで割ることで、総gcdが1でないような部分集合のうちサイズが最大のものを計算する問題になる。もっと言えば素数pで割り切れる数列の要素の個数をpそれぞれに求められればよく（p|gcdとなるような部分集合のサイズとなる）、これはエラトステネスの篩の要領で各数に対して素因数を1つ求める前計算をし、O(log A)で素因数分解すればカウントできる。なんとなく怖かったので同じ値の要素をまとめて計算したが、別にそのような必要はない。

Bは気合いで場合分け。1x6が必ず埋められるので、縦横をmod 6で考えることにした。2x5や3x4が埋められるのは結構非自明な構成だが、運よく手で作れた。他には、2x2は1つも入れられないが2x8だと埋められるとか、2x3は2マス空くが8x3や2x9だと埋められる、1x2も7x2も2マス空くが13x2だと埋められるなどの処理が面倒だった。書いていて発見したが、僕のコードは7x8で落ちるようだ。7x2と同様に2マス空くと思っていた。

Cは頑張る。グループのvalueの和がpであるような分割（pによる分割と言うことにする）が可能であることの必要十分条件は、分割の仕方が一意であることに気づくと、全体のvalueの和（sumとおく）がpで割り切れて、かつ部分木のvalueの和がpで割り切れるような頂点の個数がsum/pに等しいことだとわかる。このとき直ちに、pによる分割とq|pによる分割があった場合、pを経由してqの分割が作れることがわかる。

あとはpを全探索。ただ毎回チェックすると間に合わないので、sumを素因数分解して、素因数ごとにbitsetでチェック結果を持っておき、具体的なpに対してはpを素因数分解してテーブルをbitwise ANDすることにした。すべての倍数に対して遷移するDPを書こうとしたが、よくわからなかったので、pとしてありうるものを列挙した後2乗かけた。これはsumが高度合成数のとき最大で26880²ステップくらいになりそうだったが、通った。

解説は頭がよく、コードも簡潔ですごかった。sum/pに着目する。s_uを、uを頂点とする部分木のvalueの和とすると、p|s_uとsum/gcd(sum,s_u)|sum/pは同値になる。sum/p<=nなのでsum/gcd(sum,s_u)<=nとなるような頂点だけ考えればよく、個数のカウントやDPの遷移も添え字がnまでなので調和級数の要領でできるというもの。

またノクターンノベルズを読んだ。

https://novel18.syosetu.com/n7438gs/

溜めていた日記を書いていたら午前5時くらいになった。広義明日は午前10時から学科ガイダンスがあるので起きなければならない。まだ途中までしか書けていなかったが切り上げて布団に入った。しかしそれからもしばらくなろうを読んでしまい、結局寝たのは午前7時頃だった。

04/08(木)

午前10時起床。学科ガイダンスに参加する。

4年目ということもあって特に目新しいことは言っていない気がする。院試の日程とか、インターンとかに触れられていた。資料もアップロードされるので、無理やり起きて出る必要性は感じられなかったが、出なかったら出なかったで自分の知らない情報があるのではないかと心配になるはずだから、出ておくべき。

途中で昨日の分の日記を書いていたら、バチャのB問題が落ちることに気づいた。自分でHackしておこうと思ったが、コンテストが終了したのでそのような機能はないらしい。とりあえず修正したものを投げておいた。

ガイダンスは時間が少し余ったので近況報告をしようという話になり、数人喋っていた。僕も何を話そうか考えていたが、結局すぐ解散になった。謎。こういう交流イベントは心臓に負担がかかるが、それでも今は久しぶりに（カメラ越しに）顔を見た同級生が懐かしいという思いが強い。僕はカメラオフだったので、一方的に観察していたことになる。

午後1時から4年次ゼミの初回、初顔合わせがある。それまで2時間くらいあるから寝ておこうかとも考えて布団に入ったが、万が一寝坊すると大変なので、なろうを読みつつ起きておくことにした。

ゼミが始まった。自己紹介のタイミングで皆カメラをオンにしていたので僕もオンにしたが、パジャマだし洗濯物を片していないしでもう大変。自己紹介については、競技プログラミングから数論に興味を持った……ということを言った。プログラムで問題を解くとは何をするのか？ということを聞かれた。これはよくある質問だが、いまだに何を喋ればいいのかわからなくなる。今回は「AのB乗を普通にB-1回掛け算するより高速に求められる方法がある」という話をした。といっても二分累乗法の説明をしたわけではなくて、そうやってプログラムをアルゴリズムの力で高速化する競技である、とだけ言う感じ。

今年読んでいく本を決める。「Introduction to Analytic Number Theory」と「Multiple Zeta Functions, Multiple Polylogarithms and Their Special Values」の2冊の候補があって、それぞれグループを作る。前者を希望したところすんなり通ったので、それをやっていくことになった。3人チームで順番に発表を担当し、僕はその3番目だ。ゼミ生同士の連絡手段をどうするかという話になって、博士課程の人の主導でLINEグループが作られた。SlackとかDiscordを提案しようとしたが、そういうところで目立つのもどうかと思い止めておいた。

読む本を手に入れなければならない。僕が読む本についてはネットにPDFが落ちていると言われ、探してみると確かにあった。しかしこれは……いいのか？あんまり触れちゃいけない話題なのかもしれない。もう1冊はないようなので、また後日入手方法が知らされるか、あるいは自分でコピーしてくるかしなければならないだろう。

library--/Introduction to Analytic Number Theory (1976) - Apostol.pdf at master · isislovecruft/library-- · GitHub

ゼミが終了したので即座に布団に入り、午後3時から午後8時まで寝た。起きたらりんごさんの配信が始まっていて、TLでその話題がたくさん流れてきた。

布団でなろうを読んだ。「金で買えないスキルはない　～『外資系投資銀行に勤める俺が、異世界転生して金の力でチートする』～」。

https://ncode.syosetu.com/n7340da/

かなりテンポよく進んでいった。意図的にリーマンショックを引き起こすのは面白かった。ところで、美醜の基準が違うのでヒロインは異世界ではとんでもない醜女だとされている、という設定はいらないと思う。周りの反応が読んでいて不快だった。

続いてもう1作。「スゴいカードを拾ったので株式投資で資産家目指します」。

https://ncode.syosetu.com/n6412fu/

面白かったが、自分がこれを面白いと感じてしまうことがちょっと信じられなかった。お金が無限に使えるようになったので株を買い漁って財閥（コングロマリット）を作る、という話。経営の話は一切出てこなくて、主人公が社会的地位を得たり有名になったりお金を使ったりするシーンが延々続くが、それでも面白いと感じた。

前々から「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」が好きだという話をしているが、その流れで会社を経営したり投資したりする話に興味を持ち、それで検索して読んだ作品だった。ほぼ無限にお金を使える設定のものは他に書籍化したものを読んだことがあるが、そちらは全然合わなかったので、自分は「どうやって稼いだか」ということに興味があるのだとばかり考えていたが、この作品を面白く感じてしまった以上、結局主人公が社会的地位を得るのを一番面白がっているということが明らかになった。

布団から出て食事し、火曜日解けなかったECR6-Fと向き合ったが、やはりわからない。適当に提出したらTLEしてしまった。手元で試行錯誤した結果26secが23secになったが、TLは10secなので焼け石に水。ふてくされて布団で丸まっていたら寝てしまった。午前2時だった。

04/09(金)

午前5時半起床。うつらうつらしていたら神崎さんのなろう読了ツイートが流れてきて、それを読み始めたら止まらなくなった。「転生したら皇帝でした～生まれながらの皇帝はこの先生き残れるか～」。

https://ncode.syosetu.com/n6066gi/

午前11時までかけて一気読みした。非常に面白かった。傀儡を演じるため思うように動けない主人公のもどかしさや、そんな中で少しずつ自分の味方を増やしていく緊張感が良い。

読み止しにしていたノクターンノベルズを読んだ。

https://novel18.syosetu.com/n0019fz/

正午にまた意識を落とし、途中一瞬の覚醒を挟んで午後8時まで寝た。食事してyukicoderに出た。全完。

AはPerlで置換したが、制約をよく読むと文字数が5e6だった。よく間に合ったものだ。22Bで、これ以外ないと思っていたが、tailsさんが同じくPerlで16Bを出していてびっくり。コンテスト後に見るとy/a-z//s（の短い書き方）を使用していた。オプションsは同じ英子文字が連続している箇所を1文字にまとめてくれる。なるほど。このオプションはBashのtrでも使えるので、tr -cs _を提出して8Bとなった。

B、Cはよい。Dはよくわからなかったので飛ばし、先にEを解いた。Eも特になし。Dに戻って、9が連続すると考えて提出したがWA。ここでようやく実験コードを書いてみると、どうやら最初に1文字8が入るらしい。実装してAC。

Fは面白かった。ある人に配られたPの個数をX、qの個数をYとすると、Y=0であるか1<=Y<=S<LかつX>=L-Yである必要がある。このときY>0であるような人数とそのYの総和が分かれば絶対に使わなければならないPの個数が求められ、残りのPは自由に配ってよいことになる。人数と総和をキーにするDPが計算できるので、余ったPの配り方をさらにかけ合わせれば解ける。

ECR6-Fがどうにも解けないので解説を読むことにした。Mo's algorithmのようだ。僕も考えたが、削除ができないと思い諦めた。しかし今回の問題では削除が必要ないらしい。

長さNの数列aに対してクエリ[l,r)が飛んでくるので、数列のl番目からr-1番目までの要素から2つ（u<=v）選んだときのu^(u+1)^...^vの値の最大値を答えるという問題。まずMo's algorithmの前提の話をしよう。f(x)=0^1^...^xと置けばf(u-1)^f(v)の最大値を答える問題になり、Trie木が使える。Trie木は2本用意し、f(u-1)を入れるTrie木の各ノードにはその値を達成する最小のuを持つ。これで、ただ^f(v)した最大値を答えるのではなく、u<=vなるuによって達成され得る最大値が求まる。f(v)を入れるTrie木も同様にする。これでuとvのどちらからも相方を探せるようになったので、Mo's algorithmにおける区間の伸長ができることが分かった。

削除不要とはどういうことなのか。区間から2点選んで計算する形式の時にそうできるようだ。ブロックサイズをB=sqrt(N)とし、クエリ[l,r)であってl/B（切り捨てとする）が等しいものを集める。ここでmid=l/B*B+Bとおき、[l,r)を[l,mid)と[mid,r)に分ける（空になる区間は今は考えない）。区間から2点選ぶというのは、どちらかの区間から2つとも選ぶか、1つずつ選ぶかの3通りに分けられる。rで昇順ソートすると、[mid,r)から2点選ぶ方法に関しては区間は伸びる一方なので削除の必要がない（①）。あるクエリに対して[mid,r)を処理したとき、いったんストップして、[l,mid)を考えることにする。挿入せずにペアの相方を探すだけにすると、Trie木を変更せずに2つの区間から1つずつ選ぶ場合が計算できる（②）。最後に、クエリそれぞれに対してTrie木を初期化して、[l,mid)から2つ選ぶ方法を計算する（③）。

計算量を考えよう。Trie木のlogは一旦無視して、区間の伸長だけ考える。 $B=\sqrt N$ であった。①は $\frac N B$ 個のブロックに対して $O(N)$ なので $O(\frac{N^2}B)=O(N\sqrt N)$ 。②はクエリの個数 $Q$ に対してそれぞれ $O(B)$ なので $O(Q \sqrt N)$ 。③もクエリごとに $O(B)$ なので同じく $O(Q \sqrt N)$ 。合わせると確かに $O((N+Q)\sqrt N)$ である。

この問題ではN<=5e4、Q<=5e3だった。計算量は $O( (N+Q)\sqrt N \log \max a)$ である。解説には $O(N^2+Q)$ で通されたと書かれていた。TLが10secということもあり、なるほど確かに $O(N^2)$ が通りそうだ。 $N\gg Q$ であることに気を取られて、区間を全探索できることに気づいていなかった。Trie木だと $\log \max a$ がつくからどうするのだろうと思ってtouristのコードを読んだら、シンプルな $O(N(N+Q))$ で解いていた。ペアの一方を決め打ってもう一方をそこからインデックス順に試しつつ累積maxを取り、決め打った項を含むようなクエリに対してクエリの右端rでの累積maxで更新する。

ECR7を埋めた。慎重にコーディングした結果全部1発ACだった。AtCoderではコードゴルフに関係する再提出がたくさんあり自分の提出一覧が汚くなりがちだが、CFではそんなことはないため、全部ACで揃わないかとちょっと気にしていた。div.3を埋めているときは何度も発生した状況だが、ECRはやはり難しく、これが初めてであった。

ABCはよい。Dは必ず0にできる。Eは簡単なバージョンを2018年のICPC横浜大会で見たので、それの解説を参考に解いた。

Fは $\sum_{i=1}^n i^k$ を $1\le n\le 10^9$ 、 $1\le k\le 10^6$ で求める問題。 $k$ がもっと小さな制約の問題を2019年のICPC バンコク大会で見て、当時解けなかったのを覚えている。多項式補完が思い浮かぶが確か漸化式でも解けたはずで……と当時のやり取りをSlackで漁ったが、 $O(k^2)$ だったので今回は使えなかった。いい機会だと多項式補完を実装することにした。

多項式補完というとxには相異なるという制約しかないはずだが、例えばうしさんのライブラリを見るとx=0,1,...,N-1と決め打ちされているようだ。この制約は何だろうと思っていたが、アルゴリズムを見れば当たり前だった。より一般にxが等差数列であれば、1点とその他の点の差の積を求めるのが簡単。というか逆にxが等差数列でない場合の処理がO(N log N)でできるのがびっくり。

適当に書いて実験したらよさそうだったので提出、AC。ライブラリにもしておいた。求める値xは最初modintで与えられることを想定していて、この時大小比較ができないのですでに計算された値であっても知らないふりをする必要があった。後から必ずlong longで与えられるように修正した。

library/lagrange_interpolation.cpp at master · kotatsugame/library · GitHub

ライブラリのverifyにはyukicderの「貯金箱の溜息」を使用した。これはうしさんやbeetさんのライブラリのverifyを真似している。しかしこれが多項式補完になるというのはにわかには信じがたい。解説をいくつか読んで議論は追ったものの、狐につままれた印象。maspyさんの解説を読むと、累積和を6回取るので5次式であるということが式から見て取れるので、少しだけ理解できた気持ちになる。

ついでにコンビネーション類の計算をするライブラリも作った。毎回fac[]とinvfac[]を作って前計算していたが、さすがに面倒になった。以前はmodpowも毎回書いていたのだが、今から考えるとちょっと信じられない。

library/combination.cpp at master · kotatsugame/library · GitHub

ライブラリの設計に関する議論だけは済んでいた。これはLayCurseさんに教えていただいたものだったと思う。

mod上の逆元リストを必要に応じて生成する方法についての議論があった。前から作成する方法は、オーダーだけ見ればO(N)だが、実際は変数による除算や連続的でない配列アクセスなどがある。その点、後ろまで作ってから1回だけ逆元を計算する方法は、O(N+log mod)と変なのがついていても、定数による除算しか行わなかったりシーケンシャルアクセスが保たれたりと良いこと尽くめ。必要に応じて生成する場合も、倍々に増やしていくことで対応できる。これに関しては、呼び出しごとにif文による分岐が入るのが気になっていたが、分岐予測がかなり効くだろう、という話を聞いた。
週記（2021/02/01-2021/02/07） - kotatsugameの日記

ノクターンノベルズを読んだ。

https://novel18.syosetu.com/n6343gw/

午前10時からGCJ R1Aなので寝なければならない。午前6時、布団に入るも寝られない。なろうに手を出したところ午前10時直前まで読んでしまった。そのまま食事も摂らずコンテスト。

Abcで646位、何とか通過した。Aは愚直にやってよい。これを通したときは6位くらいだったのでびっくりしたが、両方Visibleなので確かに正しい答えを出力できたのだろう。

Bはわからない。とりあえず積を全探索する愚直なコードを書いてVisible 2つを取った。しばらく考えてもわからなかったので次に進むことにした。

Cは難しい。まず値がとても大きくなるようだったので言語をRubyに切り替えた。問題ごとにそれがT（もしくはF）だったときの場合の数を数える。これはどの問題で計算しても和が等しくなるはずで、場合の数が大きい方を選択すればよい。場合の数を数えるのは計算量的にちょっと大変かもしれないが、N人の回答は2^N通りしかなく、それぞれの個数を数えてメモ化することでQ回ではなくO(2^N)回しか計算しなくてよくなる。ここまで考えて細かい解析をせずコーディングした。小さいサンプルは合ったが、N=3、Q=120がどれだけたっても終わらない。とりあえず2つ取ることを目的に提出しておいた。

しばらくRubyで高速化して、大きなサンプルも3secくらいで通るようになったが、あるとき値が大きくなるとは言っても2^120をちょっと超えるくらいであることに感づく。そこでC++の__int128_tを使うことにして書き直した。大きなサンプルが0.15secくらいになったので時間ギリギリに提出したが、WA。ここでコンテストが終了した。

Bは積ではなくそれに使った数の和を全探索すればよかったらしい。xの素因数の和をf(x)とおいたときx+f(x)=sumだな～とは思っていたが、f(x)の値が全探索できるとは一瞬たりとも考えなかった。知ってしまった今では逆になんで考えられなかったのかわからない。CのWAの原因は分かった（Rubyで高速化しているときに嘘になったらしい）が、出しても結局TLEのままだった。N=2のときはどちらかの人のコピペをするか逆張りをするかで4通り試せばよかったらしい。

さらに1時間くらいなろうを読んで、午後2時就寝。AGCがあるので非常にまずい。

04/10(土)

午後3時、新年度1回目の弁当配達を寝過ごさないための目覚ましで起床。ここからうすぼんやり意識を保てればよかったのだが、思いっきり寝てしまった。午後5時半くらいに弁当が来て、何とか受け取れた。またすぐ寝ればいいのになろうを読んでしまう。午後6時半に再度就寝。

午後8時半起床。眠すぎて動けないが、食事だけでも摂っておく必要があったので、さっそく弁当を温めた。焦りながら食べてAGC053に臨む。

2完3WA、136位、パフォーマンス2447でレートは2692→2670(-22)。崖がデカすぎる。

Aは各項をできるだけ小さくした数列を引く方針で2WA。たくさん引いておいたほうが良い項もありうると気づく。隣合う項の差の最小値だと感じて、とりあえず最小値を取る2項を構築しようと思い立つ。極端に偏らせると別の項にしわ寄せがいくことがわかり、できるだけ均して置くことを思いつく。実は全ての項でできるだけ均したほうが良いのではないか？と思い考えたところ、証明がなんとなくつけられたので、提出してAC。

Bは大きいものから貪欲に取ることを考えた。setで管理するコードを書いている間に考えが整理され、中央の2i項のうちi項までしか保持してはいけないという条件になることに気づく。これはBITで計算できる……としたらWA。大きいものから貪欲というのはただの直感であったから、ちゃんと考え直し、priority_queueに2個入れて1個出す方針を生やしてACした。

Cはまず列が与えられたときの答えを考える。解説の2段落目の考察はかなり早い段階でできていた。そのあと、2Nがある山を固定して、挿入DPっぽくすることを考えていた。しかしmaxをうまく管理できなかった。maxについての数え上げで、maxの値を掛け算するのだから、p(x)を「答えがx以上になる場合の数」とおくとsum pになる。この方針を生やして、答えがx以上になる原因となりうるペア（他の場所に答えがもっと大きくなるペアがあるかもしれないが、一旦無視する）を配置し、数え上げてみたところ、全然答えが合わない。そのまま2時間念入りに椅子を温め続けてコンテストが終了した。

Cの解説を少し読んだが、p(x)を「答えがx以下になる場合の数」とおいている。これだけの違いかと思うとちょっと残念。しかしどうやって計算できるのかはまだよくわからないため、別に惜しくもなんともないのかもしれない。

AGCと少し被っていたCF #713 div.3に出て全完した。ABCはよい。Dは1個削除したときの最大値を見る。Eは大きいほうから貪欲に当てはめてよい。Fはどこで立ち止まるか全探索。Gは前計算。input validationが壊れていたらしく、AがHackされて嫌な気分になった。

AGCのコードゴルフをする。Aは、均すとき、今何個目の数列を作っているか見るのではなく毎回Aの値をインクリメントすることでも実現できるらしい。a//k+(i<a%k)みたいな式を使っていたが、a++//kでよくなる、ということ。BはPythonでheappushpop。Cythonによるループ部の改善があって負けたかと思ったが、n>i>=0を~n<i<0にして-1Bできたので再度奪取。

朝方布団に入ってからもずっとなろうを読んでいて、寝たのは午後1時だった。最近読んでいるなろうはこれだ。

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

04/11(日)

午後8時半起床。なろうが面白すぎて布団からの脱出に失敗しそうになるが、食事のため何とか這い出た。ABC198に参加する。今日はスクリーンキャプチャを録画しようと思ったが、なぜか録画が始まらなかった。原因を探している時間もないので、今回はあきらめた。

44分1WA全完で3位。Fが解けたのはかなり運がよかったと感じる。

AはABCで既出。こういう問題で既出かどうかを考えるのは無駄だということはわかっている。

atcoder.jp

Bはよくわからなかったので素直に書いた。Cはコーナーケースで1WA。D、Eはよい。

Fは、面に書く数の重複度を調べる。ある重複度についての回転して一致しないような書き込み方の個数は、最初は手で全通り生成しようと思ったが、さすがに正気に戻ってプログラムで書くことにした。さいころのありうる状態をすべて列挙するのに自信がなかったので、さいころライブラリを検索して拾ってきた。初期状態で面に配置する数を6!通り全探索して、それぞれに対しハッシュ値を計算する。ハッシュ値は、さいころの面の数値を6桁の6進数として読んだ時の値として、さいころを回転させて最も小さかったハッシュ値をもとに一致判定した。いくつか試すと手で計算した値と同じなのでよさそう。

重複度の列挙は再帰関数でよい。重複度の昇順・降順ではなく、実際に重複している値の昇順に列挙することにした。これを適当に組み替えると、a+2b+3c+4d+5e+6f=Sとなる正整数a..fの組み合わせの数を数える問題になる。係数のいくつかは使わないかもしれない。

これはつい最近見たことがある。金曜日に作った多項式補完のverify用問題、yukicderの「貯金箱の溜息」とほとんど一緒だ。貯金箱のため息では硬貨の額面という設定上1|5、5|10など係数の間に約数・倍数の関係があるが、答えが多項式補完で求まることの証明にはあまり関係がない。結局LCM(1,5,10,50,100,500)=500だったのがLCM(1,2,3,4,5,6)=60になるだけ。というわけでいそいそと多項式補完のライブラリを貼り付けてみたところ、サンプルが見事に合った。提出してAC。

コンテスト後のTLを見ていて気付いたが、Fの最後のステップは素直に考えれば行列累乗だった。

コードゴルフをする。Aの3B解もまた既出であるから、27秒ACで82位だったのを見て絶望していたが、蓋を開けてみれば僕が最短だった。Bは末尾の0を正規表現による置換で削除して云々、と考えていたが、reverseして数値として解釈すると勝手に消えることに気づいた。+0とすると括弧が必要になるので、負号をつけて判定する。Cはdcで、sqrt((X^2+Y^2)/R^2)を考えていたが、sqrt(X^2+Y^2)/Rのほうがよい。sqrtだけ精度を高く設定して計算する。コーナーケースの場合分けはいろいろ試したが、切り上げしてしまうとちょうど1歩でたどり着ける場合と区別がつかないので、切り上げする前に答えが1未満かどうかを見ることにした。Eは適当にPerl。他は手付かず。

CF #714 div.2に出た。ABCDFの5完。どうせ全完できるだろと思ってEを飛ばしたが、Fが大炎上した。

Aはよい。Bは適当に書いて合わせる。Cはsum Mにも制約がついていると思ってO(TM)で解いたらTLEした。行列累乗でO(T log M)でもまたTLE。結局行列累乗したものを前計算することで解いたが、850msとギリギリだった。前計算することさえ思いついていればDPっぽく書けたと思うが、行列累乗のコードを流用することばかり考えていた。Dはaの昇順にどこまで辺を張れるか見る。見るのはgcdのセグメント木で二分探索する。

Fはつらい。差分を計算する。swapする2数を $a_1,b_1,a_2,b_2$ とすると、 $a_1\lt a_2 \land a_1\le b_1 \land b_2\le a_2$ というものしか考えなくてよい。 $a$ の昇順にペアを見て、 $a_1,b_1$ の管理にデータ構造を使おう。 $-(a_2-b_2)-(b_1-a_1)+|b_2-a_1|+|b_1-a_2|=2\max(a_1,b_2)-2\min(a_2,b_1)$ なので、まず $a_1$ と $b_2$ の大小で場合分け。

$a_1\le b_2$ の場合は $2b_2-2\min(a_2,b_1)$ になる。セグメント木で $a_1$ に対する $b_1$ の最大値を管理しておけばよい（当然座圧が必要になる）。

$a_1\ge b_2$ の場合は $2a_1-2\min(a_2,b_1)$ になる。この $a_1$ が曲者。 $a_1$ の最小値と $a_1-b_1$ の最小値の両方を見ておく必要があったので、とりあえず $a_1$ の最小値を管理するセグメント木に入れて、 $b_1\lt a_2$ となったものから順に $a_1-b_1$ を管理するセグメント木に移し替えた。 $a$ の昇順に見ているので、これでよい。インデックスに対して値を複数持たせるといけないので、座圧の際は複数の要素を1つのインデックスに割り当てないよう $a$ と $b$ のペアでソートしておく必要がある。

Fを通した時には残り9分しかなかった。Eに適当に2回提出したが合わず、これだ！と思ったコードの提出は数秒間に合わなかった。直後にTLでそのコードも間違っていたことを知る。upsolveしておいた。

午前3時くらいから溜めていた日記を書き始めた。木曜日から4日分！いまここを書いている時点で4時間半経過して、12000文字書いたらしい。