12/07(月)
寝たのが午前5時で、目覚ましで起きたのが午前8時半だった。しかしあまりにも眠すぎる。予定は8時50分からなので、間に20分もあるのは辛い。そこで、8時45分に目覚ましをセットしなおしてもう一度寝た。これの起床も成功し、見事説明会が始まるのと同時にzoomに接続することに成功した。
別に内容に注意を払ったりはせず、音声を流しっぱなしにしてPCKの問題を進めていた。自分が数学のどんなジャンルが好きでどのような研究に興味があるかなどを一切考えたことがない。そもそも1年次の負債を返そうと躍起になった結果再履修と被って取れなかった選択必修はかなり重要だったらしい。このまま4年に進んでも自分の知識不足で炎上し続けるのではないかと薄々思っている。しかし焦燥感とかは一切湧いてこず、ずっと競技プログラミングをしている。
自分の将来に対して深く考えることができない。心の奥底ではまだその必要がないと思ってしまっているためである。自分の将来を考えたところで競プロの実力とは一切関係がない。競プロと関係のないことを考えて落ち込んで身動きできなくなるのは時間の無駄。
チュウニズムには30日連続ログインの称号が存在する。取得したときのツイートを探してきた。高校生の頃の微妙に受験を意識したツイートを今見るのは非常につらい。
俺は受験生💪💪💪 pic.twitter.com/vibz164dw4
— こたつがめ (@kotatsugame_t) 2017年10月8日
この称号はそろそろ配布が終了して取得できなくなるらしい。なんでそうするのかよくわからない。
学食に行って帰って、しばらくパソコンを触っていたが、うっかり布団に寝転んでしまう。非常に強い眠気に襲われて、耐えられないと確信したので、サークルの解説会1時間前に目覚ましをセットして寝た。
午後7時、無事起床。夢を少し覚えていたのでツイートした。
夢：事故で首が切断される。一命を取り留めたが、まだ接着が不安定なので注意して日常生活を送る。
— こたつがめ (@kotatsugame_t) 2020年12月7日
事故の一つの影響として、教室の机の上の棚がなくなってしまった。これは不便なので困っていたところ、学校から同じ部分に「力場」が用意された。
ARC109の解説会まであと1時間だが、発表者が誰もいない。必死に用意したが、AB問題のスライドを作ったところで時間切れ。そのまま発表して、C問題も一応絵を描いて話した。ほんの15分程度で終わってしまい、ほかにすることもないため今週の活動は終わり。この土日はABCがなかったので、来週もARCの解説会になる。また内容がないようにならないよう頑張っていきたい。
昼前からラノベを読んでいた。「天才最弱魔物使いは帰還したい」。タイトルはいかにも量産型なろうといった趣だが、これは2月ほど前にも週記で言及したように、最も好きな作品の書籍化である。
書籍化！？
週記（2020/09/28-2020/10/04） - kotatsugameの日記
1文字1文字舐めるように読んでいく。全面改稿されたものが新しい作品としてなろうに投稿されているが、そこからさらに改稿されたりはしていないようだ。ちょっとした修正が入っているだけ。元の作品から数えて、同じ展開をこれで3度読んだわけだが、やはり毎回面白い。主人公のフィル・ガーデンが元SSS級探求者であることは、以前は物語の途中で明かされることで、カタルシスの一つとなっていた。書籍版では裏表紙のあらすじに堂々と書いてあるので、ちょっとどうだろうと思ってしまいがち。ただ、主人公の実力を途中で明かすことによるカタルシスは、それまでの部分で読者が脱落してしまう可能性も孕んでいるため、書籍となって新規読者を獲得するためにはそういう情報は前もって開示しておいたほうが良いのかもしれない。
イラストがついていてかなり良い。フィル・ガーデンが思ったよりかっこよくて高身長でびっくり。アムは表紙絵なので以前から公開されていた。特にイメージを作って読んではいなかったので、そんなものかと受け入れられる。アリスもそう。アシュリーは絵がない（それはそうか）。エトランジュ・セントラルドールはたぶんイメージ通りだったと思う。
書き下ろし短編はフィルが王都にいるときの話だった。王都のフィルが描かれるのは初めてではないか？最高すぎる。これだけのために10倍はお金を出せる。10冊買ったりはしないんですが……。
https://onlinejudge.u-aizu.ac.jp/solutions/problem/0425/review/5038437/kotatsugame/C++14
左から2回シミュレートする。タイプ1のクエリについては、1回目のシミュレートでt番まで入れ替えを行ったときの左からx番目の番号を覚えておき、2回目のシミュレートでs-1番まで入れ替えを行ったときに先ほど調べた番号がどこに存在するかを答えればよい。タイプ2のクエリについても、sとtを入れ替えて同様のことをすればよい。番号の位置を調べるのは、値からインデックスを検索する配列も同時に持って更新することでできる。以上よりO(N+K+Q)で解ける。これは解説のMo's Algorithmより良いオーダーとなっている。
布団に入ってハーメルンを1作読み終えた。たこノすけのハーメルンおすすめから知った作品だった。
非常に面白かった。東方Projectのオリ主系、好きかもしれない。基本強い能力を持っているので、主人公最強モノが好みな僕にとってはちょうどよい。この作品については、主人公のキャラも好みだった。
午前7時ちょっと前に寝た。
12/08(火)
午後1時半、起きる。布団に入ったままハーメルンを読んだりatgolferをチェックしてコードゴルフをしたりしていた。結局午後6時になって学食の夜の部に行くため起床、シャワーを浴びて原付で学食に向かった。午後5時台は大学前の道路が信じられないくらい混み合うので、できるだけ避けたかったのだ。ちなみに朝もヤバい。1限は0850からだが、その前後はただでさえ多い出勤の車に交じって大学生がわんさか出てきて、自転車が長蛇の列をなす。0830までに大学に着けないならば、逆に9時になってから悠々と向かうべきである。
案の定全然混んでいなかったのでうれしい気分になる。帰りはうっかり手袋を着け忘れたまま原付に乗ってしまった。気づいたときに停まって着ければよかったものを、数分だしいいかと思ってそのまま家に帰ろうとした。走り出して1分でその選択を後悔した。冷たい風に絶えず晒され、特に右手に関してはアクセルを開けるために片時も離せないので信じられないくらい辛い。もう二度と手袋着けずに冬の原付に乗りません。
帰ってしばらくPCKを解いていた。午後9時からサークルでこどふぉのバチャを行った。#602 div.1だ。AbBCdDEが解けた。出ていれば非常に良い順位だったようだ。
C問題は1<=N,M<=1e6、1<=NM<=1e6という制約なので、固定長配列で持つことができない。わざわざvector<vector<> >を書かされて辛い気持ちになった。
D問題はかなり簡単。しかも部分点がついている。dのほうは2数を全部試してよいが、Dでは片方しか試してはいけない制約。細かいことは面倒なので書かないが、aとbを試すのではなくa+bとbを試さないと計算量を削減できなかったようだ。僕は最初からa+bとbを試していたのでdからDはスムーズに考察が進んだ。
E問題はよくわからないと思いながら解いていたら4回も同じケースでWAを食らってしまった。冷静になって、ちゃんと証明したり確かめたりしてから提出すればよかった。適切に操作をすると、問題のサイズをnからn-1に小さくできるので、再帰的に解けばよい。再帰的に解くのだから、下から上がってくる解に条件を適当に設定して、上に渡す解もそれを満たすようにする。具体的には、解がユニークな操作列であることを常に満たすようにする。
F問題はコンテスト中のsolvedが全然増えなかったので、30分残っていたが早々にあきらめてラノベを読んでしまった。点数を見るとそこまで高い値が付いていなかったので、頑張れば解けたのかもしれない。
「公女殿下と家庭教師7」を読んだ。相変わらず非常に癖のある文体だが、話は面白い。かなり中二なので、冷静にならないように一気に読み進める。Web版ではなかった描写がたくさん追加されている。次の巻も楽しみだ。蒼翠グリフォンのイメージとして王獣を頭に思い描いていたのだが、文中でグリフォン同士が「長い首を絡ませた」という描写があってびっくりした。頭の中で王獣の頭がぐにょーんと飛び出してきた。
布団に入って寝る前に少しハーメルンを読もうと思ったら、一瞬で寝落ちした。午前5時から6時の間のはず。
12/09(水)
午後3時、起きる。午後4時になるまで布団でごろごろして、学食の夜の部が始まったのを見計らって自転車で行く。この時間帯は昨日示した午後5時台という混んでいる時間帯の前だが、実際コロナ禍においてどの程度なのかを実地に確認しておきたいと考えた。交通量はそこそこ多かったと思う。
帰ってきてからしばらくAtCoderをしたりYouTubeを見たりしていた。あとブックマークも少し整理した。読み止しのなろう小説が登録されていたが、数年放置したものをいまさら読む気にはなれないだろう。あと順番も少し入れ替えて、ブラウザの上のほうに表示される分はちゃんと現在定期的に使用するものに絞り込んでおいた。
ラノベを読んだ。「精霊幻想記」18巻。不穏な展開が多くて結構つらいが、Web版では重要キャラが死んだりもっと重い展開があったらしいので、僕は書籍版じゃないと耐えられなさそう。
今日も午後9時からサークルでこどふぉのバチャをする。今日は#562 div.1。ABCを解いたあとDに取り組んだが、初めのほうのテストケースで詰まって通せなかった。
C問題はグラフの持ち方に苦労した。要素数が3e5になりうるvectorを171本持つ必要がある。正確には19x19の配列のi<jなる添え字(i,j)番目だけ必要なので、固定長配列を使うのもやりにくそう。
最初は、vectorに必要な箇所のインデックスを詰めておいて、lower_boundでアクセスしようとしていた。これはMLEした。何がMLEしているのかよくわからなかったが、dijkstraを使っていたので、priority_queueに疑いの目を向け（頂点数19なのにそんな重いわけないだろ）、Bellman-Fordに切り替えた。思いっきりTLEした。次に、試しにvectorのサイズを最初から3e5にしておいて、lower_boundで得られる値を後ろからループを回して求めておくことにした。先の実装における最悪ケースと常に同じだけの要素数になるため、変わらずMLEすると考えていたのだが、通った。
後から試してみたところ、どうやらvectorぶんのメモリを先に確保したのがよかったらしい。最初の実装でreserveしておくようにしたら同じメモリ使用量で通った。これから注意しておこう。速度面で改善されるという話は聞いていたが、メモリ使用量も改善されるのか。
D問題は最初の提出で誤りに気付いたは良いものの、その修正の際に紛れ込ませたミスにバチャ終了まで気づけなかった。良かれと思って入れたチェックだったので、あんまり見ておらず、それよりロジックの間違いをずっと探していた。
根の深さがすべて等しくないならば元より問いの条件を満たせないため、弾いておく。子を2つ持つ頂点が存在しない場合、別の処理を行う（後から見返せば、ここは分ける必要がなかった）。それ以外のケースにおいて、子を2つ持つ頂点と根だけに縮約したグラフを考えると、だいたい二分木っぽくなるので、更新があるたびにそこから根まで遡ってもO(log N)になることがわかる。あとは更新ができればよい。
各頂点はa~zそれぞれに対応する値を持つ。親は、それぞれ2つの子が持つ値のmaxを持っている。更新があるたびに毎回親の値と兄弟の値をチェックして、親の値に変動があった場合のみさらに上の更新を行う。
根が子を1つしかもっていない場合、そこだけ処理を分ける必要があった。最初のdfsによる前計算でも処理を分けており、配列に頂点に関する値を保存できていなかった。後からそれを使おうとしてバグっていた。具体的には、木の深さを知りたかったのに初期値0のままになってしまっていた。
PCKを進める。2020年の本選の問題がいくつか残っているので、頑張って解けるだけ解いた。最後の1問を諦めたところで、PCKの過去問1周が完了した。
PCKの過去問1周した。
— こたつがめ (@kotatsugame_t) 2020年12月9日
予選：187/194
本選：245/257
19問はまだ解けていない。
中難易度の問題はどれも結構面白かった。少し考えるだけで解ける問題が好きなだけかもしれない。前半の虚無はあまり言うことがないが、やたら実装が面倒だったりはしなくて、身の程をわきまえた虚無だったのでやっていて苦にはならなかった。その分ボス問は（解けていないものも多いが）異常実装や幾何、データ構造パンチでそこそこ辛かった。
微妙に穴あきなのを何とかしたいと思い、予選を見直したところ、追加で2問解けた。片方は本当に辛かったので以下に書いておく。
https://onlinejudge.u-aizu.ac.jp/status/users/kotatsugame/submissions/1/0284/judge/5044205/C++14
凸多角形と面積に関する問題。解説では三角形を付け加えることによって面積を計算していたので、一点を決めてDPをしても遷移のコストが正で正しく動く。僕は線分とX軸が囲む面積を足し引きすることによって多角形の面積を求めようとしたため、上下で遷移のコストの正負が異なり、正しく動かない。左端と右端の点を決め打って上と下の2回DPする羽目になった。
ただ面積を求めればよいのではなく、復元も求められている。一瞬pair<面積,vector<頂点> >を持ってやろうかとも思ったが、さすがにまずいだろうということで頑張って復元することにした。
最大ケースでTLEが取れない。オーダーをあまり考えていなかったが、TLEするなら間に合っていないのだろうと定数倍高速化に勤しんでいた。上側に関するDPの際には関係する点だけ集めたvectorを作ってそこだけループを回したりなど。しかし後から冷静になって計算量を考えると、どう考えても間に合うはずなので、違和感を持ってもよかった。
30分くらい溶かしてから、書きかけのfor(int st=0;st<N;st++)というループがメインのループの前の行に残っていることに気づいた。すべての計算をN回行っていた。その行を削除すると爆速で通るようになった。
ああ 少年の僕らよ
— こたつがめ (@kotatsugame_t) 2020年12月9日
心の中に 戸惑いがあるなら
きっとそれ自体が きっとこの世界で
一番綺麗で 眩しい想いだろう pic.twitter.com/ElckoWOkPK
朝方、急に#define int long longに対する憎しみが湧き出してきたのでいくつかツイートをした。午前10時就寝。
12/10(木)
午後5時、起きる。午後6時半くらいまでゴロゴロして、学食に向かった。夜も深まると学食には弁当と揚げ物しか残っていない。野菜がないと健康に悪いことはわかっているが、腹が減っているので揚げ物だけでも食べるしかない。原付で往復したが、ちゃんと手袋をつけていたため手は守られた。足は相変わらず裸足にクロックスで、冷たさが際立った。
帰ってきてからYouTubeを少し見た後ラノベを読んでいた。「いずれ最強へと至る道」3巻。1巻と2巻を9ヶ月くらい前に一気に読んだっきりだったので、キャラの名前も設定もほとんど忘れてしまっていた。帯に「122ページにわたるバトルシーンを刮目せよ」とある（これ「バトルシーンに」のほうが自然に感じるんだけどどうなんだろう）。実際本の後ろ半分はバトルシーンだったのだが、それを煽り文句にするのはちょっと謎。
チートを得ていろいろやるというシンプルな話で、結構好きかもしれない。ただエピローグが完全に打ち切りといった感じだったので、続きが本になることはなさそうに見える。ちょっと気になるのでなろうのほうを確認し、学園編を見つけたので途中から読んでみることにしたら、時間が一気に溶けていってしまった。どうやら書籍化するにあたって結構ストーリーが変わっているらしい。
ところで一般に学園編は好き。学園という閉鎖的な環境だと目立ったり有名になったりなどの設定が簡単に付与されやすいからではないだろうか。
日付が変わったので、yukicoderアドベントカレンダーコンテストの12/11の問題を解いた。非常に苦労した。この日記が公開される頃には解説も出ているだろうから書くと、問題文ではNを言ったら負けなのに頭の中ではNを言ったら勝ちになってしまっていた。それで結構WAを重ねてしまった。
日付が変わる前後はAtCoderをやっていた。bashのAC数を稼ぐべく簡単な問題をずっと探し回っていた。もはや日課。
ArCoderをしたりなろうを読んだりしているともう朝になってしまった。昨日サボってしまった分も含めて日記を書く。今日の文量が全然ないが、特にコンテストがあったわけでも難問にチャレンジしたわけでもない日なのでどうしようもない。書くことがないなら無理に書く必要はないなという結論に達した。
布団に入ってから、水曜日のvectorのメモリ使用量についてAzさんから助言があった。push_backによる再確保の際、以前のメモリ空間と以降のメモリ空間を両方持つ瞬間があって見かけ上のメモリ使用量が増えていたのではないかという話だそうだ。
測定方法によりますが、malloc/free の実装の都合上、reserve しない時は見かけ上のメモリ使用量は増えうると思います (当然ですが実際にその場で使っているメモリ量が増えるわけでは無いです)
— Az (@azaika_) 2020年12月10日
午前5時半に送ったリプライを最後に、就寝ツイートをせず寝落ちしたらしい。
12/11(金)
午後3時、起きる。午前10時頃一瞬起きて金曜日の講義から課題が出ていないか調べたことを覚えている。今週はなかったので、安心して二度寝した。
夢を見た。場面場面だけは覚えていて、その間をつなぐストーリーはほとんど忘れてしまっていたが、ツイートするにあたってそれでは困るので、多少肉付けをした。しかしなお脈絡のない怪文書になってしまったようだ。
近くに駅員がいるが、やむを得ずそこを透過して出て行くことにする。透過の成功確率はあまり高くないが、なんとか4枚連続していた窓ガラスを通り抜けることができた。しかし、このときに窓ガラスに手をついて指紋を残してしまい、後に逮捕されるという直感を得る。
— こたつがめ (@kotatsugame_t) 2020年12月11日
夢の中で空を飛ぶのは自分にとって結構ある話だ。中学生のころに2chかどこかで、明晰夢を見たり自分の都合の良い夢を見たりする方法を調べて試していたことがある。ほとんどはうまくいかなかったが、自分が飛べる夢を見ることは数度あったと思う。飛ぶときの操作も共通していて、自分が浮き上がるイメージを強く念じると飛べる。SAOの心意システムに影響されていると思う。本家キリト君は上着を翼に変えて飛行しているが（19巻あたりの機竜お披露目会の話）、特に翼を装着したりはしない。
やることがないのでTwitterアナリスティクスを見ていた。ここ3か月くらい月当たりのツイート数が倍近くまで増えているようだ。自分としてはそんなツイート頻度が変わった感覚はないが、まあツイートしないまでもTweetDeckは常に目の届くところに開いているので、無意識にツイート数が増えていても不思議ではないか。僕のアカウントのインプレッション数はこんな感じになる。
記録して後から見返すと面白いんじゃないかと思ったけど、月ごとの記録はさかのぼって見られるからなあ……。
今日はこどふぉdiv.2がある。適当に出た。5完。
A、B、Cは記憶がない。Dは変数名を間違えたままサンプルが通ってしまい、REとかWAではなくMLEを出してしまった。メモリ使用量はつい最近も少しやられたので敏感になっており、罪のないコードを一所懸命にデバッグしていた。処理を書き換えるときにコピペを多用してしまい、変数名間違いが引き継がれたままさらに1ペナ生やしてようやく気付けた。
Eは嫌な感じだ。解けてからも実装で手が止まってしまった。[l,l+x)に入るまで操作を繰り返すときに日数が尽きてしまうとどうしよう、と思って、うまく統一的に処理できないか考えていた。結局諦めて条件をベタベタ書いて済ませた。
Fは解けなかった。2 1 2 1 2 1 2は2以上の数をペアで考えていると2+1+2+1+2+1+2になってしまう。全体の積を一気に見ると3 3 1 1 1 1 1 1 1 1 2が3*3*1*1*1*1*1*1*1*1*2になってしまう。このうち、全体の積を見るときの条件付けが違ったらしい。僕は総和<=総積のとき積にしてよいと考えて、先に挙げた後者のケースにやられたけど、実際は2*(区間長)<=総積が正しい条件らしい。次のように証明できる：
区間に0を含まず、両端が2以上であるとする。区間長をL、総積をMとする。どこかに+を入れることを考えると、左右の積はaとbに分かれる。a,b>=2かつab=Mである。この元で、最大の和を評価する。理想的な状況を考えると、積は1つにまとまって、残りの1がそれぞれ（積に飲み込まれず）別途に足せるのが良い。1の個数は両端が2以上であることを考えると最大でL-2個なので、和の最大値はa+b+L-2=a+M/a+L-2以下となる。これはa=2の時に最大値2+M/2+L-2=M/2+Lをとる。M>=M/2+Lであればよいので、M>=2L、もとい2*(区間長)<=総積が得られる。
あとは2L>Mの処理だが、これは連続する1と2以上をまとめた後2以上の場所の間に関してbitDPすればよいらしい。この計算量解析はRubikunさんが行っていた。サイズは最大でもlog_2 Mとなり、2^log_2 M<2^log_2(2L)=2LなのでO(L)である。僕の実装では1と2以上の間もbitDPしているので、O(L^2)になりそうなのだが、この時は気づかず出して通った。
「私立シードゥス学院」という本を読んだ。全寮制の学校で起こる事件を描いたキャラミスだ。細かいところがよく読めてなかったのか、腑に落ちない描写がいくつかあって難しい印象を受けた。
午前8時半、就寝。
12/12(土)
午後1時、いったん目覚ましで起きる。とりあえずHTTF本選のオープンに登録して1B解を提出し、午後2時のOUPCまでいくらか時間があるので再度寝た。午後1時半にも目覚ましを設定していたのだが、見事に聞き逃してしまい、午後2時になってようやく起床。OUPCが始まってしまっていた。
あまりに眠いためしばらく布団でボーっとしていたが、OUPCは3時間しかないので起きる。途中生協から弁当が届いたので受け取り、1つ温めて食べた。
結果はABCDEFGの7完最速で3位。あんまり変なことを考えずに前から解いていった結果、後ろから解いてペナが爆発した人に差がついた。逆に僕より速く7完した人はみんな（2人）I問題を通して上に行ってしまった。
A、B、Cに関しては特に言うことなし。Dはちょっとややこしいし証明もゴツそうだったが、適当に書いたら通ってしまったので深く考えなかった。Eは2進Trie。そのあとFとGを読んでGに行った。適当に場合分けをしていくと二部マッチングに落ちる。復元が面倒。
Fは非常に面白かった。頂点ごとに出る辺をコストでソートして、左端からどこまで使ったかと右端からどこまで使ったかを持つ。最短距離を配列に入れる必要がないのが面白かった。各辺を使うのが左から来て1回と右から来て1回なので、そこで計算量が落ちる。
I問題は可能な(x,y)の点集合がある凸多角形の内部になるようなので、ピックの定理で格子点の数を求めるらしい。ありうる値のペアが凸多角形をなす問題はどこかで見聞きしたことがあるはずだが、実際に解いたことはなかった。また出たらたまらないのでupsolveした。
PCKを2問解いた。1問はよくわからない問題で、綺麗に解けそうにない見た目をしていたためゴリ押しで解くことにした。よくわからない高速化をしたら通って、解説を読んだところ、bool値のDPをbit並列で高速化する問題だったらしい。そう……。
もう1問は以前チャレンジした際に誤読していたことが発覚した。そこさえわかってしまえばあとは自明、と思っていたが、実装をサボってO(3^(2K))を書いたらTLEした。集合とその部分集合を列挙するのにO(3^N)でいいところをO(4^N)かけるやつの3進数バージョンだ。3進数である必要、ある？ループではうまく書けないので再帰関数を用意したら通った。
SRMがあったので出た。EasyとMedの2完で16位。2222→2306と+84した。Easyはなんかできると信じたらできた。Medは次の問題でほとんど既出のようなものだったが、蓋を開けてみると-iした後ソートしなおさない人が大量にいて大量に落ちていた。
Hardはよくわからなかった。ICPCだと信じて適当な解を書いたら落とされた。解説を読んでいないが、TLで見聞きした話によるとかなり天才らしい。ICPCじゃなかったのか……。
途中で本を1冊読んだ。創元推理文庫「タルト・タタンの夢」
週記（2020/07/20-2020/07/26） - kotatsugameの日記
朝、1冊本を読んだ。創元推理文庫「ヴァン・ショーをあなたに」
週記（2020/10/26-2020/11/01） - kotatsugameの日記
シリーズ3作目。このシリーズはどれもかなり面白かった。ほろ苦いタイプの日常の謎はたまに読むと効く。
眠れなかったので、少しだけ本を読もうと思って「〔少女庭国〕」を手に取ったら、最後まで一気読みしてしまった。ふろん氏からお薦めされて、あらすじに惹かれて購入したのだが、この本をあらすじで買ったのは完全に間違いだった。まさかこんな本だとは……。面白いことは面白かったが、何と言ったらいいかわからない本だった。何と言ったらいいかわからないので、内容については何も書かない。
午前9時、就寝。
12/13(日)
午後5時起床。夢うつつでABC遅刻すると思い込んでしまい、起き抜けは非常に焦っていたが、時計を見て落ち着いた。
ABCまで結構時間があるので、明日の朝期限のレポートに取り組むことにした。コンピュータグラフィックスという講義の3回目のレポートで、これまでは座標変換の行列を書く問題だったのが、ついに実際にCGを作成する課題になった。使用するソフトはPOV-Ray。公式のエディタが嫌な挙動（何もないところをクリックしてもそこにカーソルが移動する）をしてそこそこ使いにくいと感じたが、オプションをググっていじるほどやる気はない。
やるだけなら簡単なんだけど、基本立体6個で作成可能って書いてあったから6個でやろうとしたら初手が違って微妙に苦労した pic.twitter.com/H8U7ocI9g3
— こたつがめ (@kotatsugame_t) 2020年12月13日
黄色の立方体から「赤い球引く球」「緑の球引く球」「青い球」をそれぞれ引くと、6個の立体で構成できる。カメラ位置や立体の大きさなどは違っていてもよいとされていたが、せっかくなので手本をガン見してできるだけ合わせた。
今日はABC185。A問題で2分、C問題で7分くらいコードゴルフしていたが、DEFが全部2分くらいでACできたのでタイムは21分だった。残り時間はコードゴルフをして、終了時点ではABCDFの最短だったが、Eに取り組んでいる間にBを取られてしまっていた。
消化不良なのでTOKI Regular Open Contest #17に出る。うっかりoj-bundleで展開する前のコードを提出しCEを出したのだが、これはペナルティになるらしい。ちょっとびっくり。
結果は1時間と少しで全完、全体3位だった。レートは2249→2439と+190した。多分次出たら赤だろう。このコンテストサイトでは赤は2500から。
少し誤読もあったが、Eまではおおむね問題なく進んでいき、Fでしばらく詰まっていた。この間にtouristが一気に全問正解してトップに立ち、すごいなあと言っていた。
Fはx日目に使用したらx+D日目に回復する、というのをマスク使用量の+1/-1で考えることにすると、左からの累積和をセグ木で持つことを思いつく。更新は右端までのrange add2回で（書いていて気付いたが、どう見ても1回でよい）、取得は左端からのrange maxがkより大きくなる点を求めればよいが、これは二分探索でできる。ACLを使用するとlogが1つになるので、ドキュメントを見ながら書いた。あまり慣れていないが、かといって自前のセグ木を持ち出してlogを2つつけるのは少し怖い。
Gもrange addとrange maxのセグ木だったが、今度は自前のセグ木を持ち出して解いてしまった。後から思い返せば、コードを使いまわすと実装量が減ったのにと少し後悔。これはFより簡単に感じた。
H問題はSum a_{i+r}*b_iをどうやって求めるかしばらく考えていたのだが、どう見てもNTT。気づくのがかなり遅かった。入力も実装もそこそこややこしくて頭が爆発してしまい、うっかり2^T回畳み込みを計算したのでTLEギリギリだったが、その後冷静になると畳み込みはT回でよいことに気づいた。システムテスト形式なら迷わずリサブだが、このコンテストはフルフィードバックなのでそのままにしておく。もし提出しなおしてそちらがペナルティに加算されたらたまったものではないため、触らないのが吉。
一時は上位10人中8人が日本人だったが、最終的には6人だった。侵略する側としては面白く見ていられるが、実際インドネシアの人たちはどういう気持ちなんだろう。
ラノベを1冊読んだ。
ABCのF問題の最短が更新されている。言語をRubyからPerlに変えると縮んだようだが、実行時間がギリギリであるので、少し変えて提出してもすぐTLEしてしまう。しばらくバトって、2時間ほどおいてまたバトっていた。この日記を書いている時点ではブレイクスルーがあって相手より-8Bしたものが最短となっているが、このあとどうなるかはわからない。
PCKを1問解いた。弱めのSingle Dotなので実装をコピペしようと拾いに行ったが、かなりややこしいので諦めて1から書き直した。
https://onlinejudge.u-aizu.ac.jp/solutions/problem/0292/review/5056511/kotatsugame/C++14
以前見たときは、中途半端な壁がないかわりに壁が座標軸に平行でない問題を解いた直後だったので、それと同様幾何のつもりで考えて面倒になって諦めたのだが、改めて見直すと幾何要素はどこにもなかった。
