dohatsutsu’s diary

日記を書いています。

【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通り。

 

この問題にはすでに解説スライドがあります。

www.slideshare.net

 

このスライドの途中で

 {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 の元になった問題のリンクと、その問題を解いたときの提出へのリンクです。

整数の和 | Aizu Online Judge

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=802876#1

 

2011年の11月のある日、蟻本のp66を読んで「すべての数字を1小さくする遷移」に感動した僕はAOJで似たような問題があることを思い出し、この問題をO(ns)で解くことに挑戦しました。

 

このときはまだ動的計画法を勉強し始めたばかりだったので、この遷移が典型なのかそうでないのかなど分かるはずもなく、これが作問のきっかけになるとは思ってもいませんでした。

 

 

それから1年ぐらいが経過した2014年9月、

ビンゴ | Aizu Online Judge

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が出来上がりました。