06/07 (MON)
8:30 起床。大事な用事（オンライン）が 10:00 からあったので大学に行かず家で待機していた。 今日の典型を確認する。
https://atcoder.jp/contests/typical90/tasks/typical90_bh
問題概要。長さ $ N $ の数列 $ A $ が与えられて、その部分列を $ B $ で次の条件を満たすものを考える。（ $ B $ の長さは $ M $ とする）
- ある整数 $ K \quad ( 1 \leq K \leq M) $ が存在して次の $ 2 $ つの条件をともに満たす。
- $ 1 \leq j < K $ に対して、 $ B_i < B_{i+1} $
- $ K \leq j < M $ に対して、 $ B_i > B_{i+1} $
LIS っぽい見た目をしている。とりあえず左から見ていって最大値が $ A_i $ になる LIS を考える。 これは $ O(N \log N) $ で、次に右から見て最大値が $ A_i $ になる LIS が欲しくなる。 LIS の DP は $ O(1) $ で revert が可能なので、事前に右からの LIS は計算しておき順次 revert していけば欲しいものが得られそうだ。 でも★5 の典型で LIS の DP を revert するなんて問題が出るだろうか…と思ったが考えるのをやめた。 とはいえ、ABC で有名な DFS 中で LIS を revert する F - LIS on Tree が青 diff なことを考えると、やはり想定ではなさそうだ。
10:00 になり用事が始まる。そして終わる。 大学に向かう。
大学に着くともう昼食の時間なので、いつものようにケイジャンビーフチーズステーキ＆ライスを頼む。 これ本当に美味しいので、なんかの用事で矢上キャンパスに月曜に来たら食べてほしい。
食べ終わって少しするとゼミの時間になる。こちらも割愛。 週記なのに割愛する部分が多すぎて涙がちょちょ切れるぜ。
ゼミが終わり、作業をする。楽しいパートに入っているのだが、やりたいこと自体は依然として難しいのでかなり困っていた。 一応最低限今週とるべきデータらしきものは取れた気がするので、一旦思考パートかもしれない。
思考につかれてきたので研究室内で平然と競プロを始める。 tester を頼まれていたので、それを考えるなどする。当然内容は言えない。 tester をやっていること自体はインターネット上から一応確認もできるはずなのでこれは言っていいはず、だよね？ 解けたので writer に解けたから帰ったら実装すると報告する。
作業に戻る。なかなかうまくいかないので 18:00 ぐらいで切り上げてゲーセンに行って気分転換をする。 本日も 19 の 1 ERROR を出してしまい、人生の体現者となっている。 最近ボルテ上手いからここらで実力を伸ばしていきたいところなんだよな。
帰宅。飯を食べるも、胃にばくだんいわを $ 100 $ 発生させる結果となり本日の活動終了が決定した。 ベッドに横になりながら兄とみんはやをやったりして時間を過ごしていた。
11:40 ぐらいに今日の Streak をつないでいないことに気が付き、これが今の競技モチベの一つになっているので無理やりつないだ。 writer に申し訳ないと思いながらも活動不可能だったので翌日に実装は回すことにした。
典型未ACがたまっていることが気になったが、健康状態の面でしょうがないので就寝。
06/08 (TUE)
10:00 起床。典型を通してないので朝の TL を見ることが許されない。ついでに今日の典型も確認できないからつらい。 胃の調子は依然として最悪なので、朝食は抜くことにした。乳酸菌飲料を一本だけ飲んだ。
午前中の記憶があまりない。正午ぐらいから tester の実装をしていた。AC。 このタイミングで昼食の時間になる。母親が弁当を作っておいてくれたのでこれを食べればよい。感謝。
昼食を終える。
writer とやりとりをしていた。出題の日が楽しみ。俺も writer デビューしたいな。しようかな。
ピアノの練習をなかなかできていないの本当につらいなあと思って開始する。 結局夕食の直前まで弾いていた。 弾けないところを一生練習していると段々つらいのが気持ち良くなってくる。 完全に脳内物質が出ちゃってるんだよね。
今日の練習にはメトロノームを久々に使ってみた。最近使ってなくって埃っぽかった。 こいつは BPM を合わせると左右に振れてその BPM の四分でカチカチ音を鳴らしてくれる優れものだ。 あと地味にこの見た目も好き（いらすとやの画像を下に貼ってみた）。 如何に自分が拍を取れていないのかを実感させてくれた。 心なしか安定感が増したように思う。明日も頑張ろう。
夕食の後、コンテスト予定表を見る。明日の 20:05 分から SRM らしい。完全に忘れていた。 流石に TopCoder で黄色になりたいな。 黄色と言えば今週中に色変記事を書こうかな。とは言え、自分が何をしてきたかなんて全然覚えていないな。
競技プログラミングの練習のために、忘れてそうな令和 ABC を再バチャした。最近ちょくちょくやろうとしている。
AtCoder Beginner Contest 128 - AtCoder
D 問題。制約が緩めで 4 重ループを書いた。こういう制約が緩くて方針がよくわかりにくい問題でワタワタしなくなったのは成長かな。
E 問題。これ普通に難しいぜ。まあ $ 1 $ つの工事に引っかかるかどうかの条件は $ [S_i - X_i, T_i - X_i) $ であることにはすぐ気づく。naive にやると、 $ O(NQ) $ なので工夫が必要だな…今回は双対セグ木を使って chmin クエリで $ Q $ 個のクエリの答えを更新していった。多分想定は $ X_i $ の小さい方から見ていって引っかかるクエリを除去していく、みたいなやつな気がする。
F 問題。地力で通せた初の橙 diff 問題だったこと以外の全てを忘れていた。なんか時間内に合わんかった。 最悪の気分になったが、今こそ記事にするべきだと思って記事を書くことを決意した。
本日の活動はここまでとなった。就寝。
06/09 (WED)
10:30 起床。微妙に起床が遅い日が続く。 典型を確認しようとするも、最近連日で典型の問題を見ていないため Twitter で典型を確認できないという悪循環に陥っている。
今日は週一でピアノに行く日なので、手ならしをしたいが寝起きはキツイのでちょっとしてからすることにした。 典型も見られないし、いい加減処理しておきたいなあといいつつ怠けていた（ここ今週の最悪ポイント）。
具体的には体調も気分もノっていなかったので漫画を読んでいた。 今週のジャンプを月曜に買ったのに読んでいなかったので読んでいた。 最近のジャンプは猛烈に次が気になる漫画がなくて困っている。 いや、ヒーローアカデミアと Dr. STONE は続きが結構きになるかも。 ただ、ハンターが連載している時期は、毎週次のハンターが読みたくて狂いそうになっていたのだが、そういう感覚はすっかりしなくなってしまったな。
うーん、あとは金色のガッシュを読みなおしているのだが、こちらは結構刺激的だ。 話の流れをある程度覚えていても面白い漫画は面白いなぁ。 今度ハンターを読み返そうかとも思ったが、休載期間を思って辛くなりそうなのでやめておくことにした。
そんなことを思っているうちに身体が目覚めてきたのでピアノを弾く。 日が高い時間に指を動かすのはどうも得意じゃないらしく、指がよく開かない。 指がよく開かないからこそ事前にウォーミングアップをするという側面もある。
昼食を食べて、稽古に向かう。 今日の稽古はダメすぎて引いた。もっとしっかり練習時間を確保しなければ死が待っているかもしれない。 凹みながら帰宅。
家に帰って作業をしようと思うも、なんかダメな感じだったので競プロすらせずに金色のガッシュを読んでいた。 今週はなかなかやる気を失うタイミングが多くて困った。
少しして、競プロ自作問題の考察をしてメモったりしていた。 自作問題を考えて、自分で解法をまとめる作業楽しいんだけど放出のタイミングがわからない。
色々やっている内に夕食の時間になり食べた。サッサと食べてしまい SRM に備えていた。 が、しかし自分は大事なことを見落としていた。SRM 807 はどうやら Only rated for Div. 2 らしかった。 昨日の日記に黄色になりたいとか書いていたが理論上不可能なことだった。 直前にそのアナウンスに気づいたが、Combined とのことで多分難しい問題もあるだろうということで参加した。
A 問題。文字列 $ S $ が与えられて、文字列当てゲームみたいなことをする。 文字列を推測する側のプレイヤーが文字を指定すると、その文字が書かれた index が全て明かされる。 推測する側のプレイヤーが指定した文字のリストが与えられるので、現在推測される文字列を不明な位置を '_' として返せ、と言う問題。 無難に $ 26|S| $ 回ループして処理した。
B 問題。長さ $ N $ の整数列 $ A $ を考える。このうち $ 1 $ つの値がわからなくなっている。 この数列は、すべての要素の平均の値が数列中に現れるという性質を持つ必要がある。 $ N - 1 $ 個の要素が与えられるので残り一個の整数の候補のリストを返せ、という問題。 数式を書けばよくて、$ \frac{ \sum _ {i=1} ^ {N - 1} A_i + X}{N} = A_k \quad (1 \leq k \leq N - 1) $ の $ X $ を求めれば良くて簡単な一次方程式。 と思いきや、$ \frac{ \sum _ {i=1} ^ {N - 1} A_i + X}{N} = X $ も考える必要がある。Hack のためにこれが要るケースを作っておいた。 最後に重複を除けば OK。
C 問題。長さ $ N $ の整数列 $ A $ が与えられる。 十進数で考えたときに $ 2 $ 整数の「違い」を「足りない桁は $ 0 $ 埋めして違っている桁の数字の数」と定義したときの全てのペアに対する「違い」の和を求めよ、という問題。 こういうのは桁ごとに見る。以上。
D 問題。長さ $ N $ の数列 $ A $ と $ LO,HI $ という整数が与えられる。 $ LO $ より大きく、$ HI $ 以下の部分和の個数を数えよ（和が同じでも index の set が異なれば異なる）、と言う問題。 制約を見ると $ LO,HI $ が大きく、 $ N \leq 40 $ 。こんなのは半分全列挙する。以上。 upper_bound と lower_bound を取り違えていて頭を悩ませていたのは内緒。
そんなこんなで結局難易度も Div.2 レベルだった。Combined とは一体…！？ Hack Phase に入ったので B 問題の Hack を試みるも、意外とみんな $ X $ そのものが平均になるケースを見落としていなかった。 偉いなみんな。一人見落としを発見したため Hack した。気が付くと、unrated の人たちが rated の人の提出を撃墜しまくっていてワロタ。
ビックリするほど得るものがないセットだったのだが、問題の質自体は悪くないと思った。
SRM が早い時間だったため、作業をしたりしていた。
余談だが、世の中に Online Judge が多く存在している。これを作ってみるのもまた面白いとは思うのだが、初期制作の時間コストはもちろん、維持コストがかかるし実際に人が使うとなるとどのぐらいアクセスされるとか色々な事を考える必要があって面倒な気がする。 そこでクソみたいな Offline の Judge が一つぐらいあってもいいんじゃないかと思って作ろうと時々考えていて設計について調べものをしている。 時間ができたタイミングで一旦形にしたい。 名前はそうだな Arien Offline Judge で AOJ とかどうかな？怒られそう。
06/10 (THU)
6:50 起床。木曜は早起きすることにしているのだが、他の人のバランスが悪くて体調悪化に貢献している気がしてならない。 依然として典型90 を処理していないため朝の Twitter 確認ができない…
いつもこの時間に起きて支度をして朝食を食べて大学に向かうと時間はちょうどいいのだが、満員電車で気分最悪になる。 一限はオンラインで録画が存在しているため、今日は一回時間をズラして登校することに決めた。
結論から言うとズラして登校はかなり快適だった。問題点としては講義を録画で受けることになるため真剣みが半減する。 まあもともと院に入って超真剣に聞く講義などあまりないので気にならないかもしれない。
もう一つ今日試したことがある。行きにゲームセンターに行くことである。 今まで大学の帰りにゲームセンターに行っていたのだが、帰りはシンプルに疲れていて下手くそだったりするし、 なにより夕方以降は人が多くて待ちが多く発生するというのがストレスフルだ。 行きにゲーセンに行けばこの問題が解決しそうと思って試した。 真昼間から初手ゲームセンターに行くという行為自体に若干の抵抗感があることを除けばよかった。 というか学部生の時は昼に授業が入っていなければ普通にみんなでゲーセンに向かった気がするし、どうでもいいな。
元気なこともあって、普通に成果が出る。気分よく大学に向かうことに成功。 しかし、肝心の研究の作業自体は難航しているんだよね（かなり困っています）。
～大学で時間を過ごす～
帰宅。行きにゲーセンに行くというのは、帰りが遅くなることを防ぐという効果も望めそうなので今後も導入していこうかな。 いつも木曜日に食べているタンドリーチキン丼の画像を一回も週記に上げてないことに気づいたので、来週はアップしようと思う。
夕食を食べて、胃を休ませながら CLIST を開く。今日は Div.3 であることを思い出す。 時間が来た。相当に眠いが諦めて(？)出場する。
A 問題。$ N $ 個の石が与えられてそれぞれの力が $ A_i $ で与えられる。力は distinct である。一回の操作で左右端のどちらかから石を取り出すことができる。力が最大と最小の石を両方取るには最小で何回の操作が必要か、という問題。 distinct なので最大最小の石の index を事前にもっておいて、それぞれの石について左右のどちらから取るかを全探索することで最小回数が分かる。
B 問題。$ N $ 人の子供がいて $ i $ 番目の子供は $ A_i $ 個のキャンディを持っている。子供を何人か選んでキャンディを全て預かり、それらのキャンディを自由に再分配することができる。最終的にすべての子供が持っているキャンディの数を同じにしたい。この時最小の選ぶ子供の人数を答えよ、という問題。まずキャンディの数の平均が整数になっている必要がある。あとは平均より多くの数のキャンディを持っている子供を選択すれば十分。
C 問題。長さ $ N $ の整数列 $ A $ が与えられて、$ L \leq A_i + A_j \leq R $ となるような $ i,j (i<j) $ の組を数え上げろ、という問題。 昨日の SRM の D の半分全列挙マージパートと同じ。
D 問題。$ A $ と $ B $ の $ 2 $ つの整数が与えられる。 $ 1 $ 回の操作では、それぞれの数をその正の約数で割る。 ちょうど $ K $ 回の操作で、$ A=B $ にすることはできるかどうか判定しろ、という問題。 $ A,B $ の一方がもう一方の約数になっている場合回数の下限は $ 1 $ 回。しかし $ A=B $ の場合のみ $ 2 $ 回になる。そのほかの場合も $ 2 $ 回。次に上限を考えると、$ A,B $ の素因数の数の和が操作回数上限である。よってこれに合うようにする。 素因数の数を求めるパートが一番つらいが、これは $ \sqrt{10^{9}} $ までの素因数を事前に列挙しておくのが良いらしい。 本番中は焦って高速素因数分解を yosupo judge からパクってきたが、なんか System Test で落ちていた（涙…）。
E 問題。嫌がらせ問題なので本番中は一回飛ばした。文字列を変数に代入する文と、 $ 2 $ つの変数を結合してできた文字列を変数に代入する文からなるプログラムがあって、最後の分で代入された文字列の中に "haha" という文字列がいくつ存在するか答えよという問題。変数名や単一の文字列は $ 5 $ 文字以内。 アイディア自体は簡単で、連想配列とかに変数の中身を持っていれば処理できるが $ N \leq 50 $ ぐらいあり、愚直は通らない。 よって、変数の内容の prefix, suffix を $ 3 $ 文字まで持つことにする。また文字列中に存在する "haha" の数も持っておく。こうすることで、後は丁寧に初期化や結合を掛ければ解けた。 結合部分の文字列に "haha" が $ 2 $ つ含まれる場合を忘れていてコンテスト中に合わせることはできなかった。
F 問題。初期値 $ L $ として $ 1 $ ずつ足していって $ R $ にすることを考える。$ R - L $ 回のの演算で変化した桁の数の合計を答えよ、という問題。$ 10^{x} $ の倍数になるときに $ x+1 $ 桁だけ変化していることに気づくので、$ 10^{k} \quad (0 \leq k \leq 9) $ の倍数の数を足し上げれば解ける。面倒なので $ L=0 $ の問題を解けば引き算で良い。
G 問題。$ X $ 個の赤いボールと $ Y $ 個の青いボールがあって、これらを使って $ A $ 個の赤いボールと $ B $ 個の青いボールのセット、もしくは $ B $ 個の赤いボールと $ A $ 個の青いボールのセットを作りたい。作れる最大のセットの数を求めよ、という問題。 こういうのはとりあえず数式を立てると良さそう。
上の式で $ x+y $ を最大化したい。$ x $ を固定すると、$ y $ の最大値は $ \min( \lfloor \frac{X - Ax}{B} \rfloor, \lfloor \frac{Y - Bx}{A} \rfloor) $ と決まることに気づく。$ f(x) = x+y = x + \min( \lfloor \frac{X - Ax}{B} \rfloor, \lfloor \frac{Y - Bx}{A} \rfloor) $ と置けて、これは上に凸である（コンテスト本番は直感的に感じた）。真面目に言うと、$ f_1(x) = x $ は自明に凸関数で、$ f_2(x) = \min( \lfloor \frac{X - Ax}{B} \rfloor, \lfloor \frac{Y - Bx}{A} \rfloor) $ は凸関数と凸関数の $ \min $ なので凸関数。凸関数の和は凸関数なので $ f(x) $ は凸関数。 よってあとは三分探索をした。床関数を抜いて、実数で比較は行った（でないと壊れそうだったため）。
後で editorial を見たら、$ n $ セット作ることが可能かどうかを判定して二分探索する方針を取っていて、式を変形することで $ 4 $ つの条件を満たしているかどうかで良いという解き方をしていた。賢い。
06/11 (FRI)
11:00 ぐらい起床。最悪。例によって典型を処理していないため（以下略）
朝食にワッフルを食べる。研究作業をしていき、昼の時間になって昼食を食べる。 こいついつも飯を食っているな。
14:30 ぐらいからはマジで最近だれも質問に来ない TA をやる。この時間も作業自体はしている。 16:30 からはゼミがある。そういえば来週のゼミのスライドまだ一ミリも作っていない。 今回は余裕を持って完成させたいが…
18:30 になってゼミも MTG も全てが終了する。研究はなかなか面倒ごとが起きていて困るがまあこんなもんだろうという感じで金曜をおしまいにした。
明日の ARC の配点が来ていた。400 500 600 700 800 1200 らしい。 maroon さん単独W回だし、敗北する臭いがかなり強い。 特に最近難しい問題に全然ちゃんと取り組んでいないため、やばい。
夕食をたべる。 土曜日にここを書いているのだが、夕食を食べた後何をしていたのか全然思い出せない。 とりあえず寝る前に sak さんが Twitter でスペースを開いていたためお邪魔をしたことだけ覚えている。
びっくりするぐらい本日の内容が薄い。 日記にできないことが多い日はこうなりがちなのかな…
06/12 (SAT)
12:00 起床。土曜を無駄にする天才になっている。かなりウケる。いや全然ウケない。
朝飯は諦めて、昼飯はマックを食す。UberEats。 僕マックを食べる時ダブルチーズバーゲーだけでは物足りなくて、チーズバーガーを足すとかいう珍プレイをしているんですが、 皆さん足りないときどうしているんだろう…？気になります。 というかまた気づいちゃったんだけど、マックですらチーズと牛のコンビに洗脳されているな、自分。 これからプロチー牛野郎として生きていこうかな。
最近もこうの動画をあまり確認していなかったため、確認する。 やっぱりもこうは頭がおかしい。妙にスマートな量産型 YouTuber なんかより頭のおかしいもこうの方がずっと面白いと思うんだけどあまり共感が得られない。 あとなんか、もこうが世にも奇妙な物語に出るらしい。草。見ようかな。
友人と通話の予定があったのでちょっと話した。研究室以外の人と話す機会を大切にしていきたいなと思った。
今日が ARC であることを思い出し危機感を覚える。 競技プログラミング開始！ というわけで競技プログラミングをしていた。新たに難しい問題を解くとかはしなかった。
夕食後、ARC 開始。
A 問題。 長さ $ N $ 非負整数列 $ A $ が与えられる。各項の間に + か - を入れる。その時、連続して - が存在しないような書き入れ方を良い式と呼ぶ。
良い式の値の和を $ \bmod 10^{9} + 7$ で求めよ、という問題。
難しい。 $ i $ 番目までの隙間を見て、- が $ j $ 個連続している場合の数は DP で求められる。
$ j \leq 1 $ のため $ O(N) $ で求められる。この DP table を利用しながら $ i $ 番目までの隙間を見て - が $ j $ 個連続している場合の数を DP で求めた。AC。
かなり混乱した。
B 問題。$ N $ 個のシナリオが与えられる。$ i $ 番目のシナリオでは $ A_i $ 円を失ってしまう。それぞれのシナリオは等確率で起こる。 $ x $ 円 (任意の値) 払って保険に入ることによって、$ A_i $ 円を失った時に $ \min(A_i, 2x) $ 円補填してもらえる。 最終的に失うお金の期待値の最小値を求めよ。 明らかに $ 2x $ が $ A_i $ 以上かどうかで性質が変わる。$ A $ をソートして累積和を事前計算することで、 $ x = \frac{A_i}{2} $ の場合を全て試すのを高速にできる。AC。
C 問題。むずすぎ。本番は落とした。フィボナッチっぽいことに気づいていたのに、考察を続ける堪え性がなかった。 任意の整数は、隣接しないフィボナッチ数の和で表現できるため、計算するとちょうど $ 130 $ ぐらいで目標を達成できる。 明らかに 3,4 を繰り返さないと間に合わない大きさの数字だったので、早く気づくべきだった。
D 問題。本番わかったのだが、落とした（？？？）。$ 2N $ の非負整数が与えられて、$ 2 $ 人が交互に数字を取ってきてその xor が黒板に書かれて、最後に黒板に書かれた最大値がスコアになる。 先行の人は最大化したいし、後攻の人は最小化したい。 xor の最大値を考えるので、整数列中で一番高い位置の pop している bit に着目するのが良いだろう。 着目すると、この bit が pop している整数が偶数個なら、ミラーリング戦略を取ることでスコアでその bit が立つことを防げて最適。 奇数個なら、スコアで必ずその bit が立ってしまう。故に、後攻はなるべくそれより下位の bit で小さくしたい。 着目している bit が立っている整数集合とそうでない集合間の要素同士の xor でもっと小さいものが答えになる。これは Binary Trie で効率よくわかる。
偶数の場合に立ち戻る。偶数の場合はミラーリング戦略で良いが、どれとどれを組ませるかは後攻が決めることができるので再帰してその右側の bit で同じ問題を解く。 桁数が $ 30 $ 程度なので再帰しても十分間に合う。また着目した bit が pop していない整数の集合に対しても問題を解いて、結果をマージする。 これで解けたはずだったが、chmin のところが chmax になっていて落とした・・・無念・・・
E 問題。本番は読んだだけだった。冷静になると、比較的にわかりやすい貪欲で解けることに気づいた。 ただ ad-hoc 要素が強いな。本番この問題に突撃するのは勇気が要りそうだ。 この問題と D は記事にしようかな。
普通に青落ちしてしまった。まあ、気長に競プロやっていこう・・・。D 落としてなかったら落ちてないし、まあ実力は黄色ってことで・・・。
06/13 (SUN)
11:00 起床。ワッフルを朝食に食べる。
さらっと昨日の ARC のコンテスト復習まで含めて昨日の日記に書いてしまったが、ARC の復習をしていた。 E 問題が貪欲なのに驚いた。ARC E はまあまあな頻度で気づき枠が出るなぁと思いを馳せていた。
昼飯を食べてしばらくはゆっくりしていたが、普通に明日のゼミのスライドを一ミリも作っていないことを思い出す。 読んだ論文の中から発表する論文を決めて、読み直す。
読み終わる。 スライドを作っている。B4 にもわかるようなスライドにしようとした結果、辛い思いをしている。 そして多分これは B4 がわかるかどうか怪しい気がする。あまりにも救いのない作業に涙が出てくる。
間に夕食を食う。 ABC があるので何もしていないけど出てみる。まあ黄色 perf は出るやろ・・・。
AtCoder Beginner Contest 205 - AtCoder
A 問題。A で実数問題でた。珍しい。
B 問題。与えられる配列 $ A $ が $ {1,2,...,N} $ の並び替えか確かめる問題。ソートする。
C 問題。$ A^{C} $ と $ B^{C} $ の大小を比較する問題。負数があってめんどくさい。実数入力がない分だけましだけど辛かった。
D 問題。配列 $ A $ と $ Q $ 個のクエリが与えられる。 各クエリは、$ K $ が与えられるので、$ A $ に含まれない正整数で $ K $ 番目のものを答えよという問題。 ソートしてそこまでに幾つ正整数があるかをメモして二分探索した。混乱した。
E 問題。左上が斜めに切り取られた経路数問題に落ちることはわりとすぐ気づいた。$ O(N^{2}) $ しか思いつかない。 というかこれを書いている今も実は解けていない。HELP! ここで精神崩壊してしまった。
F 問題。グリッドが与えられる。$ N $ 個の部分矩形が与えられるので含まれるマスにコマを置ける。 同じ行や列にコマを $ 2 $ つ以上コマを置くことができない時、最大幾つコマを置けるか？という問題。 こんな問題 DP とか貪欲で解けるわけがない。最大流だなと思った。 しかし深刻なことに「同じマスに $ 2 $ つ以上置けない」に誤読していて間に合う気がしなかった。 コンテスト終了 $ 2 $ 分前に気づいた。書きなおしたが間に合わない。助けてくれ！！！！！！！！！！！！
結果はさらにレートを削ることになった。 それはそうと E が解けないのはダメらしい。そこは素直に反省します。
スライドの手直しに戻る。 今週末はこの作業中に日が明けた。カラスがバカうるさい。奴ら深夜に鳴くのマジで何？
今週は競プロがあまりできなかったので、来週は競プロを中心に生活を回したいと思ったりした。 それでは。
