AHC中だったのでAだけ解いて撤退。
Bは読んで多少考えたので、すぐ解けたのなら解いていたと思うが。
No.3448 ABBBBBBBBC
解法は自力で分かったが、WAだったためテストケースを見てAC。
こういうのを合わせるのどうすれば良いんだろう？ 本番ならランダムテストを書いて頑張ると思うが、短時間で解ける気がしない。
割り算の感覚（商と余りなど）が重要そうだけど。
titiaのノート
2026年2月27日金曜日
2026年2月25日水曜日
AtCoder Regular Contest 215
Cまで三完。良い成績とはいえないが、ARCで黄パフォを出せたのは久しぶり。
コンテスト後のツイート
B 各数字を0と1で塗り分け、数字が異なる間に仕切りを入れる。できるだけ同じ色にしたいので貪欲。
— titia (@titia_til) February 22, 2026
C (x,y,z)と(a,b,c)についてa>=x or b>=y or c>=zなら勝敗が付かないのでUnion-findでくっつける。くっつけたあと、(min(x,a),min(y,b),min(z,c))にして良い。x,y,zについてソートし大きい方から処理。
D - cresc.
解法ツイートを参考にAC。
Aの一つおきの配列が広義単調増加になることはコンテスト中に気付いていた。しかし、それだけだと重複があってダメ。
じゃあ、重複をなくすためどこか固定・場合分けすればいいのでは？ と考えるのが重要。
A[0]=0とした場合、A[1],A[3],...は全ての広義単調増加列を取りうる。
それ以外の場合、A[奇数]の最後の値がMにならなくてはダメ。なぜなら、A[偶数]を全てｰ1したものが同じ配列を作るから。
これで重複なく全て数えられているので、二項係数を使って計算できる。
初項を固定・場合分けする発想がもてれば決して難しくないし、重複をなくすためにどこか固定してみようと考えるのは自然。
今見ると難しくない気がする。
また、二項係数の何か（積か和か）になりそうなことはコンテスト中から見当がついていたし、実験コードも書いていた。
それで解けないのは、こういう二項係数を使う数え上げに苦手意識があるのかなぁ、と思ってしまう……。
AtCoder × Engineer Guild オンサイトコンテスト ～ACからはじまる27卒キャリア～予選 （AtCoder Beginner Contest 446）
全完できた。
簡単めの回とはいえ、全問解けると嬉しい。Gは想定の計算量ではなかったようだけども。
コンテスト後のツイート
F 可能かどうかは、max(fr,to)ごとに辺をもっておき、グラフを更新していく。可能な場所が増えたらDFS。消す個数は、iまでの頂点から行ける頂点を列挙。
— titia (@titia_til) February 21, 2026
G DPで更新する候補が多くなさそう。候補を持っておき、indexが進むごとに候補を減らした。次の場所をbisectで探したらTLE。bisectをなくしてAC
2026年2月18日水曜日
AtCoder Regular Contest 214
ABの二完。ARCで連敗が続く。
コンテスト後のツイート
AtCoder Regular Contest 214 AB二完。Dが解けず。
— titia (@titia_til) February 8, 2026
A 斜めを一致
B ある点を0とし一回計算すると、答えはそれらにxor xしたもの。各bitについて、立っている個数と立っていない個数を計算。元のN+1個と比較して、同じものは必ず使う。（十分性は分からず）
D 2ベキで作ろうとしたがN=13を満たせない。
C - Divide into 4 Teams
解説放送を見てAC。
コンテスト中、SUM/2の二つに分けることは考えたが、その後何も思いつかなかった。
ランダムテストを書いて実験すべきだった、ということはあるかも。SUM/2の二つに分ける方法と、答えとを比較したら答えが導けた可能性はあるね。
今回のSUM/2の二つに分ける方法みたいに、これを使いそうだと感じたのなら、とりあえずそれを求めてみて答えと比較して考えるのは一つの方針としてありそう。
D - Distinct Sum Grid Path
コンテスト直後にしばらく考えても解けなかったが、今考えたら簡単に解けた。
1から順に数字を作っていこうと考えるのは自然（コンテスト中も、まず考えたはずなのだが……）で、右上ルートより左下ルートが大きくなるようにしようとしたら自然に構築できる。
普段なら解ける問題という気もするので、あまり解けなかった原因を考えてもしょうがない気もする。
が、こういうのが解けるかどうかでレートには大きく差が出るんだよねぇ。
yukicoder contest 297
Bまで。コンテスト後にCをAC。
No.1520 Zigzag Sum
自力AC。
実験したらACできたが解説の考え方を再現するのは難しい。
No.1521 Playing Musical Chairs Alone
自力AC。
行列累乗が思い浮かべば難しくない。
一回遷移行列を間違えた（行と列を逆にした）けど、それでsample通るのね。
2026年2月17日火曜日
yukicoder contest 292
Cまで。Dはコンテスト後にAC。
No.1490 スライムと爆弾
自力AC。
簡単だったけど、
・各マスのダメージがいくつかを求めるためのimos法
・矩形のダメージの総和を求めるためのimos法
を両方やるので、二回累積和を取ることになるのが面白かった。
2026年2月15日日曜日
AtCoder Beginner Contest 445
Fまで六完。Gも解法はあっていた。惜しかった。
コンテスト後のツイート
G 二部グラフの最大独立集合だと思い、https://t.co/xw3a3nUvRfを参考に実装したが答えが合わず終了。
— titia (@titia_til) February 14, 2026
この前のARCでこの話が流れてたから思いつきやすかったけど、実装していなかった。
G - Knight Placement
フローした後、最大独立集合を求めるために色を塗るところで、色を塗った後間違ってもう一回初期化してた（塗った色を消していた）のが敗因だった。一行消したらバグは取れ、そのままだとTLEしたけどfloat("inf")を1<<63に直したりしたらACした。
（ただし、1<<30にしたらもっと早くなるかな？ と投げてみたらTLEしたので、運が良かっただけみたい。コンテスト中のACは厳しいかも？）
惜しかった……。
登録:
コメント (Atom)