C. Hacking Numbers
こたつがめさんの放送の振り返りを見てAC。
こんなの思いつかない。初手で掛け算すること自体を考えなかったので厳しい。
D. D/D/D
自力AC。
偶奇に分けて、最大何歩歩けるか？ 各マスまで最小で何歩でいけるか？ を求めればOK。
2025年5月19日月曜日
2025年5月17日土曜日
yukicoder contest 467
ABCEの四完。Dは、問題の意味がぱっと理解できなかったから飛ばしたけど、分かっても難しかった。
No.3143 Colorless Green Parentheses Sleep Furiously
WAが出た後、テストケースを見てAC。
カッコ列が正しくなければダメ、というのはOK。その上で、
できるだけ少ない個数の1を加えたとき、何個加えることになるかを知りたい。
()なら、(1+1)+1にしなくてはいけないが、
()()なら(1+1)+(1+1)で良い。
(())なら、((1+1)+1)+1にしなくてはいけないが、
(()())なら、((1+1)+(1+1))にする。
カッコ列の対応を考えて、その対象範囲に自分のカッコだけしかないときは、()+1としなければならない、というのがなかなか気付きにくいポイント。
実装では、最初に、どの"("がどの")"と対応しているかindexの対応を調べておき、((...))となっているようなら、後ろか前かに+1を置けば良い。
No.3145 Astral Parentheses Sequence
解説AC。難しい。
括弧列の個数（カタラン数）をDPで求める方法を応用するとこの問題のDPも導ける。ただ、括弧列の個数を求めるDPがそれほど明らかではないため、それと似た方法でこれもいけるというのは直感的に分かりづらい。
No.3146 RE: Parentheses Counting
解説AC。難しい。
解説の最初にある漸化式（三乗の計算量になるやつ）を自力で出そうとしていたが、それすらできなかった。
ネストの深さが0の部分がカタラン数の積になるっていうところが思いつかない。ここは主客転倒で考えているのか。
その後の、計算量削減の式変形も難しい。カタラン数が満たす漸化式を知っていればいけるかもしれないが。
自力で解くには、実験→oeisしかなかった気がする。
No.3147 Parentheses Modification and Rotation (RM Ver.)
解説AC。
解説を見てしまったけど、これは自力で解けて良かった。括弧列の累積和（いつものやつ）を使い、最大値・最小値から答えが導ける。
タイプ1が右回転なのがちょっと引っ掛けな気がした。S[1:]+S[0]だった方が直感的に分かりやすい。
2025年5月15日木曜日
AtCoder Regular Contest 197 (Div. 2)
Dまで四完。
コンテスト後のツイート
D setとして、A[i]がA[j]を含むならiはjの親。木を作ったときAになるか十分条件をcheck。A[i]=A[j]の重複度の階乗の積が答え。
— titia (@titia_til) May 4, 2025
E - Four Square Tiles
解説AC。
二項係数でどうにかするのでは？ という気持ちになるのが大切だったか？ 中央の重なりがない場合については、そういう気持ちになれば求められたと思う。
しかし、中央に重なりがある場合も、それと独立に、二項係数で表せると気付くのは難しかったと思う。
ただ、中央に重なりがない場合が二項係数で表せたなら、正しい答えも二項係数の足し引きで表せるのでは？ と思って実験し、正しい答へ辿り着けた可能性はあるか。
2025年5月14日水曜日
AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）
Fまで。
コンテスト後のツイート
AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY） Fまで
— titia (@titia_til) May 10, 2025
C A[i]*（iより右の和）を足し合わせる
D BFS
E 一番右にあるAより左にあるBの個数で場合分け
F 線分の間を+1すると、クエリは階段を何段上り下りするかになる。実装はセグ木で。
G Mo's algorithmと思ったが分からず。
G - Range Shuffle Query
ACできなかったのは仕方ないが、Mo＋セグ木の解法は自力で思いつかなくてはいけなかった。
平方分割するとセグ木を使うより計算量が良くなることは知らなかった。頭に入れておきたい。
ところで、Moを書くときは、区間を広げた後、縮めていくように書くべきだということも知らなかった。今回、PyPyでTLEを取ることができず、ChatGPTにRUSTに直してもらったのだが、それが原因で配列外参照が起こってしまった。原因が分からず大分苦労した。
2025年5月13日火曜日
Codeforces Round 1024 (Div. 1)
ABDの三完。
コンテスト後のツイート
Codeforces Round 1024 (Div. 1) ABDの三完。
— titia (@titia_til) May 11, 2025
A 中央からぐるぐる
B (偶数番目の転倒数＋奇数番目の転倒数)の偶奇は不変。
D 尺取り。LIS/LDSのDPで、最初の要素を消したときにどちらかのDPの一ヶ所が消える→LISかLDSかは、以前どちらを増やしたか見る。A[i]に近いものを消せばOK。SortedSetで実装。
C. 23 Kingdom
解説を見たがそのままは理解できず。
使う個数xを固定した場合、「x,x-1,...,1の順に、できるだけ左にあるものを貪欲に使う」「x,x-1,...,1の順に、できるだけ右にあるものを貪欲に使う」として取ったものを合わせれば良いことは分かった。
それを三分探索すればACできるというコメントを見て、AC。PyPyじゃ間に合わないので、ChatGPTにRUSTに直してもらった。
もっと良い方法があるようだが理解できていない。
2025年5月7日水曜日
AtCoder Beginner Contest 404（Promotion for Engineer Guild）
Eまで五完。
コンテスト後のツイート
AtCoder Beginner Contest 404（Promotion for Engineer Guild）Eで右側へ行けると誤読して時間を食う。Gは牛ゲーに見えるけど、どういう最短経路に帰着できるか分からず。
— titia (@titia_til) May 3, 2025
B 回転四通り試す。
C 次数は2か？ 全頂点繋がっているか？
D 2^(2*N)全探索
E すぐ左の1へ行くまでの手数を求めていく。
F - Lost and Pound
解説AC。解説放送も見た。
分割数全部調べる方法は理解できたけれど、DP内でDPする方法の方が理解できず苦戦した。
結局自分で（再帰で）書いて見たらACコードは書けたけど、かなり難しく感じた。
残りターンT回、残り押さなくてはいけない回数K回のときの勝率をcalc(T,K)、とし、
（残りターンT回のとき）残りボタンを押す回数M回、kai回押す場所を決め、残り押さなくてはいけない回数x回のときの勝率をcalc2(M,kai,x)という関数を定義し、計算した。
引っ掛かっていたのは、kaiという変数が必要なこと。
kai回当たらなかった場合、当たりのボタンはN-kai個の中に含まれるので、当たりの確率は上がっているはず。
解説や解説放送のDPではこれをどう処理しているのかが分からなかったので、必要ないのか？ と思ったけど、やっぱり必要でした。
snukeさんのコードだと、26行目に(n-i)を掛けているのがそれに当たるんですね。
再帰だと（多分）同等なコードが書けるけど、このDPを書くのは難しい……。確率DPは再帰じゃないと書けないかもしれない。
G - Specified Range Sums
解説放送を見てAC。
牛ゲーは、解説を見れば理解できるけど自力で構成するのは難しい。
牛ゲーじゃないかと思ったときは、けんちょんさんのこの記事を見るのが良いかもしれない。
2025年5月3日土曜日
yukicoder contest 466 オムニバスコンテスト
ABDの三完。
No.3134 二分探索木
自力AC。コンテスト中は思いつかなかった。
二分探索木を構築する部分が難しい。
単純な方針だとできなそうに思えたため、SortedSetを使う方針を考えたら上手くいった。
使ってなさそうな提出もあるけど、大抵の提出では使ってそうだし、まあ良いかな（？）
※逆順列のCartesianTreeを作ると良いらしいです。
No.3137 Non-Intersect Chord Triangle Game
解説AC。
葵ちゃんの行動を誤読していたのでそもそもダメだが、正しく捉えていたとしても解けたとは思えない。
小さく、かつ弦のない円で実験したとき、2頂点、6頂点で茜ちゃんが勝つ、と正しく把握できたら考察を進められそう。
2025年4月29日火曜日
AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）
Fまで六完。
コンテスト後のツイート
AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY） Fまで。
— titia (@titia_til) April 27, 2025
C Xがクエリ2で指名されたか、(X,Y)がクエリ3で指定されたか。
D Counterを使い、連結成分ごとDP
E Trie木
F 最初BFSで全列挙しようとしたりしてダメ。そのまま掛け算できるかで分けるとDPできる。
G - Odd Position Sum Query
解説放送を見てAC。
この前のこたつがめさんの解説放送で、セグメント木≒Binary Trieだという話を聞いていた。知識はあったので解けなくてはいけない問題だった。
ただ、そもそも、値が小さければ普通のセグメント木で解ける、ってこと自体思いついてなかったんだよね……。
BrainPad プログラミングコンテスト 2025 （AtCoder Heuristic Contest 046）
384位。終了間際の提出がTLEになってしまい悲しい。
コンテスト後のツイート
BrainPad プログラミングコンテスト 2025 （AtCoder Heuristic Contest 046）
— titia (@titia_til) April 26, 2025
BFSでブロックを置かない経路を求めた後、序盤から見て行って、ブロックを置いた方が点数が向上するなら更新、を書いていました。
五分前くらいに書き終ったけど、提出したらTLEが出てダメでした。
コンテスト中考えていた提出でバグがなかったら81位相当だった。
https://t.co/yIqj6QO9az
— titia (@titia_til) April 26, 2025
コンテスト中のコード、バグがなかったから217445点で81位だったみたい。
本番コードに二行足しただけなんだけど、ChatGPTと一時間くらい相談してやっとTLEの原因に気付いたので、近くはなかった。
落ち着けば気付けたかもしれないが、コンテスト終盤に落ち着けるはずもなし。
惜しかったようで惜しくなかったのでは、考えていた方針はそれほど悪くなかったと慰めたい。
2025年4月26日土曜日
yukicoder contest 465
Eまで。
No.3129 Multiple of Twin Subarray
自力AC。コンテスト後に自力で解けたけど、大分時間がかかった。
左右から、累積和の差分が最大・最小になるような値を見つけられれば良い。これは、左右から累積和を取り、さらに今の累積和の値とそれまでの累積和のminの差分を取り、そのmaxを取っていき……のようにやればできる。
最初、切れ目を全探索を考えて上手くいかず悩んでしまった。
2025年4月25日金曜日
CPCTF2025
81位でした。
「CTF」初体験だったので、CTF中心にやったつもり。LV1は一応全部解いたけど、LV2から苦戦する問題が多くて大変でした。
競技プログラミングがパズルっぽいとすれば、CTFは謎解きっぽい印象。
面白いとは思うけど、自分は謎解きよりはパズルの方が好きかつ得意だと思うので、もしCTFを解くために必要な基本技術を習得したとしてもそんなに上手くはなれないだろうな、と感じました。
まあ、もう少し勉強してみないとなんとも言えないだろうけど。
コンテスト後のツイート
個別の問題について。
— titia (@titia_til) April 20, 2025
Math Test：私はpyautoguiを使ってコピペ→計算機で計算→コピペを自動化しました！
Bench：最初「こぼちゃん」で検索していた。植田まさしといしいひさいちの絵の違いも分からなくなってしまったのか……と悲しみました。
以下は、yukicoderの問題について書きます。
No.3117 Reversible Tile
解説AC。これが解けないのはダメ。
こういう区間をひっくり返すやつは、0と1の切れ目が二個変わる、と考えるのが定石。制約を見ると、二乗DPということが分かるので……というところで詰まってしまった。
ここまでの考察は合っているのに、なぜ解法にたどりつけないのか。
今回は、「切れ目の値が入れ替わっている個数」を持ってDPすれば良い。なぜかそう思いつけなかった。
No.3119 A Little Cheat
解説AC。
swapによって増大する分と、通常の値を分けるというのは考えたけど、swapによる増大分が高々1と気付かなかったし、それをDPで求められるというのも分からなかった。
また、解説を理解した後も、DPの遷移（場合分け）が大変過ぎて実装が大変過ぎるのでは、と感じた。実際に場合分けしてみると遷移に共通する部分が多い（コピペで良い部分が多い）ためそこまで大変ではなかったが、とはいえ、こういうのをさくっと実装するにはどうすれば良いのかなぁ。
No.3120 Lower Nim
自力AC。
最初にx=1を選択するとすると、Aの総和が奇数だと先手必勝。
なら、最初にx=2を選択するとすると、A[i]/2の総和が奇数だと先手必勝。
なら、最初にx=4を選択するとすると、A[i]/4の総和が奇数だと先手必勝……というようになることを利用した。
No.3121 Prime Dance
自力AC。
メモリ制限が大変だけど、難しいという気はあまりしなかった。
……と思ったら、メモリ制限が大変だったのは、左に操作した回数、下に操作した回数を持ったせいか。
自分は、DP[left, down, x ,y]で、左にleft回、下にdown回操作して(x, y)に辿り着いたか？ をboolで持ってやったけど、もう少しメモリを減らせたんですね。
AtCoder Beginner Contest 400
Eまで。
コンテスト後のツイート
AtCoder Beginner Contest 400 Eまでは速かったがFが解けない。
— titia (@titia_til) April 5, 2025
C bは奇数として良い。
D 01BFS
E 平方数で、素因数が二つのもの
F どう見ても区間DPだが遷移が書けない。
F - Happy Birthday! 3
解説AC。解説放送やこたつがめさんの放送の振り返りも参考にした。
区間DPなのは良いが遷移が難しい。四乗にする時点でかなり難しくないか？
こたつがめさんにやると、計算量削減部分は「区間DPの遷移でDPする必要があるとき」という典型らしい。l降順、r昇順にDPを計算していく。
しかし、そのパートにたどりつくためには遷移を把握できていなくてはいけないのが厳しい。ただ、こういう典型があると知っていれば、どういう遷移かを掴める確率は上がるはず（と信じたい）。
2025年4月18日金曜日
Kotlin Heroes: Episode 12
Eまで。
コンテスト後のツイート
Kotlin Heroes: Episode 12 Eまで。FG分からず。Eまで二時間かかっているのひどい。
— titia (@titia_til) April 7, 2025
B sortしてindexの偶奇で場合分け。不等号を逆にしたりして2WA+25分。
C 累積和
D 最初に1を聞き、後は二分探索。思いつくまで時間かかったし、その後もバグらせた。
E 折り返す。overflowに気を付けましょう。
F. Weapon Upgrade
三乗で良いというツイートを見てAC。難しくない。
残り時間が少なかったのでACまでもっていくのは厳しかったかもしれないが、方針は立っているべきだった。
a, bをそのときのそれぞれのパワー値とし、DP[a][b]=そのときのダメージ量の最小値として更新していけば良い。(a, b)が分かれば、そのときまでに倒した敵の数が分かる。なのであとは、(a, b)のときに倒せる敵の個数さえ分かれば良いが、これは、毎回500*500のマップを更新していけば良い。
敵が出尽くした後も、さらにn回くらいDP更新作業を続ければ答えが得られる。
Codeforces Round 1017 (Div. 4)
全完。
Hの方針が若干自信なかったけど、通って良かった。
コンテスト後のツイート
Codeforces Round 1017 (Div. 4)
— titia (@titia_til) April 13, 2025
D ランレングス圧縮
E 各bitの個数を前計算
F m%k==0かで場合分け
G reverseしたかのflagと、合計とreverseした/してない場合の答えを持ち更新していく。
H 各数について、A中のどのindexに入っているか、というリストを持っておき、約数列挙＆二分探索で頑張る。
AtCoder Beginner Contest 401
全完でした。
調べてみたら、ABC全完はABC197以来だったらしい。四年ぶり！
当時のABCは六問時代だった！
最近も何度か簡単なABCはあったけど、いつも全完を逃していたからね。
嬉しいけど、自分の実力で全完できるくらいのABCはちゃんと全完できるようになりたいね。
コンテスト後のツイート
F https://t.co/uDLI6Yaggrの解説を見に行った。できた木の直径は、・元の木の直径・「つないだ点から最も遠い点への距離」の和+1のうち大きい方。「つないだ点から最も遠い点への距離」は列挙できるので、ソートして尺取り。
— titia (@titia_til) April 12, 2025
G 二分探索→二部グラフマッチング。
2025年4月12日土曜日
yukicoder contest 464
ABの二完。
No.3101 Range Eratosthenes Query
解説AC。これが見えなかったのは良くない。
たとえば、[L,R]中にあるx=20を食べるかどうか考えるとき、xの1でない一番小さい約数は2なので、20/2=10が[L,R]中に存在するかどうか、で判定できる。Lが10以下か10以上かで変化する。
このことに気付いていなかった。
これが分かれば、クエリを先読みし、Lの順にソートして見ていけば解くことができる。
No.3102 floor sqrt xor
解説AC。
x^√xを考えると、上半分の桁はxのままなことを利用できそう。xを動かすとまずいけど、√xを固定すると、ルートして切り捨てた値が√xになるような範囲が分かるので、それで調べられる。
……というようなことを考えたはずなのに、実装する段階になると分からなくなってTLEの解法を書いてしまい、解説を見て考察していた内容を思い出した。
ちょっとあやふやなところはあったけど本質的解法は一度自力で考察したはずなので、時間があれば解けていたと信じたい。
No.3103 Butterfly Effect
自力AC。
その人がはじめて噂を知った時刻を持って、毎回ダイクストラすれば良いように見えるが、それだとTLE。
同じ辺は二度通らないように見えるため、なぜTLEするのかしばらく気付けなかった。
なぜTLEするかというと、ある人から辺（AさんとBさんの噂話）がたくさん出ているとき、（伝播しないのに）それらの辺を何度も見ることがあるため。
じゃあ、「同じ辺は二度通らない」という性質があるのなら、辺もheapqで持ち、一度通った辺は削除すれば良い、と気付きAC。
「ダイクストラで解けそう」という方針自体は思いつきやすいけれど、ちゃんとそこから一捻りしてあった。
2025年4月11日金曜日
AtCoder Grand Contest 071
A一完。
コンテスト後のツイート
計算量は四乗な気もするけどRUSTで提出するとAC。（PyPyだとTLEなので、もっと高速化できるのだろうけど……）
— titia (@titia_til) March 30, 2025
C サイクルがあってもYesになる条件を考えていた。二部グラフじゃないならYesっぽい！ とか、サイクルの全部の頂点に毛が生えていて欲しい！ とか。
C - Orientable as Desired
解説AC。解説放送も見た。
全く惜しくはなかったが、サイクルがあってもYesになる条件を考える、という方針自体は良いのかも。そういうグラフを列挙していけば正しい条件にたどりつけるかもしれない。
ただ、解法を理解した後も、二重頂点連結成分分解を実装したことがなかったため、自力で実装できなかった。LOWLINKを使った関節点や橋は実装したことがあるので、あと一歩なはずなのだが……。
とりあえず、二重頂点連結成分分解をChat-GPTに実装してもらいAC。原理は理解したつもりだけど、実装がよく分かっていない。ちゃんと自力で実装しなきゃなぁ。
ついでに、二重頂点連結成分分解を調べる仮定ででてきたこの問題も解説（放送）ACした。ポリアの数え上げ定理（バーンサイドの補題）はこういうときに使うのか。数え上げパートまでいけたとしても解けなかったと思うので、そこまでいけたら解けるようになりたい。
2025年4月3日木曜日
April Fools Day Contest 2025
ADの二完。
B. Plinko
自力では解けず。
0～17におくとゲームをプレイしなくてはいけないが、その外側におけば良かった。これは思いつきたかった。
C. Would It Be Unrated?
解説AC。
一つACが出るまでできることがなくないか？
D. Where Am I?
写真を検索するとラスベガスだと分かるので、その緯度と経度を書く問題。それっぽい提出をしても「very close!」などと返ってきて、submitデバッグするしかなかった。
……が、もっと狭い範囲に絞れたらしい。
E. Pair Count
解説AC。リンクがあればそこを押す、ということさえしていれば、順を追って解ける問題でした。
エイプリルフール部分の後にもk=0というコーナーがあるのも面白い。
G. Definitely a Geometry Problem
解説AC。
制約に引っ掛けがあるだけで普通の（注意力を要する）問題だった。問題文は丁寧に読まないとね。
2025年3月30日日曜日
AtCoder Beginner Contest 399
Eまで。
コンテスト後のツイート
E Sの各文字にTのどの文字が対応するかを見る。Sの一文字にTの二文字以上が対応していたら-1。グラフを考え、各連結成分について、サイクルなら頂点数+1、x→xが含まれるなら頂点数-1、それ以外なら頂点数回必要。ただし、サイクルで26個が覆われたら-1。私の書き方だとS=Tでの場合分けが必要だった。
— titia (@titia_til) March 29, 2025
F - Range Power Sum
解説AC。
「積の和典型」とも呼ばれる、組み合わせに帰着して解く問題。この解法、何度見ても解けるようにならないのだが……。
コンテスト中に「積の和典型」で検索したのに解けておらず、辛い。
yukicoder contest 462
AHCがあるのでAだけ解いて撤退した。
No.3075 Mex Recurrence Formula
自力AC。
実験するとN+1周期になると分かった。MEXを求めるところを愚直にやってしまったためTLEしたが、heapqを使えば良いと気付きAC。
No.3076 Goodstuff Deck Builder
自力AC。これは迷わなかった。
コストが大きい方から使うのが良い。残りのコストと、カードを使った回数をもってDPすればOK。
2025年3月27日木曜日
Codeforces Round 1013 (Div. 3)
全完。
Div. 3も最近は全完を逃していたことが多いので、今回は全完できて良かった。
コンテスト後のツイート
G sが大きい（s>k*kなら明らか。もっと小さくても良いと思うけど……）と答えはkかmax(1,k-2)になりそう。あとはシミュレーション。
— titia (@titia_til) March 25, 2025
2025年3月24日月曜日
AtCoder Regular Contest 195 (Div. 2)
三完はしたがレートは落ちた。Bは同じ解法で通している人を何人か見かけた。
コンテスト後のツイート
AtCoder Regular Contest 195 (Div. 2) Cまで通したけど、Bは嘘解法だと思う……
— titia (@titia_til) March 23, 2025
A 前からと後ろから
B k=A_1+B_1を固定すれば判定可能。kの絞り方が分からない。結局、a in A,b in Bについてa+bを列挙し個数を見て、その個数がOKになりうるもののみ判定した。
C Rが奇数ならダメ。あとは地道にやる。
B - Uniform Sum
嘘だと思ったが、（嘘かもしれないけど）それほど嘘ではなかった。
A, Bがdistinctだとすると、S=A[i]+B[j]が何個ずつ現れるかをカウントすれば、それを見るだけで判定できる。
今回はdistinctじゃないのでもう一工夫必要だが、大体それで良かった。
distinctなら上手くできるのでは？ と考えるべきでした。
D - Swap and Erase
解説AC。
コンテスト中に考えていた貪欲（左から見ていき、A[0]==A[2]ならA[1]とA[2]をswapする）がどういうときまずいのか気付けなかったのが敗因。
たとえば、
・1 2 1 1 1
のときまずかった。A[0]とA[1]をswapしなくてはいけないときもある。
Aの各要素が高々一回しかswapされないというのは言われてみれば自然だし、貪欲でダメと分かればDPしようと思えた可能性はあるかもしれない。
E - Random Tree Distance
解説AC。解説放送も見た。
まず、lcaを考える（u,vの距離を、D[u]+D[v]-2*D[lca]とする。D[x]は1からxまでの距離です）のはすべきだった。lcaがどこにあるか分からないから、lcaを考えることで状況が良くなるとすぐには思えないけれど、これはまずして良いですね。
あとは、D[lca(u,v)]が、u<vのときvの値によらないと気付けるか、だが、これは実験していれば気付けるかもしれない。しかし、その後、D[lca]に関する漸化式を立てる部分が理解できず、解説を見ながら悩んでしまった。lcaが再帰的に決まっていく、と考えれば難しい式ではないのだが……。
発想があった方が良い部分（D[lca(u,v)]が、u<vのときvの値によらないと気付く部分）もあるけれど、それ以外の定石的な部分でも詰まっているので、その部分はどうにかしたい。
2025年3月23日日曜日
AtCoder Heuristic Contest 044
98位。
コンテスト中バグらせて書き終わらなかった方針を最後まで書いていれば30位くらいにはなったので、惜しかったといえば惜しかった。
コンテスト後のツイート
AtCoder Heuristic Contest 044 98位。
— titia (@titia_til) March 16, 2025
答えの配列をANSとすると、NOW=[0]*Nと初期化したとき、
NOW[ANS[i][0]]+=T[i]//2
NOW[ANS[i][1]]+=T[i]-T[i]//2
としたときのNOWがTとできるだけ一致して欲しい。
→Tが大きいindexから貪欲に割り振るとそこそこ強い。
そこからほとんど伸ばせず終了。
Codeforces Round 1011 (Div. 2)
Cまで三完というまずい成績。
コンテスト後のツイート
Codeforces Round 1011 (Div. 2) DもEも解けずまずい！
— titia (@titia_til) March 22, 2025
A 高々1回でOK
B 最初の0とその隣に処理。まだ0が含まれているなら、残りを処理。
C max(x,y)にkを足して桁が変わるところを見る。
D 考えていたのは嘘貪欲だったぽい。
E a=A[i]について、{a-B[i]の約数}が候補ということから絞ろうとしていた。
D. Serval and Kaitenzushi Buffet
解説AC。
heapqを使って上手くやる問題だと見てすぐ思い、それはあっていたのだが……。
後ろから見てheapqで、それまでで最も良いのを出していく感じだと考えてしまったが、これだと上手くいかない。
寿司を取る回数の最大回数が決まり、その回数だけ取るべき、というのが重要。そうすると、一回目、二回目……について、どの範囲の寿司から取れるかが定まり、heapqで答えを求めることができる。
各回について、どの範囲の寿司を取ることができるかと考えなくてはいけなかった。愚直解（DP）と比較し、自分の解法がどういうケースで落ちるかも分かったのだけど、答えにたどりつけず。こういうときはどうすれば良いのだろうか……。
E. Serval and Modulo
解法ツイートを見てAC。
kはsum(A)-sum(B)の約数になる。言われてみれば確かに……。
2025年3月22日土曜日
yukicoder contest 461
EHJの三問が解けず。
コンテスト後のツイート
yukicoder contest 461 E、H、Jが解けず。J、AC提出を見て気付けなかったことにがっくり。Fで、N*Nの外側にもマス目があると勘違いし、一手足りない……とずっと悩んでたのもダメでした。
— titia (@titia_til) March 21, 2025
D 必要なときまで10秒時計を持っておく。
F 斜め移動
I ワープAB間の距離を前計算。あとは二分探索で。
No.3068 Speedrun (Hard)
解説AC。
二つ固定すれば、残り二変数については連立方程式になり、解ける。気付かなかったのはまずい。
No.3071 Double Speedrun
自力AC。
斜め向きにDPしていけば良い。ちょっと雑に書いたらPyPyで間に合わず、ChatGPTにRUSTに直してもらいAC。
No.3073 Fraction Median
解説AC。気付けなかったのは悔しい。
「中央値」というのを見て二分探索でどうにかしようとしてしまったが、それだと上手くいかない。よく問題を見ると、x/yとy/xの両方が含まれるので、この中央値は大体1。つまり、1以下で最大の数を求めれば良いと分かる。
2025年3月15日土曜日
yukicoder contest 460
11ペナを経てA一完。
No.3056 Disconnected Coloring
1の周り、もしくは、Nの周りだけ青にすれば良いだろう、という方針はすぐに立ったが、そこからが長かった。
どういう場面でWAになるか分からず、submitデバッグも経てなんとかAC。
No.3057 Tree Distance Set
自力AC。コンテスト後、落ち着いて考えたら思いついた。
2頂点の間に辺がある状況から、もう一点、それらから等しい距離Dの頂点を作りたいなら、その辺の中央に頂点を作り、そこから辺を伸ばして、新たな点を加える（そして、それのみSに加える）とすれば良い。
そうして作った木は、「2頂点の間に辺がある状況」を維持しているのでその後も再帰的に作れる。
No.3058 Deque and Brackets
解説AC。
hamamuさんの解説ツイートが分かりやすかった。
分かってしまえば難しくない問題なはずなのに、「後ろから見る」というキーワードを見ても自力で解けなかった。
こういう貪欲系は、調子いいと解けたりするんだけど、安定させるにはどうしたらいいのかなぁ。
2025年3月13日木曜日
Codeforces Round 1009 (Div. 3)
Fまで。D以降どれも難しい印象。
と思っていたら、Fはシステムテストで落ちた。
コンテスト後のツイート
F 再帰。メモ化したらTLEし、しなかったらACした。
— titia (@titia_til) March 11, 2025
G 区間DPにしか見えないが上手くいかない→考え直したら区間DPだった。コンテスト中に書き終わらず、PyPyで出したらTLE→ChatGPTに翻訳してもらうもWA。オーバーフローを疑う（オーバーフローもしていた）が、元のPythonのコードにも間違いがあった。
F. Counting Necessary Nodes
ちゃんとメモ化してAC。
tupleでメモ化しようなどとしたのが浅慮でした。ちゃんと整数でメモ化したら通った。
G. Game With Triangles: Season 2
区間DPなのは良いけれど、円環だということを意識する必要はなく、シンプルな区間DPで良いと気付けなかった。（自分が書いたコードは結構複雑……）
それに気付けていればもっと簡単に書けたねぇ。
2025年3月10日月曜日
AtCoder Regular Contest 194 (Div. 2)
ABDの三完。終了10秒前にDを通して青落ちを免れた！ かと思いきや、その後、Dが（本質的に）嘘解法だったことが発覚！
コンテスト後のツイート
D 深さが低い方から見ていく。[l,r]で同じ深さから出る山の種類・個数を見て二項係数で計算。同じ山の判定方法が分からず、A[j]>A[j+1],A[j-1]になるA[j]を列挙したりしていた。それにさらにr-lの長さの条件も加えたらAC。
— titia (@titia_til) March 9, 2025
上手いhash値を求めれば良いとは思ったけど、上手くやれないまま無理矢理AC！
C - Cost to Flip
一応自力AC。
三分探索解と比較して、バグ探しを頑張った。
コンテスト中は、(1,1)→(0,0)→(0,1)と変化させるものの個数で三分探索できる気がしたが、それでは上手くいかず。なら、差分計算するしかない！ と書いたもののWAが出て、諦めてDへ行った。
しかし、差分計算するしかない、というのは正しい。
愚直解（三分探索解）とランダムケースで比較し、どうにかAC。
この問題では、AHC的な能力を問われている気がした。差分計算は山登りや焼きなましをするとき重要。
AHCでも、差分計算の立式が下手で失敗していることは結構ある。足りないのは状況整理能力だろうか……。
なお、差分計算の失敗だけでなく、（三分探索で失敗したのに）凸性が保たれていると勘違いして実装していた。これも反省。せっかく差分計算しているのだから、全探索しないと。
D - Reverse Brackets
嘘解法でした。
ARC194のD、自分の提出は嘘解法ですね。
— titia (@titia_til) March 9, 2025
28
((()()())(()))((()())(()()))
で2を返します。（正解は4）
自分のハッシュだと、「((()()())(()))」と「((()())(()()))」を区別できないので、答えが1/2になってしまう。
コンテスト中は時間なかったけど、落ち着いて考えていれば気付けたはず……。
E - Swap 0^X and 1^Y
解説放送を見てAC。
標準形（辞書順）を考えるという方針をまず考えたけど、それで正しいのかが分からず解説を見てしまった。
実はそれで正しく、どうやって高速に標準形を求めるか？ という問題だった。swapできるものを最初にまとめておくという方針は分かりやすいですね。
あまり考えずに解説を見てしまったけど、考えたら気付いたのかなぁ。
2025年3月9日日曜日
Codeforces Round 1005 (Div. 2)
Dまで。
コンテスト後のツイート
C 負を選ぶと、それ以降は全て負のものを選ぶことになる。
— titia (@titia_til) February 16, 2025
D 上のbitから考える。上のbitが0になっているか？ そのときそのbitが0なら次に1が出てきた場所で終わり。1なら、次のところまでは下のbitは守られ、その次で終わり。
E. Mycraft Sand Sort
解説AC。
簡単なのかと思ったら、全然簡単ではなくて、解説など色々参考しても理解するまでずっとかかってしまった。（なお、解説の方法は理解していないし、自分がやった方法に嘘の疑いもある）
Cは与えられたものと同じものを使うしかなく、Pの個数を求める。
P_iとP_jが交換可能なのは、
・iとjが隣接しており、同じ色なとき
だけではなく、
・iとjが同じ色で、iとjの間にあるもの全てが、P[i]やP[j]より小さいとき（これは、上の条件を内包している）
と気付かなくてはいけない。
コンテスト中はここにも辿り着いていなかったが、それをどう数え上げれば良いかが難しい。
解説とは（多分）違う、左右を管理する方法でやった。
P[i]が小さい方から見ていき、隣合っている同じ色がどの範囲までか、を見て、その要素数を答えにかける。その後、index iを削除する。
削除というのは、左右を管理し、
・RIGHT[LEFT[i]]=LEFT[i]
・LEFT[RIGHT[i]]=RIGHT[i]
のようにするということ。まあ、左右を管理するときはよく使う手法ですね。
ここで、毎回同じ色がどこまでか？ を調べるとTLEするので、Union-findでくっつけ、Unionできる端の値をもっておく。
しかし、そうすると、その端の値は既に消えていることがある。そのときは再計算（消えていないindexまでLEFT,RIGHTをたどる）してACした。
最後の再計算するところの計算量が怪しいけれど、今回はACできた。危ないテストケースはありますか？
2025年3月8日土曜日
yukicoder contest 459
ABの二完。Cを考えているうちに寝てしまった。Cは一応自力で解けたけど、寝なかったら解き終っていたかというと微妙なところ。
No.3050 Prefix Removal
自力AC。
もし、Aの要素全てを使い切るとすると、満足度の変化は、
・最初の操作で全てのiに対して+A[i]
・選ぶpより大きい全てのiに対して+A[i]
のようになる。
これを最大化するためには、Aの後ろからの累積和を取って、大きい方から選んでいけば良い。ただし、最初に0を必ず選ばなくてはいけないことに注意。
ここまで分かったら、後はAのうち何個使うか？ という部分。
これがなかなか思いつかなかったのだが、heapqを使えば全探索できることに気付いた。やや思いつきにくいし面倒ではあるけれど、何度もしたことがある方法だった。
上手くやれば全探索できるのでは？ と考えてみなくてはいけないねぇ。
No.3051 Make All Divisible
テストケースは見たけど、一応自分で考えてAC。
まず、
・sum(A)がkで割り切れる
・max(A)<=sum(A)/k
のとき、この操作で全てを0にすることが可能（ということは考えているうちに思い出した）。
なので、各A_iをA_i%kに置き換えた数列でこの条件を満たせば一番良い。
そして、満たさない時は、現在のAの中で最も小さい数で、かつ、+kしても最初のAの値以下であるようなものに+kして、条件を満たすかを見ていく。
計算量は分からなかったが、この方法でACできた。
No.3052 Increasing Sliding Window Minimum
解説AC。
二乗DPになりそうなのは分かる。
DP[i][j]を、左からindex iまで埋め、使っていない数字の個数がj個のときの個数としてできそう、と思いかなり長いこと取り込んだがWAが取れず解説を見た。
すると、小さい数字から埋めて行くのが正解だった。
考え方は似ていたが、それだと、次の数字がどこのindexにまで入れていい、ということが分かるため、最初から分かっている数字を扱いやすい。
DP[i]をindexいまで置くことが可能なときの個数、と定義してやったが、この定義の仕方が悪く、n=2のときに例外処理をしなくてはいけない実装になってしまったが、無事AC。
DP[i]を、今までの数字で一番右に置いたindexがiのときの個数、とすべきだったか。
2025年3月7日金曜日
Codeforces Round 997 (Div. 2)
Cまで三完。
D. Unique Median
こたつがめさんの放送の振り返りを見てAC。アイディアは自然だが難しい。解法を理解するまでに、三回放送を見返した。
コンテスト中は、中央値が1～10それぞれになるときに、場合の数を求めるという方針を考えていた。
中央値がaのとき、aを0、a未満の数を-1、aより大きい数を1としたとき、（1の個数と-1の個数の差）が(0の個数)/2切り捨て以下になれば良い、というところまでは分かったが、数え上げに持っていけず。
そうではなく、k以下で-1、kより大きいとき+1として、累積和を取らなくてはいけなかった。
こうすると、区間和が0のとき、k以下のものの個数とkより大きいものの個数が等しくなるため、goodでない配列の個数を求められそう。（Zero-Sum Ranges系の処理ですね）
これに加えて、「kが中央値になるため区間内にkが存在する」という条件が必要になる。これは二分探索で処理できる。
2025年3月1日土曜日
yukicoder contest 458
Eまで五完。Eまではすらすら解けたが、Fが分からず考えこんだところで睡魔に襲われてしまった。
No.3040 Aoiスコア
自力AC。
DPを考えていたがうまくいかず、三頂点のpathなら列挙できると気付きAC。
結構苦戦した。眠りに落ちる前に一度解けたと思ったが、そのときはDPを考えており、それではダメだった。
No.3041 非対称じゃんけん
解説AC。
bitsetの利用は考えたけれど、bit_countの部分が速くならないためダメだと思ってしまった。その部分も1/64になるんでしょうか？
PyPyではTLEだったけれどPythonだとAC。
No.3042 拡大コピー
自力AC。
こういう問題で重心を考えるのは定石ですね。
No.3043 括弧列の数え上げ
苦労したが自力でAC。
括弧列の個数がカタラン数であることは分かっているので、calc(x):長さxの括弧列Sのf(S)の総和を、最初の(と何番目のindexが対応するかで場合分けして計算した。
一番外側で"("と")"が対応している長さxの括弧列Sたちのf(S)の総和は、長さx-2の括弧列たちの総和に、その個数*(x-2)/2（閉じカッコの数）だけ足したものとなることを利用した。
難しかったし、解説の方法も簡単ではない気がするのだが、AC人数を見ると解けなくてはいけない問題だったのか。
No.3044 よくあるカエルさん
自力AC……と言っていいのかな。
「すごろくであるマスに止まる確率」と検索したら、DPで求められるということが出てきて、それなら行列累乗で求められると気付いた。
検索しないとDPと気付かなかったのは良くない。
No.3045 反復重み付き累積和
解説AC。
解説を参考にしたけど、行列ベースで考えていた。
長さ4の数列A（1*4の行列として見ている）に対して、重みkの累積和を一回取る操作は、
1 k k^2 k^3
0 1 k k^2
0 0 1 k
0 0 0 1
という行列を右からかけることに対応している。
このx乗がどうなるかというと、実験すると、これらのk^nなどのところに、Combi(n+x-1,x)という二項係数を掛け合わせたものになる。
のだが、これだと三乗になってTLE。
解説を見ると、この行列計算はFFTで計算できるらしい。
それを見てAC。
行列計算のうち、どのようなものが形式的ベキ級数的に表せるのかを知っていると良いのかもしれない。
2025年2月25日火曜日
鹿島建設プログラミングコンテスト2025（AtCoder Beginner Contest 394）
Fまで。Gも解法はあっていた。
コンテスト後のツイート
G 並列二分探索。https://t.co/v1xHE0HJA0
— titia (@titia_til) February 22, 2025
を見に行った。
PyPyだとTLEで通せなかったけど、ChatGPTでRUSTに翻訳してもらってAC。
ただ、ChatGPTで一発では正しいコードが出ずちょっと手直ししないとダメだったので、ルール的にどうかな、と思いコンテスト中は提出しなかった。
G、unratedだったから提出しなかったけど、ratedだったらどうしただろう。多分提出していたと思う。
ChatGPTにプログラミング言語の変換をしてもらう→自分で修正、は許されていると思っているんだけど……。
ただ、ルールにある文言を入れても、忠実に変換してくれなかったり、元のコードのコメントアウトしろ、っていうのを無視されたりする。また、そのままでは動かないコードが出てくることも多い。
意図通りの変換になることはそれほど多くないよね。
yukicoder contest 457
AHCの最中だったため、Aだけ解いて撤退。
No.3028 No.9999
一見、何も分からなかったが、タグの「循環小数」というのを見て、循環節の長さと一致することに気付く。
それでも分からなかったので、ChatGPTに解き方を聞いてみたところ、コードを教えてくれ、そのままAC。
10^L=1(mod x)を満たす最小のLは10のxに対する位数と一致し、これはトーシェント関数の約数のうち最小のものなので、トーシェント関数の約数のみを試せば良い、という解説も分かりやすい。
トーシェント関数のライブラリも、自前のものよりこっちの方が良いのかと、考えてしまう。
No.3029 オイラー標数
setにソートしたものを放り込んでいき、AC。
クエリの与えられ方の意味がぱっと分からなかったけど、三角形をなす三頂点をどんどん与えられているということなんですね。
No.3030 Kruskal-Katona
定理の名前で検索したら、貪欲で良いと書いてあったためAC。
なお、N_i=N_i-1+1じゃなくてはいけないと定理を検索するまで誤解していた。サンプルの答えが全部連続した数なのが分かりにくくしている気がする。
2025年2月16日日曜日
yukicoder contest 456 オムニバス
Cまで三完。
No.3022 一元一次式 mod 1000000000
解説AC。だが、解説を読んだ後も混乱した。
整数論の問題なので、2と5に分解してどうにかするしかない。Mに2や5の素因子が多いとダメそう……というところから、整数解が存在する条件が得られる。
すると、両辺を2や5で出来る限り割ることで、
・N'*k+M'=0(mod d')
という形の式になり、N'とd'は互いに素になる。なので、オイラーの定理を使って-M'/N'の値を求めることができる。
この値が0になるのは、そもそもM'がd'の倍数のとき。なので、N*kがd'の倍数になれば良い。N'とd'は互いに素なので、このときはd'が答え。
No.3024 全単射的
自力AC。
二部マッチングだからフロー！ と思ったが、うまくグラフが構築できず、よく考えたらUnion-findで解けると気付きAC。
しかし、公式解説の解法はフローで解いていた。景品だけでなく、人の方も頂点にすると思いつけなかった。
2025年2月14日金曜日
Codeforces Round 1004 (Div. 1)
AB二完、だった。が、AはinteractorのバグでACになっていて、正しいinteractorだとWAだったらしく、WAになっていた。このブログを書いている2/14現在、レートも、当初は+1だったのが-76になっている。
UPD3: After the analysis, it was determined that this problem affected a small number of participants. There are no submissions that get AC with the correct interactor and erroneously received a non-AC verdict earlier. Therefore, the following decision was made:
If your solution worked with the old interactor, but does not work with the correct one and your rating has decreased, then the round will be unrated for you.
に該当するためこれが正しければunratedになるはずだけど、この後、unratedになりレートが戻るのだろうか？
コンテスト後のツイート
Codeforces Round 1004 (Div. 1) Bまで。終了直前にD1が二項係数の値そのままだと気付いた。
— titia (@titia_til) February 11, 2025
A Xが順列でなければ辺が出てないかで判定。そうでないときは、X[i]=1,X[j]=nとなる(i,j),(j,i)を聞く。値が違ったり両方1だったらA。
B 0は一つしか残せない。0は一番左のものを残すのが良い。あとは判定。
A. Object Identification
自力ACだが、本質的な考慮漏れがあった。
自分のツイートの方法で大体良いのだが、「値が違ったり両方1だったらA」の「両方1だったら」というところがおかしい。両方n-1未満なら、などとしてAC。
ここでは、1とnが巡回する場合を考えている。1とnだけが巡回するなら両方1だが、1→2→n→3→1なら距離2で巡回するわけで、距離1だけで巡回するわけではない。
コンテスト中は距離1で巡回する場合しかありえないと思っていたので、本質的な間違いだった。
本質的なミスでWAになっているのだから、システムテストで落ちたときと同じ気持ちで、レートが下がったとしても受け入れるべきか。
D1. Club of Young Aircraft Builders (easy version)
自力AC。
実験したら二項係数そのままだったので、それを使ってAC。
あと10分あれば解けていたと思うけど、なぜ二項係数になるかは分かっていない。
2025年2月11日火曜日
AtCoder Regular Contest 192 (Div. 2)
BCの二完。
コンテスト後のツイート
AtCoder Regular Contest 192 (Div. 2) BC二完。
— titia (@titia_til) February 9, 2025
A ARCやCRAのARの部分を1に変えられると誤読。終了五分前くらいに誤読に気付くも解き切れず。
B 実験。N>=4ならsum(A)の偶奇。N=3は奇数が含まれるか。
C "? 1 x"を聞いて、端の一つを探し、そこからもう一回。木の直径を探すアルゴリズムに似ていた。
A - ARC Arc
解法ツイートなどを参考にAC。
コンテスト終了直前に4の剰余で場合分けすれば良いことには気付いたので、時間があれば自力で解けたとは思う。
しかし、誤読に気付いた後、10分くらい時間はあったのだが正しい解法にはたどりついていなかった（10分くらいかかって4の剰余で場合分けすれば良さそうなことに気付いた）ので、4で割って2余る場合の考察にはもう少し時間を要したと思う。
惜しい、という感じではなかった。
D - Fraction Line
解説AC。
素因数別に考え、後でまとめられるということに気付けば難しくない。しかし、この部分は結構非自明な気がする。
ただ、こういう問題で素因数ごとに考えるのは定石の一つなので、それでできるのでは？ と疑い、実験してみるべきだったか。
2025年2月10日月曜日
日本レジストリサービス（JPRS）プログラミングコンテスト2025#1（AtCoder Beginner Contest 392）
Fまで六完。だが、Fまでも時間がかかり過ぎだし、Gも解けなくてはいけない問題だった。
コンテスト後のツイート
F 後ろから見て、最初入れた位置から何個右へ移動するかを二分探索。自分以下の要素が何個現れているかをセグ木で管理した。
— titia (@titia_til) February 8, 2025
G - Fine Triplets
まず、類題（このC）をやっていたのに、それを生かせなかったのがまずい。
いや、FFTを最初考えたのは類題経験があったからかもしれないが……。FFTを思い付き、しばらく考えたにもかかわらず棄却したのはひどい。
類題の記事でも書いた、「登場回数の配列同士を畳み込めば、二つの配列の和の要素の登場回数になる」が本質。頭に入れておかねば。
2025年2月3日月曜日
AtCoder Beginner Contest 391
Eまで五完。
コンテスト後のツイート
AtCoder Beginner Contest 391 Fが解けなかった。解説を見たらKの制約を見逃していたことに気付いた……。
— titia (@titia_til) February 1, 2025
C 各穴にいる鳩のsetと、鳩がどの穴にいるかを持つ
D 各列の一番小さい値が消える時間が分かる
E 再帰で書いた
F - K-th Largest Triplet
解説AC。
Kの制約に気付いていたら正解できたと思う。こういう致命的な制約見逃しはあまりやったことなかったのだが。
G - Many LCS
自力AC。
LCSを求めるのにDPが必要なので、この問題もDPで解くしかなさそう。
N<=10という制約を見て、bit DPなどを考えたがちょっと違った。「i文字の部分列を構成するときの最短のindexはどこか？」を考え、それをDPのキーとしたいと考えると、それは単調増加なのでindexの部分集合の個数しかない。これを利用すれば解ける。
2025年1月28日火曜日
Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)
Cまで三完で紫に落ちる。
コンテスト後のツイート
Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2) DもE1も分からず悲しい。
— titia (@titia_til) January 26, 2025
A 1の個数
B 端まで行って戻る時間を見る
C 一回以上操作したときsum(A)もしくは-sum(A)が作れる。
D l=rなら全方位木DPでいけそう→三分探索しようとしたが実装間に合わず
E1 Wが最大の頂点を基準に考えたがダメ。
D. Balanced Tree
こたつがめさんの放送の振り返りを見てAC。
全方位木DPが必要などと思っている時点で解法には遠かった。
（全方位木DPのためにトポロジカルソートはしていたが）根付き木にして考えて良いということも分かっていなかったため、正しい解法まではかなり遠かった。
惜しいところまで行っていないため、まず根付き木で上手くいかないか考えましょう、くらいしか言うことがない。
E1. The Game (Easy Version)
こたつがめさんの放送の振り返りを見てAC。
コンテスト中に似たことは考えていた時間はあった気がするが、まとめられなかった。ただ、実際の敗因は、実装（LCAと比較する）が思い浮かばなかったことだと思う。この放送を見たときも、まず思ったのは、実装どうやるんだろう？ だったので。
木の問題で、subtreeについて問われているのだから、LCAを考えるのは自然。そこを元に考えていたら正しい解法を見つけられたかもしれない。
2025年1月27日月曜日
AtCoder Regular Contest 191 (Div. 2)
Bまで二完。
コンテスト後のツイート
AtCoder Regular Contest 191 (Div. 2) AB二完。Cは諦めるべきだったかも。
— titia (@titia_til) January 26, 2025
A 最後の一個以外は貪欲に。最後の一個は、一番後ろに入れるべきかチェック。
B bitが立っていない箇所を1にする個数。
C オイラーのトーシェント関数っぽいからそれ関係の資料を読んでいたが上手くいかない。
C - A^n - 1
解説AC。
オイラーのトーシェント関数などを考える方針は悪くはなかったようだが、そこからどうすれば良かったか。原始根などに関する知識がもっとちゃんとあれば良かった？
想定解の方はどうやって思いつけば良かっただろう。
実験はしたがそこから進めなかった。n乗が絡むので、二項定理に思いを馳せるべきだったか？
D - Moving Pieces on Graph
解説AC。
場合分けがちゃんとできたとしても実装で引っかかる部分が多く、難しい問題だった。2nd shortest pathを求める必要がありそうだが、実際は必要ない……といったあたりも混乱しやすい。
2025年1月26日日曜日
AtCoder Beginner Contest 390
ABCEの四完。
コンテスト後のツイート
B A[i]*A[i]=A[i-1]*A[i+1]を使った
— titia (@titia_til) January 25, 2025
C 黒いマスの端の行、列を見て、その間に"."が存在しない
E 各ビタミンごとにDPしておき、答え二分探索。
D - Stone XOR
冷静にDFSを書いてAC。
全探索する問題なのは制約を見れば分かる。あとは、どうやって書くかなのだが……。コンテスト中は、部分集合ごとにbit全探索しており、「ただ全部見る」というのより明らかに時間がかかっていた。
DFSし、今ある分け方のどこへ次の要素を加えるか？ を見るようにしたらAC。制約が厳しいのか？ と思ったけど、PyPyでも問題なく通る問題でした。
F - Double Sum 3
解説AC。
コンテスト中にあまり考えず、コンテスト後すぐ解説を見てしまったけど、主客転倒と言われれば確かに、となる問題。
[L, R]のLの方を基準に考えるのは自然だし、A[i]=Lとなる範囲はどれくらいか？ と考えるのもそんなに思いつきにくい感じはしない。
Dを中心に考えていたとはいえ、問題を読んだのなら解けなくてはいけない問題でした。反省。
2025年1月25日土曜日
Codeforces Round 1000 (Div. 2)
Dまで四完。
コンテスト後のツイート
Codeforces Round 1000 (Div. 2) Dまで。
— titia (@titia_til) January 22, 2025
A 注意すべきはl=r=1だけ？
B 左右のどちらかから貪欲に取る
C 次数が大きいものを何個か試し、残った中で次数が最大のものを削除、でACした。
D A,Bとも左右の端から貪欲に取る。A側の頂点が足りなくなったら、AABの三角形を一つ削除、とやっていく。
E. Triangle Tree
苦労したが、公式解説など色々参考にしてAC。
まず、木DPでできそう、と思ってしまったのが筋が悪かった。
主客転倒的な考え方でいくべきだった。
その後は、うーん、どうすれば良かったんだろう。
min(d_u, d_v) の総和と、d_{LCA}の総和に分けて考えれば良い、というのは立式を見れば分かるが、その時点でちょっと思いつきにくい。
さらに、それぞれの求め方も簡単とは言えず……。
とはいえ、立式し、式を簡単な形に分解しようと思う部分は自然。
その後、主客転倒でいこう、と思えるかどうかが勝負なのかな。
2025年1月23日木曜日
Codeforces Round 998 (Div. 3)
Eまで。Div. 3なのにFから難しい……。
F. Multiplicative Arrays
こたつがめさんの放送の振り返りを見てAC。理解した後でも難しい気がするが……。
二項係数でどうにかする問題というのは分かるが、そこで止まってしまった。
たとえば、k=6でn=4のときの場合の数は、2を入れる位置と3を入れる位置を考えて、4*4となる。なので、n以下のを足し合わせる場合、4*4+3*3+2*2+1*1＝30となる。
……のように考えて、上手くいかなかった。
このように考えるのではなく、数字を入れる箇所を何個にするか？ と考えると二項係数の和になり高速化できる。
先程の6の場合だと、[6], [2, 3], [3, 2]の三通りがある。
[2, 3]の順で入れるとすると、Combi(4, 2)通り。n=3, 2, 1の場合を考えると、Combi(3, 2), Combi(2, 2), 0通りとなり、その和は（公式により）Combi(5, 2)と計算できる。
単純に素因数分解するのではなく、何をどういう順番で掛け合わせてkにしたか？ と考えなくてはいけなかった。
2025年1月22日水曜日
ALGO ARTIS プログラミングコンテスト2025 冬（AtCoder Heuristic Contest 041）
413位という苦しい成績。
このツカモさんのツイートを参考に、コンテスト後に話題になった貪欲を実装してみた。
コンテスト後のツイート
ALGO ARTIS プログラミングコンテスト2025 冬（AtCoder Heuristic Contest 041） 400位にも入れず厳しい。
— titia (@titia_til) January 19, 2025
・葉が全体にいきわたるようrootとそこから出ている芽を決め、高さ10の葉の集合が減らないように高さ9,8,7,..の頂点を固定。あとは貪欲に、できるだけ高い高さで頂点を埋めていく、という方針。
高さ10の頂点をできる限り増やしたい、というのは分かるのだけれど、どうすれば実現できるか分からず上手くいかなかった。
山登りなども考えた（し、どうやらそれをやった方が良いスコアが出たらしい）が、子たちも一斉に変えなくてはならないず、高さが10より大きいものが出た場合どうすれば良いのか？ というあたりで躊躇してしまった。
これで76,108,082点出た。
— ツカモ (@tsukammo) January 19, 2025
ちょっと書いてある事をストレートに解釈できなかったんだけど、以下のやり方にした。
①根(高さ=0)を決めるため、美しさAの小さい順に頂点を選択し、全頂点が根から距離10以内に入る組合せを全通り求める。
②(続 https://t.co/PtKxMCVioz pic.twitter.com/VBlif4LMPb
根にできるだけ小さい値を割り当てたい、という気持ちは良いのだが、そのために、「Aを小さい順に見て、全点にいきわたるよう必要なだけ取る」、というのではなく、「Aを大きい順に見て、その点がなくても全点にいきわたるようなら除く」としているのが技巧的に感じた。
ただ、その方法にさえ気付けば後は自然ともいえるか……。
コンテスト中どうすべきだったかは悩ましい。
自分がコンテスト中考えていた方とこの貪欲解法は結構似ているので、そこへ辿り着けたら良かったのだが、上手くいかなかった。
DFSを試すべきだったとは思うけど、普段再帰でのDFSを書いていないため、解説放送にあるようなDFSにはちょっと慣れていないんだよね……。解説放送のDFSを再現するのに時間がかかってしまった。それだとあまり良いスコアが出なかったので、DFSの良さに気付くのもそんなに容易でなかった気がする。
シンプルな解法を考えて、山登り/焼きなましなり、ビームサーチなりを試す、という方針の方が良かったのかなぁ。
IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)
Eまで。
コンテスト後のツイート
D Bの分け方は一意
— titia (@titia_til) January 20, 2025
E 各aについてm個のうちいくつかを使ったときの減少分を全探索。x個で減少させられる量の最大値は、x-1個で減少させられる量の最大値より小さいので、減少量をソートして貪欲。
F1 左から貪欲でいいのでは？→WA
F1. Kevin and Binary String (Easy Version)
端から貪欲で良いという情報を目にしてAC。
ツイートにも書いた通り、コンテスト中も端から貪欲で良いのでは？ と思ったのだけれど、「SとTで端に同じ文字があったら消去する」という処理を入れていたためWAになっていました。
いやこれ、まずいかも、とは思ったのだけど、検討したら大丈夫に思えたため、実装の都合で入れたんですよね。実際はそれほど実装が楽になるわけでもないのに、無駄な処理を入れたためWAになったのは悲しい。ACしなくてはいけない問題でした。
yukicoder contest 300
ABの二完で終わってしまった。
No.1552 Simple Dice Game
Writer解説とほぼ同じことを考えていたのに詰められなかった。
解説中の、
ベン図を考えれば、最小値が L 、最大値が R の数列の個数は、
・(R-L+1)^N-2(R-L)^N+(R-L-1)^N
と求まります。
という部分。この式がもっと複雑な包除原理の式になる気がして悩んでいた。
（今回は二つの集合だけの単純な場合だけど）包除原理を使う問題は苦手なんだと思う。包除原理を疑ったらまずベン図を描いてみると改善するかな……。
No.1554 array_and_me
自力AC。作者さんが、ABCで似た問題が出たとツイートしていたのを見て挑戦、無事ACした。あまり似ている気はしなかったけれど……。
heapqに入れて貪欲という解法はすぐに見えたのに、heapqに詰めるものを間違えて実装に時間がかかったのは反省。
2025年1月18日土曜日
yukicoder contest 455
Bまで。A,Bは制約の違う同じ問題なので、実質一完でした。
No.3004 ヤング図形
自力AC。
二項係数と階乗の数の積で表すところまでは問題ない。問題は、制約が大きいため、それを愚直に計算しては間に合わないところ。階乗たち（F[i]とする）を陽に持っては間に合わないため、どのようなF[i]を何個かければ良いか、または何個割れば良いか？ を持てば良い、というところまでは分かったが、これでもTLEだった。
コンテスト後、冷静になれば、どのような入力でTLEするかに気付ける。
1
2 5
を、Combi(10,8)*Combi(8,6)*Combi(6,4)*Combi(4,2)*Combi(2,0)を計算し、5!で割る、と計算しようとしていたが、これだとm（この入力だと5）が大きいとき間に合わない。
この積が実は、10!を2=で5回割ったものだ、と気付きAC。
うーん、コンテスト中にACできなくてはいけない問題でした。
No.3005 トレミーの問題
トレミーの定理（覚えていなかった）の逆を使ってAC。
解説を見ると、整数だけで解く方法があるらしくびっくり。
No.3006 ベイカーの問題
自力ACだけど、タグに「行列」とあったのを見てしまったから自力とは言えないね……。
行列累乗だと気付ければ解ける。漸化式を考えるのだから行列を考えるのは自然ですね。
2025年1月14日火曜日
AtCoder Regular Contest 190 (Div. 1)
A一完。
コンテスト後のツイート
AtCoder Regular Contest 190 (Div. 1) Aはまあまあ速かったものの、Aしか解けず。
— titia (@titia_til) January 12, 2025
A 三回あれば操作可能。二回以下でできるか丁寧に場合分け。
B メモ化再帰でN^3程度の計算量にはなったが高速化できず。(a,b)が固定されているのをどう使えば良いのか……。
A - Inside or Outside
ACしましたが、after contestでWAが出ました。
ソートの仕方がまずくて、[a,b],[a,c]と、左端が同じものがあるとき、包含関係の判定がおかしかったのが原因でした。
本番中にWAが出ていたら気付くのに非常に苦労した気がする……。運が良かった。
B - L Partition
解説AC。解説放送も見ました。
コンテスト中に考えていた再帰では間に合わなそう、ということで、何か方針転換しなくてはいけなかったのだけど、そういうとき、二項係数を考えるのは定石の一つ。考えなくてはいけない方針でした。ただ、解法ツイートなどを見てそう言われても全然思い浮かばなかったので、解くのは厳しかったかもしれない。
また、二項係数の和を順に求めていくところも、（多分やったことはあると思うのだけど）記憶にありませんでした。
C - Basic Grid Problem with Updates
解説放送を見てAC。
コンテスト中、スタートとゴールからDPして、差分計算をどうにかすれば良い……というところまでは考えていた。
あとは、それらを用いて答えがどう表せるかが分かれば良かった。ただ、各クエリごとにmin(H, W)使って良いということにも気付いていなかったので、正解に近かったという感じではないが。
ただ、Bよりは惜しかった気がするので、こっちに集中すべきだったかもしれない。
D - Matrix Pow Sum
解説AC。解説放送も見ました。
難問に思えた。実験すればある程度分かるという意見も見たけど、あまり思いつきそうにないなぁ……。
ただ、解説放送で言及していたように、行列をグラフの経路数と見て行列の累乗をn歩進むときの行き方と捉える（たとえば、ここが参考になる）という考え方は身に着けておきたい。
特に、「隣接行列をn乗してできる行列の各要素は、その行番号から列番号への頂点までを、そのグラフの辺をちょうどn回使うルートの総数」である。
2025年1月12日日曜日
HHKBプログラミングコンテスト2025(AtCoder Beginner Contest 388)
Eまで五完。
コンテスト後のツイート
F いける場所を区間の和で表し、各区間がどこへ遷移できるかを調べる。（A==Bのときは別に実装するとして）いける場所が[x,y]のみで、y-x>=Bならば、次の障害物直前まで進んでいいことを利用して実装した。コンテスト中に終わらず、非常に苦労してACしたけど、この方針はあまり良くなかった？
— titia (@titia_til) January 11, 2025
F - Dangerous Sugoroku
コンテスト中の方針でACしたが、実装に非常に苦労した。というか、自力じゃデバッグできず、ACしているコードとランダムテストで比較した……。
区間で管理する方針が良くなかったのだろう。
どこへいけるかをlistで持った方が実装しやすかったようだ。
G - Simultaneous Kagamimochi 2
Eの正しい解法を理解し、セグ木を使うと知れば後は難しくなかった（添え字で少し苦労したけど）。
この問題がどうこうというより、Eで間違った考察をしていたのが敗因。
2025年1月9日木曜日
Hello 2025
Cまで三完。
コンテスト後のツイート
D B=[A[i]+1 for i in range(n)]みたいなのを用意すると、平面走査みたいなので最初の答えは分かる。あとはクエリで差分計算したいのだが上手くいかない。
— titia (@titia_til) January 4, 2025
E1 答え二分探索で毎回BFSするとTLEする。
D. Gifts Order
けんちょんさんの記事を参考にAC。
セグ木を使うのは第一候補だったのにこれを思いつかなかったのは良くない。可換性が成り立たないとセグ木が使えそうという判断が鈍ってしまうようだ。気を付けよう。
E2. Another Exercise on Graphs (hard version)
こたつがめさんの放送の振り返りを見てAC。
ワーシャルフロイド法で、一辺を変更するときは辺の二乗の計算量でできることは覚えておきたい。
妙に制約が厳しい気がするけど、クエリ問題だから仕方ないのかな。（と思ったら、公式解説の方法はもっと速いらしい）
G. Secret Message
証明は難しいが、「十字のマスのうち一マスを塗れば良さそう」というところから発想することは可能だったか。
ただ、制約が厳しく、二次元配列を一次元に直さないと通らなかったので、コンテスト中にACするのは厳しかったかもしれない。
2025年1月8日水曜日
AtCoder Beginner Contest 387（Promotion of AtCoderJobs）
Cを飛ばしてFまで五完。
コンテスト後のツイート
D 01BFS
— titia (@titia_til) January 4, 2025
E Nが小さいときは全探索。そうでないとき、aの最初の数桁以外は0の場合を考えると、aの桁和が2,3,8,9のときは条件を満たし、そういうものが必ず存在する。
F iからA[i]に辺を引き、SCCして、木DP
C - Snake Numbers
桁DP（もしくは、それに近い）方法でやっていた人が多そうだったけど、コンテスト中に考えた場合分けの方針のままでAC。
ただし、場合分けに苦戦し、かなりの時間がかかった。解けることは分かったけれど、桁DPで書いた方が混乱は少なそうです。
登録:
投稿 (Atom)