ctyl's problem solving

競技プログラミングが主な話題です。

yukicoder No.441, 442, 443 コメンタリー (解説なし)

初めてyukicoder contestのwriterをやりました。100人ほど参加してくださって、いろいろwriterとして得られるものがあったので書き残しておきます。解説はそれぞれの問題の解説タブに書いてあるので、ここでは解説や提出コードは書きません。

コンテストのリンク: yukicoder contest 153 - yukicoder

No.441 和か積

No.441 和か積 - yukicoder

簡単な問題、でも少し考察が必要という願いのもとで作りました。結局多倍長整数が扱えたらやるだけ、という問題になってしまいました。多倍長整数が使えなくても簡単な考察で正解することができますし、大きい数の組なら積が大きいというアバウトな考察でも正解することができます。コンテスト参加者の9割以上が正解していました。

No.442 和と積

No.442 和と積 - yukicoder

和&積シリーズで簡単な問題がもう一問作れないかと思って産まれた問題。多倍長整数は使ってほしくないけど A Bの最大公約数なら計算しても良いよ、という願いのもとで作りましたが、予想通り提出は多倍長祭りでした(C++だと__int128という抜け道があるのでほぼすべての言語でやるだけができる)。コンテスト終了後であっても64bit以上の整数型を使わず提出してくださった方、ありがとうございます。No.441とNo.442はyukicoderだから出せるかなというお楽しみ(?)問題でした。

No.443 GCD of Permutation

No.443 GCD of Permutation - yukicoder

コンテスト中想像以上に荒れた問題でした。荒れた原因としては、入力の制約に従っていないケースがあったり、乱択解やnext_permutation解を通してしまったテストケースの質の悪さが大きかったです。 O(N!)を試す人なんていないでしょうと思っていた(怠慢)のですが、そこはrandom_shuffleを使ったりしてうまくやっている人が多くて感心していました。

そして想像以上に難しく感じている人が多くてびっくりしました(当初は問題案は10分くらいで作れたし、考察もそこそこだからと★2に設定していました)。解法のポイントを簡単にまとめると、

  •  Nの並べ替え N_1 N_2(N_1 \neq N_2)を考えた時、その差は必ず求める最大公約数 Gの倍数になる。
  • 下二桁の入れ替えで起こる差の最大公約数だけ考えれば、任意の桁の入れ替えで起こる差の最大公約数を考えていることになる。

の2点です。

この記事を書く直前に乱択解を撃墜するケースを追加してリジャッジをかけましたが、結局コンテスト中に正しい提出をしている方は8人でした。コンテスト中の時のAccepted rateがとても低かったので、かなり不安でした(問題の不備やwriter嘘解法説など)。

総評

問題を作る以上にテストケース作りが大変でした...ちゃんとしたテストケースを用意するにはいろいろな解法に触れている経験が必要ですね。自分の問題をいろいろな解法(嘘解法含む)で解かれているのは提出を見ていてとても勉強になりました。初writerにしてNo.443の評判がかなり良かったのはとても恵まれていたと思います(TLの感想は大体読んでいます)。また面白い数学的な性質を利用した問題を作りたいと思います。