作問まとめ
---
yukicoder contest 426
初の単独コンテスト
A - Amaou
元ネタはクイズのベタ問「『あかい』『まるい』『おおきい』『うまい』の頭文字をとって名付けられた福岡県のイチゴは何でしょう？」です．
上級者の方にとってははいで終わりがちな簡単枠ではありますが，「あかい」を「あまい」だと思っていたなど別の学びがあればなと思い作問しました．
"akai", "marui", "okii", "umai" の個数を別々に数える素朴な解法もありますが，この機会にソートの便利な使い方の一つである「順序を無視したいときはソート」を身につけてもらえればと思い作問しました．
なお，これが B 問題へのヒントにもなっています．
B - Unique Chimatagram
元ネタはニコリのパズル「チマタグラム」です．好きな文字を 1 文字追加できるのでアナグラムと比べてかなり作りやすいです．
文字の頻度分布を管理してもいいのですが，文字列が短いので「順序を無視したいときはソート」で済ませてしまうと楽だと思います．
ここで問題：
Python3書こう（ぱいそんさんかこう）から 1 文字削って並べ替え，【四字熟語】にしてください．
皆さんもぜひ作ってみてください！
C - Falcon Method
元ネタはファイアーエムブレムシリーズ GBA 三部作における乱数調整法，通称「ファルコン法」です．
RTA でカーソルを小刻みに動かしているのを見たことがある方もいるのではないでしょうか．
失敗してもリセットで戻せるので乱数調整入門におすすめかもしれません．
一通りの競プロ典型が身についてきた人に向けての実践的な複合問題になればと思い作問しました．
「単調性がある→答えで二分探索」，「区間和を高速に→累積和」，「周期性がある→1周期はまとめて計算」のそれぞれが正しく処理できたでしょうか．
D - Sum of Subarray of Subsequence
どっちがどっちだったっけ？となりがちな「部分列」と「部分文字列」ですが，同時に登場させればその心配もないだろうというところから思いつきました．結局文字列ではなかったので呼称は部分文字列ではなく「連続部分列」に改めてしまいましたが……
問題が入れ子になっていますが定石通り主客転倒で解けます．式の整理では二項係数の「くくり出し公式」bin(n, r) = n/r bin(n-1, r-1) が活躍します．
結果が思った以上に簡潔な式になったので，もっと組み合わせても解けるのでは？となり G 問題が生まれました．
E - Best Consonance
元ネタは音楽理論より協和音のしくみです．ずっっと昔に MIDI の打ち込みをやっていたことがあり，ほんっっの少しだけ音楽理論をかじっていたことが活かせました．ただこの理屈だと純粋な正弦波同士はハモっていないことに・・・？
最も調和している楽器の組を見つける問題で「調和級数」に関係する計算量解析が出てくるの面白くない？と思っていたのですが，テスターの Shirotsume さんに約数列挙でも解けることを教えてもらいあっ……となりました．Shirotsume さんの解説もぜひお読みください．
F - Equal Inner Products in Permutation
構築系の問題が好きなので自分でも 1 問は作ってみたいなと思い試行錯誤の末なんとか生まれました．
想定解よりも大幅に思いつきやすい別解がないだろうか不安でたまりませんでしたが，大丈夫だったかな・・・？
「小さいパターンを作りそれを繋ぐ」というのは構築系問題ではしばしば見かけますが，本問では同じ数を二度使えないので単純には適用できません．それでも粘れば定数加算により性質が崩れないパターンを見つけるというアイデアにたどり着けるかと思います．
G - Sum of Subarray of Subsequence of…
D を一般化した問題で今回のコンテストのボス枠です．どう考えても自分の実力を超えた難易度なのですがたまたま解けてしまったので出題したくなり，せっかくならと取り巻きを揃えてのコンテストの開催に至りました．yukicoder さんありがとうございました！
二項変換とは指数型母関数の方が相性がいいのですが，誘惑を振り切って通常型母関数を選択し，しかも展開せず因数分解形のまま計算を進めることで正解に辿り着けます．実験していてこれに気づいたときは衝撃でした．
元ポスト
---
yukicoder April Fool Contest 2025 E - 間に合いませんでした＞＜；
エイプリルフールコンテスト用のおふざけ問題
裏話 1
最初は TL を 100ms にしていたのですが，元の問題で shobonvip さんに 35ms を出されていて大慌てで TL を 20ms に縮めました．
Python だと 1 文字出力するだけで TLE するので AC 不可能な問題になってしまいましたが，元の問題の解説に C++ の実装例も載せているので許してください…
裏話 2
間に合わなかった感を出すためにやったこと：
・OUPC2024 Day2 のテスターを異常な熱量でやる（総提出数 291）
・Puzzle Boss Rush 4 のソロ攻略（Boss の討伐に丸 3 日）
・リジャッジをかけて Solved を 0 にリセット（実際は 2 月中に完成してました）
・直前の AGC で爆死して不貞寝（？）
裏話 3
テストケースハッシュ化 は通常のコンテストでも有用な場合があります．
例えばあるケースのみで WA が出たとき，ハッシュ値が奇数のときだけ exit(1) することで，1WA のままならそのケースのハッシュ値は偶数，0WA になったら奇数と確定します．
同様のことを繰り返せばハッシュ値を特定できます．
裏話 4
先に How Many Liars Are There?(2025) のテスターを引き受けていたのですが，How Many Liars Are There?(2024) の Solved が 5 しかなく，これ誰にも気づいてもらえないのでは？と思いヒントになりそうな問題を作問しました．
ヒント過剰にならないかが心配でしたが AC 数的には大丈夫そう？
元ポスト
---
MojaCoder
単発問題集
元ポスト