Shirotsume の日記

嘘Greedyを生やすな

Library Checker「Partition Function」

形式的冪級数を用いた解法について書きます．もっと高速な解法もあるようですが，わかんないです． maspyさんに教えていただきました．この記事の最後で説明しています．

問題概要

0, 1, \dots, N の分割数をそれぞれ求めてください．

judge.yosupo.jp

分割数について

ja.wikipedia.org

分割数は，総和が N である正の整数の多重集合の個数といえます．もうちょっと簡単に言うと，1円硬貨，2円硬貨，3円硬貨…が無限枚あるときにピッタリ N 円を払う方法の個数です．

解き方

それぞれの硬貨を何枚使うか？に着目します．明らかにN円硬貨より大きい硬貨を使うことはありません．なので，以降は1円硬貨，2円硬貨，3円硬貨，…，N円硬貨が無限枚あるとして考えます．

1円硬貨を何枚か使うとき，0円，1円，2円…が払えて，2円硬貨を使うとき，0円，2円，4円…が払えます．以降も同様に考えていくと，結局形式的冪級数 f = (1+x+x^{2} + \dots)(1 + x^{2} + x^{4} + \dots) \dots (1 + x^{N} + \dots) の N 次までの係数を求めることができればよいことがわかります． N 次以降の項を適当に切ってしまえば， N 次の多項式の積になるのですが， N 次の式が N 個出てくるので，そのまま計算するのはしんどいです．

これは，等比数列の形になっているので， \displaystyle f = \frac{1}{1 - x} \times \frac{1}{1 - x^{2}} \times \dots \times \frac{1}{1 - x^{N}} として変形できます．

これを計算するために，俗にexp-log典型と呼ばれるテクニックを使います．

exp-log典型

f = \exp(\log(f)) という性質を用います． \displaystyle \log(f) =\log( \frac{1}{1 - x}) + \log(\frac{1}{1 - x^{2}}) + \dots + \log(\frac{1}{1 - x^{N}}) であり，logの性質から

\displaystyle \log(f) =- \log( {1 - x}) - \log({1 - x^{2}}) - \dots - \log({1 - x^{N}}) として求めることができます．

ここで， \log(1 - t) のマクローリン展開を考えると， \displaystyle \log(1 - t) = -t-\frac{t^{2}}{2}-\frac{t^{3}}{3} \dots となります．

さて， k = 1, 2, \dots, N について -\log({1 - x^{k}}) のマクローリン展開したやつ \displaystyle -\log(1 - x^{k}) = x^{k}+\frac{ x^{2k}}{2}+\frac{x^{3k}}{3} \dots を足し合わせていけばよいです．この式を計算する際， N 次以降は切ってよいことから，いわゆる調和級数のやつで足し合わせる項の個数は O(N \log N) になります．

さて， \log(f) が求まれば，あとはexpを取ればよいです．これは， O(N \log N) で求めることができます．

judge.yosupo.jp

全体での計算量も O(N \log N) となります．

提出↓

judge.yosupo.jp

五角数定理を用いた解法

ja.wikipedia.org

オイラーの五角数定理より，

\displaystyle \frac{1}{f} = (1 - x)(1 - x^{2}) \dots = \sum_{n = - \infty}^{\infty}(-1)^{n} x^{\frac{n(3n+1)}{2}}

が成り立ちます．右辺は n の絶対値の小さい方から計算していくことで N 次までを線形時間で求められます．あとは，この式のinv（逆数）を取ればよいです．これは， O(N \log N) で行うことができます．

↓提出 judge.yosupo.jp

どちらも計算量は O(N \log N) ですが，exp-logを用いた解法は 5998 ms かかっていたのに対し五角数定理を用いた解法は 649 ms と，かなり高速になりました．

ABC294-F「Sugar Water 2」

atcoder.jp

↑問題文へのリンク

タイトルを見て，あの幾何のやばいやつの続編か，いやだな～と思っていたのですがそれは D - Water Bottle でした．

考察はほぼ一瞬で終わって実装で手間取ったのですが，twitterを見ると考察が難しいと言っている人が多くてびっくりしていました． それぞれはそんなに難しくない（茶～緑diffくらい？）典型的な要素がいくつか組み合わさって難易度が青diffまで上がっている地力ゲーという印象があって，こういうのを安定して早く解けるかどうかで実力出そうだな～と思っていました．ということで振り返り兼自省としてこの問題の解説を書きます．

問題文

高橋君は N 本の砂糖水を、青木君は M 本の砂糖水を持っています。

高橋君の持っている i 番目の砂糖水は砂糖 A_i グラムと水 B_i グラムからなります。

青木君の持っている i 番目の砂糖水は砂糖 C_i グラムと水 D_i グラムからなります。

2 人の持つ砂糖水をそれぞれ 1 本ずつ選んで混ぜる方法は NM 通りあります。そのような方法でできる砂糖水の中で、濃度が高い方から K 番目の砂糖水の濃度が何 % であるかを求めてください。

K番目は何ですか問題

この問題のような，ある順序で並べ替えたとき K 番目になるものは何ですか？という問題には大きく2つの解法があると思っています．

  1. 前から貪欲に決定できる構造があるもの

例題↓ atcoder.jp

辞書順で～と言われたらまずこれです．辞書順では，先頭の文字がaであるものは絶対にbよりも先になるので，先頭から文字を貪欲に決定していくことができます．

例えばこの例題では，先頭がaであるかbであるかをまず判定し，次に2番目が…と順番に決めていくことができます．

  1. 二分探索で判定問題に落とし込めるもの

例題↓

atcoder.jp

辞書順のように，これを取ったら絶対に最小になるみたいなうまい性質がないときは多分これです．最終的な答えを決め打って，判定問題に変えてしまいます．

今回は砂糖水の濃度にいい性質がないので，1の方法で解くのは厳しそうです．よって2の方法で解きましょう．

二分探索に落とし込む

上から K 番目の砂糖水の濃度は X 以上か？という判定問題を考えます． X「以上」という条件にすることで，いい感じに解けます．この問題に限らず，ぴったり X を判定するのが難しければ X 以上/以下を考えてみるというのは良い発想だと思います．

上から K 番目が X %以上ということは，上から 1, 2, \dots, K 番目は X パーセント以上じゃないとダメです．よって，この判定問題は，以下のように言い換えられます．

  • NM通りの砂糖水のうち，濃度が X 以上の砂糖水が K 個以上あるか？

これが解けると，あとは X について二分探索すればACです． (0, 100) の範囲で実数で二分探索すればよいです．

実数の二分探索についてはえびちゃんのすてきな記事をお読みください．自分は決め打ちの方が（競プロ文脈では）いいと思います．

rsk0315.hatenablog.com

rsk0315.hatenablog.com

以降はこの判定問題の解法を考えていくことになります．

判定問題を解く

  • NM通りの砂糖水のうち，濃度が X 以上の砂糖水が K 個以上あるか？

という問題は，愚直に全通り試すことで O(NM) で解けます．が，これでは遅いので高速化を考えましょう．

まず，式を書いてみましょう．問題文に式を書いてくれているので，高橋君が砂糖水 (A_i, B_i) ，青木君が砂糖水 (C_j, D_j) を取ったとして，式に代入して濃度を計算します．

（濃度）= \frac{100(A_i + C_j)}{A_i + B_i + C_j + D_j}

よって，判定問題は，

以下の条件を満たす (i, j) (1 \leq i \leq N, 1 \leq j \leq M) が K 個以上か判定せよ．

  • \frac{100(A_i + C_j)}{A_i + B_i + C_j + D_j} \geq X

という数え上げ問題に帰着できます．

変数分離

このような (i, j) の入り乱れた問題は， i のついた項を左辺， j のついた項を右辺に寄せられるか考えてみるとよいです．こうすると， i を固定して j を高速に数えるみたいな方針で解けることが多いです．

↓例題

atcoder.jp

ということでそれを目指して式変形します．

\frac{100(A_i + C_j)}{A_i + B_i + C_j + D_j} \geq X

100(A_i + C_j) \geq X(A_i + B_i + C_j + D_j)

100A_i + 100C_j \geq XA_i + XB_i + XC_j + XD_j

100A_i - XA_i - XB_i \geq XC_j - 100C_j + XD_j

(100 - X)A_i - XB_i \geq (X - 100) C_j + XD_j

できました．あとは， P_i = (100 - X)A_i - XB_i とした数列 P ， Q_i = (X - 100)C_i + XD_i とした数列 Q を用意すると，以下の問題になります．

以下の条件を満たす (i, j) (1 \leq i \leq N, 1 \leq j \leq M) が K 個以上か判定せよ．

  • P_i \geq Q_j

ここまでくると茶diffくらいですかね．それぞれの i について， Q に含まれる P_i 以下の要素の個数が分かれば良いので， Q をソートして二分探索すればよいです．Pythonなら bisect_left やるだけです．

実装の際に

コンテスト本番で，式変形までは割とストレートにできたのですが，帰着してからが大変でした．素直に Q を二分探索していいところ，尺取り法的にできないか？みたいなことをずっと考えていました．制約が控えめで，log2つくらいなら通すよという感じなのでおとなしく甘えるべきでしたね．

実装を炎上させているところ，maspyさんのこのツイートを思い出しました．

（なんかちょっと前に似た趣旨のツイートがあった気がするが思い出せない）

これを参考に，愚直を書きつつ合わせていくことにするとすぐ答えが合いました．

愚直を書きつつ細部を部分ごとに合わせていくみたいなのは競技に限らずプログラミングの汎用テクニックだと思うので，こういうのをすぐできないのは反省ポイントです．

感想など

コンテスト中の提出です↓

atcoder.jp

いざ解説を書いてみると，しっかり青diffだなという印象になりました．しかし，F問題の実装量としては少ない方なので，もうちょっと早く通せてればという感じです．

ACLを使ってみよう！

この記事は 競プロ Advent Calendar 2022 の二日目として書かれた記事です。#競プロAdC

Nachia さんによる先日の記事 競プロAdC やってるみたいなので Library Checker の解法紹介をぶっこむ | Mathenachia に引き続き、ライブラリについてのお話です。主に対象とする読者層はAtCoder茶色以上くらいで、どんなアルゴリズムの勉強をしたらいいんだろう？と悩んでいるような人です。暖色の人に有用な情報はあんまりなさそうです。

ライブラリについて

AtCoder などでの競技プログラミングでは、計算量で差がつくアルゴリズムがよく出題されます。有名な方法は特に何度も出題されるので、あらかじめプログラムを用意しておきます。競プロ文脈でライブラリというと、この事前に用意したプログラムのことを基本的に指します。

ライブラリは自分で作ってもよいですが、他の人が作ったものを借りてくるという方法もあります。今回私がおすすめするのは、 AtCoder Library を有効活用する方法です。

AtCoder Library について

AtCoder Library (ACL) は AtCoder によって公式に提供されている C++ 用のライブラリです。UnionFind や最大フローなど、よく出題されるアルゴリズム/データ構造から、FloorSum のようなコンテストではあんまり見たことのないものまで数多く取り揃えてあります。

https://atcoder.github.io/ac-library/document_ja/　←ドキュメントです。ここに使い方が載っているので、調べて使うことができます。ここからダウンロードもできます。

ACL を使う利点を以下に示します。

  • AtCoder により公式に動作テストがなされており、非常に高速に動作する
  • あらかじめ AtCoder のジャッジサーバに組み込まれているので、コピペをする必要がない
  • ABC 等のコンテストで出題されやすいアルゴリズムがそろっている
  • AtCoder Library Practice Contest でいろいろ試してみることができる

他にもありそうです。特に、アルゴリズム/データ構造をどこから勉強していいかわからない…と困っている茶色～緑コーダーは、ACLの使い方を順番に勉強していくとよいと思います。*1

例えば A - Disjoint Set Union は次のコードでACできます。（本当に、これをそのまま提出欄に貼ればACです）ライブラリを貼る必要がないので、非常に短く済んでいることが分かると思います。*2

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
int main(void)
{
    int n, q;
    cin >> n >> q;
    dsu U(n);
    int t, u, v;
    while(q--){
        cin >> t >> u >> v;
        if(t){
            cout << (U.same(u, v) ? 1 : 0) << endl;
        }
        else{
            U.merge(u, v);
        }
    }
}

ここまで C++ の話をしましたが、有志による ACL の他言語版が用意されているため、 C++ ユーザ以外はそれを利用することができます。

参考

ここで力尽きたので、過去に書いたACL紹介スライドを貼っておきます。各アルゴリズム/データ構造のざっくりとした説明はここをご覧ください。

*1:灰色コーダーは、まずはSTLに入っているような標準的なデータ構造（dequeとかsetとか）や、より基本的なアルゴリズム（全探索、DFS、 BFS）から勉強することをお勧めします。ABC-C問題まででACLに入っているアルゴリズムが必要になる問題が出ることはほとんどないと思います。

*2:余談ですが、これのコードを提出しようとしたとき間違えて記事全体をコピペしてしまい、事前に記事を公開してしまって終わりになっています。暇な人は探してください

積の和典型

最近積の和典型が話題になっているので書きます。

N個のマス目が横一列に並んでいる状況を考えます。初め、全部のマスは白色です。このうち K 個のマスを選んで黒く塗った時にできるマスの状態は何通りでしょうか？

これを

こうする

これは　 _{N}C_{K}通りです。

これを応用すると、次のような問題が解けます。

長さが N であって、総和が M である非負整数列の個数を求めよ。

非負整数列というのは、各要素が負の数でない整数からなる数列です。[1, 2, 3, 4, 5] とか [0, 0, 1, 4, 3] とかです。これの個数を数えるのに、先ほどのマスの数え方を使うことができます。

まず、 M + N - 1 個の白いマス目を用意します。そのあと、そこから N - 1 マス選んで塗ります。こうしたとき、必ず M 個のマスが白いままで残っています。また、マスの両端や黒マスを境目として考えると、白いマスが連続するような区間は N 個の部分に分かれます。（黒いマスが連続するような塗り方もありますが、その時は白いマスが0個の部分があると解釈します）

ここで、それぞれの部分について白いマスの連続する個数を数えると、長さ N の数列ができます。白いマスは全部で M 個なので、これは総和が M で長さ N の数列となり、求めたいものの1つとなっています。

N = 5, M = 5 のときの例。この塗り方は、数列 [1, 2, 1, 0, 1] と対応している

また、塗り方と数列は一対一対応します。つまり、ある塗り方からできる数列はちょうど1つであって、ある数列から復元できる塗り方もちょうど1つであるということです。よって、数列の個数を数える代わりに塗り方を数えてもいいことになります。 塗り方は、 M + N - 1個のマス目から N - 1 個を選んで塗る方法なので、 _{M + N - 1}C_{N - 1}通りです。

発展テク: 「総和が M 以下」の場合、数列の後ろに追加で 1 つダミーの値があるとします。数列の総和が M より小さかった時は、このダミーに押し付けると考えると、解くことができます。

長さが N であって、総和が M である非負整数列 A すべてに対して \prod A_i を計算した時の総和を求めよ。

今回の本題です。

\prod は総積記号で、数列 A の要素を全部掛け算してねという意味です。その掛け算を A としてあり得るもの全部でやって、それを足してねという問題です。

さて、これを解くためにいくつか準備をします。まず、A_i を掛けるという操作は、A_i 個のマスから 1 つ選んで塗る方法と対応付けることができます。

例えば下の図のように、複数のマスが並列して並んでいる場合を考えるとわかりやすいと思います。

5個、4個、3個の3種類のマス目があって、それぞれから1マスずつ選んで塗る方法は、60 通り

この考え方と、先ほどの非負整数列の数え方を組み合わせます。

まず、 M + N - 1 個の白いマス目を用意して、そのうち N - 1 個を黒く塗ります。ここまではさっきと同じです。先にも言ったとおり、どんな塗り方をしたとしても、白いマス目からなる N 個の区間ができます。その N 個の区間から 1つずつマスを選んで、赤く塗ることにします。

3 つの区間から 1つずつマスを選んで、それぞれを赤く塗る

長さ 0 の区間ができたときは赤に塗るマスが無いので困りますが、そのようなときはどうせ掛け算すると0になるので無視できます。これを無視した時、マス目には赤色と黒色を合わせて N - 1 + N = 2N - 1 マスの色のついたマスが存在することになります。（初めに塗った黒マス N - 1 個 + N 個の区間それぞれで塗った赤マス N 個）

このように塗ってできるマスの状態の総数は、求めたい答えと一致します。

ここで、重要な考察をします。初めにどんな黒の塗り方をしても、後でどんな赤の選び方をしても、マスを左から見たときに、色のついたマス目の色は赤、黒、赤、…、黒、赤の順番で並びます。なので、もしマス目の色が赤と黒どちらか分からなくなってしまったとしても、色のついたマスがどこにあるかさえ分かれば、色を一通りに復元することができます。よって、実は赤と黒を区別する必要はなく、一緒くたにしてしまってよいことになります。よって、このような塗り方は M + N - 1 個のマスから 2N - 1 個選ぶ方法、 _{M + N - 1}C_{2N - 1} 通りです。

発展テク: 「総和が M 以下」の場合、さっきと同様に、数列の後ろに追加で 1 つダミーの値があるとします。また同様に数列の総和が M より小さかった時は、このダミーに押し付けると考えますが、ダミーの値の部分を掛けることはないので、ここを赤く塗ることはありません。よって、塗るべきマスの個数は 2N 個になります。

ABC268 G - Random Student ID

問題概要

　N人の生徒がいて、それぞれの名前はS_i。アルファベットの並び順をランダムに決めて辞書順にソートした時、indexの期待値はどうなるかをそれぞれの生徒について求めよ。

解法

　この問題は、文字列アルゴリズムでも解けるが、もっと簡潔な解法がある。abc...という通常の順番とzyx...という反転した順番でソートして、それぞれの場合でindexを求めて平均をとれば解ける。

解説

　2つの（異なる）文字列a, bに対し、辞書順は以下のようなアルゴリズムで決定される。一般性を失わず、|a| <= |b| とする。 ①1 <= i <= |a| かつ a[i] != b[i] であるようなiがあるとき、その中で最小のものjをとってa[j] < b[j]ならa < b、a[j] > b[j]ならa > bとする。 ②①でiがとれなかったなら、bが辞書順で大きいとする。

①の場合、アルファベットの並び順によって順序が変わってくる。具体的には、決めた並び順でa[j]とb[j]のどちらが先に出てくるかによって順序が変わる。よって、アルファベットの並び替えで2要素のうちどちらが先に来るかにのみ注目すればいい。

②の場合、アルファベットの順番は順序に関係がない。よって、並び方によらずどちらが後ろが決定する。

　さて、indexの期待値は、「ソートした時自分より前に来る文字列の期待値」と言い換えることができる。（正確にはそれより1大きくなる） まず、1つのペアa, bに着目して、a < b となるようなアルファベット順が選ばれる確率を考える。期待値の線形性より、これをbを含む全ペアに対して計算できればbに対する答えがわかる。 　さて、abc...の並び順でbより小さくなる要素がx個、zyx...の並び順ではy個だったとする。このとき、①のケースで順序が決まるものが|y - x| 個あったということになる。（反対に、②のケースで決まるものはmin(x, y) 個。）①のケースの寄与は、順列でどちらのアルファベットが先に来るかのみで決まるので1/2、②のケースは1（全部同じなので）寄与する。よって、期待値は|y - x| / 2 + min(x, y) となる。計算すると、これは (x + y) / 2 に一致する。よって、平均を取ることで正しい答えが求まることが分かった。

感想

合宿前全然寝れなかったので怪文書を生成

ABC196-F 「Substring 2」

道場鯖の練習セットにあった問題。事前にネタバレを食らっていたので、何を使うかは知っていたが考察は一からやった。このテクニックは非競プロでもよくつかわれるみたい。

atcoder.jp

問題概要

2 つの 01 文字列 S と T が与えられる。 T が S の連続部分文字列となるように S の文字を書き換えるときの最小回数を求めよ。

初めに: ハミング距離

同じ長さの 2 つの文字列が与えられた時、片方を書き換えてもう片方に一致させるために必要な書き換え回数の最小値のことをハミング距離という。

特に今回は、文字が 0, 1 なので、これをそのまま数として読んでしまうと、同じ長さの 2 つの文字列同士のハミング距離は以下のように表せる。

{\displaystyle \sum_{i=1}^N \left |S_i - T_i \right | }

特に、 01 列であることから、これは

{\displaystyle \sum_{i=1}^N \left (S_i - T_i \right )^{2} }

と等しく、式変形により

{\displaystyle  \sum_{i=1}^N \left (S_i - T_i \right )^{2}  = \sum_{i=1}^N S_i + \sum_{i=1}^N T_i  - 2 \times  \sum_{i=1}^N S_iT_i}

として計算できる。

元の問題の解法

さて、今回の問題では、 S' := S の k 文字目から N + k 文字目 とおいた時のハミング距離の最小値を求めればよいことになる。ナイーブにやると二乗かかってしまうので、式変形をうまく生かしたい。

{\displaystyle  \sum_{i=1}^N S'_i }

については容易に計算できるが、問題は

{\displaystyle  - 2 \times  \sum_{i=1}^N S'_iT_i}

である。これを書き直すと

{\displaystyle  - 2 \times  \sum_{i=1}^N S_{i + k}T_i}

ここで、 T を反転させてみる。そうすると、

{\displaystyle  - 2 \times  \sum_{i=1}^N S_{i + k}T_{N - i} = - 2 \times  \sum_{i + j = N + k} S_{i}T_{j}}

となり、FFT で計算できる形になる。

AC提出

atcoder.jp

実行時間がかなりギリギリ…

yukicoder contest 355 C問題の出題不備について

yukicoder contest 355 - yukicoder が 2022/08/05 に開催されました。参加してくださった方、ありがとうございました。

時間があれば全体の開催記を書きますが、今回はC問題で発生した出題不備について書こうと思います。 C問題 No.2029 Swap Min Max Min - yukicoder のネタバレを含みます。

初めに、C問題の不備によって混乱させてしまったことに対しお詫び申し上げます。この件については、Writerである私に責任があると考えています。申し訳ございませんでした。

次に、コンテスト中に Clar で指摘していただいた maspy さん、 SSRS さん、 Nyaan さん（Clarの時系列順に並べています）にお礼を申し上げます。本当にありがとうございました。参加者としてはジャッジが壊れていると推測するのは非常に難しいと思いますが、少しでもおかしいと思った場合はすぐにClarを投げていただくと、出題側は非常に助かります。特に今回はACが多数出ていてコンテスト中にも気づかなかったので、本当に助かりました。

また、リジャッジ後にKazunさんにもClarで順位表更新方法を教えていただきました。ありがとうございました。（yukicoderの順位表では、WA → AC の変化が正しく表示されていなかったようです。現在は修正されています。）

以降で、何が起こったかの説明と、現在考えている解決策を書こうと思います。

時系列

  • コンテスト前 yukicoder 355 のC問題において、実際には最適でない解を最適解としてケースを作成していた

  • 21:50 ごろ Clar により指摘を頂く。Y.Y.さんと相談し、修正を行う

  • 22:00 C問題のClarに、この問題に不備がある旨の通知を行う。この時は修正はコンテスト後に行おうと考えていたので、その旨をC問題の問題文に追記

  • 22:15 Y.Y.さんが正しい解答を書く。相談の結果、コンテスト後ではなくすぐ修正をして、チャレンジしてもらおうということに

  • 22:30 Shirotsume が書いた解答とY.Y.さんの解答が合わない。ここで、Y.Y.さん、maspy さん、SSRS さんの解答が一致することが確認できたため、テストケースを差し替えてリジャッジする

  • 22:40 Clar でリジャッジを行ったとアナウンスする

  • 23:10 Shirotsume の解答が合う

  • 23:20 コンテスト終了

どのような不備があったのか

Nが偶数のケースでは、この問題は \frac{N}{2} 個の 0 と \frac{N}{2} 個の 1 からなる数列を、 1 どうしが連続しないように並べ替えるための最小 swap 回数を数える問題となる。 これを解く際に、 010101 \dots と 101010 \dots のケースの 2 種類だけであると勘違いし、 10100101 \dots のようなケースを考慮していなかった。 結果、最適でない解を想定解としていた。

どのように対策するか

このような論証漏れに対する最も有効な対策は、maspyさんもtweetで指摘しておられたように、愚直解を書いて比較することだと考えています。

同コンテストの問題（FやG問題）では愚直解を書いていましたが、この問題は愚直が書きにくいことや、コンテスト中でも難易度設定が低めであることなどからそれを怠っていました。

このコンテストでは、解説をしっかり書くことを目標にしており、できるだけ論理の抜けがないよう注意しました。そのため、この解説は間違っていないだろうという自信を持っていました。今回はそれも裏目に出たと思います。

自分で書いた解説から論理の抜けを指摘することは、自分の思いつかなかったことを見つける必要があり、かなり難しいです。testerにとっても、解説を読むとそれが正しいものだと思ってしまうので指摘は難しいと思います。TLEなどと違い、hackケースを見つけることも困難なので、可能な限り愚直など機械的な方法で判定するべきだと思います。

writerをするときだけではなく、testerをする際もできる限り愚直を書くべきだと思います。

今回はありませんでしたが他の不備として入力形式やジャッジ不具合等も考えられます。これらについてもtesterがチェックしておく必要があると思います。

実際に不備があった場合、どうするべきか

今回はyukicoder等有志コンテストについて書きます。AtCoderなどでは話が変わってくると思います。

コンテスト中に不備があった場合、その問題を即修正すべきかどうか悩みましたが、私はできる限り早く修正して、参加者に取り組んでもらうべきだと考えました。yukicoderはレート等がかかっているわけではなく、純粋に楽しみで参加してくださっている方が多い印象があります。そのような方に最も楽しんでいただくためには、単に取り下げるより、修正して再度仕切り直した方がよいと思いました。今回は修正解が早く用意できましたが、そうでない場合は取り下げ等考える必要があると思います。

おわりに

今回の不備について、改めてお詫び申し上げます。現在はC問題も修正されており、正しいジャッジが行われるようになっています。解法が面白い問題なので、ぜひ取り組んでみて下さい。他の問題についても、良い問題をそろえられたと思いますので、ぜひ解いてください。また、testerをしていただいたとりゐさん、Y.Y.さんに、改めてお礼申し上げます。ありがとうございました。

この件で作問やtesterに対して「大変そう…」という印象を持たれた方もいるかもしれません。確かに今回はかなり大変でしたが、作問/testerはとても楽しいです。ぜひ積極的にやってみることをお勧めします。その際は、解説を批判的に読む、愚直解を書くなどして、できるだけこのようなことを起こさないように頑張ってください。

私は今回のコンテストで持っている原案をほぼ全部出してしまったのでもう残っていないのですが、また溜まってきたら開催したいと思っています。その際はよろしくお願いします。