Cまで。Dはコンテスト後にAC。
No.1490 スライムと爆弾
自力AC。
簡単だったけど、
・各マスのダメージがいくつかを求めるためのimos法
・矩形のダメージの総和を求めるためのimos法
を両方やるので、二回累積和を取ることになるのが面白かった。
titiaのノート
2026年2月17日火曜日
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は厳しいかも？）
惜しかった……。
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。
なお、これだけで良いことは、公式解説を開いても「帰納法などで証明可能」としか書いていなかった。現在も証明方針が分かっていないが、やろうとすれば自力で証明できるのだろうか（やる気はない）。
2026年2月2日月曜日
デンソークリエイトプログラミングコンテスト2026（AtCoder Beginner Contest 443）
Eまで五完でレートをまた下げる。
コンテスト後のツイート
デンソークリエイトプログラミングコンテスト2026（AtCoder Beginner Contest 443）Eまで。FもGも分からず。
— titia (@titia_til) January 31, 2026
B 愚直でOK
C シミュレーション
D 左右から更新
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（定数）の場合を絵で理解できていることが大事な気がする。それが押さえられていれば応用できそう。
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。
2026年1月28日水曜日
JPRSプログラミングコンテスト2026#1（AtCoder Beginner Contest 442）
Fまで六完。Eで偏角ソートに苦戦。自分で実装したが遅かったためレートを落とす。
コンテスト後のツイート
あ、Fセグ木DPって書いたけどセグ木使ってない。
— titia (@titia_til) January 24, 2026
最初セグ木でやろうとしていたけど、実装途中で累積minで良いことに気付いてそっちで書いたんだった。
G - Lightweight Knapsack
解説AC。
6でまとめるというヒントは見たのだが、ピンと来ず、解説を見てAC。
何個か取った後、貪欲に帰着するというのはなるほどです。
条件反射で、「ナップザックならばDP」と考えていたので、自力でこの解法に至るのは厳しかったと思う。
Codeforces Round 1075 (Div. 2)
C1まで三完。C2もD1も難しい……。
C2. XOR-convenience (Hard Version)
分からず解説を見てAC。
2ベキだと解が存在しないことは分かるが、そこからどうすれば良いか分からなかった。
nが奇数ならC1のままでOK。
nが偶数でもC1の解法を利用を考えるべき、というのが重要か。
そのままだと、最初の要素が上手くいかないので、そこをどこかとswapすれば良いのでは？ と考え、最上位bitに思い至れば構築方法が分かる。
偶数の場合、全く別の構築方法が必要だと考えてしまったのがまずかったかもしれない。が、普通に難しい気がする。
D1. Little String (Easy Version)
苦戦したが自力AC。
こちらはcについてはあまり考える必要がなく（答えがn個程度の数の積になるため）、数え上げを行う問題。
まず、S[0]="0"やS[-1]="0"のときは存在しない。
それ以外のとき、0001という部分を一度に考える。
012までの位置関係が決まっているとし、そこに3～6を付け加えるとすると、6はその最も左か最も右におくしかない。そして、3～5は端以外のどこにおいても良い。
なので、2（左右）*3*4*5をかける。
……というのを繰り返していく。
かなり長いこと実験したら気付けたけど、難しかった。
登録:
コメント (Atom)