06/14 (MON)
8:00 起床、スライドをやや直す。
朝食をたべる。鳩サブレ―を食べた。鳩サブレ―って言って通じるかな。
夜暑くて身体ベタベタしがちなのでシャワーを浴びるなどしていた。 どうやら、外では雨が降っているらしいことに気が付く。 かなり嫌だが今日は必ず大学に行く日なので参った。とりあえず、家で少しダラダラすることにした。
雨がやんで晴れてきたので大学に向かう。 大学につくとちょうど 12:00 ぐらいでキッチンカーに直行する。 伝家の宝刀ケイジャンビーフチーズステーキ＆ライスを今週も頼む。 なんなら合わせて飲む飲み物も毎週モンスターエナジーで固定化されつつある。
胃が悪い日だったため、チー牛飯がかなり堪える。しかも今日はゼミ輪講の当番の日だったのでかなり嫌だった。 ゼミでもう一人の人の発表中に、斜めになりながら画面を見ていたら、 研究室の秘書さんに「難しい内容ですか？」と聞かれたので「胃が悪くてナナメってるだけです」と答えた。 多分今週で一番かっこ悪い瞬間が記録されたと思う。
自分の発表をする。今回はそこそこ読みやすくて発表もしやすい論文を選んだ。 今回は B4 にもわかってもらいたいな～と思ったので結構丁寧にスライドを作成した。 とはいえ M1 以上は英語でスライドを作成することが義務づけられているため B4 がわざわざ読んでくれるか怪しい。 オンラインのゼミで発表するの、B4 の時は周りのリアクションがなさ過ぎて本当に何かの罰ゲームに感じたのだがもう最近は気にならなくなったな。 今の俺なら平常時のテンションで配信もできると思った。
発表中にアクシデントがあってつらかった。今回初めて zoom 共有で発表者用のカンペを表示するやつを試してみたのだが、Google Chrome を最新版に更新していないと存在するバグで、スライドを切り替えたときに前のスライドの下部が消えずに残留して共有画面が破壊されてしまうというものだった。 発表している自分の画面は全然普通なので気づかなかったが、大学にきている先輩に見せてもらったら本当に酷かった。草。というか普通にカンペ見れなくて焦った。英語のスライドだから、カンペないと現在位置を見失いがちなので助けてほしい。
このことによって俺が Google Chrome のアップデートを全然していないアホ野郎だということが研究室中に知れ渡ってしまった。 セキュリティの観点もあるから更新はこまめにした方が良いよと教授に言われた。 うん。いや、頭ではわかってるんだけど、更新を先延ばしにしちゃう病気なんですよね、と心の中で言った。 教授に「〇〇くんはなんでも先延ばしにするタイプだよねｗ」って言われて早く人間になりたいと心から思った。
そんなこんなで胃が悪くてあまり作業が進まず、喋ったりしてて大学を出た。 帰り道、降りるべき駅を寝過ごすということを久々にやってしまった。
家に帰って夕食を食べる。寝過ごして遅れても安心して食べられる飯が提供される実家、良すぎる。 気を遣うこともあることにはあるけど、永遠に実家にいたいぜ。どうも子供部屋おじさんです。
昨日の ABC の E 問題について頑張って考えていたけど、ついに諦めた。 黄色ぴったりぐらいの難易度で自力で解くのを諦めた問題は久々だったのでかなり自信をなくした。
解説をいくつか見るが、条件違反をするとボーダーライン+1 の斜めの直線に触れるため、 この直線を基準にして線対称に経路を反転してくっつけると、ミラー先の始点からの経路と 1 対 1 で対応することがわかる。 結果的にその経路数を、違反を無視した経路数から引いてやれば求める場合の数になる。 いや、天才かよ。どうやらこれは最短経路数問題の典型の 1 つらしい。
06/15 (TUE)
9:00 起床。したのだが、二度寝を繰り返し結局 12:00 に起床した。顔面終了した。
朝食を食べることは諦めた。直接昼飯を食べる。 そぼろご飯うまし。
昼食を食べ終わってからは、ぷよぷよ最強リーグの YouTube のアーカイブを見ていた。
この人達、人間を辞めすぎていて面白い。 個人的にクソウマいプレーヤーを見ているだけでも楽しめる。 というかぷよぷよという競技はかなり e-sports に向いているなと思う。 対人戦で、長い歴史で蓄積されてきたセオリーがありつつ、新しい戦い方を模索する人達もいて… などなど一言で表現することはできないが、もっと e-sports で騒がれてもいいようなゲームに見える。
それに比べると音ゲーはかなり e-sports 化苦しそうに見える。 自分は音ゲーが好きなので期待しているのだが…
さてひとしきり休んだところで、昨日解説を見た E 問題について再考する。 最短経路数問題について、「特定の斜め線を通る経路数を、線対称に移動した始点からの経路数と考えることができる」 という事実は、知っておいて損はない。しかし自分はこの手の特殊操作テクニックが苦手なのでなんとか別のアプローチでいけないものか考える。
ちなみに問題が $ K=0 $ で固定だった場合、カタラン数に一致することがわかる。 これは聞いたことがある。Wikipedia でカタラン数について調べたときに、カタラン数の実例みたいなものがいくつか挙げられていた。 しかし、よく考えるとカタラン数についてよくわからず、式しか知らない。 その導出方法が分かれば、E 問題をパズルチックに解く以外の方法に結び付くのではないかと考えて、勉強をすることを決意した。
上記のことを踏まえてE - White and Black Ballsの記事を書くことにした。
記事を書いている間に用事の時間が来た。 また、それが終わったらピアノを弾こうとしていたのでしばし中断となった。
今日取り組んだ箇所がマジで全然うまくならなくて閉口した。 先週にいらすとやの画像を貼ったメトロノームをかけっぱなしにして気が狂いそうになっていた。
さていつも通り夕食までピアノを弾き続けていた。夕食を食べる。
夕食後休憩を終えると、また勉強に戻る。 母関数によるカタラン数の導出、フィボナッチ数列の一般項の導出などを見る。感動する。 そもそも母関数周りを真面目に勉強したことがないため、勉強するかと言う感じ。
形式的冪級数とかも関わってくる領域なので、合わせて勉強しようとして色々調べているとあっという間に時間が過ぎていく。 そもそもフィボナッチ数の一般項を誤差なく求めたいと思ったりして mod sqrt を発見して感動するなど、 かなりわき道にそれた検索行為をしているためこうなってしまう… 目的のものだけを調べることってできなくないですか？俺に集中力がないのは認めるが、みんなそうだと思いたい。
06/16 (WED)
10:00 起床。そういえば書いたショートレポートを提出していなかったので起床即提出。
朝食を食べる。 水曜日はピアノなので練習していくことになるが、午前中はイマイチ練習できる状況にないので別の事をする。 E - White and Black Ballsの非天才的解法を模索しているが、依然として成果がない。 非天才的解法の模索がかなり面倒なことは、TL にも AtCoder のページにも誰も解説を上げていない時点で想像はできたが、かなり苦しい。
割と無駄な時間をすごしてしまったなと思いながら昼食の時間になる。 昼飯の後に、昨日父親がお土産に買ってきた CINNABON を家にいる人で食すことになる。 これは美味しいシナモンロールなのだが、昼食直後に食べるのは自分の胃の事情には厳しいものがあった。 とはいえ、シナモンロールはかなり賞味期限がすぐ来てしまうため、このタイミングで食べるしかなかったので食べた。 美味しいも苦しくなった。美味しかったのでいいか。
そんなことでピアノを練習して、レッスンに向かう。 今週も散々だった。というか、遠回しに早く曲を形にして来いと言われた。 反省しながら、帰り道はまた例の問題の非天才解法に思いを馳せていた。 競技プログラミング的には、最近出題された (Binary) Trie を自分のものを持っていない（これは本当にクソで反省をしています）ので、作るというタスクもあり、あまり ABC の復習に時間を使ってばかりもいられないなとも思った。
そもそもなんで例の問題の非天才解法が詰まらないかということをここに書いておく。
適当な例を下図に示す。 この図の太線部の交差点への太線を超えない経路数が出れば答えが出そうだ。 なぜなら余事象を考えると、初めて太線を越える位置を決めてやれば その場合の数は、$ 越える直前までの経路数 \times 越えた後からゴールまでの経路数 $ で求められて、後者は二項係数なので十分高速に求められるためだ。
$ K=0 $ の場合に太線のラインの経路数を数列として観察をすると（漸化式を立てても良い）、カタラン数になっていることがわかる。これは嬉しい。解ける。
しかし、 $ K \neq 0 $ だとかなりつらい。漸化式すらうまいものが立てられないんだけど、どうしたものか… 漸化式さえ立ってくれればそれをなんとか処理できるのでいい感じの漸化式を立てたいな。
とまあ、全然思いつかないためやるべき作業をして脳をリセットすることにした。
作業後、全然わからないので困った。並行して調べている、形式的冪級数とかの話はシンプルに面白いのでそっちを読み進める方向で一日を閉じた。
6/17 (THU)
8:50 起床。もう一限の時間に登校するのは嫌になったのでこの時間に起床をしてしまっている。 ゆっくりめに登校することによって QoL が改善するのだから仕方がないだろう。
一度典型をやらない生活をしてしまうと、中々典型 90 をやる生活に戻すことが難しくなっている。 来週にはちゃんとそっちのリズムに戻していきたいと思う。
一方で、学校に到着する前にゲーセンに行くというリズムはすっかり出来上がっている。人間の欲望の力ってスゲー。
普通にボルテうまい。たまにはキッチンカー以外のものを食べようと思って First Kitchen で食べることにした。 頼んだメニューは チーズベーコンエッグバーガー のセットだ。 久々に来た First Kitchen のメニューにすらチー牛の匠としての影が見えるのウケる。 ちなみに本当に狙ってなくて、記事に書くときに気づいています。
そんなこんなで大学に着く。大学に着いたときに先週の週記で来週はタンドリーチキン丼の写真をブログに記録するとかなんとか書いていたことを思い出す。来週、来週こそはちゃんと記録する。
大学に着いて作業を進める。2 つの作業をなんとなく並行しているのだが、1 つの作業の進捗が芳しくないため、今日はもう一つの進捗を見える形にして、MTG に持っていくことにした。
教授と話して思いのほかちゃんと論文が書けそうな話にはなりそうな気が（勝手に）してきた。
関係ない話になるが、論文と言えばゼミで発表できそうな論文読み溜めストックがそろそろ切れた気がする。
まずいので、何本かまた読んでおかなきゃならない。
たまにゲボ程読みにくい論文もあって、そういう論文に当たると最悪で、ゼミで発表するのも大変だからである。
全部読んだ結果、そんなおもんなかった時ははったおしたくなる
なんだかんだ喋ったり作業したりして、研究室を出るのが 20:00 を過ぎていた気がする。 腹減ったという話になるも、緊急事態宣言中で飲食店が 20:00 に閉めてしまう。 しかし、そこは学生の街・日吉、自粛に応じない飲食店などそこそこあるだろうという張りをして先輩とひようら（日吉キャンパスの裏の街）を見て回ることにした。
正直、日吉をなめていた。日吉なら適当をやっている飲食店がそこそこあるという期待はかなりこっぴどく裏切られた。 マジで全然開いていない。ラーメン屋も大概はしまっているし、開いてそうな店もテイクアウトしかやっていない。 ただ一軒を除いて…。
がっ〇んとかいう店が普通に開けていて先輩と爆笑するも、死ぬほど並んでいるので流石に食うという感じにはならず、笑って帰路に着いた。というか通りのど真ん中の店なのに、すげぇ心臓だなと思った。
帰るとかなり疲れていて、元気は全然なかったのだが D - 動的計画法を解くことにした。
問題概要。下図のような DP テーブルを構成することを考える。具体的には下と左のマスの数字を足したものでマスを埋めていく。 ただし $ \bmod 10^{9}+7 $ で数字は表現される。 このテーブルで L 字に $ 3 $ つの領域の数字が与えられる。この領域が当てはまる場所（列・行）で、最も行が若く、列も若いものを求めよ、という問題。
ちょっと観察するとすぐ二項係数テーブル最短経路数経路数テーブルであることがわかる（2021/06/22 修正）。というかアルゴリズムからもわかるだろう。
例えば下図のようなパーツが与えられていて、$ 15 $ の位置の数字を $ A $、$ 35 $ の位置の数字を $ B $、残り $ 1 $ を $ C $ とする。 すると、 $ B $ の左や、$ C $ の下の数字も求められる。それぞれ $ B - A $ と $ C - A $ だ。 こうすることで斜め $ 3 $ つのラインが求められたことになる。 この右肩下がりの斜め $ 3 $ つの数字はどれも $ r+c $ の値が同じだなあということに気づく。 というわけで二項係数の式にしてみる。当てはまる位置を $ (r,c) $ と置いている。
となる。見るからに割り算で良い感じに打ち消せるため、$ (1) \div (2), \quad (1) \div (3) $ をする。 整理後の式を次に示す。
これらの式を連立させれば $ (r,c) $ が求まる。$ \bmod 10^{9}+7 $ で求まるため、大丈夫か考える。 問題文に行と列は $ 99,999,999 $ 以下であることが書いてあるため、一意。 よって出てきた $ (r,c) $ を出力すれば OK。
結構好きな問題だったので安眠。
6/18 (FRI)
11:30 とかに起床した気がする。最近寝つきが悪くなってきて、夏の到来を感じています。
読み始めよう読み始めようと思っていた、怪獣8号をついに読み始めることにした。 初回無料なので、一気読みが可能なため今まで自分にステイをかけていた。
昼飯をまたぎながら読んでいる。 半分ぐらいをゆっくり読んだ。自分は漫画を相当ゆっくり読むタチだと思う。 なぜなら、文字情報が少なくしっかり色んな情報をキャッチするのはテキストベースの物語ほど容易ではないためだ。 また、アニメのように勝手に流れてしまうということもないため心おきなくゆっくり読むことができる。
ゆっくり読みすぎた。ついでに他の木曜日更新の漫画とかも読んでいたりしたせいですっかり夕方になっていた。
しょうがないので（？）今日の典型をチラ見した。
https://atcoder.jp/contests/typical90/tasks/typical90_br
問題概要。$ N $ 個の二次元点が与えられて、二次元平面上の $ 1 $ 点を次の不便さが最小になるように選ぶ。
- 不便さは $ N $ 個の点の選んだ点とのマンハッタン距離の総和
この時の不便さを求めよ、という問題。
う～ん、まあこれは見た瞬間 $ X,Y $ 座標がそれぞれ独立に考えられて、中央値を選ぶのが最適。 証明も簡単なのだが、これはもはや競技er の中では知識として定着していそう。
TL を眺めているとこれが線形でできるとのこと。単純な解法ではソートがボトルネックになって $ O(N \log N) $ だと思う。 よくよく記憶をたどると、数列の $ k $ 番目の数を選択するアルゴリズムであるところの Median of Medians の存在を思い出した。これを使えば確かに線形でできる。しかし面倒だし、実装したことないという理由で見送った（カス）。
夕食のあと、なんとなく胃がだるくてダウンしていた。Codeforces の時間まで休むことにした。 最近胃の調子が悪い一因として「濃い緑茶」みたいなのが家に沢山買われていてこれを飲んでいることがありそうだと思えてきた。胃の悪い人は麦茶でも飲んでいたほうがよさそう。
さて Codeforces (Div.2) をやる。これはもともと Div.3 用だったらしい。全完を狙いに行く。
Dashboard - Codeforces Round #726 (Div. 2) - Codeforces
A 問題。数列が与えられて、平均が $ 1 $ になるように末尾に非負整数を足す。何個足せばできるか、という問題。まあ数列の総和と長さ $ N $ を比較して、総和の方が大きければ $ 0 $ を足し続ければよく、それ以外なら足りない数字をそのまま足せばいい（同じなら答え $ 0 $ だが）。
B 問題。$ N \times M $ グリッドが与えられて、人が $ (i,j) $ にいる。$ 2 $ 個のヨーヨーをグリッド上に落とすと、人は最短ルートで $ 2 $ 個回収して元の位置に戻る。人の移動量を最大化するヨーヨーの落とし方を答えよ、という問題。グリッドの外周より大きく移動させることは不可能なのは自明。よく考えると隅に置くことで、これを達成することができる。ギャグだ…。
C 問題。長さ $ N $ の数列が $ A $ が与えられて、$ | A_0 - A _ {N - 1} | $ が最小になる並び方について考える。 このうち、$ A _ i \leq A _ {i+1} $ となるような $ i $ が最も多くなるような並び方を答えよ、という問題。 とりあえず、$ |A_0 - A _ {N-1}| $ が最小にするために $ A $ をソートする。 最小の差を見つけたら、実はその間で数列を $ 2 $ 分割して逆さにつっくけ直せば最適である。 こうすることで、$ |A_0 - A_{N-1}| $ は最小で、条件を満たす $ i $ の数も昇順より $ 1 $ しか損しない。 $ N=2 $ の時だけ、昇順にできるため例外処理を怠らない。
D 問題。整数 $ N $ が与えられて、 $ 2 $ 人がゲームをする。それぞれの人は自分のターンに現在の整数の $ 1 $ とそれ自体以外の正の約数を引くことができる。最初に操作ができなくなった人の負け。最適にゲームが進んだ時の勝敗を判定せよ、という問題。 $ N $ が $ 10^{9} $ と大きいので DP とかをするのは無理。Nim に容易に落ちたりすれば簡単なのだが、そうでもないので難しい。 観察をしていくと、どうやら奇数が回ってきたら負ける。理由は奇数が回ってきたら相手に偶数を返すことになり、その偶数に対しては直近で選ばれた約数がそのまま選べて、操作をすることが可能である。よっていつか素数に行きついて負ける。しかし偶数がいつでも勝てるというわけでもなく、$ 2 $ に行きつくと負けてしまう。$ 2 $ のべき乗以外の数字は上記の理由と同じように必ず操作を続けられるので、$ 2 $ のべき乗のみ例外として考えると、$ 2^{odd} $ は負けて、$ 2^{even} $ は勝つ。以上を整理すると AC。
E 問題。文字列 $ S $ が与えられる。これに以下の操作が行える。
- 末尾の文字を消す。
- 現在の $ S $ を末尾に連結する。
長さ $ K $ の作れる中で辞書順最小の文字列を求めよ、という問題。 $ S $ の prefix を見て、その prefix を無限に連結して最初の $ K $ 文字を取るので良いことがわかる。 これを愚直な文字列比較でやっても E1 の要求には応じることができる。$ O(NK) $ でできる。
しかし E2 では線形ぐらいでできることが期待される。 一文字ずつ左が見ていって最適な prefix を発見したい。
- 頭文字より辞書順大きい文字が来たら打ち切り
- 頭文字より辞書順小さい文字が来たら続行
は割と自明。同じのが来ると困るが、とりあえず続行して頭文字じゃなく一つ右の文字を基準にするとよい。 ただし、打ち切ったら基準をズラした分は戻ったところまでの prefix が best。 あとは、愚直解法と同じで連結をして $ K $ 文字だけ取り出す。 文字列の線形アルゴリズムは賢いなぁ…
F 問題。連結無向グラフが与えられる。また各頂点の最初の値と目標の値も与えられる。辺を選択して端点の値に整数 $ k $ を足すことができるとき、目標の値にできるか判定せよ、という問題。 見た感じよくある、DFS 木を取ってきて葉から構成していく問題に見える。 単純に葉から構成して根の値が目標に一致していれば YES と書く。WA。 冷静に考えると、無向 DFS 木を使っているのでなんか悪さをするとすると後退辺ぐらいしかない。後退辺は根へのパスのショートカットと考えられるので、深さの parity が異なる $ 2 $ 頂点をつないでいる場合、$ 2k $ を根の値に加算できる。このような後退辺がある場合は、根の値と目標の値の parity が一致しているか見る。なんとかコンテスト内 AC。
ギリギリ全完できていい気分だと思っていたらきよしくんが不穏なことを言っている。
E1,E2死ぬほどプレテストが弱いです
— 碧 (@KOKTOSbot) June 18, 2021
え？？俺 E 問題全然ケアをしていないんだけど大丈夫か？
5 10
— 碧 (@KOKTOSbot) June 18, 2021
babab
で3人落としました
ほう。試す。落ちる。よく自分のコードを見ると、最後まで基準をズラした状態で行ったときは打ち切りとみなして、ちゃんとズラした分を戻して prefix を取らなければならないのにやっていない。 結構このミスをしていた人は多いらしく、TL が阿鼻叫喚に（主観です）。
結局 E1,E2 同じコードを投げた僕は滅されました。うくく…。 F を通していたのでなぜかレーティングは上昇した。紫だと失敗してもレート上がるしよくわからない。
6/19 (SAT)
昨日の Codeforces の System Test が遅かったためかなりの夜更かしをしてしまった。 案の定 12:00 起床とか。
本日も朝飯を食べることを諦めた。 生活崩壊最高！（最低！）
土曜の典型は難しいのでチラッと見たけどまあぱっと見ただけでは解けないので割愛。
13:00 からは約束があり、高校同期と通話をしていた。
午後に活動をしようとする。一応活動はしたが、すぐ飽きる。 生産的な活動をすることを諦めてためている漫画を読むことにした。
怪獣8号の続きを読む。めちゃくちゃ王道で、いい漫画だと思う。 よく自分は逆張りオタクだと思われるんだけど、逆張りではなく流行に対してマイペースなだけなんだよね。 好きなものが流行ってたり、全然流行ってなかったりする。 この週記で話題にする漫画は流行っているものばかりだけど。
単行本発売ペースがかなり緩やかな Artiste という漫画の最新刊を読んだ。 これもかなり雰囲気が好きな漫画。 もちろんキャラクターも好きなんだけど、この漫画はかなり作品全体に流れる雰囲気がやさしくて好き。 あと、クロックムッシュっていう名前のネコが出てくるんだけどかわいい。
漫画の最新刊を途中まで読むと、以前までの刊を読み返したくなって結局以前の話を全て読み返してしまう。 特に単行本のペースがゆっくりな漫画はその傾向が強い。 新刊を読むたびに全てを読み返すため、既刊を $ N $ として $ O(N^{2}) $ かかるオンラインアルゴリズムとなっている。
さてぐだぐだしているうちに、夕食の時間になる。両親の結婚記念日なので、近所の行きつけのイタリア料理店のテイクアウトをしていた。 イタリア料理は好きだ。トマトが好きだし、何よりチーズたっぷりだからかも。この場合必ずしも牛要素がないからチー牛ではなさそう。
食後は胃の不調に苦しみながらも、AtCoder Beginner Contest 206（Sponsored by Panasonic） - AtCoderに出る。
A 問題。税抜きの金額が与えられるので、 $ 8 $ % の消費税を加味して $ 206 $ 円との比較をする問題。
B 問題。$ i $ 日目に $ i $ 円貯金して行った時に、何日目に $ N $ 円以上の金が貯まるかという問題。 $ i $ 日目の貯金総額は $ \frac{i(i+1)}{2} $ なので実は愚直に判定しても $ O(\sqrt{N}) $ で解ける。
C 問題。整数配列 $ A $ が与えられて、$ A_i \neq A_j $ かつ $ i < j $ の組を数え上げろという問題。
これは一億回ぐらい出題されていて、余事象を考えて等しい要素ごとにカウントをして、等しい要素同士の組を数え上げて全体から引く。
std::map とかを使うと楽。
D 問題。長さ $ N $ の整数列が与えられる。これを回分にするために、「ある数字を選んで、全てのその数字を別の単一の数字に変更する」という操作を任意回数行う。 最小の操作回数を求めよ、という問題。これかなり詰まったので反省。$ \lfloor \frac{N}{2} \rfloor $ 組の数字を最終的に等しくすることが目標になる。 複数の等号条件を推移など含めて表現をするために、グラフを使うのは典型ですね。 これをすると各連結成分に対して、その要素数 - 1 だけの操作回数がかかる。最初有向にして最長路の長さだと思ったんだけど、脳が壊れているだろ。
E 問題。むずすぎて泣いた。$ [L,R] $ に含まれる正整数 $ x,y $ で、$ g = \gcd(x,y) $ として、 $ g \neq 1, \quad \frac{x}{g} \neq 1, \quad \frac{y}{g} \neq 1 $ となるような $ (x,y) $ の組を数え上げよ、という問題。 見た瞬間 $ g $ を固定したくなって、$ \frac{x}{g} $ と $ \frac{y}{g} $ を $ x' $ や $ y' $ と置いて、全て $ g=1 $ と同じ問題を解きたくなる。 さらに、扱える整数の範囲も $ g $ の値によって $ [\frac{L}{g}, \frac{R}{g}] $ となるので $ y' $ を固定しても $ O(R \log R) $ で済む。 また、$ y' > x' $ として最後に $ 2 $ 倍しても問題がない。 ここからが全然つまらなかった。$ y' $ の値に対する $ x' $ の数を求めるのが難しかった。 最終的に苦し紛れに $ y' $ を素因数分解して素因数の数を $ L $ として $ O(2^{L}) $ の約数包除をした。 $ L $ が小さい（かつ最大ケースは非常に稀）ので間に合うことを祈った。通った。
F 問題。ここに来て F を通さないと冷える状況になってしまった。$ N $ 個の半開区間が与えられて、$ 2 $ 人でゲームをする。 それぞれの人は、自分のターンに現在選ばれている半開区間のどれにも overlap しない半開区間を選ぶことができる。 最終的に選ぶことができなくなった人の負けになる。最適時の勝敗判定をする問題。 $ N \neq 100 $ なので当然愚直は愚か集合を状態にもつような DP をすることも難しい。 焦っていたため、タイムアップの直前に区間 DP を思いつく。 具体的には、それぞれの人は高々 $ N $ 個の選択ができて、それぞれの残しの区間は $ 2 $ 分割される。 それぞれについて、同じ問題を解いた上で結果をマージすることで全ての遷移先を網羅できる。 ちょっと考えると、boolean ではダメで grundy 数を考えれば良い。結果的に $ O(N^{3}) $ で解ける。
DEF 問題、どれも自分の典型力や演習量が足りなかったなという感じで反省。 E 問題は特に苦手なのでちゃんと復習しておきたい。
6/20 (SUN)
12:00 起床。来週の目標は早起きです。
昼食を食べる。今日は父の日なので、事前に絞っていたプレゼント候補を決定して買いに行くことにした。 Mac 周辺機器にあたりをつけていたので家電量販店に向かう。
色々あって、購入が完了する。家電量販店でものを探すのってなんでこんなに大変なんだろう。 遊びたくなったのでゲーセンに行く。
写真をすっかり撮り忘れたが、XROSS INFECTION [GRV] の PUC が狙えるところまで持っていくことができたりした。 インペリアル 2 になったらボルテの頻度を少し減らすかもしれない。
帰って夕食。すき焼きだった。美味しかった〜。
さーて今日は早めの時間に Codeforces があった気がするので Codeforces を開くと Running って書いてあって声出た。 21:05 からだと思っていたんだけど、19:05 からだった。これ不可能だろ。
1 問易しめの問題を通してお茶を濁してから今週を終えることにした。
今週も全然競技プログラミングしてなかったな。来週からはちゃんと典型を処理したい。
