JOI バチャ (難易度 7+8) を開催します

JOI とは

日本情報オリンピックJOI)です。

JOI の問題に関する情報についてはこの記事をご覧ください。

qiita.com

JOI の問題には下記の特徴があります。

  • 実装量が多い
  • DP やグラフの問題が多い

難易度 7+8 のレベル感

前述した記事において、下記の言及があります。

AtCoder レート 解くべき難易度帯
水色コーダー 6〜7
青色コーダー 7〜9
黄色コーダー 8〜10

自分の感覚としても、難易度 7 は diff = 1200〜1800、難易度 8 は diff = 1400〜2000 くらいかなと思っています。

本バチャの対象レベル

対象レベルとしては水色青色の人になると思いますが、今の ABC で「水 diff を倒したい!」「青 diff を倒したい!」と思っている全ての人にオススメできます

バチャの計画

現在の難易度 7+8 の問題数は下記の通りです。

  • 難易度 7 = 39 問
  • 難易度 8 = 31 問

合計 70 問です。これを「3 問セット + 100 分」のバチャで次々に消化していきます(最終回だけ 4 問にします)。毎週月曜日と水曜日の 21:00〜22:40 で固定します。

難易度 7+8 それぞれの問題数をバランスよく配分してランダムに選択して作成します。

バチャの予定表

# 日程 難易度 7 出題数 難易度 8 出題数 リンク
1 2021-10-11 (月) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/157e1484-b91f-4474-8605-91c6c2a96227
2 2021-10-13 (水) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/f1bc9975-f614-4f1c-be9b-6b30fe4f903a
3 2021-10-18 (月) 21:00〜22:40 1 2 https://kenkoooo.com/atcoder/#/contest/show/525e23fa-94ee-463b-a48e-91956ca28423
4 2021-10-20 (水) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/28c985d4-f3e8-43ea-b971-f9513b55f94b
5 2021-10-25 (月) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/7b5669a6-9d8e-429b-9dc5-c4bf86d66a43
6 2021-10-27 (水) 21:00〜22:40 1 2 https://kenkoooo.com/atcoder/#/contest/show/e7ec1b08-4a70-4d04-a115-fd32361efa92
7 2021-11-01 (月) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/2e64d274-89bc-4be5-aecb-1fd6a30aa05a
8 2021-11-03 (水) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/787f7c00-4192-479c-90be-b9e7756e2627
9 2021-11-08 (月) 21:00〜22:40 1 2 https://kenkoooo.com/atcoder/#/contest/show/38d60372-0b48-4189-966f-024966e8a951
10 2021-11-10 (水) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/0822cf8f-dfec-4f6b-9f8f-4773b247e957
11 2021-11-15 (月) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/d2691836-9280-40ea-b1b8-04930ab33f28
12 2021-11-17 (水) 21:00〜22:40 1 2 https://kenkoooo.com/atcoder/#/contest/show/9da1531c-f364-42d9-b540-86b257890bac
13 2021-11-22 (月) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/1cb707ff-815b-45dd-ad4d-7a143fe98cda
14 2021-11-24 (水) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/5896253c-8c88-48ae-997e-93bdee62b5e5
15 2021-11-29 (月) 21:00〜22:40 1 2 https://kenkoooo.com/atcoder/#/contest/show/5375f02a-61c9-4a10-8d9c-a35a5d66b0a0
16 2021-12-01 (水) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/92677da6-79d1-4bb3-bef9-34a22e566440
17 2021-12-06 (月) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/792776d8-7321-4711-b1d4-31176fd10af3
18 2021-12-08 (水) 21:00〜22:40 1 2 https://kenkoooo.com/atcoder/#/contest/show/0731a380-bd30-4ac5-ad2f-30c8111b9527
19 2021-12-13 (月) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/8088a82e-4fbf-4594-8290-4917e1ecf3bc
20 2021-12-15 (水) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/4f811f73-abce-430e-b3d8-ee82810bc1ce
21 2021-12-20 (月) 21:00〜22:40 1 2 https://kenkoooo.com/atcoder/#/contest/show/81d794e2-8d10-4246-a6a2-283d28cf0e45
22 2021-12-22 (水) 21:00〜22:40 2 1 https://kenkoooo.com/atcoder/#/contest/show/5e085420-c402-44b6-86cb-6ea82c787c69
23 2021-12-27 (月) 21:00〜23:00 2 2 https://kenkoooo.com/atcoder/#/contest/show/1877fe8e-c92c-44bd-9988-089f2a9aa772

天下一プログラマーコンテスト2015予選B C - 擬二等辺三角形

公式解説のミスや説明不足を補って解説します

解説

部分点解法( O(L) の内容までは理解できている前提とします。

 a + 1 = b の場合のみ解説します。このとき  b をキャンセルして下記の不等式を得ます。


a + 2 \leq c \lt \min{(2a + 1, L - 2a)}

左側に等号を入れるようにしているのは、 l \leq x \lt r における整数  x の個数が  r - l と簡単に書けて便利だからです(恐らく)。

さて、ここからが本題です。 \min が残っていると考察が進まないので外すことを考えます。 これは絶対値記号を外す考察と似ていると思います。  \min を外すモチベーションとして「 \min が外れて右辺が一意に定まれば、 c の個数を左辺と右辺から簡単に求められる」があり、 考察の流れとしてはこちらが自然だと思われます。

 a + 1 = b かつ  2a + 1 \leq L - 2a の場合

整理すると以下が得られます。


a \leq \frac{L - 2}{4}

 s = \mathrm{floor}{(\frac{L - 2}{4})} とおくと、本条件下での求める個数  n_{1} は下記となります。


\begin{aligned}
n_{1} &= \sum_{a = 1}^{s} \left[ (2a + 1) - (a + 2) \right] \\
         &= \sum_{a = 1}^{s} (a - 1) \\
         &= \frac{1}{2} s (s + 1) - s \\
\end{aligned}

 a + 1 = b かつ  2a + 1 > L - 2a の場合

先ほどの条件式を利用して  s + 1 \leq a と言い換えられます。 上限が分からなくて困ったように見えますが、元の不等式の左辺と右辺を比較することで事なきを得ます。 具体的には、 a + 2 \leq c \lt L - 2a より  a + 2 \leq L - 2a として  a \leq \frac{L - 2}{3} です (この評価に等号が含まれている理由は、恐らく総和計算の際に上限としてそのまま利用できて都合がいいためです。等号成立したとき個数は  0 になるので悪影響はありません)。

 t = \mathrm{floor}{(\frac{L - 2}{3})} とおくと、本条件下での求める個数  n_{2} は下記となります。


\begin{aligned}
n_{2} &= \sum_{a = s + 1}^{t} \left[(L - 2a) - (a + 2) \right] \\
         &= \sum_{a = s + 1}^{t} (L - 3a - 2) \\
         &= -3 \left[ \frac{1}{2} t (t + 1) - \frac{1}{2} s (s + 1) \right] + (L - 2)(t - s) \\
\end{aligned}

 b + 1 = c の場合

 a + 1 = b の場合とほぼ同じです。 しかし、数え上げが重複しないように  a + 1 \lt b としておく必要があるため、 3 \leq b になることに注意が必要です。  s, t に相当する  u, v についても  L の値によっては大小関係が壊れるので注意が必要です。 詳細は解答例のコードをご確認ください。

解答例

https://atcoder.jp/contests/tenka1-2015-qualb/submissions/26354667

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
 
    ll L; cin >> L;
 
    if (L < 8) {
        // (2) より L < 8 のときは手計算(L = 5, 6, 7 すべてで 0 になる)
        COUT(0); return 0;
    }
 
    mint ans = 0;
 
    {
        // (1) a + 1 = b
        mint s = (L - 2) / 4;
        mint t = (L - 2) / 3;
 
        // (1-1) 2a + 1 <= L - 2a
        ans += s*(s+1)/2 - s;
 
        // (1-2) 2a + 1 >  L - 2a
        ans += (t*(t+1)/2 - s*(s+1)/2)*(-3) + (t-s)*(L-2);
    }
 
    {
        // (2) b + 1 = c  (a + 1 < b より 3 <= b もある)
        //     ※ L < 8 のとき u, v の大小関係が u > v になって壊れる
        mint u = (L + 1) / 3;
        mint v = (L - 2) / 2;
 
        // (2-1) b - 1 <= L - 2b
        ans += (u*(u+1)/2 - 3) - (u-2)*3;
 
        // (2-1) b - 1 >  L - 2b
        ans += (v*(v+1)/2 - u*(u+1)/2)*(-2) + (v-u)*(L-2);
    }
 
    COUT(ans);
 
    return 0;
}

謝辞

この問題は milkcoffee さんとの Lockout バチャで出会いました。milkcoffee さんいつもありがとうございます。

また、この問題の公式解説に対する指摘と正しい読み方について、いつもお世話になっている暖色コーダーさんに助けてもらいました。 いつもお世話になっています。

upsolve バチャについて

upsolve とは

コンテスト終了後に解いていない問題を解くことです。

Weblio には次のように書いてあります。

(competitive programming, neologism) To solve a problem after the end of a contest.

解けなかった問題に再挑戦するのか、それを解説 AC をするのか、問題文を見ていない問題に挑戦するのか、本記事では特に区別しないことにします。

経緯

精進においてこれがかなり重要だと思っているんですよね。 高難易度 diff を通せるようになるための必要条件だと思っています。

また、ジェシーさん主催のこどふぉバチャ に参加させてもらっているのですが、これがなかなか良くて、すっかり習慣になりました。 そこで・・・

と思ったのがキッカケです。

ルール

  • ハッシュタグ#upsolveバチャ
    • 参加募集ツイートに含めて探しやすいように(テンプレに入っています)
  • upsolve バチャを立てる(この人を「バチャ作成者」とします)
  • バチャ作成者は upsolve バチャの参加募集ツイートをする(テンプレ後述
  • 参加者は開始 10 分前までにリプをする(テンプレ後述
  • バチャ作成者は開始時刻までにリプ内容をバチャに設定する
    • 参加者ごとの ID を発行して問題の点数として設定する
    • 参加者ごとの ID はバチャ概要欄に記入する
    • 問題が被った場合は共通 ID を設けて設定する

参加募集ツイートのテンプレ

「upsolve バチャ #1」を開催します!
#upsolveバチャ

参加される方は開始時刻の 10 分前までに
テンプレを埋めてリプをお願いします!
(テンプレはルールをご覧ください)

■ 日時
yyyy-mm-dd hh:mm〜hh:mm

■ リンク
[バチャのリンクを貼る]

■ ルール
https://mts1104.hatenablog.com/entry/2021/09/28/202618

参加用ツイート(リプ)のテンプレ

■ AtCoder アカウント
[AtCoder アカウント]

■ 問題リスト
[問題1]
[問題2]
[問題3]
(※ abc200_e のような形式で)

■ 自由記述
[書きたいことを書く]

サンプル

■ AtCoder アカウント
parentheses

■ 問題リスト
abc214_e
abc218_f

■ 自由記述
よろしくお願いします!

Q&A

1 問は必ず解くべきとかある?

全くないです。バチャ中の時間の使い方や目標などは完全に自由です。

バチャの時間は何分?

標準 2 時間 (120 分) で考えていますが、ここはバチャ作成者の自由です。

問題設定の数に上限はある?

上限はありませんが、時間内に取り組み切れる範囲でお願いします。
目安として 3〜5 問あたりが現実的な上限になると思います。

こどふぉとかの問題を設定したい!

AtCoder Problems を使用しているため、残念ながら AtCoder にある問題しか設定はできませんが、 「こどふぉの hoge 問題を AtCoder の fuga 問題として設定する」ということは可能です。
その場合、バチャ作成者がその対応関係を周知することはしませんのでご了承ください。

upsolve じゃない問題をやってもいい?

やってもいいです!(upsolve バチャとはいったい何だったのか…笑)

自分で upsolve バチャを立ててもいい?

全く構いません。むしろ歓迎します!
誰かが勝手に立てて自動的に運用されていくのが理想です。

Prime & Divisor Contest 001 開催記

milkcoffee さんと共同 writer で「Prime & Divisor Contest 001」を開催しました。MMNMM さんに全体 tester をやっていただきました。参加していただいた皆様、問題を解いてくださった皆様、mojacoder 様、関係者各位、誠にありがとうございました!

mojacoder.app

想定以上に参加していただけて嬉しい半面、ジャッジが重くなってしまい途中から順位表が見られなくなってしまいました。ここは申し訳なかったです。

準備は約 1 か月前から始まりました。自分が D 問題 (Coprime Path) の原案を投げたのが 7 月 23 日で、そのあたりからになります(毎日作業していたわけではないです)。あらかじめ決められた出題分野の問題を狙って作るのは意外と難しく、特に素数・約数という分野ではそれが顕著なのかなと感じました。

自分は作問とテストケース作成の経験は少しありましたが(mojacoder に投げてる問題たち)、writer/tester をやるのは今回が初めてでした。至らない点があればごめんなさい。

文章にまとめるのが面倒になってきたので、箇条書きでつらつら書きたいと思います。開催記と言いながらメモ書きみたいになってしまいました…

  • なぜやろうと思ったか

    • 本コンテストは元々 milkcoffee さんが温めていた企画の一つで、それに参加させていただいた形になります
    • 素数・約数などの整数論の分野は元々苦手でした(今はたぶんレート相応くらいになったと思います)
    • 苦手克服のために素数・約数に関する問題を以前作問していました(いくつかは mojacoder に投げてます)
    • その延長としてチャレンジしたいと思い、milkcoffee さんに声をかけて準備が始まったという経緯です
    • 原案作成・類題調査・テストケース作成・解説作成などの作問作業を通して、素数・約数に対する認識が「数学の不思議な概念」から「正の整数の中で定義できる、様々な面白い性質を持った DAG」くらいの認識に変わりました
  • 役割分担

    • milkcoffee さん
      • コンテスト企画者
      • writer は主に ad-hoc 問題を担当
      • コンテスト全体の管理
    • mts (自分)
      • writer は主に典型問題を担当
      • Python 想定解コードを担当
      • 嘘解法もいっぱい書きました
    • MMNMM さん
      • 全体 tester をやってくださいました(詳細は後述します)
      • 天才
      • 天才(大事なことなので二回言いました)
  • 推定 diff

    • あくまで自分の推定です(milkcoffee さんも大体同じくらいでした)

    • 問題名 点数 推定 diff コメント
      A. Odd Even Divisor 200 easy 強いて言えば 20~30 くらい
      B. Div All 300 100~200 もっと低いかも
      C. LCM Knapsack 300 400~600 1 年前なら 600~800 かなあ
      D. Coprime Path 400 1000~1200 個人差がありそう
      E. 3 perf Number 400 1000~1200 個人差がありそう
      F. Rich Primer 500 1200~1400 もっと低いかも
      G. Pairwise Coprime Segments 500 1200~1400 実装が大変なのでもっと高いかも
      H. Prime Collector 600 1600~1800 1800 を超えることはないと思ってます
  • 問題ごとのコメント

    • A. Odd Even Divisor

      • 原案・writer をしました
      • 「for 文 + if 文 + 偶奇 + 約数」です
      • easy 枠ということでサクッと作りましたが、特に怖いところもなくやるだけなので、そんなに悪い問題ではないんじゃないかと思います
      •  O(N \log N) で解けることは多くの人が気付けると思いますが、 O(N \log \log N)  O(N) でも解けることを MMNMM さんに教えてもらいました。まだ理解できていません…
    • B. Div All

      • tester をしました
      • これは一目で解けました。最大公約数は便利です
      •  N \leq 10^{5}, A_{i} \leq 10^{12} なので有力な嘘解法はなさそうと思いました
      • 既出な気がしましたが、同じものは見つけられなかったのでセーフでした
    • C. LCM Knapsack

      • 原案・writer をしました
      • B・D・E・F の原案が出ている状況で全体バランス的に「最小公倍数と DP を入れたいな」と思ったのが作問のモチベーションです。合体させたら丁度良さそうなのが作れました
      • ド典型ですが結構好きな問題です
        • 恐らくド典型すぎて AtCoder だったら出せない気がします
      • 既出な気がしましたが、意外と見つかりませんでした
        • とはいえナップサック問題は有名問題なので、ナップサック問題をまだ勉強していなかった灰〜茶コーダーさんの中にはその場で勉強しながら解けた人もいたのではないでしょうか
      • MMNMM さんに  O(NW) 解法を教えてもらいましたが、まだ理解できていません…
    • D. Coprime Path

      • 原案・writer をしました
      • このコンテスト向けに自分が最初に作問した問題です
      • 木 DP + bit DP の問題を作ろうとしたら失敗して(?)、この問題が出来上がりました
      •  O(N^{3}) の愚直解が落ちることは確認しましたが、定数倍高速化の神がいたら通されるかもしれません
      • HL 分解などの別解も色々あり、いろいろ考察しがいのある問題だと思います。この問題を最初に作れて良いスタートを切れました
      • テストケース作成が大変でした。木の問題に含めるべき典型的なグラフを色々盛り込みました。 \mathrm{gcd} の計算量を考慮して色んなケースを作りました
      • 最悪ケース  O(N^{2} \log A_{\max}) の作り方がずっと分からなくて、不可能なんじゃないかと思っていたのですが(実は解説にも元々そう書いてました)、MMNMM さんに速攻で思い付いてもらって非常に助かりました(このコンテスト全体で一番感動したのがこれかもしれません)
      • 二乗の木 DP でも解けることを MMNMM さんに教えてもらいましたが、まだ理解できていません… ABC のあの問題をちゃんと upsolve しておけばよかった…
    • E. 3 perf Number

      • tester をしました
      • 自分は F 問題よりこれの方が時間かかりました
      • ad-hoc ですが結論が綺麗で感動しました
      • こういう問題を作れるようになりたいですね…
      • 全完するためにはこの問題をどれだけ早く通すかが勝負所の一つだと思います。たぶん時間泥棒です
      • tester として解いたので証明寄りで考察していましたが、そうでなければ早々に実験する気がします
      • 自分は調和級数が発散することの証明と同じ要領で証明しました(本質的には milkcoffee さんの解説と同じだと思います)
        • 約数  \frac{N}{2} を使わないことにすると、最大ケース  \frac{N}{3} + \frac{N}{4} + \frac{N}{5} の和が  N より小さくなるので、 \frac{N}{2} は必要、みたいな感じで順次 3 つの約数を確定させることができます
      • 自分のゴリ押し解法が通ってしまったので制約及びテストケースが強化されました(オフレコで)
        •  \sqrt{A_{\max}} 以下の素数リストの埋め込み
        • 素数リストを用いた高速な素因数分解
        • 約数列挙をして愚直に三完数を判定(三重ループを回して適宜 break)
      •  O(N^{1/4}) 素因数分解で殴られる可能性がありそうだけど、対策は諦めようという話をしました
    • F. Rich Primer

      • tester をしました
      • 個人的には考察しやすくて割とすぐに解けました
      • 倍数の感覚と制約の謎解きがポイントになる考察メインの問題だと思います
      • 他の問題との相対評価も加味して 500 点になりましたが、ARC なら 400 点あたりに出て緑 diff になりそうな感じもします
      •  \lfloor \frac{(A-1)}{p^{n}} \rfloor \lt \lfloor \frac{B}{p^{n}} \rfloor のチェックで  p^{n} がオーバーフローしていても実は通ってしまうので、それを咎めるテストケースを作ることを考えましたが、探すのも大変で本質部分でもないので諦めようという話をしました(たぶん探索計算しないといけなくて、そもそも見つからないかもしれない)
    • G. Pairwise Coprime Segments

      • 原案は milkcoffee さんと一緒に作りました
      • tester をしました
      • milkcoffee さんの「pairwise coprime の判定を素因数について鳩ノ巣原理を使って解かせる問題を作りたい」から始まって、二人であれこれ考えた結果、区間クエリにすればいけそうということを自分が思い付いて何とか実現しました。かなりお気に入りの問題です
      • C++ なら素因数の登場数の累積和を持っても何とか間に合います
      • MMNMM さんが  O(\pi (A_{\max})) 部分を落としていて驚きました。鳩ノ巣原理さん「えっ…」
    • H. Prime Collector

      • 原案・writer をしました
      • 自信作です!!!
      • 素数とフローの問題を作りたい」という気持ちから始まり、適当にお絵描きしていたら偶然思い付きました(まさに天啓)。既出な気もしましたが特に見つからなかったので良かったです
      • 6 問 ABC の易しめの F 問題(青 diff くらい)のイメージです
      • 自分が調べた限りでは AtCoder と yukicoder に出た最小辺被覆の問題はこの問題(8 年以上前!)しかなかったので、本問の価値は高いのではないかと思っています
      • 本当は TL を引き上げて  N \leq 10^{5} くらいにしてフローとバレにくいようにしたかったのですが、mojacoder の仕様上 TL は変更できなかったので断念しました
      • 原案の時点で問題文は「重複を許さない集合  P, Q があって最初は空。1 回の操作で  i を選んで集合  Q に入れ、同時に  A_{i} の素因数を集合  P に入れる。それぞれ全種類を入れるための最小操作回数は?」という感じだったのですが、何だかストレートで無機質な感じがして本コンテストのボス問としては面白味に欠けると思ったので、後付けですが楽しめそうな問題設定を与えました(ギルドとかクエストとか)。ここは我ながら上手く書けたと思っています
        • 非本質な情報をあえて加えた形になるので、邪道と言えるかもしれません… 集合に入れる操作が直接的すぎたので、それを避ける問題設定にして考察ステップを若干増やしたかったという狙いもあります
      • 自分の実力を超えていることもあり、テストケース作成と解説作成が本当に大変でした。しっかり時間をかけることで手を抜くことなく最後までやり切れたのでよかったです
      • writer 作業初期では高速素因数分解も要請する制約を目指していたのですが、どうにも上手く作れなかったので断念しました。そんな都合よくあれこれ詰め込めるものではないですね…
  • 全体 tester さんについて (MMNMM さん)

    • コンテストまで残り 2 日間しかない急な募集にも拘らず引き受けてくださいました
    • めちゃくちゃスピーディーかつ丁寧にチェックしてくださり本当に頭が上がらないです
    • ここまでの作業を無償かつ迅速正確にやっていただいたことに少し罪悪感を感じてしまいました… そのくらい凄まじいものがありました
      • 確か 20 分くらいで 7 問目までの解き方を一気に見抜かれました(早すぎる)
      • 気付けば tester 募集してから 24 時間以内に全ての tester 作業が完了していました
      • コンテスト本番まで時間が差し迫っているので配慮してくださったのだと思います。大変感謝しているとともに負担をかけてしまって申し訳ない気持ちも… 募集するならもっと早くにするべきでした
      • 時間的にも体力的にも、たった半日で 8 問を完璧に tester するのは暖色コーダーでも結構大変なんじゃないかと思っていて、MMNMM さんがいかに凄腕であるかということを実感しました
    • 特に下記について非常に勉強になりました
      1. 一文字ずつの入力チェック(自分は C++/Python で読み込み + assert で制約チェック、で全て確認した気になっていました…)
      2. 論理的・数学的な文章の書き方
      3. 想定解より効率的な解法
    • 大変良くしてもらったので何か恩返ししたいなーと思いつつ、今できることはコンテストの準備を完全なものに近づけることくらいなので、いただいたアドバイスを最大限に活かして、出来る限り全て対応する努力をしようと心がけていました(二乗の木 DP などは実力不足もあり自分自身での確認が間に合いませんでした)
      • とりあえず、早く黄色になりたいと思いました
  • いつもお世話になっている某暖色コーダーさん
    • いつもお世話になっています(いつもお世話になっているので)
    • 準備期間の初期に D 問題と H 問題 の原案とテストケース作成についてコメントいただきました
    • 原案を投げたらどちらも数分で解かれました(H 問題が瞬殺されたのは悔しい)
    • D 問題
      • 「ランダムに頂点を選んでグラフを生成すると確率的に直径が短くなると思われるので、もし気になるなら適当な長さのパスグラフを作ってから頂点を適当に繋げていくケースを入れると良い」ということを教えてもらい、実際にそのケースもいくつか入れました
      • binary gcd というのを教えてもらいました(これ賢い)
    • H 問題
      • 自分の実力を超えていたので、問題として成立していることが分かっただけでも助かりました
      • 時間ギリギリまで乱択する嘘解法を教えてもらいました。この嘘解法が落ちることも確かめながらテストケースを作りました
  • 反省点
    • 作問するにあたりこの記事は参考にしていたのですが、yukicoder に置いてある便利なチェックリストの存在にコンテスト前日に気が付いて、これを使っておけば効率的かつ正確な準備ができたのではと思いました(とはいえ、ほぼクリアしていたようで、MMNMM さんの tester 作業によって細部が仕上がったので、今回は特に問題なかったと思っています)
    • コンテスト 3 日前の夜遅くに思い付きで「できれば黄色以上の tester さんを募集した方がいいのでは」と思って募集したのですが、tester さんを募集すること自体の判断は良かったものの、もっと早くに募集をかけて計画的にやるべきでした(tester さんに短期集中の作業を強いる負担をかけてしまいました。それを分かっていながら引き受けてくださった MMNMM さんには本当に頭が上がりません)
    • testlib.h を MMNMM さんに教えてもらって初めて知りました。これを知らずに writer 作業していたのは世間知らずだったなと思いました
    • 問題文だけでなく解説にも細かいところで甘さがあり、MMNMM さんの指摘によって色々修正しました。ここは場数を踏んで経験していくしかないのかなと思いつつ、日頃から意識していきたいと感じさせられました
    • 同じ日に writer 作業と精進をバランスよく行うことが全くできませんでした(実質どちらかしかできなかった)。なんか頭の使い方が違う気がしていて、一方をやるともう一方をやる気にならないというか、まあ半分くらいは言い訳ですね… writer 作業はコンテスト準備が間に合えばいつやってもいいんですが、精進は小まめにやらないとすぐに実力が下がる感覚があるので、毎日できるように writer 作業との折り合いを付けられるようにしていきたいです(しばらく writer 作業を封印して年内に黄色を目指すことに集中しようと思っています)
  • その他
    • mojacoder は yukicoder よりもゆるふわで作問やコンテスト主催ができる、みたいな印象を抱いていたので、かなり本格的な作り込みをしたコンテストを開催したことでハードルを上げてしまったのかもしれない?みたいなことを少し思いました(自意識過剰かもしれません)

競プロ用ランダムテストのコード紹介(C++・Python)

本記事はこの記事の下位互換です

競プロでWAが出たときのランダム入力データ生成入門

本記事を書いている時に見つけました。
もっと多くの人に見つかりますように(調査不足でした、ごめんなさい)。

これを踏まえて、本記事の差別化ポイントとしては、 Python ユーザ向けのランダムテストとして 「Python コードだけでランダムテストができる」手順が整っていることでしょうか。

あとは特にない気がします・・・

目次

はじめに

競プロにおいて考察結果を全くミスなく実装し続けられる人はいないでしょう。 我々は人間なのでミスをします。考察は正しいはずなのに、出力される答えが合わない。 そんな時、皆さんはどうするでしょうか?

  • コードを読み直してバグを探す
  • 計算過程を出力して確認する
  • 経験則や直感を利用する
  • 典型バグ(?)のガチャをする
  • 最初から書き直す

色々あると思います。 答えが合わないテストケース(サンプルケースなど)が分かっている場合、時間をかければ大抵は解決できるでしょう。 そうでない場合(ジャッジに投げて WA が返ってくる場合)、一体どこが間違っているのか突き止める、つまりデバッグするのは難しくなります。

そんなとき、最後の手段として使えるのが「ランダムテスト」です。 ランダムテストは下記のようなステップによって行われ、 「自分の書いたコードが WA になるケース(以下、撃墜ケース)を見つけ出すこと」を目的として行われます。

  1. 計算量を無視して愚直解を求めるコード(以下、愚直コード)を書く
  2. 小規模な入力ケースをランダムに生成するコードを書く(以下、入力生成コード)
  3. 入力生成コードに対して、「WA になるコード」と「愚直コード」の2つの答えを突き合わせる
  4. 撃墜ケースが見つかるまで繰り返す

以上のことは、特に緑コーダー以上の人たちのほとんどは聞いたことがあると思いますし、既に実践している人も少なくないと思います。 しかし、ランダムテストの重要性が言及されることはあっても、具体的なコードを紹介する記事は見かけません。 これが本記事を書こうと思ったモチベーションです。 本記事の冒頭に書いたように上位互換の記事が既に存在します。

動作環境

本記事でご紹介するコードは下記の動作環境でのみ確認しています。

ランダムテストのコード(C++

シェルスクリプトを利用した C++ 用のランダムテストです*1。 用意するのは下記の4つです。

入力生成コードは Python としています(楽なので)。 問題の入力に合わせて入力生成コードを実装して、入力サイズ( N など)を小さめにしておきます。 愚直コードも実装しておきます。そうしたら、下記のようにしてランダムテストを行います。

# g++ main.cpp -o a.out
g++ greedy.cpp -o b.out
bash random_test.sh
  • main.cpp
// 絶賛バグらせ中のコードです
  • generate.py
import random
# random.seed(777)

# 1 <= K <= N <= 5
N = random.randint(1, 5)
K = random.randint(1, N)
print(f"{N} {K}")

# for _ in range(N):
#     a = random.randint(-10, 10)
#     print(a)

A = " ".join(map(str, list(random.randint(-10, 10) for _ in range(N))))
print(A)
  • greedy.cpp
// 愚直コードを書きます
  • random_test.sh
while true; do
    python3 ./generate.py > random.in
    A=$(./a.out < random.in)
    B=$(./b.out < random.in)
    if [ "$A" != "$B" ]; then
        echo "----------------------------------------"
        echo "Wrong Answer"
        echo "[test case] "
        cat random.in
        echo "[./a.out] "
        echo "$A"
        echo "[./b.out] "
        echo "$B"
        echo "----------------------------------------"
    fi
done

ランダムテストのコード(Python

Python 用のランダムテストです*2。 用意するのは下記の3つです。

C++ の方にあった generate.pyrandom_test.sh が、こちらでは random_test.py として一体になっています。

  • greedy.py
# 愚直コードを書きます
  • main.py
# 絶賛バグらせ中のコードです
  • random_test.py
import random
import subprocess

TESTCASE_FILE = "random.in"
MAIN_FILE = "main.py"
GREEDY_FILE = "greedy.py"


def read_random_case():
    with open(TESTCASE_FILE, "r", encoding="utf-8") as f:
        return "".join(map(str, f.readlines()))


# NOTE: 問題に合わせてランダムテストケースを作成する
def write_random_case():
    with open(TESTCASE_FILE, "w", encoding="utf-8") as f:
        lines = []

        # 1 <= N, K <= 10
        N = random.randint(1, 10)
        K = random.randint(1, 10)
        lines.append(f"{N} {K}")

        # N = random.randint(1, 10)
        # K = random.randint(1, 10)
        # lines.append(f"{N}")
        # lines.append(f"{K}")

        f.write("\n".join(lines))


def solve(proc_name):
    with open(TESTCASE_FILE, "r", encoding="utf-8") as f:
        res = subprocess.run(
            ["python3", proc_name], stdin=f, stdout=subprocess.PIPE, encoding="utf-8")
        return res.stdout


def main():
    while True:
        write_random_case()
        A = solve(MAIN_FILE)
        B = solve(GREEDY_FILE)
        if A != B:
            print("----------------------------------------")
            print("Wrong Answer")
            print("[test case]")
            print(read_random_case())
            print(f"[{MAIN_FILE}]")
            print(A, end="")
            print(f"[{GREEDY_FILE}]")
            print(B, end="")
            print("----------------------------------------")


if __name__ == "__main__":
    main()

ランダムテストのコードの詳細(共通)

  1. 入力生成コードから得たケースを random.in に書き込みます。
  2. 2つのコードに対してそれぞれ入力して答えを突き合わせます。
  3. 答えが一致すれば、入力ケースを作り直します(無限ループ)
  4. 答えが一致しなければ、入力ケースとそれぞれの答えを標準出力して、新しい入力ケース生成に戻ります。

挙動としては、一致しないケースが見つかるごとに詳細が標準出力に出てきます。 停止したければ [Ctrl] + [C] をしてください。

想定質問

それ別の記事にも紹介されてるよ!

二番煎じになってすみません。リンクを貼っておくので教えてください…

冒頭に書いたとおりです… 他にもあれば教えてください。

こうした方が便利だよ!

そうですね、ランダムテストの方法は色々あると思います。 いま僕はこの方法で満足していますが、より良い方法は人によって異なるため、 本記事の内容をベースに各自で使いやすいように改造してもらえればと思います。

改造などの案としては・・・

  • ビルドも組み込んで自動化する
  • alias を利用する
  • コンテスト用ディレクトリに一式コピーするようにする

それ oj にあるよ!

そうなんですよね、ランダムテストの仕組みは実は oj にも存在します。

online-judge-tools: ランダムテスト

こちらを使うことも十分に考えられます。

どのレベルから使ったほうがいいの?

これは難しいところですが、僕は青コーダーになってから使うようになりました。 僕は業務経験もそれなりにあるのでデバッグには少し自信があって、 青になるまでは特に困ることはありませんでしたが、 解くべき問題が複雑になっていくにつれてランダムテストの必要性を感じるようになりました。

個人的には、水色あたりから持っておけばよいのではないかと思います。 ただ、ランダムテストは「愚直コード」「入力生成コード」の2つを書き上げる必要があり、 実装スピードが低い人や不慣れな人がやると結構な時間を消費します。 そういう意味でも、水色くらいのレベルになってきてから導入するのがコスパがいいのかなと思います。

もしくは、必要性に駆られた時に導入する、の方が分かりやすいかもしれません。

ご参考

謝辞

  • 僕がランダムテストのコードを書くキッカケになったのは、TL に流れてきたのいみさんのツイートでした。 この場を借りてお礼申し上げます。のいみさん、ありがとうございます。

  • シェルスクリプトは露草さんの指摘によって頑健なものになりました。ありがとうございます。

  • Python 用のコードはそーさんがキッカケで作成しました。ありがとうございます。

*1:のいみさんのコードを一部改変したものです

*2:のいみさんのコードを一部改変して Python に移植したものです。random_test.py の中で C++ と被っていない部分は自分で書きました

milkcoffee Penalty Contest 001 参加記

※※※ネタバレ注意!※※※

milkcoffee さん主催の第一回ペナコンに参加しました.

mojacoder.app

せっかくなので参加記を書きます.
普段とは違って(?)砕けた文体で書いたのでご了承ください.
なお,6/9 (水) 21:30 頃から書き始めているので記憶は新しいです.

18:00 〜 18:30 頃

リモートワークを終えて夕飯を食べながら YouTube を適当に観た.ショウヘイオオタニがまたホームランを打ったらしい.

順位表も時々チェックしていた.しばらくしても 1 問目を数人しか提出していなくて,問題が難しいのか慎重になっているのかどちらかだろうな,などと考えていた.

準備

ローカルに作業フォルダを準備.ランダムテスト用のファイル群もコピー配置して準備万端(結局使わなかったけど…). このとき既に 3 完している人がいたが 3 問目は誰も解いていなかった気がする.

作戦

サンプルケースをローカルに作った上で,自作のテストケースをたくさん作って慎重にやる作戦にした. できれば愚直コードを書いてランダムテストをしたかったけど,愚直を書くタイプの問題ではなかったので, 実際は考察しながら丁寧に丁寧にテストケースを作りまくった. 問題毎に作ったテストケースの数は下記の通り(サンプルケースを除く).

  • 1 問目:12 個
  • 2 問目:18 個
  • 3 問目:14 個
  • 4 問目:18 個

また,提出は 4 問まとめてにしようとしていた. というのも,ペナ数が抑えられれば 30 時間以下の差は気にしなくていいと思ったので. 他の人の提出状況からペナ率の情報も分かるので,最後の最後まで確認してから tourist 出しするのが理に適っていると思った.

1 問目:Under M

 N^{N} の下  M 桁ですか,なるほどこれは難しい,普通の 100 点ではないですね.

Python が楽そうだなと思ったけど,多倍長整数が使えるなら C++ でもいいかなと思い, MojaCoder で boost が使えるかどうかをサンプル問題(A + B)でチェック(許される範囲ですよね…たぶん). 使えたので,多倍長整数を使うことにした.

愚直に  N^{N}多倍長整数で計算して,文字列型に変換して,下  M 桁を解析するだけ( N \leq 100 なのでこれで十分). 罠は何だろうと考えて,とりあえずサンプル 2 のように  M N^{N} の桁数を超えるケースがあった. 他は思い付かないのでテストケースを色々作ってみる. 0 が続くケースとかはちょっと怖いけど, 文字列型に変換したあとに長さが取得できるので解析も対処も割と簡単で他に罠は無さそう. 多倍長整数を使うことでかなり楽が出来た気がする(想定解は何だろう).

2 問目:RGB walking

右と下だけでなく上にも左にも移動できるので自由度が高くて難しそう,というのが第一印象.

まずは Bishop よろしく, \mathrm{min}(H, W) = 1 のケースを考えてみる. まっすぐ移動するしかないので,これは  \mathrm{mod} \, 3 で考えれば簡単. それ以外の法則はすぐ見えないので,とりあえず  (2, 2) 〜 (5, 5) を全て書いてみたら  (2, 2) 以外は全て Yes にできた.

直感的にも,盤面が広ければ調整が効くから Yes にするのは簡単そう. コーナーケースを除いてすべて Yes では? 証明が難しい… 色々お絵かきしていて「 (h, w) の道順を拡張して  (h, w+1) の道順が作れる」という傾向に気がつく. これを基に改めてお絵かきしてみたが,やはり拡張する方法で上手く Yes が作れそうだった.

ここで, (2, x) のケースの盤面が狭くて自信がなかったので  (2, 3) 〜 (2, 7) までお絵かきして問題ないことを確認. これでヨシ!

3 問目:Slice Cube

パ研合宿のあの問題を思い出した(解けてない). めちゃくちゃ苦手なタイプの問題で,最初は解ける自信がなかった.

とりあえずお絵かき.うん,全然わからない.
こういう時は調査でしょう.「立方体 切断面」でググって神サイトを見つける.

www.geogebra.org

みんなこれ使ってそうだな〜などと考えつつ,しばらく遊んでみる.割と楽しい. その結果,六角形は作れなさそうで,三角形・四角形・五角形が登場することがわかった.3 択問題ですね.

適当に  L = 10 で固定して少し自信なさげにテストケースを作る. 三角形の出現ケースに特徴があることに気付く.これは最初に場合分けできそう. 点を動かして確認すると,三角形の出現条件の中で  X = Y = Z = 0 \, \mathrm{or} \, L のときに四角形になることに気がつく.危ね〜.

残りは四角形か五角形.ここからが難しかった.他のサイトも色々読んでみたがよくわからない. しばらくして,「辺 DH を z 軸に重ねたときに,3 点を通る平面と z 軸の交点の z 座標で判別できそう」ということに気が付いた. 点を動かしてみるとこの交点の位置によって四角形と五角形が切り替わるように見えたので.

ということで平面の式の計算方法を調べる(すっかり忘れているので…). 色々あったが,今回は 3 点の座標が分かりやすいので  ax + by + c = z とおいて代入して係数を求めることにした. すんなりキャンセルして係数が求まる.コードを書いてみると WA が大量に出る.  a = \frac{Y - Z}{L} をそのまま計算して使っていたので切り捨てになっていた… うわー.

今知りたいのは  (x, y) = (0, 0) としたときの  z 座標の値なので, a, b を経由せず  c を直接求めるようにしたら,  c = X - Y + Z と綺麗に求まってビックリした.これは面白い. あとはこれが  0 \leq c \leq L なら四角形で外側なら五角形になるはず.

あれ,まだ WA が出る.あー, X = 0 とか  X = L のときに四角形になってやがる. このコーナーケースも潰して実装したところ,手元のテストケースを全てパス. 手応えがあったのでこれにて完了.丁寧に作ったテストケースに救われました.

4 問目:Sqrt Equality

お前,見たことあるぞ.

Sqrt Inequality よろしく,移項と二乗計算を駆使してルートを消した状態で等号判定すればいい. これが 4 問目だなんて,案外楽勝だな(フラグ).

順位表で意外にペナが出ているが,このときはピンと来ていなかった.

値が大きいので,再び多倍長整数を使う.丁寧に式変形をしていく. 途中で片側がルートのみになったので,反対側が負数になっていないかチェックを入れる. これは Sqrt Inequality と全く同じ.特に難しいところはない.

 \sqrt{513 \times 3^{2}} + \sqrt{513 \times 28^{2}} = \sqrt{513 \times 15^{2}} + \sqrt{513 \times 16^{2}} などの テストケースもしっかり作って,全てパスした.やはり,あっさり終わってしまった.

tourist 出し・最後の戦い

何せ初めてだったのでめちゃくちゃ緊張したが,tourist 出しを決行.この時点でノーペナ全完が二人いた.

後ろから出していったが,いきなり 4 問目が WA になるのが見えてつい笑ってしまった. そのあとも WA が続くのか? と思いきや,1 〜 3 問目は耐えてくれて AC.3 問目がノーペナは嬉しかった.

さて,4 問目と最後の戦い.ミスの原因が分からない.式変形の過程を眺める. 二乗計算は 2 回やっていて,2 回目は片側がルートのみになるので負数チェックをしているが, 1 回目は  2 (\sqrt{AB} - \sqrt{CD}) = (C + D) - (A + B) となっていて,気にせずそのまま二乗していた.

…あ〜そういうことかあ… 反例は作れなかったけど,1 回目の二乗計算でも符号確認が必要そうということに気付いた. 他に原因は思い付かなかったので,確信度 70 % くらいでこれが原因だと思い,丁寧にチェックを追加実装.

順位的には 1 ペナに抑えられると結構良さそうな結果になりそうだったので, ここでもかなり緊張したが,エイヤで投げたところ AC を獲得. 20:40 時点で 1 ペナ暫定 3 位につけた.中々上手くやったのではないだろうか.

体感 diff

体感 diff を書きます.3 問目がめちゃくちゃ難しかったです.4 問目はコーナーケースが難しくて diff が上がっている感覚です.
ところで,全て緑以下想定ってマジですか… 3 問目は人によっては考察しやすいのかな? 自分にとってはかなり辛かった.

  1. 茶 600〜800
  2. 緑 1000〜1200
  3. 青 1800〜2000
  4. 水 1200〜1400

まとめ

面白いコンテストをありがとうございました.早く解説とテストケースが見たいです. 個人的には 2 問目 と 4 問目 が好きで,3 問目はよくこの問題作れるなあ〜と感心しました.

一通り書き終わって誤字脱字等のチェックを済ませ,現在,22:50 頃なので 1 時間 20 分ほど使ってこの参加記は作成されました(もっと早く書き上げたかったけどこんなもんか…).

追記

終結果は 4 位 (1 WA) でした.終了 30 分前くらいに 3 人目のノーペナ全完者が出たようで,残念ながら 3 位から陥落しました.とはいえ,自分は 1 ペナを出していますし,調べたところノーペナ全完者は 3 人とも暖色コーダーだったので納得の結果ではあります.そもそもこんな上位になるとは思っていなかったので良い記念になって嬉しいです.

以上

Educational Codeforces Round 43 E. Well played!

公式解説を理解するのに時間がかかったので日本語の記事を書いておきます.
(現時点で日本語の記事は見つけられませんでした)

解説

便宜上,問題文にある二つの spell を「呪文 A」「呪文 B」と呼ぶことにします.

呪文 A の使い方

公式解説にある背理法の証明は個人的にはやや理解しづらかったですが, 要するに「呪文 A は一体に集中させても損しない」ということです. ここでは「どの一体を選ぶのが最適か」という話まではしていないです. あくまで,「呪文 A を使うなら一体に集中させても損しないので,その方が議論が簡単になる」ということだけ言っています.

よって, i 番目の creature に呪文 A を使うと決めたときには  hp^{'}_{i} = hp_{i} \times 2^{a} としてよいです.

呪文 B の使い方

呪文 B を  (n + 1) 回以上使う必要はないので  b = \mathrm{min}(b, n) としておきます.

どの creature に呪文 B を使うべきかを考える必要がありますが, これは「 dmg_{i} の代わりに  hp_{i} を使ったら(=呪文 B を使ったら)どのくらい得をするか」に着目して,  hp_{i} - dmg_{i} の降順ソートをすることでその利得の大きい順に creature を並べることができます(相対評価). 最大  b 体にしか呪文 B は使えないので,上位  b 体にだけ呪文 B を使うことを検討すれば十分です. ただし,この時点では呪文 A を考えていないことに注意してください. また,利得がマイナスの場合は呪文 B を使わない方が得なので呪文 B は使いません (使わずに余った分を後半の creature に回す必要もありません.なぜなら,利得の大きい順にソートしているので,利得マイナスが生じたら,その後もずっと利得マイナスが続くからです).

答えの求め方

方法は色々あると思いますが,ここでは公式解説ベースの説明をします.

まずは呪文 A を使わないで答えを仮計算しておきます. 利得マイナスのときは呪文 B を使うべきではありませんが, 実装上は  \mathrm{max}(hp_{i}, dmg_{i}) で評価してしまうと簡単です.

次に呪文 A の使用を考慮して答えを最適化します. 「呪文 A はどの一体に使うべきか?」を探索なしに特定するのは恐らく不可能であるため 「 i 番目の creature に呪文 A を使った場合は答えがいくつになるか?」を愚直に全探索します. このとき,先ほど行った降順ソートの順で調べていき,上位  b 体かそれ以降かで場合分けします.

  •  1 \leq i \leq b 番目
    •  i 番目の寄与  \mathrm{max}(hp_{i}, dmg_{i}) を一時的に引き算する
    • 代わりに  hp^{'}_{i} = hp_{i} \times 2^{a} を足し算して評価する
  •  b + 1 \leq i \leq n 番目
    •  i 番目には呪文 B が使えないので, b 番目に使っている呪文 B を取りやめて  i 番目に使う
      • 「呪文 B をどこから拝借するか?」は利得が最も小さい creature を選ぶのが最適
    •  b, i 番目に対して一時的な引き算と足し算をした上で評価する(前半の場合と同じ要領)

これで最適解が求まります.

所感

最初は  dp[n][a] の DP を考察していたんですが,「呪文 B を誰に使うか?」が残って上手くいきませんでした. こういう場合には greedy で考察できるようにしていきたいです.

解答例

https://codeforces.com/contest/976/submission/114846390

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
 
    ll N, A, B; cin >> N >> A >> B;
    VLL h(N),d(N); REP(i,N) cin >> h[i] >> d[i];
 
    ll x = (1LL<<A);
    chmin(B, N);
 
    vector<tuple<ll,ll,ll>> X(N);
    REP(i,N) X[i] = tuple(h[i] - d[i], h[i], d[i]);
    RSORT(X);
 
    // b のみで仮計算
    ll tmp = 0;
    REP(i,N) {
        auto [_, hh, dd] = X[i];
        if (i < B) {
            tmp += max(hh, dd);
        } else {
            tmp += dd;
        }
    }
 
    // b が 0 なら
    if (B == 0) {
        COUT(tmp); return 0;
    }
 
    // a を考慮して最適化
    ll ans = tmp;
    REP(i,N) {
        auto [_, hh, dd] = X[i];
        if (i < B) {
            tmp = (tmp - max(hh, dd) + hh*x);
            chmax(ans, tmp);
            tmp = (tmp + max(hh, dd) - hh*x);
        } else {
            // b 番目に使っていた b を取りやめて i 番目に使用 & a を使用
            auto [_, hh2, dd2] = X[B-1];
            tmp = (tmp - max(hh2, dd2) + dd2);
            tmp = (tmp - dd + hh*x);
            chmax(ans, tmp);
            tmp = (tmp + dd - hh*x);
            tmp = (tmp + max(hh2, dd2) - dd2);
        }
    }
    COUT(ans);
 
    return 0;
}