雨上がりって良いよね 解いた問題1 少し前のARCのC。コンテスト後に解説を見た覚えはあったが解法は覚えていなかった。普通にDPをするだけ、天才…次に活かせるようにしたい 解いた問題2 典型90から。xor基底を出してどうする？と思ったら、基底じゃない奴は使う/使わないを選べるから最終的な答えが2倍されるみたいな話だった。xorとはいえ数値ではなくvectorなのでsetにしていろいろ頑張る必要がある。掃き出し法の気持ちになればできる。 一応。 まとめ 定期考査
余裕のある人間になりたい 解いた問題 AGC-黄。bit全探索が見えるが判定にO(N^2)ぐらいかかるので間に合わない。他のこともしつつ4時間ほど考察をしたが解法は浮かばず… 解説を見ると天才が書いてあった。ABC355Fの話と少しだけ似ていると思った。ある数字を消して、答えが構築できなくなったらその数字は必須、みたいな条件を使うとうまくできる。 まとめ 明日はABC。ABC前に行事があって忙しいのでABC355Gを通す時間が無さそうだがいつにしようか…
5月があと1日で終わってしまう～ 解いた問題1 AGCの黄Diff。思ったより簡単だった、というかこういう数え上げは得意なのかも？寄与を考えるみたいなことをすればよい 解いた問題2 2-SATを使うんですね！…どう使うんですか？となって解説を見た。2-SATはあまり見かけない気がするがいつか役に立つときが来るだろう 解いた問題3 最大流ですね！…どう使うんですか？となって解説を見た。二部マッチングに帰着できるのは前に見た気がするが身に付いていなかった。これはよく出
忙しい充実した一日だった。 今日のアルゴリズム：なし 簡易LARSCHをちょっと眺めて、「こんなんで本当にできるのか…？」をしただけ。明日は簡易LARSCHを使ってABC355Gを解説ACしようかな 解いた問題1 ARC青。どちらの花束でも、2種類を一本ずつは使うのでまずはそれを引いてみると見えやすい。二分探索。 解いた問題2 全然わからんので解説を見た。区間DP、天才か…となった。 あとこれも通した（2回目？） 1回目で自力ACできたかなり好きな問題。両側か
寝坊した。 今日のアルゴリズム：Monotone Minima （直接貼ると重いのでリンク）https://speakerdeck.com/tatyam_prime/monge-noshou-yin-shu tatyamさんの「Mongeの手引き書」を読み進めた。Monotone Minimaは、一度だけ使ったことがありましたがほとんど仕組みを理解していなかった。今日このスライドを読んで完全に理解することができた！ 実装も人のコードを見ずにスムーズにすることができた。
お久しぶりです。ぴったり1か月空いたらしい。 日々の精進の記録あるとやっぱり良いなと思ったので再開してみます。またすぐ更新途絶えるかもしれないけどできるだけ続けられたらいいなと思っています。日記を書いていると、「日記に書ける程度の精進はしたい」って意識も生まれますし！ 今日のアルゴリズム：黄金分割探索 前回のABC-Gを理解するうえでさまざまな知識が必要になることがわかったので、一つ一つ理解していこうと思いました。というわけでまずはどの解法でも使われている黄金分割探索につ
この記事はABC351の直後に書いています。あんまり読んでいてたのしい記事ではないと思うので読まなくて良いです。それでも読みたいという物好きの方、ありがとうございます 言い訳から入ろうか いや、まずは結果を ひどい語彙力をしているが、本当にこれしか感想が無い。 いや、CとDで地味に沼ったなあというのはあったけど解法が見えなかったわけではないので。 問題はE。「マンハッタン距離は45度回転」という典型の問題だと思う。自分はこれが苦手だ、というか自力で解けたことがほとんどな
雨でした。 今日のアルゴリズム クエリ平方分割です。前回のABC-Gで出た。平方分割の考え方をクエリに適用する方法を考える感じかな 解いた問題 クエリ平方分割の練習用に前回のGを解いた、というかクエリ平方分割を使う問題があまり出てこなかった。別解として出ることが多いのかな…？ 解いた問題2 畳み込みです！知らね～～ ちゃんと理解しないとな… まとめ 明日はLinkCutTreeのつもりだったけど変わるかも
けっこう期間が空いちゃった。書きたくなったので再開 今日のアルゴリズム 新しい知識に触れるのは良いこと。というわけで今日はLowlinkです（今更） いや～酷い。これ学んだって言えるのだろうか… とりあえず使えなくはない…？よくわからない… 典型90 bitDPやるだけ。 O(DN2^N)で書いて、あ～これO(D(2^N+N))になるなあと思って高速化したら大して変わらず。9倍ぐらい速くなった。 まとめ ここに書ける程度には毎日精進していきたい。これぐらいの軽い
頭が痛いです。 解いた問題 O(ND^3)がすぐに見えますが流石に捨てます。遷移先が斜めに連続しているので斜めに累積和をとっておけばO(ND^2)におさまりそうです。TLを見ると6secなので間に合います。実装…できません！！！！！ 斜めに遷移するDPに慣れていないので実装ができない、というか頭が壊れる。落ち着いて紙に書いて整理するのが重要そうだが… まとめ タイピングが最近早くなってきているのを実感する。良いことです 実装力が無い、特に知らない問題や慣れていない問題
仮入部二回目でした。あんまり新しい人は来ませんでしたが、前回来た人たちが今回も来てくれて嬉しい 解いた問題 DP。こういうパターンのDPを部分列DPと言うらしい…？あまり得意では無さそうなので対策しておきたい。 まとめ あとEDPCを3問解きました。朝練もいつも通り。 ゼータ変換を履修したい
日曜日でした。 解いた問題 どこからどう見ても最小カットですね。ところで復元はどうするんでしたっけ…？となっていました。ACLは復元も含めてできるらしいです。すごい。 まとめ あと、素因数分解を3倍高速化（2と3を先に処理する）しました。日曜日は一応休むのを重視しているつもりです。スニペットの整理をしたいなあって最近思っているのですが手を付けられていない。あ、EDPCもう一周やらないと！
ABCでした。Eでしょうもないミスでひたすら時間を溶かしてしまった、大反省… しょうもないミスをしないようにするために朝練などで場数を踏んでいるのになぜ改善できないのか… 普段から、しそうなミスを意識しながら実装するようにしてみようかなと思う。
1日サボったのはわざとです。たぶん。 今日は1年生の仮入部初日でした。かなりうまく行って良かった。 解いた問題1 EDPC最終問題。 ちゃんとした（単調性がない）CHTもライブラリ化しておきたいなという気持ちになった。 解いた問題2 ABC-橙 Aを全探索すると条件にハマるBはN-1-Aの約数なので全探索…できない！困った！！ 解説を見るとA-Bを全探索し、ずらすのをうまくO(1)でやっていた。式変形力～～ まとめ 式変形できるようになりたい。
新学期です！！後輩がたくさん入学してきた。TCAにも既に6人が入部を確定させていて嬉しい限りです。 解いた問題1 ABC-橙 フローにしか見えない…絶対フローだこれ…から全く考察が進まず… 辺の貼り方はやっぱりいろんな問題を解いて身に着けていくしかなさそう。というか、ちゃんと解けなかった時に辺をどうしてそういう貼り方をしているかをしっかり理解した方が良さそうだなあ。 解いた問題2 EDPC-Yです。座圧かな？でも座圧するとごちゃごちゃになるなあ 解説を見ると包除的なこ
今日は入学式。明日から新学期です。高2になります。 解いた問題1 それぞれの点の寄与を考えて、包除原理かなあ…でも同じ座標にある点の処理がめんどいしなあ…と思っていたら同じ座標にある点が制約で省かれていた（制約はちゃんと読もう） 2次元動的BITで点を管理するとTLEしたのでx昇順/x降順で二回、セグ木を使いながら走査して、各点の左上/右上/左下/右下にある点の個数を数えた。平面走査っぽいかも。 まあそんな感じでAC！ 解いた問題2 はいはいセグ木の基本操作書けばいい
