yukicoder 456の作問と、冬の大三角と(^^*)のテスター記録

投稿型プログラミングコンテストであるyukicoderで、僕が作った1問でコンテストが開かれた。この問題は、yukicoderに1日1問アルゴリズムに関する問題を出すイベントである、yukicoder Advent Calendarの問題として出された。yukicoderは最近勢いのあるコンテスト基盤で、気軽に皆が問題を投稿できることが特徴である。16世紀のルネサンスのような、問題を出し合って解き合う雰囲気が楽しい。

No.456 Millions of Submits! - yukicoder

また、yukicoder Advent Calendarの他の2問（冬の大三角と(^^*)）のテスターを引き受けた。テスターは、要するに査読者である。問題文が多義的でないか、非想定解がないか、愚直解で通らないか等をチェックする。

No.455 冬の大三角 - yukicoder

No.457 (^^*) - yukicoder 

Millions of Submits!

僕の問題は、炎上した。重要な順に以下の要因がある。

  1. 問題自体の不備（解答が複数あるのに1つだけ出せと問題文が言っていた）
  2. 制限時間の不備（powをfor文で回すと通る、というアホらしいことをして通る）
  3. そもそも定数倍高速化の問題（理論屋に嫌われる）
  4. ジャッジに異常に時間がかかる（yukiさんにwishしたらこの問題以降改善）
  5. 出力制限があり謎のランタイムエラー（yukiさんにwishしたらこの問題以降出力制限を明記）

問題自体の不備

今回、本来複数解あるのに、一つだけ出力せよと言っていた。これに気付かなかったのは、僕の頭が悪い。また、複数解があるのに僕とテスターが80 submitsして、500万テストケースに対する答えが一致するという奇跡が起きていた。本当にたまたま、僕とテスターが求めていたものが「あり得る解の中で最大のもの」であったため、コンテスト開始20分くらいに、問題文をわずかに書き換えることで対応した。

解決方法は、基本能力を上げるしかないので、

  • 僕がレッドコーダーになる
  • テスターがレッドコーダーになる、の二点である。

制限時間の不備

この問題では、浮動小数点aに対して、{a^n}を計算する必要があった。しかしnが小さくかつ整数だったので、pow(a, n)より for (int i = 0; i < n; i++) ret *= a; の方が高速だった。僕の実装力の低さにより事前に発見できなかった。これはチェックしたはずだったのだが、メモ化を一箇所忘れたため事前に発見できなかった。

これは、4つ解決方法があって、

  • 定数倍高速化の問題は作問がつらいので制約をめちゃめちゃきつくする
  • 僕がレッドコーダーになる
  • 問題で考慮すべき制約条件を網羅的にテスターと共有する
  • 利用できそうな制約を潰す（今回であればnを浮動小数点にする）

そもそも定数倍高速化の問題

結構根が深い問題で、定数倍高速化は嫌われる（許さんぞお前！みたいな扱いされることが多い）。

嫌われる原因は3つあると思う。

一つ目は、訊いている知識やアイディアがコンパイラの最適化でボヤけるから。ちょっと順番を替えたり、ループアンローリングするだけで通ってしまったら興ざめである。今回の問題では、訊こうとしているアイディアは明確だったが、制限時間が長くぼやけてしまった。なお、今回訊いていたことは以下の2点であった。以下のどちらかが思いつけば、通るようになっていた。(1) 二分探索内部の演算量を減らすための変数変換（logを取る、ランベルトのW関数を使うなど）。(2) 1次収束の二分探索ではなく、2次収束のNewton法や、3次収束のHalley法といったHouseholder Methodを使うと高速であること。

二つ目は、言語を限定しないと何を聞いている問題なのかわからなくなるので、C++を強要するから。C++を前提にして、TLを闇魔術を使わないタイプのライター解を書いて、時間制限をライター実行時間の+50%くらいにするのが良いのかな、と思った。複数言語で解答可能のようにすると、訊いているアイディアがボヤける。

三つ目は、理論屋はオーダーが下がるのを見るのが好きだから（知るか）。でも今回は、収束次元数が変わっているから、誤差要求仕様を計算量に含めると、多分オーダーも変わっているはず。

定数倍を頑張るのもまたプログラミングなのだから、プログラミングコンテストでそういうノウハウを醸成する基盤を除外するのは分野に健全ではないと思う。定数倍高速化を出すときには、それ専用の方法論を持つべきだと感じた。

ジャッジに異常に時間がかかる＆出力制限

僕の問題が終わったあと、yukiさんにwishを投げたら即対応していただいた。神。

モチベーション

この問題のモチベーションは、数値計算でニュートン法を使う問題を見たことがなかったことである。ロボコンで極値計算したくなった時に、ニュートン法が高速で感動した。その感動を伝えるために、定数倍高速化の問題を作った。そしたら、よくよく考えると競プロ的な逆関数が大概ランベルトのWで表されてしまってとてもつらい、という感じだった。思考停止して、ランベルトのW+Halley法を想定解としてぶん投げた。

テスター

テスターとしては、冬の大三角と(^^*)を引き受けた。

冬の大三角

スペシャルジャッジのバグに気づけなかった。テスターはきちんとジャッジまで気を配らないとなあ、と戒めた。

(^^*)

(1) 問題文が構造化されていなかったので、修正案の提案。誤読を避けるために強調すべきポイントの指摘

(2) {O(n^2)}が想定解だったが、筋肉を使うと{O(n \log n)}があるのが自明だったので報告

管理人のyukiさんが、問題文を編集したので読みやすくなった。テスターも、問題文を積極的に編集していったほうがいいのかなあと悩んでいる。また、想定解として{O(n)}を思いつけなかったので修練不足を感じた。

感想

また、問題の著作がyukiさんと共同であるのだから、テスターとのやりとりは初めからyukiさんを混ぜるべきだと感じた。