AB二完だが、BはHackされた。
No.3250 最小公倍数
マージテクの練習問題だった。
ただ、PyPyだとTLEし、PyPyで通している人もいなかったので、PyPyのコードをChatGPTにRUSTに翻訳してもらってAC。
今はこういう翻訳もAtCoderでは禁止されているし、この問題はアルゴリズムの練習問題みたいなものだから、自力で書いた方が良いとは思うけど。
2026年6月21日日曜日
2026年6月19日金曜日
Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)
Dまで。二時間近くあってE通せないのは悲しい。
コンテスト後のツイート
D (長さ%3,0の個数%3)でbeautifulかは決まるのでDP。だだし、一回も反応しないものはダメなので、後で引く（尺取り）。
— titia (@titia_til) June 18, 2026
E 必要条件で決まるものを決めた後、Aを置換に分解して当て嵌めていけば良いと思ったが上手く出来ず。
E. Permutation Commutation
コンテスト後、落ち着いて考えたら自力でACできた。
Functional Graphと見て、サイクルに分解する。
たとえば、
A=[4, 5, 1, 3, 6, 2]
を考えると、(1,4,3)と(2,5,6)というサイクルがある。
これに対応するBは、(1番目, 4番目, 3番目)が(1,4,3),(4,3,1),(3,1,4)もしくは、(2,5,6),(5,6,2),(6,2,5)でなくてはならない。（2番目, 5番目, 6番目）も同様。
ここまではコンテスト中に実験で分かっていた。i→A[i]とうつるとき、対応するいずれかのサイクルでindexを一つずらしたように入れなくてはいけない、と。
しかし、さらにサイクル長に関して条件がありそうだとは思ったが、上手くまとまらなかった。
実際は、同じサイクル長のものでないといけない。サイクル長3のものをサイクル長1のもので埋める……みたいなことができる気がして混乱してしまったが、こういうことができないと気付き、同じサイクル長のものしか使えないと分かった。
なので、サイクル長で分類すればACできた。
2026年6月15日月曜日
第七回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 222）
Aしか解けず。
コンテスト後のツイート
第七回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 222） A一完でおしまい。
— titia (@titia_til) June 14, 2026
A LRをlの昇順にソートし、rもr_i>r_i-1を満たすもののみ残す。あとは使えるものをheapqで管理して貪欲にやっていく。
B 三分探索を二回したら解けるのでは？→WA&TLE
C 左右の三列に寄せるのでは？→WA
B - Circular RPS
解法ツイートを見てAC。
コンテスト中は、正当性の怪しい三分探索にいってしまいダメだったし、a=0,b=cのようなケースも思いついていなかったため、全然ダメだった。
冷静に、勝者が一人の場合、二人の場合、三人の場合について立式していったら解けた。配列から「二つの要素を選んで1ずつ減らす」という操作が何回できるか？（最大値が他の要素の和以上かによって場合分け） という頻出問題を意識したら分かりやすい。
ただ、a=0,b=cのようなケースは全く頭から抜けていたので、コンテスト中にACできた可能性はなさそう。
C - 2 Directions vs 4 Directions
解法ツイートを見てAC。
分かってしまえばなんてことはない。
三列ずつ動く感じになるというのはコンテスト中も考えていたが、端にいかないとそこからはみ出てしまうと勘違いしてしまった。実際は、横三マスをキープしたまま、一つずつずれて上下に動ける感じになる。
手痛い考察ミスで、そういう変な思い込みをしてしまっては修正は難しかったと思うが、もっと落ち着いて考えられていたなら正しい考察ができていたようにも思う。
AとBをすんなり通せていたら違ったのでは？ とも思うけど、Bがすんなり通せた可能性はなさそうなので厳しい。
D - Shift and Add
解説AC。
下八桁くらいの数字と、その上の桁に9が何個続いているか？ を持ってDPすれば良いと思って実装を始めたが、TLEやWAが出てダメ。
まず、下八桁ではなく九桁が必要。そして、9が何個続いているか？ ではその個数が複数あったときに計算量を減らせない。なので、「1を足したときに桁和がいくつになるか？」を持たなくてはいけなかった。
また、桁和を求めるときは、int(str(x))を足していくのではなく、x%10を足してx//=10する、という風にした方が速い。その辺に気を配らないとTLEは取れなかった。（し、codonにしないとTLEは取れなかった）
おおまかな解法はあっていたが、そこから実際にACするまでは遠い問題だった。
2026年6月13日土曜日
yukicoder contest 501
A一完。
コンテスト後のツイート
yukicoder contest 501 AだけAC。
— titia (@titia_til) June 5, 2026
連続する数字をまとめて管理するようにしたら色々やりやすかった。
No.3566 Subsequence Sum
解説AC。
そもそも通常の部分列DPでK=1の場合を解くことができなかったのは反省。
しかし、そこを理解しても難しかった。
まず、部分列DPでNEXTを使わずにやる方法があることを知らなかった。それを行列累乗に持ち込むためにどういうコードを書けば良いかも分かっていなかった。
勉強になった。
No.3567 Modulo Grid
実験して、行の数が足りていればいけそうな解法と、ギリギリでも大体大丈夫な解法を作り、組み合わせることで無理矢理ACしたが、多分Hack caseがあります……。
とりあえず、良いペアという条件が、gcd(a,M)%gcd(b,M)==0 or gcd(b,M)%gcd(a,M)==0と表せることだけは理解しておこう。（ACしたのにそれすらよく分かっていなかった）
2026年6月7日日曜日
AtCoder Beginner Contest 461
Dまで四完で破滅。Eは一分後に通ったが。
コンテスト後のツイート
E oooxxxと並んでいて、クエリが来たら一番後ろへ移動させると考える。oの後ろにあるxの合計が答え。セグ木で解けるが、SortedSetが必要と勘違いし迷走
— titia (@titia_til) June 6, 2026
F - Total Product is N
解法ツイートなどを参考に、Aを降順に列挙するDFSを書いたら（codonなら）通った。コンテスト中の提出（はmodの余りを取るの忘れたけど）とあまり本質的には違わないのだが。
2026年6月5日金曜日
AtCoder Beginner Contest 460
Eまで五完。このFは思いつけない。
コンテスト後のツイート
AtCoder Beginner Contest 460 Eまで。
— titia (@titia_til) May 30, 2026
B abs(r1-r2)<=d<=r1+r2
C 大きい方から貪欲
D とりあえず二回操作を行う。その後、"#"から偶数距離にあるもの。
E yの桁を決めると、k*x+y=x+y(mod M)という形になる。yが消える、l*x=0となるようなN以下のxを数える問題になる。gcd(l,M)を考えると計算できる。
F - Farthest Pair Query
解説放送を見てAC。
セグ木と言われても、何を乗せるか分からず、解説放送を二回見て（解説も読んで）ようやく理解。
分かってしまえば当たり前に思えるが、全く発想になかった。
「その頂点集合のみを見たときの、直径の端点」を乗せれば良い。
登録:
投稿 (Atom)