【No.031】「AdventCalendar用の記事 (2つ目) 」
自分が過去に過去に合宿で出題した問題の中から3つ選び、簡単な解説と当時の感想などを書いていきます。(この記事はその2つ目です)
立命館合宿2015 2日目 会津大学セット F問題 Sum of Numbers (RUPC2015 Day2 F)
問題URL
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp15Day2&pid=F
a以上b以下の整数が書かれたカードがc枚ずつあります。
これら c ( b - a + 1 ) 枚のカードの中からちょうどd枚のカードを選択したとき、それらのカードに書かれてある整数の合計がちょうどeになる場合の数を1,000,000,007 で割った余りを求めてください。
1≦a≦b≦1000
1≦c≦100
1≦d≦1000
c≦d≦c(b-a+1)
1≦e≦20000
a=2,b=5,c=3,d=3,e=11の場合
{2,2,2,3,3,3,4,4,4,5,5,5}の中から3枚選び合計が11になるのは、 {2,4,5},{3,3,5},{3,4,4}の3通り。
この問題にはすでに解説スライドがあります。
このスライドの途中で
{2,2,3,3,4,4,5,5,6,6} の12枚の中から
という表現が何度か出てきますが、それらはすべて
{2,2,3,3,4,4,5,5,6,6} の10枚の中から
の間違いです。 ( 2016年の忘年会のときに気づきました )
----------
この問題が出題されたのは2015年3月ですが、実は問題の核となる部分を思いついたのは2013年の11月(当時学部1年)でした。
以下のURLは、スライドの最後に書いてあるように、Sum of Numbers の元になった問題のリンクと、その問題を解いたときの提出へのリンクです。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=802876#1
2011年の11月のある日、蟻本のp66を読んで「すべての数字を1小さくする遷移」に感動した僕はAOJで似たような問題があることを思い出し、この問題をO(ns)で解くことに挑戦しました。
このときはまだ動的計画法を勉強し始めたばかりだったので、この遷移が典型なのかそうでないのかなど分かるはずもなく、これが作問のきっかけになるとは思ってもいませんでした。
それから1年ぐらいが経過した2014年9月、
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1085385#1
ビンゴという問題をO(N^2 S)で解きました。解いたあとにほかの人の提出を見るとO(N^2 MS)で解かれていて、不思議に思って公式の解説のページを見に行きました。するとそこでも想定解がO(N^2 MS)になっていました。
このときはじめて「すべての数字を1小さくする遷移」を使った問題を作ろうと思うようになり、2015年3月にSum of Numbersが出来上がりました。