課題
以下の問題のいずれかについて解くこと． また，その解き方と実装の方針についてレポートを書け． 期日までに問題を解けない場合，どこまで解決できたかを説明し，また解決できない部分についてはその理由を考察せよ．
なお，問題「カードシャッフル」は難しい． 問題「カードシャッフル」を解いてレポートを書いた場合は他の問題のレポートを書いた場合よりも高く評価する．
- 問題：フクイ国の両替
- ヒント
- シンプルな五重ループで全探索が書ける．
- 各硬貨を何枚ずつ使うかをすべてのパタンを試し，合計金額が両替金額 N に一致するとき，その硬貨の合計枚数は解の候補となる．
- ループの終端（各硬貨の最大使用枚数）としてどのような値を使うべきであろうか？
- N = 40000 のとき，40フク硬貨の使用枚数は 0, 1, …, 1000 (= N / 40) をすべて試すべきであろうか？
- 40フク硬貨を5枚使うくらいなら，もっと良い方法（硬貨の合計枚数を少なくする方法）が存在するのではないか？
- 若干の考察をすれば，1フク硬貨，200フク硬貨の枚数は容易に決定できることに気付くはず．
- その場合，残りの硬貨の枚数については三重ループで探索できる．
- 問題：カードシャッフル
- 資料：ダブリング（繰り返し二乗法）について．
- 愚直な方法では計算量は O(ML)，少し工夫すれば計算量は O(MN + L) となる．
- 適切にダブリングを応用すれば計算量は O(N log M + L) となる．
- M に依存しない O(N3 + L) の方法も存在する．
- ただし，よほど N が小さくないと実用性がない上にコーディングも難しい．
- 方法に気付いたものは方針をレポートに書いてみよ（コーディングは不要）．
- ヒント：対角化．
- 2020-06-06 17:40 追記 M, L, N の大きいサンプル入出力ファイルをアップロードした．
- このようなケースでも正しい答えを返すか， （各自のPC上での実行時間とコンテストシステム上での実行時間は異なるが） 時間制限に間に合いそうかの判断の参考にせよ．
- ファイルは zip アーカイブ・圧縮されている．各自で展開して使用せよ．
提出要領
- レポートおよび回答ソースコード（.c ファイル）を提出すること．
- 提出期限は 2020-07-02 23:59（4週間後）．
- 提出は Google Classroom の「宿題（自己学習およびレポート）」から行うこと．
- レポートは PDF で提出すること．
- レポートのページサイズは A4，ページ数の上限は5ページとする（説明が十分ならどれだけ短くても構わない）．
- レポートにはレポートタイトル，氏名，学籍番号，日付，ページ番号を含めること．
- レポートにソースコードを含めなくても良い．ただし，説明に必要であればソースコードの部分または全体を載せても良い．
- アルゴリズムの計算量や記憶量について見積もること．
- 説明がわかりやすくなるよう図を使うなど工夫すること．
- 誤字脱字に注意し，レポートの体裁にも気を配ること．
課題解説
- 解説資料
リンク先ファイルはレポート提出期限後にアップロードされる． 2020-07-16 アップロード．