2023-01-01から1年間の記事一覧
初めに atcoder.jp 解説放送で AC です 解法 中央値の最大化で手が止まります. では最小値の最大化は? 二分探索ですね 同様にできます. 具体的には, := を適当に xor を取ったもので 以上が何個作れるか という関数を考えます. この値が 以上であれば, 中央…
初めに atcoder.jp 解けなかったので 敗因 最小値が変わらないような操作はまとめてしまってよいなみたいなことを考えた。 (正直、眠くて頭が働いていない...) 当然 WA でした... (でもどんなケースが WA なのかは分からない...) atcoder.jp 解法 gcd は変わ…
初めに atcoder.jp 解けなかったので 敗因 keisuke6 と相談, 6「貪欲でよくね」 5「でも aaaaa とかバグらない?」 6「たしかに」 解法 方針はほぼ同じ. 3 文字を分割する際に 1, 2 で切るか 2, 1 で切るかどちらかを選ぶことができるが, 3 文字の直前とこの …
初めに atcoder.jp 解けなかったので 敗因 解法 座標圧縮などをして のグリッド上の問題に言い換えておきます. また行を固定した際(行 とします)に, 列をどう決めるかを考えます. まず列(列 とします)の総和を求めておきます.総和の大きい順に選んでいってい…
初めに atcoder.jp 解けなかったので 敗因 精選 150 問 を解いています. 半分全列挙の問題というところはヒントとして知っていたけれど, 解法がよく分かりませんでした... Unite 部分が難しくて解決方法がまったく思いつかなかった. 解法 グラフ上で考えて …
初めに atcoder.jp 解けなかったので 敗因 分からない... 0 以外の数字を sort して, そこに 0 を変化させた数字を挿入するみたいな考えをしましたが, 全部 0 の時にうまく行かなかった. 解法 期待値に縦横反転(造語)を適用する. 要するに だと考えづらいの…
初めに atcoder.jp 解゛け゛ま゛せ゛ん゛で゛し゛た゛... 敗因 最初は変な風に誤読をしていて 2 ペナをしました. そのあとある数 が与えられるのでそれが に存在するふたつの数の積で表せるかを判定する関数みたいなものをつくりました. 当然, 最後の方は と…
初めに atcoder.jp 解けなかったので 敗因 := と の集合が等しくなるような最小の := と の集合が等しくなるような最大の みたいなものを考えて, set の比較が O(1) でできると信じていたので裏切られて TLE. (WA はなぜか分からない) atcoder.jp 解法 サイ…
初めに atcoder.jp 解けなかったので 敗因 典型1 最大/最小から K 番目の要素は答えで二分探索する←知ってた 典型2 ふたつの組み合わせの数え上げは, 片方を固定してみる←知ってた 典型3(?) 砂糖/食塩水の問題はある濃度に達するまでの砂糖の量とかをみると…
初めに atcoder.jp 解けなかったので 敗因 実はけっこう前から温めてた問題. 最初は精選100 + 50 問で, RMQ の練習問題としておいてあったのを見て. 普通に考察すると何回魔法を使うかで場合分けして最小値をうまくとるみたいな噓貪欲をはやして 9 WA (In 21…
初めに atcoder.jp 解けなかったので 敗因 昨日解いた AGC020B みたいに, 各山について最小値 / 最大値がひとつ前から線形に求まるか...? みたいなことを考えていました. 実際は決まるのは最大値だけなのでそれは考えなくてもよいです. (よく考えると最大値…
初めに atcoder.jp 解けなかったので 敗因 例えば は必ず 2 でないといけなくて, は 2, 3 でないといけなくてみたいなこと( -1 のときはどうなるのかを)を考えていました. ( -1 になるときを中心に考察を進めても難しいので) から線形にできる方法を考えるべ…