挨拶
にゃ～ん
本題
2024/05/17に開催されたyukicoder contest 430でF,G,Hの3問のwriterをいたしました。
あと全問testerもしました。
writerをした各問についてtwitterで書いた内容よりちょっと多めに語ります。
twitterに投げたやつは↓ここのツリーから見てね～
F Counting and Deleting
部分列の種類数を数え上げる方法は有名です。けんちょんさんの記事によくまとまっています。
同じ文字列を重複なく数え上げるのが大事です。同じ文字を拾うとき前からできるだけ拾っていくか、後ろからできるだけ拾っていくか。というルールを決めよう。
解説に丁寧に書きましたがこれはセグ木に乗ります。行列の形で書くとわかりやすいよ。
区間変更クエリが要素 $S_i$ に対して定数回しか作用しないなら（遅延評価しない）セグ木で十分という面白要素も盛り込んだけど、軽い構造体にしたり高速な言語を使ったりで遅延セグ木でも通る。おこ(# ﾟДﾟ)
愚直がありえないくらい早い vs 行列がありえないくらい重い
TLは4 secsですが、愚直でも10 secsあると通ってしまいます。これでもpython系は少し割を食う制約です。
愚直は↓こんな感じのコードになります。
mint query2(int l, int r){
mint f = 0;
mint g = 0;
for(int i = l; i <= r; i++){
if(s[i] == '0') f = f + g;
if(s[i] == '1') g = f + g + 1;
}
return f + g;
}
どこかで見たことある気がするけど見つからない……もしや未出？ と思ったらちゃんと既出でちゃんと解いたことあった。
20人解いてくれました。行列に帰着しないと構造体作るのめちゃ苦しいよね～！
G Macaron Gift Box
問題の内容は同値ですが、初期段階ではこんな感じで考えていました。
次の等式を満たす $0$ 以上 $K$ 以下の非負整数から成る列 $(x_1,x_2,\ldots x_N)$ は何通りありますか。
$$\sum_{i=1}^N ix_i = N$$
コンテスト1週間前にTLでこちらのツイートをみたとき血の気が引きました。ひゅいっ……！
よく考えると違う方針で解かなきゃいけないのでセーフ。こちらは分割統治（誤用？）FFTとBostan-Moriの合わせ技だね～
問題に戻ります。exp-log典型のやさしめの問題を出したかったです。知らなくても「分割数」などから検索で辿り着けてくれたらうれしいなという気持ちがあったので、かなりシンプルな形で出題させてもらいました。
あとオイラーの五角数定理さんも忘れないであげてね。
個数制限付き分割数（？）とでも呼ぶべき問題ですが分割数列挙+畳み込み一撃だけで解けるの面白くないですか？
次数の小さい方からFFTしていくやつがABCでついこの前に出題されたので、次はexp-log典型が近いうちに出てくるのではないかと睨んでる。こいつら見た目が似た形で出題されるのでセットで覚えちゃおう！
25人解いてくれました。やっぱ人々FPS強いな～
H Warp Drive Spacecraft
$O(N^2)$ 辺ある最短経路問題を問題の性質に注目して考える辺を減らす、という類の問題。実は半年くらい原案を温めてきた問題です。最近Convex Hull Trickも出題されてないしこれはきっと受けいいぞ～(^^♪
コンテスト1週間前の土曜日
ABC353-G Merchant Takahashi
$O(NQ)$ 辺ある最短経路問題です。
CHT で解けます。
そんな……( ´◔ ‸◔`)。
ポンポンとテスターさんが見つかるなら手元の他の問題との差し替えてようとも思ったのですが、twitterで募集かけてみると厳しそうだったのでそのまま出題。悲しいね
軽いワープと重いワープをいくつか候補にいれてDijkstraする嘘解法が実は通ってしまいました。
自分もtesterさんも思いつかなかったなら仕方ないよな……学びを得たので次に生かしたい
結構面白い問題になったと思ってるよ！ ぜひ解いてね！
22人解いてくれました。ぼくは2時間で解ける気がしません。すげ～
難易度評価
HはFとGと比べて6,7割のAC数だろうと思ったけどF,G,Hの3問ともAC数ほぼ横並び。
あと全問testerしてたのですがB,Cは☆0.5個分プラスすべきだったのか。
難易度評価は本当に難しいですね……
おわり
原案のストックはあるのでまた出題したいなの気持ち。共催してくれる人いたらいつでも声かけてください。
あとtester募集を見かけたら積極的に凸ってあげようと思った。