yukicoder contest 420 H 別解
問題： No.2670 Sum of Products of Interval Lengths - yukicoder
公式解説が天才っぽかったので、包除原理を使用したシンプルな解法を説明します。（多分最終的な結論は一緒ですが、導出が異なると考えています。）
数え上げるものは、値が $1$ ずつ増加する際の極大なブロックに分割したときの、各ブロックの長さの積の総和です。
極大なブロック間の仕切りを固定したときの答えを考えると、仕切りの左右の要素の差は $1$ ではないという制約が付きます。この制約は扱いづらいので包除原理で処理します。
仕切りのうち、仕切りの左右の要素の差は $1$ という制約が課された仕切りを青い仕切り、制約のない仕切りを赤い仕切りとして、赤い仕切りの位置を固定します。
赤い仕切り同士で区切られた長さ $n$ の区間にたいして青い仕切りを入れる方法全てに対する（包除原理の $-1$ 倍を含めた）答えへの寄与を $f_n$ とすると、$f_n=n-\sum_{i=1}^{n-1}i \times f_i$ という漸化式が立つので $f$ を $\mathrm{O}(N)$ で列挙できます。
（余談：実は $f$ は $(0,1,1,0,-1,-1,0,1,1,0,-1,-1,\ldots)$ と $6$ 個周期で繰り返していることが、漸化式を解くか実験をすることで分かります）
長さ $n$ の極大なブロックの個数を $g_n = \max(m-n+1,0)$ と置けば、求める答えは、形式的冪級数 $F(x) = \sum_{n=1}^{N} f_ng_nx ^ n$ として$[x ^ N] \frac{1}{1-F(x)}$ です。これは $\mathrm{O}(N\log N)$ で計算できます。
実装（の本質部分）
long long n, m;
array<mint, 6> f{0, -1, -1, 0, 1, 1};
int main() {
cin >> n >> m;
fps g(n + 1);
g[0] = 1;
for(int i = 1; i <= min(n, m); i++) g[i] = f[i % 6] * (m + 1 - i);
cout << g.inv()[n] << endl;
}
ARC 170 の Writer をやりました
やりました
きっかけ
問題思いついて投げるのを繰り返してたら案外問題ストックが溜まってきたので、単独コンテストをやりたいなって思って準備しました。
卒論期間中に Writer やったら Writer 当てられなさそうだし面白いかな？って思ってこの時期にしました。みなさんの応援のおかげでそろそろ卒論出せそうです、ありがとうございます！
問題の感想
A:Yet Another AB Problem
前回の単独 ARC の A が AB Palindrome という AB 文字列に操作をしてなんやかんやの問題だったので、似た感じに考えてたら出来ました。設定が自然で良い。
なんだかんだ A だとは思うけど、少し難しいですよね。簡単な A が作れるようになりたいです。
B:Arithmetic Progression Subsequence
前回の単独 ARC の D で等差数列を含まない集合に関する問題Non Arithmetic Progression Set を出したので、今回は等差数列を含むという設定で考えてたら生えました。
まあこれは典型かなと思っていますが、TL で解説賢い！という声を何件か聞いて嬉しかったです。解説より速い解法もあるらしい。
C:Prefix Mex Sequence
今回一番のお気に入り。Yukicoder かどこかで接頭辞の eq,neq に関する条件が付いた問題を見て作った気がしてたのですが、Yukicoder 探してもそういう問題なかったので夢だったかもです。
Ad-hoc よりだと思います。ARC では 3 連続で Mex ネタを出していますが、毎回問題のタイプが違う感じで面白いです。（4 連続は、ないかな）
D:Triangle Card Game
昔の ARC に 3 人でカードゲーム という問題があり、自分も 3 人以上でのゲーム問題を考えてみたのですが、作れなかったので 3 人を三角に変えてみたら生えました。
普段僕が作らないタイプの問題で、想定解は OI とかでありそうな感じになっています。noshi 先生のユーザー解説解法は、天才だと思います、どっちの解法も好きです。
もともと550 点で ARC-C に置かれる予定でしたが、解かれ方見た感じ D で良かったっぽいです。
E:BDFS
はじめに、やや難読気味だったみたいで申し訳ないです。random に BFS と DFS を行うという設定が好きで、元々なもりだったのでこういう書き方でしたが、円グラフに変えたのでもう少し分かりやすい表記でも良かったかなと思っています、ここは反省点です。
設定がかなり好きなタイプの問題です、解法は言われればそんなに難しくないと思います。Tester の maspy さんは 15 分くらいで解いててびっくりしました。
Tester さんから指摘があるまで E と F が逆でした。（あぶない）
F:Edge Deletion 2
今回のボス枠です。はじめ D 提案でした。（？？？）
大まかな解法を立てるのは全然難しくないと思うけど、書いてみると色々罠があって大変。Tester さん以外で日本でまだ解いてる人いないっぽい（2024/1/23時点）ので、是非チャレンジしてみてください！
まとめ
久々の単独 ARC でしたが、全問自分の問題なので色々感想が聞けて面白かったです！
また、僕が数え上げ以外の準備経験がなさ過ぎて D や F のテストケースがはじめ弱かったですが、maspy さん Nyaan さんお二方の力で強くしていただきました。本当にありがとうございました。D の乱択を落としきれなかったのは僕の弱さです、すみません。
参加していただいたみなさん、ありがとうございました。また ARC を書くと思うのでよろしくお願いします！
upsolve もぜひぜひ。
【SDVX】つまみが回せなくてもインペになりたい人におすすめの譜面紹介！
こちらはB4UT Advent Calendar参加記事です。記事一覧はこちら
はじめに
こんにちは、B4UT 4th のつちのこです。最近、SDVX でインペリアルになりました！嬉しいです。
今回の記事では、インペリアル達成のために稼げる譜面、その中でもボルテをサブ機種として始めた人におすすめ、特にボルテ特有の要素であるつまみが簡単で鍵盤主体の譜面をどんどん紹介していこうと思います。
今回の記事の対象読者
チュウニズムやオンゲキ、iidx をメイン音ゲーでやってきたけど、ボルテでもインペリアル達成したい！けどつまみ難しい！みたいな人です。
つまみ回せる人はなんでもできるポテンシャルがあると思うので頑張ってください（投げやり）。
それでは本編です。
鍵盤主体で S が取りやすい 19 紹介
Immortal saga
まずは、イモサガです。この曲はまじで単純なつまみしかなく、鍵盤もあまり難しくないので、19 初 S におすすめです。正規譜面は左手の負荷がややでかいので、ミラーが当たりです。
↑つまみ下手すぎてここ抜けがち（？？？）
Trill auf G
これも鍵盤主体で、かつノーツが多いのでとてもスコアが出やすいです。(BPM 188 の 24 分は当然間に合わないので諦める）
↑最近、両手でゆっくりつまみ回せばいいことに気付きました。
FLOWER
つまみ、ほぼなし。
↑ここは覚えましょう。
LaμreLs ~the Angelus~
速いだけで鍵盤もつまみも単純なので、行けます。（省略）
LubedeR
実はこの譜面、つまみ譜面じゃなくて片手力譜面です。つまみは下の箇所以外ほぼ全部直角だけなので、適当にガチャガチャしていれば入ります。許容が超狭いので S はちょっとむずいかも。
↑魂のハイエナ
Sailing Force
まじでつまみ簡単です、24 分でニアを減らすゲーム
↑つまみを入れたあとは両手でトリルを取ると安定しやすいです。
Staring at star, Fin.ArcDeaR, 極圏
特に言うことない譜面、鍵盤です。癖には注意。
XyHATTE
何箇所か難しいところはありますが、そこさえ対策すれば全然 S 可能コンテンツです。以下で難所の解説をします。
↑直角は入らないので、諦めましょう。ラストも同様。
↑左3右3->左3右3 で餡蜜が S 狙いでは非常におすすめです。片手 6 連打は絶対間に合わないし、正規は人間にはもっと不可能。
↑青をめっちゃ見ると良いです。（普通に抜けるけど）
↑左つまみ、右鍵盤から入ることを意識しまくる。
ここら辺さえ覚えれば、あとは鍵盤を無心で押せば S 出ます！
BLACK or WHITE?
暗記さえすれば、つまみの形自体はむずくないです。あと許容が広い。開幕が最難関なんですが、おすすめの運指を記します。
↑右手で BCDCB と 3 連階段を処理します。左手が弱い人に特におすすめ。右手で折り返しが来る部分は普通に頑張りましょう。（FX 出張とかもあるみたいですが、普通に押したほうが安定しました。）
DIABLOSIS::Nāga
つまみはむずかしいけど、鍵盤が簡単すぎるのでおすすめです。（ぼくはニア16、エラーがつまみ14の残り0で、16-14 で S 出しました）
月光乱舞
簡単なんですが、癖がつきやすすぎるので本当におすすめしたくはないです。988 とか出たから行ける！とか言って粘着しないように。
まとめ
ハイエナしたり、つまみ少ない 19 触ってればインペリアルにはなれるけど、そこから苦労する（している）ので、皆さんはつまみもちゃんとやりましょう。（Pet Peeve 未鳥、灼熱未鳥プラです、助けて～）
ICPC2023 Asia Yokohama Regional・nok0 (チームSPJ) 視点
今回はそこそこ結果に満足できたので、書きます。割と適当に時系列順に書きなぐる感じです。
本番前
去年の横浜は正直散々な結果でした、実力的には 1 桁順位取って当然な状況だったにもかかわらず酷い冷え方をして、本当に悔しかったのを覚えています。
今年は実力を出し切ることを目標にしていました。また、上振れて僕のレートがチームで一番高くなっていた1 ので、貢献できないとまずいなとも思ってました。 不安要素としては、卒論や駒場祭準備などで去年に比べて忙しく練習がそこまで取れていない点や、エディタをVS Codium から CLion に変えた点などがありました。
Day 1
存在しませんでした。2チームメイトとスタッフの皆さんには多大に迷惑をお掛けしてしまったみたいで、本当に申し訳ないです。
チーム自己紹介の終わり際について、ちょっとだけ環境を確認していました。
チームメイト二人はなぜか夕飯食べに行くことなく帰っちゃったので、慶応の masamune の皆さんについていき、中華街でご飯を食べました。masanune の皆さん、ありがとうございました！全然メニュー貰えなくてイライラしたりもしましたが、コスパは抜群で良かったです。
ご飯後はまーたさんと小さいゲーセンで少し音ゲーをして、音ゲー欲を発散しました。
早く寝たかったのですが、ABC330 の Writer をしていたので Clar 対応をしていました。ABC330-G はかなり面倒な問題だったのですが、最終的に複数 AC 出てて嬉しかったです。ABC が終わって少しして、寝ました。
Day 2
いつものことですが、あまり眠れなかったです。5 時くらいに起きて、そこから二度寝を試みるもうまくいかずぼーっとしてました。
コンテスト会場には 8:40 直前につき、緊張するな～と言いながら待機してました。今回は setup をくまーに任せて、A を自分が読んでやる感じの初動でした。
コンテスト中
A 問題を緊張しながら読むと、まあ簡単だったので DP を書いて実装、AC。B も程なくして通りました。
その後 F から順に読むが、F が簡単には見えなくてむずいかも？と言ってしまい、反省です。F をくまーに投げるとぱっと解いてくれて助かりました。D は明らかにくまーが得意分野なので任せることに、繰り返し回数が 9 以下なことだけ気づいたのでそこを強調しておきました。（大事そうでよかった）
僕は数え上げ担当なので E と G を考えます。 E は素直な bit DP で解けることに気付き提出するも、配列適当に確保しすぎて TLE 。定数倍を詰めると手元で 16 sec で不安だったが、これ以上早くならない気がしたのでお願いしながら出すと無事 AC が帰ってきて安心します。
K をチームメイトが考えている間に G を考えます。よく考えると状態数が少ないいつものやつであることに気付き、K の実装途中でしたが G の実装が非常に軽いことから交代してもらい、すぐに AC。 K もその勢いで通ります。
残りは C,H,I,J です。AC 数と得意分野的に自分が H 、zkou が I 、くまーが J を考えることとします。この割り振りが結果的に功を奏しました。
10 分程度で、zkou が I の想定解と同じ解法を急に言ってくれて、感動。実装も最初は大変な方針があったらしいですが、幾何担当のくまーが簡単な実装を思いついてくれて、I を FA。チームメイト二人が天才すぎてありがたいです。
H は最初 DP を考えていたが、問題的にどうしようもない気がして詰まっていました。制約が小さく、各 $i$ について状態を $2$ つのどちらかにすることから Project Selection Problem か？と思うと解法が生えます。 普段はライブラリで辺を張っているので、辺の張り方がわからず zkou に相談しながら無事 AC！実は計算量 $ 10 ^ {10 }$ オーダーでしたが、フローなので行ける！と言って勇気を出してよかったです。（賢く辺を張れば頂点数が $2$ 乗オーダーにならないことにコンテスト後に気付く）
C, J は残りの時間並列に考えていましたが、解けませんでした。C はある程度詰まっていて、最後の処理が書ききれなかったですが、tonosama の話を聞いている感じ出していても TLE してたかなという印象。
J は貪欲に気づけないの良くないですね、一つの解法に固執してしまったのが反省です。
結果
5 位で、東大内では 3 位でした。Speed Star はやっぱり強いですね、悔しいという感情を抱くのが程遠い程度には実力差があります。
The Raspberry Candies に負けたのは普通に悔しいです。DELIAIR と The Raspberry Candies はライバルという印象で、今年で引退されるので、勝ち切りたかったです。
懇親
大会に参加された方、スタッフの方、企業の方とそこそこお話できました。JAG の夏合宿で話した人から声を掛けてもらえてとても嬉しかったです、次回こそは名札を持っていきます。
まとめ
良くも悪くも今の実力相応の結果だったかなと思います。去年よりは勿論非常に良い結果で、実力を出せたのは嬉しいんですが、まだまだ強さが足りないなというところもあり悔しいです。
来年は僕たちのチームが最高代ということになります。5 年間同じチームで出ているというのはかなりレアだと思うので、有終の美を飾れるよう頑張ります。応援よろしくお願いします。
p.s. 来年は駒場祭と日程ずらしてくれると嬉しいです、後宿泊費もうちょい欲しいです（横浜のホテル、高い！）
ICPC 2023 国内予選 参加記
はじめに
ICPC 2023 国内予選に nok0、Kite_kuma、zkou で出場しました。予選 3 位で、アジア地区予選への出場を決めました！嬉しい
チーム紹介
nok0
数え上げが好き（得意ではない）。実装は割とできるタイプで、タイピングが早めなのでめんどい実装を気合でゴリ押す問題が得意。時々変な知識を人のブログで仕入れたりしている。
ICPC で良く出る構文解析、幾何とかは全然出来ないのでチームメイトに任せている。最適化も苦手。
Kite_kuma
ぼくができないこと全般が得意そう。構文解析も幾何もできる。数え上げは得意じゃなくて嫌いらしいが、ぼくの ARC162 の D,E を普通に通していたので数え上げ苦手でもなさそう。
幾何とか DP とかをよく書いている。
zkou
天才。典型知識は橙なのに全然なくてびっくりするけど、構築とか天才パズルに異常に強い。また、国内予選はいつもぼくと Kite_kuma はすごい緊張しているが、彼は緊張せず毎年高いパフォーマンスを発揮しているので凄い。
Python 使いかつ実装が遅いので、並列なしのコンテストでは実装 0 で、常に考察をしてもらっている。
まとめ
3 人の得意分野が全然違うので、チーム全体としてはかなりバランス良くまとまっている気がする。チーム 4 年目なこともあって、最近連携もかなりスムーズになってきていい感じ。
前日まで
去年まで予選は並列ありだったので、並列なしでの練習を繰り返していた。 毎週あった Universal Cup はめちゃくちゃありがたかった。正直国内予選、模擬予選の問題は殆ど使い果たしていたので、適当に残ってる問題でセットを組んで 3h 練習するのも何度か行った。
当日（コンテストまで）
朝起きたら緊張が酷かったので、午前中は音ゲーをして緊張を緩和することにした。音ゲーでそこそこ高いスコアが沢山出てテンションが上がった。
14 時前くらいに大学に集まって、準備を始めた。モニターの配置やキーボードの配置などをして、リハーサルで 1 問通した。
15 時からは暇だったので、お菓子を買いに行き、お菓子食べながら暇だ～と言っていた。隣のチームから何位目標？と聞かれ、Speed Star と tonosama に勝つのは流石に厳しそうなので、3 位目標かな～と答える。（まさかこれが現実になるとは思ってなかった）
16 時 20 分くらいから、また緊張してきて困った。
当日（コンテスト）
コンテストが始まったので、問題文を印刷する。プリンターの調子が悪くて、印刷が遅くて焦る。
とりあえずテンプレを写経しながら、Kite_kuma に A を読んでもらう。自明だったので途中で交代し、実装してもらう。
A 問題を AC(3:41)
手が空いたので、zkou くんから B の概要を聞く。上からと下からをやると簡単に解けることに気付き、実装。
B 問題を AC(15:11)
C が構築だったので zkou に任せ、ぼくと Kite_kuma は D を考える。 7 個が上界と聞き、確かにーとなり、枝狩り全探索で解けることを主張。実装してもらう。
D の実装が終わったが重いらしいので、実装を奪って軽くする。まだ動かないらしい + zkou が C が解けたと主張しているので、D を print debug し、C の実装に移動。
C は、偶数行目について半分に分けて swap ->偶数列目について半分に分けて swap をすると通るらしい。本当？と思いながら実装をする。validator を書けと言われ、確かにと思いながら書くと、全てのテストケースでうまくいっていることが分かる。安心して提出。
C 問題を AC(39:56)
C をやっているうちに、D のデバッグが終わったらしい。直すと、そこそこの速度で実行が終わる。
D 問題を AC(44:06)
ここらへんで、前半が順調でみんなテンションが上がってくる。全員で E を考察。zkou が inline DP を主張するので、自分が整理するとセグ木を使って $ O ( N ^ 2 \log N ) $ で解けることが分かる。実装をすると一瞬で実装が終わる。実行すると、1 ファイル 5 分くらいかかり、色々定数倍良くしたりを考えるが、所詮 10 分で終わるので放置する。
E 問題を AC(1:26:25)
F は幾何だったので Kite_kuma と zkou に任せ、G に向かう。G で式を弄っていたら、 zkou が F の本質に気付いたらしい（天才！）。 Kite_kuma が実装すると．．．
F 問題を AC(1:43:47) ！
正直、ここら辺で予選確定した感がありかなり嬉しかった。しかしコンテストはまだ 80 分くらい残っていたので、慢心せず G を解くこととする。
G 問題の式変形を終えると、zkou くんの変形と一致したので安心する。更に丁寧に変形すると、DP で持てる形となる。この時点では、 $ O ( N ^ 2 M ^ 2 \sum a_{i,j} ) $ だったので遅くて困ると言っていたが、二人に分配するとき、片方が空になるような最適解がないことに着目すると、$M$ が落ちて、十分高速であることを指摘される。これを丁寧に実装すると
G 問題を AC(2:20:44) ！！！
G の AC により、地区予選進出をほぼ確定させ、チームメイトと喜びまくった。その後は H をぼんやり考えていたが何もわからず、順位表を見たりしていた。
まとめ
今回の結果は、正直練習と比べても一番高いパフォーマンスで、本当に嬉しかったです。ペナも出さず考察もスムーズで、最高に上手くいったコンテストでした。
zkou 君は C,F で天才を遺憾なく発揮してくれて、式変形の正当性などをしっかりチェックしてくれて本当に助かりました。 MVP。
Kite_kuma 君は、F の幾何をしっかり通してくれて神。コンテスト後に、F は丁寧に実装しないと落ちることを聞き、ひえーとなった。（多分ぼくが書いたら WA が出ている）
自分も、BCDEG の実装をして、ほぼバグらせず全部ノーペナで通せ、考察も BDEG ではそこそこ担当したので、中々に貢献できたのかなと思います。去年の国内予選はあまり貢献できなくて悔しかったので、その悔しさを今回で晴らせました。
アジア地区予選に向けて
アジア地区予選は、去年酷い成績を取ってしまったので、今年は頑張って良い成績を持ち帰れるようにしたいです。
自らの課題としては、チームの中で担当分野である数え上げがあまり強くないことが挙げられると思っていて、これからアジア地区予選までに数え上げが得意って言えるようになりたいです。あと他の分野も強くなりたいです。
SolveMe (AOJ 2378)
この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 25 日目の記事です。
問題リンク
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2378 (1200+ 点)
問題概要
集合 $S={0,1,\ldots,N-1}$ にたいして、 $S\to S$ の写像 $f,g$ を考える。 $(f,g)$ の組であって、$f ^ X g f ^Y g f ^Z$ が恒等写像となるものは何通りあるか、$1000000007$ で割ったあまりを求めよ。
制約
- $1 \leq N_A,N_B \leq 1000$
- $ |X|,|Y|,|Z|\leq 10 ^ {18}$
- 入力は全て整数
解法
$X=Y=Z=0$ のときはコーナーケースなので別途処理します。そうでない場合、$f,g$ は全単射であることが要請されます。式変形により、
$$(f ^ Y g) ^ 2 = f ^{(Y-X-Z)} $$
を満たす $(f,g)$ を数え上げればよいです。適切に置きなおし、$Y-X-Z<0$ のときは逆写像を考えることで、条件は
$$f ^ 2 = g ^{K}\ (K = |Y-X-Z|) $$
と表せます。
直接 $(f,g)$ を数え上げるのは難しいので、一工夫します。$h=f ^2 (=g ^ K)$ と置き、$h$ すべてに対して、($f ^ 2=h$ なる $f$ の個数) $\times$ ($g ^K=h$ なる $f$ の個数) を求め、足し合わせたものが答えと一致するので、そちらを数え上げます。
まずは、$h$ についてです。写像 $f$ はいくつかのサイクルに分解されますが、これを $k$ 乗すると、長さ $N$ のサイクル $1$ 個は 長さ $N/\mathrm{gcd}(k,N)$ のサイクル $\mathrm{gcd}(k,N)$ 個になることがわかります。
なので、まず $h$ に含まれる長さ $i$ のサイクルの個数を決め打ち、次にそれを生成する $f,g$ の個数を掛け合わせていけばよいです。前者は単純な動的計画法で出来ます。
後者についてです。長さ $i$ のサイクルが $j$ 個あるとき、それを生成する方法を求めればよいですが、これも同様の動的計画法で出来ます。
ただし、複数のサイクルを組み合わせて一つのサイクルを作るとき、サイクルを組み合わせる順番、組み合わせる際のオフセット、などやや丁寧に考えるべき点が多いです。自分はオフセットの考慮を忘れていて無限に困っていました。
サンプルが弱いこともあり、デバッグがそのままでは大変しづらいので、愚直テストを書くのが有効な問題だと思いました。
実装例 (c++)
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using vi = vector<int>; #define rep(i, x) for(int i = 0; i < (x); i++) #define rng(i, l, r) for(int i = (l); i < (r); i++) #define sz(v) (int)(v).size() #define all(v) (v).begin(), (v).end() constexpr int mod = 1000000007; struct mint { ll v; mint(ll x = 0) { v = x; v %= mod; if(v < 0) v += mod; } mint operator+(mint o) { return v + o.v; } mint operator-(mint o) { return v - o.v; } mint operator*(mint o) { return v * o.v; } mint pow(ll k) { assert(k >= 0); mint ret = 1, a = v; while(k) { if(k & 1) ret = ret * a; a = a * a; k >>= 1; } return ret; } mint inv() { return pow(mod - 2); } mint operator/(mint o) { return v * o.inv().v; } }; vector<mint> fac, finv; void init(int n) { fac.resize(n + 1); finv.resize(n + 1); fac[0] = finv[0] = 1; rep(i, n) fac[i + 1] = fac[i] * (i + 1); finv[n] = fac[n].inv(); for(int i = n - 1; i >= 1; i--) finv[i] = finv[i + 1] * (i + 1); } mint binom(int n, int k) { if(min(n, k) < 0 or n < k) return 0; return fac[n] * finv[k] * finv[n - k]; } int main() { int n; ll X, Y, Z; cin >> n >> X >> Y >> Z; if(X == 0 and Y == 0 and Z == 0) { vector<mint> a{1, 1}; rng(i, 2, n + 1) a.push_back(a[i - 1] + a[i - 2] * (i - 1)); cout << (a[n] * mint(n).pow(n)).v << endl; return 0; } init(1000); ll k = abs(Y - X - Z); // (i = j / gcd(j, k)) * gcd(j, k) auto make_table = [&](ll x) { vector table(n + 1, vector(n + 1, mint(0))); rng(i, 1, n + 1) { vi tmp; rng(j, 1, n + 1) { if(j / gcd(j, x) != i) continue; tmp.push_back(gcd(j, x)); } if(tmp.empty()) continue; int m = sz(tmp); // j個のグループを、tmp[k]以下を使って分配する個数 vector dp(m + 1, vector(n / i + 1, mint(0))); dp[0][0] = 1; rep(id, m) { mint pw = mint(i).pow(tmp[id] - 1); rep(j, n / i + 1) { mint tar = 1; for(int u = 0; u * tmp[id] <= j; u++) { dp[id + 1][j] = dp[id + 1][j] + dp[id][j - u * tmp[id]] * tar * finv[u]; tar = tar * binom(j - u * tmp[id], tmp[id]) * fac[tmp[id] - 1] * pw; } } } rep(j, n / i + 1) table[i][j] = dp.back()[j]; } return table; }; auto lt = make_table(2); auto rt = make_table(k); vector dp(n + 1, vector(n + 1, mint(0))); dp[0][n] = 1; rng(i, 1, n + 1) { rep(j, n + 1) { dp[i][j] = dp[i][j] + dp[i - 1][j]; //完成形のグループを決め打つ //それを適切に分配する mint cur = 1; for(int u = 1; u * i <= j; u++) { cur = cur * binom(j - i * (u - 1), i) * fac[i - 1]; mint tar = cur / fac[u]; mint lef = lt[i][u], rig = rt[i][u]; dp[i][j - u * i] = dp[i][j - u * i] + dp[i - 1][j] * tar * lef * rig; } } } cout << dp[n][0].v << endl; }
感想
近年の数え上げのインフレ？もあり、1200+ にしてはかなり解きやすいように感じました。ただ、正確な数え上げを要求されることもあり、中々芯のある問題で面白かったです。
ねこ鍋改造計画（仮） (AOJ 2337)
この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 12 日目の記事です。
問題リンク
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2337 (1000 点)
問題概要
$N_a$ 匹のオスのネコ、 $N_b$ 匹のメスのネコがいて、各猫には固有の重さとかわいさが定まっている。
重さの和が $W$ を超えないようにオスのネコを $1$ 匹以上選ぶ。メスのネコについても同様に選ぶ。 このとき、$\mathrm{max}( |$選んだオスのネコの重さの和 - 選んだメスのネコの重さの和$|,$ 選んだネコの可愛さの最大値 - 選んだネコの可愛さの最小値$)$ を最小化せよ。
制約
- $1 \leq N_A,N_B \leq 500$
- $1 \leq W \leq 10^ 4 $
- $1 \leq$ 各ネコの重さ $ \leq 10^ 4 $
- $1 \leq$ 各ネコのかわいさ $ \leq 10^ 9 $
解法
まず、重さが $W$ より大きいネコが入力に含まれうる（非本質。。）のでそのようなネコを捨てます。
次に、目的関数の第二項、すなわち (選んだネコの可愛さの最大値 - 選んだネコの可愛さの最小値) の取り得る最小値を求めます。これは適当に全探索しても十分間に合いますし、ソートすればより高速です。
第二項の最小値が $W-1$ 以上のとき、第一項は $W-1$ 以下であることからそれを答えとして出力すればよいです。
以下そうでない場合を解きます。最大値の最小化なので二分探索をします。答えを $x$ 以下に出来るかという判定問題について考えます。
愚直な解法として、ネコの可愛さの最小値を決め打つと、使えるネコの集合が決まるので、部分和問題を解くことで判定問題に答えられます。しかしこの解法は $\mathrm{O}(N ^ 2 W) $ かかります。(昔の問題なので bitset 高速化でこの解法も通ってしまうようです)
ここではより計算量のよい解法で解きます。ネコをかわいさでソートしておき、尺取り法のように部分和 DP を更新することを考えます。この際、使えなくなったネコによる遷移を打ち消す（戻す DP)必要性が生じます。
「部分集合であって重さ w を達成できるか？」という bool を管理する DP は戻すことが難しいですが、 boolを持つのでなく、かわりに「部分集合であって重さ w を達成できるものは何通りか $\text{mod}$ 適当な数」という個数を管理する DP にすることで、戻す DP が可能となり尺取り法のような DP 更新が可能となります。
以上でこの問題を $\mathrm{O}(NW \log W) $ で解くことが出来ました。
実装例 (c++)
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define rep(i, x) for(int i = 0; i < (x); i++) #define rng(i, l, r) for(int i = (l); i < (r); i++) #define sz(v) (int)(v).size() #define all(v) (v).begin(), (v).end() constexpr int mod = 1000000007; struct mint { ll v; mint(ll x = 0) { v = x % mod; if(v < 0) v += mod; } mint operator+(mint a) { return v + a.v; } mint operator-(mint a) { return v - a.v; } mint operator*(mint a) { return v * a.v; } }; using fps = vector<mint>; // f *= (1 + x^d) void multiply(fps &f, int d) { for(int i = sz(f) - 1 - d; i >= 0; i--) f[i + d] = f[i + d] + f[i]; } // f /= (1 + x^d) void divide(fps &f, int d) { rep(i, sz(f) - d) f[i + d] = f[i + d] - f[i]; } int main() { int na, nb, w; cin >> na >> nb >> w; using T = tuple<int, int, int>; vector<T> ctm; rep(i, na) { int m, c; cin >> m >> c; if(m > w) continue; ctm.push_back({c, 0, m}); } rep(i, nb) { int m, c; cin >> m >> c; if(m > w) continue; ctm.push_back({c, 1, m}); } sort(all(ctm)); int term2_min = 1 << 30; rep(i, sz(ctm) - 1) { if(get<1>(ctm[i]) != get<1>(ctm[i + 1])) { term2_min = min(term2_min, get<0>(ctm[i + 1]) - get<0>(ctm[i])); } } if(term2_min >= w - 1) { cout << term2_min << endl; return 0; } auto f = [&](int x) -> bool { vector<fps> fs(2, fps(w + 1)); fs[0][0] = fs[1][0] = 1; queue<T> que; for(auto [c, t, m] : ctm) { while(!que.empty() and c - get<0>(que.front()) > x) { auto [oc, ot, om] = que.front(); que.pop(); divide(fs[ot], om); } que.push(T{c, t, m}); multiply(fs[t], m); pii bef = {-(1 << 30), 0}; rng(i, 1, w + 1) { rep(j, 2) { if(fs[j][i].v != 0) { if(i - bef.first <= x and bef.second != j) return true; bef = {i, j}; } } } } return false; }; int ok = w, ng = -1, mid; while(mid = (ok + ng) >> 1, ok - ng > 1) (f(mid) ? ok : ng) = mid; cout << ok << endl; }
感想
AOJ-ICPC では 1000 点が付いていますが、特に難しい考察もなく、実装も平易なので 1000 点初 AC を狙いたい人にはお勧めかもしれません。
