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。

　
時刻: 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 件のコメント:
ラベル:
登録: コメント (Atom)