2026年2月18日水曜日

AtCoder Regular Contest 214

　ABの二完。ARCで連敗が続く。

コンテスト後のツイート


D - Distinct Sum Grid Path

　コンテスト直後にしばらく考えても解けなかったが、今考えたら簡単に解けた。
　1から順に数字を作っていこうと考えるのは自然（コンテスト中も、まず考えたはずなのだが……）で、右上ルートより左下ルートが大きくなるようにしようとしたら自然に構築できる。

　普段なら解ける問題という気もするので、あまり解けなかった原因を考えてもしょうがない気もする。
　が、こういうのが解けるかどうかでレートには大きく差が出るんだよねぇ。









時刻: 0 件のコメント:
ラベル:

yukicoder contest 297

 　Bまで。コンテスト後にCをAC。


No.1520 Zigzag Sum

　自力AC。
　実験したらACできたが解説の考え方を再現するのは難しい。

No.1521 Playing Musical Chairs Alone

　自力AC。
　行列累乗が思い浮かべば難しくない。

　一回遷移行列を間違えた（行と列を逆にした）けど、それでsample通るのね。
時刻: 0 件のコメント:
ラベル:

2026年2月17日火曜日

yukicoder contest 292

　Cまで。Dはコンテスト後にAC。



No.1490 スライムと爆弾

　自力AC。
　簡単だったけど、

・各マスのダメージがいくつかを求めるためのimos法
・矩形のダメージの総和を求めるためのimos法

　を両方やるので、二回累積和を取ることになるのが面白かった。




時刻: 0 件のコメント:
ラベル:

2026年2月15日日曜日

AtCoder Beginner Contest 445

　Fまで六完。Gも解法はあっていた。惜しかった。

コンテスト後のツイート

G - Knight Placement

　フローした後、最大独立集合を求めるために色を塗るところで、色を塗った後間違ってもう一回初期化してた（塗った色を消していた）のが敗因だった。一行消したらバグは取れ、そのままだとTLEしたけどfloat("inf")を1<<63に直したりしたらACした。
（ただし、1<<30にしたらもっと早くなるかな？　と投げてみたらTLEしたので、運が良かっただけみたい。コンテスト中のACは厳しいかも？）

　惜しかった……。




時刻: 0 件のコメント:
ラベル:

2026年2月7日土曜日

yukicoder contest 492

　A一完。Bを考えているとき睡魔に襲われてしまった。

No.3441 Sort Permutation 2

　自力AC。

　index x→P[x]に辺を張り連結成分ごとに分解した後、その差のgcdがxなら、xの約数たちには連結成分-1をプラスする。
　と、これが必要条件なのはコンテスト中に分かっていたが、それ以外にも答が増えることはありそうに思い、たとえば、「3 4 2 1」のとき2を使わないようにできるか？　と考えていた。
　コンテスト後に実験してみると、結構簡単に使わずにソートできたので、上で書いた必要条件が十分性を満たしそう、と思って提出したらAC。

　なお、これだけで良いことは、公式解説を開いても「帰納法などで証明可能」としか書いていなかった。現在も証明方針が分かっていないが、やろうとすれば自力で証明できるのだろうか（やる気はない）。

　
　
時刻: 0 件のコメント:
ラベル:

2026年2月2日月曜日

デンソークリエイトプログラミングコンテスト2026（AtCoder Beginner Contest 443）

　Eまで五完でレートをまた下げる。

コンテスト後のツイート

F - Non-Increasing Number

　解法ツイートを見たら当たり前に感じたが、実際にACするのは結構大変だった。

　最後に使った数字がxで、Nで割った余りがyのとき……というDPを考えるしかなさそう。
　この(x, y)が被ってはダメ、という状況になれば状態数を抑えられる。そのためには、上の桁につけていくのではなく、下の桁に数字を付け足していけば良い！（桁DPで下の桁に足していくような発想ですね）

　あとはDPの復元をすればOK。

　なのだが、最小性を言うため、どの数字を使うか、という順番も大事。
　普通にやればこの順番を満たすのだが、ソートしたりしてしまいハマった。

　一桁のときは、
・[(1, 1), (2, 2), (3, 3), (4, 4),...]
　となっており、これが一番上の桁なのだがから、
　左から順番に、かつ次に使う数字が小さい順に探索していけばOK。

G - Another Mod of Linear Problem

　解説放送を見てAC。

　floor sumを使うと言われても、自力では全く分からなかったのでコンテスト中に解くのは厳しかった。

　解説放送のように、X_k>C（定数）の場合を絵で理解できていることが大事な気がする。それが押さえられていれば応用できそう。
時刻: 0 件のコメント:
ラベル:

2026年2月1日日曜日

yukicoder contest 319

　ABの二完。難しくないですか？


No.1715 Dinner 2

　解説AC。

　連続して同じ料理を食べてはいけないということから、二回の食事をまとめて行うことばかり考えてしまい、

・DP[j]＝最後にjの料理を食べたときの元気の最大値

　という簡単なDPの立式を考えられなかった。
　NとDが10^3以下という制約を見ても、自然なDPの立て方。これを思い付けないのはまずい。

No.1717 Levi-Civita Triangle

　一応自力AC。

　1と2が隣り合う状態は作れないと気付き、大抵の場合は0になるんじゃないか？　と思ったがそれだけではダメ。
　実験すると、1になるパターン、2になるパターンは3種類ずつしかないと気付いてAC。

　初手から実験すべき問題でした。

No.1716 Bonus Nim

　自力AC。

　普通のNimよりBobが勝つのは難しそう。
　で、最初Bobは勝ちがないのでは？　と思ったのだけれど、sampleに一個勝つ例が書いてあり、真似っこ戦略なら勝てると分かった。

　これ以外ないと予想し、AC。

時刻: 0 件のコメント:
ラベル:
登録: コメント (Atom)