この記事は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 はいはいセグ木の基本操作書けばいい
今日は部活がありました。明日は新入生の入学式＆部活勧誘！ 解いた問題1 昨日解説まで見て、なるほどなあと思っていた問題。不変量の探し方と、共通している部分があるかの判定を文字列アルゴリズムで行うのがすごい。勉強になる問題だった。 解いた問題2 とりあえず、隣に大きいものがあったらそれを先に操作しないといけないのはわかるが、数え上げをどうするかわからず…連結成分に分解してそれぞれの並べ方をかけていい感じに出してみたりもしたがサンプル3が合わず。 挿入DP、というのがある
AHCでした。びみょ～～～ ビムサしか書けないし上手いビムサが書けない。まずは貪欲をしっかり考えるべきなのかなあ AHC精進もちゃんとしたいですね～… 解いた問題 ABC-赤です。ABC-Dの中で最もDifficultyが高い問題であり僕にとってのABC-Dのラスボスでした。 当然解けないので（え？）解説を見ると、普通にbitDPでびっくり。ここから改善があるんだろうと思ったらなくてびっくりでした。なんでこれこんなにDiff高いんだろう…？まあ置ける条件を考えるのが結構難
ABCでした。悔しい～～～ Fでbitset高速化が公式解説の解法で、う～む…って気持ちに。こういう負け方もあるんだなあという学びになった。レートは減らなかったけど、2400入黄ラインに行けなかったので微妙… 解いた問題 期待値。がんばるとできる。自力AC！ まとめ ABCの振り返りちゃんと書きたいけど眠いので少なくなってしまう。とりあえず今言えることは悔しい～～です。まあ相性が悪い回だっただけなので、気を取り直して頑張っていこうと思います。
今日は部活がありました。 解いた問題1 ABC-黄（ほとんどABC-黄しか解いてないしもう書かなくていいか…） 全方位木DPですね、はい で解ければよかったんですがやっぱまだ慣れてないですね載せるのに。かなり時間がかかってしまった。でも自力ACできたのでOK！ 解いた問題2 木DPだろうなっていうのと多項式のかけ算を使えば計算量を落とせてできそう、までは分かったのですが状態の持ち方が思いつかず…2つの状態で考えていたのですが、3つか4つが正しかったらしい。状態数は減ら
4月4日ですね。（？） 解いた問題1 ABC-黄 規則性を求めていい感じに計算するだけ！と思ったら不等号を誤読していて永遠に答えが合わなかった…ほぼ合っていたので悔しい。問題文はちゃんと読みましょう(n敗) 解いた問題2 ABC-黄 制約的に桁DPしかない。素直に出現した数字を管理するとTLEなので、個数が同じ場合を同一視したい。すると、N未満であることが確定した時点でいろいろ同一視できることがわかるので、あとはDPをがんばると解ける。自力AC！ 解いた問題3 A
ほぼ人生で初めてゲーセンに行ってきました。音が大きくてちょっと体力削られるのがつらいけど概ね楽しい場所ですね。 解いた問題1 ABC-黄色。昨日解説だけ見て寝たので実装をがんばった。が、WAが取りきれず… 時間を有理数で管理しないとダメだったらしい。解法はわかりやすくても実装ミスをしそうなポイントがいくつかあり、なかなかいい問題だなと思った。 解いた問題2 ABC-黄色。Ex問題！！自力AC！！ にころさんが黄色3問のバチャを開いていたので参加したところ1問目がこれ。
