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 件のコメント:
ラベル:

2026年1月28日水曜日

JPRSプログラミングコンテスト2026#1（AtCoder Beginner Contest 442）

　Fまで六完。Eで偏角ソートに苦戦。自分で実装したが遅かったためレートを落とす。

コンテスト後のツイート

G - Lightweight Knapsack

　解説AC。
　6でまとめるというヒントは見たのだが、ピンと来ず、解説を見てAC。

　何個か取った後、貪欲に帰着するというのはなるほどです。

　条件反射で、「ナップザックならばDP」と考えていたので、自力でこの解法に至るのは厳しかったと思う。





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

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をかける。
　……というのを繰り返していく。

　かなり長いこと実験したら気付けたけど、難しかった。

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

2026年1月27日火曜日

AtCoder Regular Contest 213 (Div. 1)

　Aしか解けず。そのAで酷く時間がかかってしまった。

コンテスト後のツイート


B - Hamming Distance is not 1

　ヒントだけ見て解こうとしたが、全然答えが合わず20ペナ以上を重ねた。

　bitcoutを2で割った余りが重要なのは分かる。
　bitcountが奇数のもののみ、もしくは、偶数のもののみを集めたものは条件を満たす。

　ところで、2nと2n+1はbitcountの偶奇が必ず異なる。（これを利用することはコンテスト中気付いていなかった）
　なので、全体の約半分は必ず含めることができる。

　問題は、Lが奇数、Rが偶数のとき、L～lastまではbitcount偶数（奇数）、last+1～Rはbitcount奇数（偶数）のものを採用すると、答えが一個増える場合があること。（このことにはコンテスト中気付いていた）

　そのようなlastをどう求めれば良いか？　というのが分からなかった。

　あるbit iについて、R^(1<<i)がL以上だったとする。すると、それとRが同じグループに入っていてはいけない。なので、lastはR^(1<<i)以上と分かる。
　これを繰り返していけば、lastの候補を絞っていってACした。

　公式解説では、LとRで異なる最上位bitに着目しているよう。なるほど。結果的には同じものを求めていそうですね。
　二部グラフへ持ち込む証明は思いつかない。というか、最大独立集合（参考）について理解していなかったことに気付きました。
時刻: 0 件のコメント:
ラベル:

2026年1月25日日曜日

yukicoder contest 491 Go on Back!!

　Cまで三完。


No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?

　一応自力AC。

　二分探索し、P番目の価格の値が求まれば、復元は難しくなさそう。が、コンテスト中は二分探索の判定方法で詰まり解けなかった。

　ソートして二分探索して……では、同じ色の場合の処理が難しい。
　こういうときは、片側だけ色で分類すると良い。半分全列挙のときと同じ感じでやれる。
　
　各トップスに対して、
・全体で何個が価格X以下か？
・同じ色のものについて、何個が割引せずに価格X以下で、割引した後価格X以下か？

　はどちらも二分探索で求められるので、判定できる。

　復元は簡単だと思ったが、復元でも詰まった。

　同じ色のものが答えになるときは簡単。
　そうでないときは、価格Xになるものの個数がbisect(A,X)-bisect(A,X-1)で求まることを利用した。

　全体で、価格Xになる個数と、同じ色で価格Xになる個数を比較し、全体の方が多くなっていればOK。

No.3437 [Cherry 8th Tune C] Silhouette

　自力AC。

　三点がどこに映るかを計算し、三角形の面積を求めれば良い。
　ただ、最初から割り算をmod 998244353で行うと正負が分からなくなる。なので、分数で計算し、最後にmod 998244353の形に直した。PythonのFractionをそのまま使ったらTLEだったが、入出力高速化してAC。

　模範解答は、三角形の向きを行列式で求める方法らしい（よく分かっていない）。

No.3438 [Cherry 8th Tune D] 競プロは向いてない

　自力AC。

　実験したら、凸包内部にあるときはNoそう。具体的な（A,B）を求める方法は分からなかったが、凸包の前後の頂点だけ見て乱択したらACした。
　しかし、凸包の前後の頂点だけ見れば良いという予想が正しいのなら、不等式を解くことで具体的な（A,B）を得ることはできそうですね……。後から気付きました。

　乱択は嘘っぽいけど、どういうときダメなのかはよく分かっていません。
時刻: 0 件のコメント:
ラベル:

2026年1月22日木曜日

AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)

　Fまで。
　Fは初めから解法は合っていたので、どうしたら良かったのか悩む。定数倍高速化を頑張るより、codonを試す方が良いんだろうか？

コンテスト後のツイート

G - Takoyaki and Flip

　解説・解説放送を見てAC。

　遅延セグメント木を使うとは分かっていたが、基本的なことからおかしかった。
　もつデータを（最大値, flipしているか）だけで良い気がしていたが、それだと、複数の皿が「全て表か、全て裏か」の二通りの状態しか表せないので明らかに間違っている。

　それを解消するため、表の皿が何枚で裏の皿が何枚か、というのをもつようにすれば自然と遅延セグメント木に乗る。

　ただし、遅延させるものは、

・(a, b)　a回flipした後、b加算

　なのだが、(a, b)の後に(c, d)を行うのと、(c, d)の後に(a, b)を行うのとで結果が違うことに注意が必要だった。
　自分が解いてきた問題は、ここが可換なことが多かった気がする。順番に注意しなくてはいけなかった。

　ところで、PyPyだと1873msなのだが、codonだと301msでした。codon凄い！


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

2026年1月18日日曜日

AtCoder Regular Contest 182

　ABの二完だが、レートは上がった。

コンテスト後のツイート


C - Sum of Number of Divisors of Product

　解説AC。
　積の和典型の練習をしようと思って解こうとしたが難しく、解説を読んでもしばらく理解できず非常に苦労した。

　公式解説のように積の和典型を適用すると、タワーと積み木の問題と同等になることは分かる。しかし、それがbit DPで表せることが分からなかった。（ChatGPTに聞いたりしつつ悩んだ）

・どこかで積み木を選ぶのだから、積み木を置いたそのときに選べば良い

　と考えると理解できた。
　たとえば、「6」の積み木を置くとき、それは、2と3の位置に積み木を一個ずつ選ぶことを意味する。
　そして、それまでに2の位置や3の位置の積み木を選んでなかったとしたら、このときに選べば良い。
　その、既に選んだかどうかでbit DPをしている。

　また、最初に積み木が一個ずつ置いてあり、それを選んでも良いので、bit DPの初期値は全て1になる。

　こういう考え方でDPを書いたものが、この提出。これを行列累乗で高速化するとACできる。



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

2026年1月16日金曜日

Codeforces Round 1072 (Div. 3)

　ACの二完。Bで詰まって一旦離脱して、最後に戻ってきてもう少し解こうと思ったけどDが間に合わなかった。


B. Hourglass

　難しくないか？
　mを2*kの余りとした後、sとkの大小で場合分けして考える……という方針は簡単に立つけれど、s=kやm=kのときどうなるか？　など注意すべきところが多い。
　コンテスト後にも2ペナを出してしまった。

E. Exquisite Array

　自力AC。
　差が大きい順に見て、Union-findで要素をつなぎ、答えを更新していく。しばらく思いつかず結構時間がかかってしまった……。

F. Cherry Tree

　自力AC。mod 3での可能な回数の集合を持って木DP。
　この解法はmod 3だからできたもの。maspyさんの解説によると、modが任意の場合にもできるらしいが理解できていない。

G. Nastiness of Segments

　自力AC。セグ木＋二分探索。問題文がやや難読だが、内容は簡単だった。

　結局、Bが一番難しい回だったみたい。
時刻: 0 件のコメント:
ラベル:

2026年1月14日水曜日

AtCoder Regular Contest 212 (Div. 2)

　ABDの三完。

コンテスト後のツイート

C - ABS Ball 

　解説放送を見てAC。

　積の和典型と言われても全然ピンと来ないし、積の和典型の解法自体も忘れているしで全然ダメでした。

　というか、最初この問題を見たとき、積の和典型を使うのでは？　と思ったはずなのに、苦手意識があるせいか、そう思ったことを忘れてDPを考えていたのもダメ。もっと練習した方が良さそう。







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

2026年1月13日火曜日

AtCoder Beginner Contest 440 (Promotion of Engineer Guild Fes)

　ABCDFの五完。

コンテスト後のツイート

E - Cookies

　コンテスト中に書いていた方針でAC。
　コンテスト中、例題を解いた経験があると思ったが、実際正しかった（どの問題かは探せなかったけど）。そして、Aを降順にソートして、[K,0,0,0,0]からはじめて、一つずつずらしていく探索をすれば良い……という方針もできていた。

　ただ、コンテスト中は、Kの値が大きいことに混乱して、[K,0,0,0,0]のような配列で扱えると気付かず、Counterを持ち出していた。そのため実装でCounterのhashを求めなければいけなくなったりし混乱。
　そして、hash値を求めているのにその値を使い忘れたり、値が0のときはじくのを忘れたりしてWAが取れぬまま終了した。

　コンテスト中は混乱して、正しいことを書いているのか分からなくなっていたけど、落ち着くことさせできればコンテスト中に通すことも可能だった気がする。






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

2026年1月3日土曜日

Educational Codeforces Round 186 (Rated for Div. 2)

　Eまで。終了後F1は通った、と思ったらシステムテストで落ちた。

コンテスト後のツイート

F2. Christmas Reindeer (hard version)

　自力AC。見直したら難しくなかった。

　各桁について、何個使うのがギリギリなのかが分かるので、ギリギリのときと、それ以上が確定したときに分けてDPしていく。ギリギリのときは何個使えば良いか？　が分かるので、それより大きい個数を使うときは確定。同じ個数を使うときはギリギリ。二項係数で計算する。
　これも桁DPの一種といって良いかな。

　コンテスト中、30分残っていたら解けて良かった気もするけど、問題把握に結構時間かかってしまったなぁ。


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

2026年1月1日木曜日

yukicoder contest 286

　Cまで。


No.1425 Yet Another Cyclic Shifts Sorting

　自力AC。
　二種類あれば隣接要素SWAPができそうなので、答えは高々2。0回の判定は簡単なので、1回でできるかどうかを調べれば良い。

　一回でできるかどうかは、ソートした配列と比較し、最大値が一致していれば消していく。
　残った配列について、ソートしたものを巡回したものになっていれば良いので、ローリングハッシュを使って判定した。

　が、解説を見たらもっと簡単にできたらしい。なるほど。

　ところで、なぜタグが「動的計画法」なのだろう？　解けたと思った後タグを見たらそう書いてあって、何か間違っているのでは？　と疑心暗鬼になりながら実装した。
（タグに頼るのはいけないかもしれないけど、yukicoderのタグはいつも出したまま問題を考えています）

No.1426 Got a Covered OR

　解説AC。
　A_iが全て正、という条件の扱い方が難しい問題。

　包除原理で扱うのかな？　とは思ったものの、DPで包除原理でやるのかと考えてしまってダメだった。

・範囲を分割できること
・それぞれの範囲について、二項係数を使って計算していける

　ことに気付ければ解ける。
　bitの中で条件を満たさないものの個数で包除すれば良い。

　方針が分かれば難しくない。何で包除すれば良いかを考えるのが大切だった。

No.1427 Simplified Tetris

　解法は自力で分かったが、ACするのは苦戦した。

　盤面が与えられたとき、ちゃんと置けるかどうかは、この問題と同じ。
　なので、元の盤面の候補を全探索したい。

　ブロックが入っているマスの前後に何マスあるか？　をDFSで調べれば良さそうだが、何列必要かが分からない。高々2列で十分だろう、と思ったらWAで、3列必要な場合があった。

　そして、それで全探索するとTLEしてしまったため、ずるいけれど時間で打ち切る処理を入れてAC。

　解説を見ると、もっと上手にやる方法が書いてあった。気付かなかった。
時刻: 0 件のコメント:
ラベル:
登録: コメント (Atom)