08/09(月)

先週日曜日の寝るまでの話。週記を投稿してから、再度院試の過去問に挑戦していた。問題が解けると楽しいので、今はかなり過去問演習のモチベがある。これも院試ゼミのおかげだ。1・2年の頃の知識をみんなで復習することで、着実に解けるようになっている。もしくは最近数学をしなさすぎていたのがさび落としされてきたのかもしれない。

と言っておいて先に手を付けた問題は結局解けなかったが、もう1問数学基礎論の問題を読んで、そちらは解けた。超限帰納法を使った。初対面だ。名前だけは聞いていたが、この度ようやくステートメントを調べた。

布団に移動してしばらくスマホと戯れ、午前11時就寝。

院試ゼミは午後3時からなので、その時間と30分前とに目覚ましをかけていたが、どちらも寝過ごしてしまった。思ったより疲れがたまっていたのだろう。午後3時ちょっと過ぎ、LINE通話がかかってきて、それで起きた。他にもLINEやSlackでメッセージが来ており、みんなありがとう……という気持ちになった。急いでZoomにつなぐ。

今回も有意義だった。多様体については曖昧な理解しか持ち合わせていないが、自分の持っている感触を他の人に伝えてみることで、自分の中でも整理されるし、もし間違いがあれば指摘される機会も得られる。全員間違っていたらみんなで落ちるしかない。また、昨日の朝方解けなかった問題は微分方程式に関する話だったが、アスコリ＝アルツェラの定理を用いるようで、かなり懐かしい気持ちになった。もはやステートメントどころかその周辺の言葉の定義も忘れ去ってしまっていた。数年に1度しか出ない分野のようだが、今やっておいて損はなかっただろう。

担当する問題以外にも発表し、その関係で話が弾んで、院試ゼミが終了したのは午後6時半だった。選択問題にも太刀打ちできるようになってきたことで、だんだん自信がついてきた。あと10日、精一杯頑張っていきたい。

そのあと夜までコードゴルフをしていた。一気に何個か取られてしまったので、いくつかを無理やり取り返した。dcをbashから呼び出すコードのはずが、Vimから呼び出したほうが1B短くなるような問題もあり、自分でもそこまでするか……という気持ちになった。この辺りは複数の言語が入り乱れており、縮めていてかなり辟易している。しかし1Bでも短くなるのならそれが絶対的な正義である。

Submission #24916483 - AtCoder Beginner Contest 210

次回の院試ゼミで担当することになった問題を解いた。また数学基礎論。見た目はゴツいが、手を動かしたらあっさり解けた。全能感が湧いてきたが、これまで見た過去問で解けない数学基礎論の問題というのはやはり存在するので、本番ではちゃんと問題の難易度を推し量る必要がある。

いつだかの問題文1行コンテストはまだupsolveし切れていなかったので、2問ほど解いておいた。

No.1619 Coccinellidae - yukicoder

かなり嫌な気持ちになっていたが、実装してみると案外楽だった。数列の総和に関しては最大の要素に適当に足しておけば達成できるので、転倒数のみ気を付ければよい。 $0\dots N-1$ を用意して、数列の先頭から構築していくのだが、このとき「使っていない要素のうち最大・最小のもの」しか考えなくてよい。こうすると、 $0\le i\lt N$ 番目に未使用かつ最大の要素を入れると転倒数を $N-i-1$ 増やすことができ、最小の要素を入れると変わらないことが言えるので、達成可能な任意の転倒数が先頭からの貪欲で構成できることがわかる。

No.1620 Substring Sum - yukicoder

自明。

やることがないなあと思いながらTLを見たら、どうやらコンテスト直前らしい。CF #737 div.2を完全に忘れていた。仕方ないのでextra registration。

Dashboard - Codeforces Round #737 (Div. 2) - Codeforces

全完12位。Eをあきらめなかったのが偉い。

Aからよくわからない。なんとなく、正の数があるならその中で最大の要素を1つ独立させるとよさそうな気はする。ここでサンプルを見ると、負の数しかなくても最大の要素を1つ独立させているので、これが答えだろうと思って実装した。落ちたらその時はその時だと思って投げた。Bは、もともと連続している部分を壊さないように分割したらいくつになるかを考える。

Cは上の桁から決める。今見ている桁より上の桁で大小関係が決定しない決め方 $t$ を持っておいて、今見ている桁でbitwise andが1になる場合と0になる場合を考える。 $n$ が偶数のときは、bitwise andが1になるときbitwise xorは0になるため、大小関係が決定する。bitwise xorが0になる場合はほかに $2^{n-1}-1$ 通りあり、それらはこの桁で大小関係が決定しないため、次に回す（ $t$ にかける）。 $n$ が奇数の時は、大小関係は決定できず、次の桁に $2^{n-1}+1$ 通り回すことになる。あとは、すでに決まった数列の新しい桁のために答えに $2^n$ 通りかけたりもしておく必要がある。ちょっとややこしいが、サンプルを合わせて投げたらすんなり通った。

Dは遅延セグメント木。適当に書いてからサンプルを試していたら、復元が要求されていてびっくりした。その時書いていたことも全然違っていたので、修正にかなり手間取った。遅延セグメント木には、残せる行数とそれを達成するときの一番下の行を保存する。各行ごと、その行とそれ以前で残せる最大の行数を遅延セグメント木で計算し、直前にくる行を保存して、今の行と残せる行数を組にして遅延セグメント木を区間更新する。復元は保存しておいた行番号をたどる。遅延セグメント木は区間chmaxしているように見えるが、実のところ対象となるノードすべてより大きな値で更新しているので、区間更新で書ける。

Eは全然わからず、考えていたら途中椅子の上で意識を飛ばしていた。キングがいる可能性のあるマスは、減ることはあっても増えることはない。よって、確実に減らしていくことを考える。クイーンから縦横1マスずつ離れたマスにキングを捉えたときに減らせる可能性があるようだ。逃げる方向は限られるため、それを追って壁際まで行くことで可能性が消せる。標的にするマスを選んで消えるまで追い続けるのを繰り返したら通った。

またしばらくコードゴルフをした後、人の日記を読んだり、書いたりした。

朝方布団に移動して、読み止しのラノベの続きを少し読む。少し読むつもりだったがあまりに面白かったため、そのまま読了してしまった。「サイレント・ウィッチ」。Web版で一度完結まで読んだが、書籍化したので購入したもの。書籍もかなり売れているようで、手に入れたのが遅かったこともあり、すでに第2版であった。

非常に面白かった。オチまで全部知った状態で改めて読み返すと、いろいろと発見（書籍化に際しての加筆かもしれないが）があってよかった。細々とした描写が小気味よく、ちょっと笑える感じで書かれているのも好み。つまりは文章が好きであるということ。あとがきにも書かれていたことだが、なろうでは200話以上かけて一つながりの物語となっていたわけで、その最初の数十話（調べたら30話未満）を取り出して1冊の本に仕立て上げるというのはかなり難題のように見える。しかし加筆修正によってちゃんとラストの盛り上がりも含めまとまっていて、感動した。改めてWeb版を読んでみると結構大胆な修正があったようだが、まあ細かい流れは大体忘れてしまっているので特に違和感はなかった。

本を読んでいたら今日もまた昼前になってしまった。明日は院試がオンラインになった場合に備えて接続テストが行われるので、午後2時には起きている必要があるらしい。徹夜することもちょっと考えたが、結構眠気があるので急いで寝ることにした。午前9時半だった。

08/10(火)

午後2時過ぎに起床。目覚ましが鳴ってからも少し眠っていたらしく、焦る。まずメールで連絡が来るらしいので、スマホでチェックしたところ、どうやら接続テストは指定された時間帯にZoomに接続してメールを1本送信するだけの形式らしかった。拍子抜け。

しかして午後4時までにメールを送信する必要がある。眠気をぐっとこらえて一旦パソコンに向かい、パパッと所定の操作を済ませ、またすぐ布団に戻った。ちょっとスマホを触ってから再度就寝、次に起きたのは午後8時だった。

まだ微妙に眠気があって何もする気が起きない。布団に倒れたままスマホを弄っていたが、空腹により起床。食事してパソコンに向かい、また動画など見てしまうが、さすがに思い直して院試の過去問を少しばかり解いた。

それなりに問題を解けるようになってはいるが、実をいうと手が出ない問題と半々くらい。幸いにして8問中3問選択して解く形式なので何とかなりそうではあるが、難易度がバラバラでちゃんと分野を選定する必要があり、最悪の場合は……最悪の状態になってしまう可能性を否定できない。問題文に登場する単語の定義もところどころ危ない。今日は2問くらい解いた。

昨日のCF div.2 Aの証明を解説を見て確認したが、やはり難しい。数列を2つの（連続するとは限らない）部分列に分割したとき、それぞれの平均の和を最大化せよという問題で、解法は上でも述べたように、最大の要素を1つだけ独立させることになる。解説の方針を真似る感じで自分なりに証明をつけてみた。

まず、分割する要素数を固定したときを考える。この時、要素に適当に係数を割り振って足し合わせると言い換えることができて、ソートして先頭と末尾で分割するのが最も良いとわかる。次に、値が小さい方の数列から大きい数列に要素を移動させても損しかしないことを示す。この操作で2つの数列の平均値がどちらも小さくなる（または変わらない）ことが言えて、具体的には値が小さいほうの数列は平均値「以上」の要素が抜けるのだから当然平均値は小さくなり、大きいほうの数列は逆に平均値「以下」の要素が加わって小さくなる。この2つをまとめて、解法の正当性がわかった。

今日も本を読む。「幼女戦記」8巻。記録によれば7巻を読んだのが2020年1月で、そのとき8巻を100ページ弱読みかけていた。栞にしていた紙が挟んであったので、今日はそこから読み始める。結構衝撃的な展開の箇所だったので、何とかそのシーンのことは覚えていた。

午前1時から読み始めて、読み終わったのが午前7時。1ページ1分ちょっとという計算になる。出現する語彙に馴染みのないものが多く、かなり読むのに疲れた。そもそも意味を知らない語彙もあり、調べる手間もあった。内容も、作者が軍隊行動に関する話を入念に描きたがっている感じがして、安直にチート戦闘を求めていると息切れしてしまう。実際これまで何度も息切れした結果が、読み止しにしたまま1年以上放置するというこの有様に繋がっているわけだ。それでも定期的に読みたくなるのだから、間違いなく面白さはある。多分、アニメを観る習慣のある人はアニメで観たほうがいいのだろう。

第7回PASTの解き残しを埋めた。KLNOが残っていた。最終問題に近いのでどれも大変だと思っていたものの、個人的には前にコードゴルフのために解いておいたM問題が最も難しかった。

第七回アルゴリズム実技検定 - AtCoder

Kはいつもの。Lは何をやってもできる気がする。僕は最小値をセグメント木で、値に対するインデックス集合をmap<int,set<int>>で持った。公式解説の方法は頭が良い。NはABC211Fで見た。Oは区間chminになるようだったのでbeatsを探しそうになったが、冷静になってもうちょっと考えると必要なかった。セグメント木上を左から右へ走査しつつ、今見ている要素から右にいくらかの範囲に対しchminし、取得は単一の要素のみとなるため、優先度付きキューで書ける。

布団に移動してからしばらく、本棚から久しぶりに掘り返したラノベを読む。積読本を綺麗に詰めすぎたため、表紙が見えず本棚のどこに何があるかわからない。今日取り出すときも難しかった。目的の本の列のすぐ上に別の本をもう1列乗せていたため、抜き出した穴をそのままにするわけにもいかず、別の本を見繕って当てはめる作業も発生した。

適当なところで切り上げて寝ようとしたが、眠れず、延々スマホを触り続けていた。途中頭皮のかゆみが気になりシャワーを浴びたりもして、午後2時くらいに寝落ちした。

08/11(水)

午後8時半起床。またラノベを読み続ける。日付が変わるあたりで読了。

「異世界管理人・久藤幸太郎」。設定とストーリーが面白かった。扉を開けると異世界につながるアパートが存在し、主人公は1部屋1国家が入居するそこの管理人、つまり国家間の問題を解決する役割を担っている。そのために特別に与えられた権能や持ち前の特技を生かして活躍する、という話。主人公がかなり有能らしく、読んでいて心地よかった。一方ヒロインはある国家のお姫様だが、悪意を知らない底抜けのお人好しで、能力的には外交を担えるものではないとされている。結局このお人好しという設定もストーリーに絡んでくるのだが、それ以外で考えなしに勝手なことをしたり、人を疑うことを知らなかったりという描写が読んでいてちょっと気に障った。

少しコードゴルフをした後、AOJ-ICPCから1問解いた。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5774311#1

よくわからないが、たぶん3つの要素それぞれについて考えてもよいだろう。期待値の線形性というやつらしいが、特に意識せず勝手に分割した。自分がアピールする回数を決め打ったとき、ある人が自分以上のポイントを獲得する確率が計算できる。適切な前計算をしておけばよいが、値が大きくなるのでlong doubleが必要らしい。とにかく、それを全員分集めて、自分が3位以上・または最下位である場合の確率を求めることができる。あとは特に工夫せず、アピール回数の割り振りを全探索できる。

別の問題を考えていたら椅子の上で意識を飛ばしてしまったので、すぐ布団に移動。今日は早めに寝られそうだとホクホクしていたものの、なんとなくスマホを触ってしまい全然眠れない。仕方なくいったん寝るのを諦め、ラノベを読んでしばらく過ごすことにした。午前8時くらい、さすがに寝なければまずいという気持ちになったので、頑張って就寝。

08/12(木)

午後2時起床。非常に眠い。今日は午後3時から院試ゼミで、それまでにお盆休み前最後の大学生協に行きたいと思っていた。今日は雨が降りそうなので徒歩で大学に向かうが、シャワーを浴びていたら結構ギリギリの時間になった。

購買しか開いていないが、そこで買い物をする。これから数日休みということで、菓子パンが20%オフになっていて喜ばしかった。コンビニにも寄って帰宅。結局院試ゼミには少し遅れてしまった。

午後7時前までゼミ。今回もいい感じ。解答を3問分くらい用意してあって、2つを発表し、1つは他の人の発表を聞いてところどころ自分の方針を喋ったりしていた。本番で選択する分野も大体見当はついたかな、という感じ。ちょっと古い過去問のほうを見ると、それでも手も足も出ない問題が散見され、自分の狙っている分野に難しい問題が出題されたらまずいな……と思うものの、ここ5年分の問題に限ればそれなりに健闘できそうなので、院試が易化しているのではないかと思っている。

このゼミも残り2回の予定らしい。両方の日程と内容を決め、解散。すでに午後7時だが、せっかくシャワーを浴びて着替えてあるので、遊びに行くことにした。霧雨が降っているので、地下鉄に乗って仙台駅まで出た。本屋で本を買い、つけ麺屋でつけ麺を食べ、ゲーセンに到着。

今日の成果は微妙だが、新曲の13でAJが出たのはよかった。曲が良い。譜面動画を見ながらエアプしている段階では、序盤、なぜかうまく腕が動かせなかったが、実際にプレイするとそこそこゴリ押せた。逆に「アポカリプスに反逆の焔を焚べろ」は全然ダメ。譜面動画や人の手元動画を見ていたのより、自分でプレイしてみると100倍速かった。何をどうしたら間に合うのかわからない。ただの鍵盤としても普通に難しいのに、超高速にされるともう手も足も出なかった。

Good bye, Merry-Go-Round. AJ pic.twitter.com/xrz1xuGKH2
— こたつがめ (@kotatsugame_t) 2021年8月12日

閉店までいて、帰宅。なんとなく地下鉄を使わずに歩いて帰ることにした。帰宅してシャワーを浴び、AOJ-ICPCから1問解いた。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5778119#1

面白い。bit演算・値を大きくするゲーム・木など、いかにも上位桁から分解してくださいねという形をしているのに、実はそうではない。考慮すべき値が8種類しかないことを利用して、それらの間の大小関係を全探索してそれぞれ前計算し、先に計算した結果を参照してクエリに答える。最近取り組んだ問題の中では一番、解法を思いついたときに爽快感があった。

ラノベを1冊読んだ。「異世界管理人・久藤幸太郎」2巻。前巻と似たような感想だが、今巻は敵役がかなりあくどい感じで、その分ラストシーンは爽快だった。シリーズはこの巻で打ち切りのようだが、それにしてはかなり面白かったと思う。ラストシーンでおめおめと逃げおおせたキャラがいるのも、後の伏線になるはずだったのに……と悲しい気分になった。

AOJ-ICPCからまた1問解いた。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2690

簡単。各頂点から一番遠い頂点にデータを送信して、次にそのキャッシュが残っている状態で一番遠い頂点にデータを送信して……ということをやりたい。このとき、一番遠い頂点を求めるdfsの最中に候補から抜け落ちた頂点については、抜け落ちた時点でのパスの長さが後々のキャッシュも含めた最短距離となるので、それを保存しておけばよい。これを各頂点から行って、最後に全部まとめてソートして貪欲。

布団に入ってしばらくラノベを読み、午前11時に就寝。

08/13(金)

午後7時半起床。今日は何もないのでのんびり起きた。最近予定が多く、そのくせ朝方まで起きているのが常になってしまい、睡眠が足りない。

起きたら部屋がかなり寒く、薄いブランケットに必死にくるまっていた。夜寝る前、この天気だとエアコンは必要ないなと思って消し、念のための暑さ対策に部屋とキッチンを隔てる戸を開いて寝たが、これがよくなかったらしい。キッチンのほうから冷気が部屋に入ってきたのはいいが、今はむしろ寒い。

食事をしてyukicoderのコンテストに出た。滑り込み全完。

yukicoder contest 309 - yukicoder

ABCはよい。Dはありうる和とそれに対する場合の数をdpで計算すればよい。Eは後ろ2文字を持つdp。'?'の場合の遷移については総和を取り、適切に引くことで26²回の演算で計算できる。Fは各行各列に対応する超頂点を作り、辺を張った上で閉路を探したら通った。僕は観光名所も頂点として持ったが、超頂点同士を直接結ぶ辺だと思ったほうが解法の正当性がわかりやすい。

solvedが多いのでHに行った。適当に分解すると、x座標とy座標が両方絡む項が問題になる。自分の左下または右上にある点に対しては大小関係が定まるので簡単に求まるが、ここですべての点のy座標を符号反転することを考えると、もう一度同様の計算を繰り返すことで全点対に対して計算できることがわかる。y座標が同じだと2回計算されるが、値が0になるため問題なし。

Gに挑戦する。まず $B=0$ の場合は $A^N=P$ かつ $A^{N-1}=Q$ となるため、BSGSで求まる。それ以外の場合が問題だが、制約より答えが10¹⁰以下であることがわかるので、こちらもBSGSと同様のことができそうだ。modintには大小比較が定義されないのでいちいちint型に戻し、それの2つ組をテーブルに持ったり掛ける数を行列に直したりしつつBSGSのコードを写す。最後答えを合わせるのに手間取ったが、定数を足してサンプル1を無理やり合わせて提出したら全ケース通ってびっくりした。後でちゃんと計算したところ、答えより2小さい値が出るはずが思い違いで出た値から2を引いていたということをちゃんと確認できた。

Gは非常に面白かったが、「10¹⁰以下に答えが必ず存在する」というような謎の制約が必須になってしまうところが難点か。例えば法を取る素数を100003とかにすると、2つ組にしても周期の最大値が10¹⁰ちょっとになるので、同様のことができるかもしれない。これくらいの制約だとdpもできない中、BSGSが使えるというのはかなり目新しく感じた。

ラノベを1冊読んだ。「前世は剣帝。今生クズ王子」。面白くなかった。クズ王子と呼ばれる王子が、実は前世では最強の剣士だった……という設定に惹かれて買った。実力を隠す系の話だと思ったのだ。読んでみると、主人公がグータラしているのは、前世での苦い経験からそれが一番幸福だと信じていたかららしい。それならそれでよくて、最強たる実力を遺憾なく発揮しているシーンもあったのだが、合間合間で執拗なまでに主人公の自分語りが入って、冷めた目で見てしまった。

「慫慂」という語彙が話題になっていた。鉄道関連ではよく使われる言葉、というツイートも目にしたような気がするが、調べた感じそれほど用例が多いわけでもなさそう。自分にとっては記憶に新しい語彙だ。なんとなれば、火曜日に読んだ幼女戦記8巻で出てきたからだ。履歴からどの時間にGoogle検索で単語を調べたか割り出し、その周辺で調べた単語が出現したシーンを探して具体的なページを見つけた。

佐賀駅でご旅行の中止を慫慂されました。 pic.twitter.com/wySsSgX1pv
— 🦜かささぎ号（ハンズマン） (@hansman_neo) 2021年8月13日

「慫慂」幼女戦記8巻229ページ4行目 pic.twitter.com/Ae0HjR8NU2
— こたつがめ (@kotatsugame_t) 2021年8月13日

C++の演算子優先順位は?:（三項演算子）が代入演算子より上だと思っていたのだが、それはC言語における話で、C++では同じらしい。自分がこれまで見ていた資料が違っていることを知った。コードゴルフに使えるかと思ったが、パッと探した限りはなさそう。

もう1冊ラノベを読んだ。「鳩子さんとラブコメ」。主人公が財閥の跡継ぎ候補という設定に惹かれていたが、読んでみるとタイトルに偽りなく、主にラブコメだった。9年以上前のラノベで、今では全然見ないような、主人公が語り手の立場でひたすら一人語りしている文体が逆に目新しい。シリーズは4巻まであるので、とりあえず読みはするが、興味はかなり薄れている。

ABC210-Fを人に説明する機会があった。グラフの圧縮については公式解説を読んでほしいと言ってぶん投げたが、実は自分も解説のやり方はよくわかっていない。向こうもさすがに無理があったようなので、グラフ圧縮に絞って一目で説明しているtatyamさんのツイートを教えたが、そちらもうまく伝わらなかった。最後に自分で図を描いてみたところ、一発で伝わったらしく、感動。苦労した甲斐があったものだ。

pic.twitter.com/rGfsicoJsT
— tatyam (@tatyam_prime) 2020年7月8日

pic.twitter.com/MaCibyNo45
— こたつがめ (@kotatsugame_t) 2021年8月13日

開いた問題の制約のところに「グラフは平面的とは限らない」と書いてあり、なぜ当たり前のことを注釈しているのか……と思ったが、どうやらストーリーで街と道を使ったかららしい。面白い着眼点だ。そのようなclarが飛んだことがあるのだろうか。

布団に移動してラノベを読んだりなろうを読んだりしていたら、午前10時を回ってしまった。明日は午後1時半から院試ゼミの予定だ。非常にまずい。祈りながら就寝。

08/14(土)

午後1時半の目覚ましで起床。無理やり布団から這い出してZoomに接続する。ちょっとだけ待たせてしまったようだ。今日はこれから時間を計って院試の過去問を解く。制限時間は2時間だ。

選ばれた年の問題は難しく感じた。数学基礎論の問題が解けそうだったので真っ先に手を付けたが、最後の小問の反例構築はすぐ思いつけたのに、その前の証明の記述に時間を取られ、1時間半もかかってしまった。あんまり直感的でないことを証明させられたので、簡単な方針がないかしばらく探していたり、丁寧に確認しながら場合分けしていたら時間を食ったらしい。残り時間でもう1つ大問を選び、そちらは位数が9の群に対して何かを計算する問題だったので、愚直に全通り計算して求めた。

本来は3問解かなければならない。残り時間、小問を少しだけ解き進められる問題が2つ見つかって、解答を書かずに詰まっている小問を考えながらシャワーを浴びたりしていたら、試験時間が終了してしまった。

みんなの解答を互いに見ながら質問を飛ばしたりする。全通り計算した問題は、計算こそ合っていたものの、勘違いで答えが少し違ってしまった。数学基礎論の問題について、最後の小問の構築は、今日はすんなり思いつけたが、普段は結構時間を使って考えているので、本番でこの分野に特攻するのは少し危険だなと思った。

他の年の問題を見つつ、しばらくみんなで話す。「実数全体に通常の大小関係を入れた全順序集合」から「有理数全体のべき集合に包含関係を入れた半順序集合」への順序埋め込みがあることを示せという問題があった。実数を2進数展開する方針で構築しようとしたが、できない。しばらく別の問題を見ていて、ふとデデキント切断を用いる方法を思いついた。つまり、実数 $r$ に対して $\{q\in\mathbb{Q}\mid q\lt r\}\in\mathfrak{P}(\mathbb{Q})$ を対応させると、実は順序埋め込みになっている。しかしこの直感との合わなさと言ったら！そもそも2つの濃度が等しいことすら素直には頷かれない。後から知ったことだが、この構成はWikipediaに載っていた。

連続体濃度 - Wikipedia

次回は8/17(火)で、これが院試前最後のゼミとなる予定だ。事前に担当を決めず、各自好きな問題を解いてくる形式。最後までやり切りたい。

ゼミが終わってから、食事したり、洗濯物を干したりした。睡眠時間が明らかに足りておらず、非常に眠い。なろうを読んだりして何とか寝ないようにし、ABC214の時間を待って、出た。

AtCoder Beginner Contest 214 - AtCoder

6完遅解き。Eでめちゃくちゃに詰まって何もかもが崩壊した。

AはとりあえずAWK。BもAWKで書こうとしたが、何となくTLEを気にしてRuby。Cはdijkstra。Dはパスの重みの総和だと思って一回コードを書き、全部消して逆から見るUFを書き直した。問題文をちゃんと読んでいなかった。

Eは非常に迷走した。区間スケジューリングのような貪欲がうまくいかないケースはすぐに作れたので、判定問題を解くことを意識する。区間の掃き出し法みたいなことをすればよいのでは？と思ったが、これは区間の微妙なずれを認識できないため、必死に実装したもののWAだった。次に、ある区間であって、その中に入れるべきボールの個数が区間の幅より多いものを探す。このようなものが存在することと答えがNoであることは同値に見える（実際にはHallの結婚定理から言える）。実装については、探す区間の左端を固定して、右端を動かして行ったときに「含む区間の個数」引く「区間の幅」の累積最大値を求め、これが正になるような点が存在するかを二分探索した（実は一番右端を見ればよい）。ACできたが、すでに54分が経過しており、絶望。

Fは焦って5WAも出した。同じ文字が出現する直前の位置から今までの総和でdpを更新すればよいが、その直前の位置の1つ手前の値も足さなければならないことにずっと気づいていなかった。ずっと同じ文字が2連続する場合だけ処理していた。ACして残り20分、Gを読んで書こうとしたが、3乗のdpに見えてしまい詰め切れず終了。

コードゴルフをする。Aは40引いて86で割るのがよい。テストケースハックで縮みそうな気もするが、ちゃんとギリギリのケースが全部入っていて、単純な四則演算を誤魔化すのは難しい。BはAWKで3重ループ圧縮を頑張る。結局1重まで詰め込めた。CはとりあえずPerl。DもPerlで、連結成分を全部管理してuniteをマージテクでやるやつ。Eは手つかず、Fはちゃんと詰めると各文字に対する値を保存する配列と変数2個で書けて、Rubyならmodを取らずに計算できるが配列を記述するのが長く、その隙をついてPerlが現在最短。

Gを解く。コンテスト中に考えたことは、 $p_i$ と $q_i$ を結んだグラフを作り、各連結成分（ループになる）ごとに違反するインデックスの個数を決めたときの場合の数を求めるもの。これが求まったら、全部畳み込んでから包除原理すればよい。連続した違反するインデックスを一気に遷移しないと遷移の係数が計算できないと思っていたが、実はループを切り開いた時の最初の値を使ったか・直前の値を使ったかの4通りを持っておけばインデックスを1つずつ処理することができて、2乗のdpになる。結構面倒だが結構すんなり答えが合って通った。ちゃんと落ち着いていたら20分でもチャンスがあったかもしれないものを……。

Hを解こうとしたが気力が切れ、少しTLを見てしまった。すると、うっかりフローの文字列が目に入ってしまう。ここでHがフローで解けることに気づいてしまった。このようなことがないようにTLを見ないようにしていたのに……。実際には、まずSCCしてループを消し、次に負辺ありの最小費用流を解くためのポテンシャル前計算をベルマン・フォードからDAG上のdpに書き直す必要があったのでちょっと面倒だが、一番難しいのはフローであると気づくところだろう。そこをスキップしてしまい、残念。

AはFAだったらしい。Hは今回も辺の重みをいじって負辺を消す方法があるらしく、なるほどなあという気持ちになった。

朝方、ラノベを1冊読了した。「鳩子さんとラブコメ」2巻。適当に読んでしまったため話の内容をあんまり覚えておらず、特に感想はない。

午前6時就寝。

08/15(日)

午後1時くらいに少し起きていた記憶もあるが、またすぐ寝たのだった。午後8時起床。しばらく布団でうだうだして、1時間くらいかけて布団から出た。

院試の過去問を解いていたが、夜中のCF #738 div.2に出た。

Dashboard - Codeforces Round #738 (Div. 2) - Codeforces

D2が解けなかった。

Aは全要素を全部のbitwise andにできて、これが最小。Bは'B'と'R'の交互で間をつなぐ。'?'が端にある場合や、そもそも全部'?'である場合に注意するべきだが、そのようなケースはすべてサンプルにある。Cは適切に場合分けすると必ず構築可能だとわかる。基本的に $i$ から $i+1$ への辺を順に通っていく。 $N+1$ から $1$ に向かって辺が出ている場合は、最初にその辺を通ればよい。そうでない場合はどこかで一旦 $N+1$ を挟むか、あるいは最後に $N+1$ に行けばよい。D1は、張れる辺を貪欲に張ってもよさそう（反例を構築できなかった）なため、全探索。Eはgcdが $1\le g\le m$ の倍数となるような列の場合の数を全部計算してから包除原理（除原理？）を行う。計算は累積和dpを用いて $O\left(\frac{Nm}{g}\right)$ くらいでできるため、全体で $O(Nm\log m)$ となる。

D2のコーディングを頑張っていたが、間に合わなかった。後から出したら通った。それぞれのUFを見て最も大きな連結成分 $U$ を取り、取ったほうのUFをA、他方をBとおく。 $v\not\in U$ を見たとき、Bで $v$ と非連結な $u\in U$ を探したいが、これはBにおける連結成分の代表点とその連結成分に含まれる $w\in U$ をmapで持っておけば可能。繋げることに成功したらmapと $U$ 自体を更新してまた先に進み、これを何回も繰り返して更新がなくなったら、 $U$ の頂点を以降無視することにしてまた最初から始める。計算量解析はできていないが、 $U$ は毎回そこそこ大きくなってくれるだろうという読み。249msで通っている。

TLで似たような解法を目にしたが、実は上のループは1回でよかったらしい。ある連結成分とどのようにしても結べなかった連結成分は、他方の森で1つの連結成分となり、選ぶ連結成分を変えたところでどうしようもない。

D2は乱択で通した人が多いようだが、非乱択解で非常に頭が良いものがあった。天才すぎる。

UF の根の集合を set とかで管理する。そうすると「グラフ 1 で相異なる連結成分に属する頂点 u1, v1」と「グラフ 2 で相異なる連結成分に属する u2, v2」を取ってこれる。この 4 頂点から上手く 2 つ選ぶと必ず上手くいく。
— 熨斗袋 (@noshi91) 2021年8月15日

シャワーを浴びて着替える。最近やたらと寒いので、長そでのパジャマを着てみることにした。

院試の問題を解き進める。やはり難しい。多様体の分野で曲率が出題されることもあるようだ。今のところ、簡単なヤコビ行列を計算したり正則値定理を用いたりする程度の能力しかないので、曲率という文字が見えた瞬間逃亡していたのだが、さすがにまずいだろうということで教科書を読んで何とか頑張る。2つ見つけてきた問題のうち一方は教科書と似たような導入だったため解けたが、もう一方は全然違うため、どうしたらいいかわからない。最初の小問から手が出なくて、絶望的。

少し年代をさかのぼると、数学基礎論の問題も解けなくてかなりつらい。願わくば、これが易化傾向を表していて、かつ今年も簡単になりますように。昼前まで院試の問題を解いていたが、週記の投稿のため溜めていたぶんの日記を書いた。投稿して1週間の区切りとするものの、今日は夕方くらいまで起きておいて、試験に向けて生活リズムを整えたい。整えるといっても1周回す方向で、だ。

kotatsugameの日記

週記（2021/08/09-2021/08/15）