課題
以下の問題のいずれかについて解くこと. また,その解き方と実装の方針についてレポートを書け. 期日までに問題を解けない場合,どこまで解決できたかを説明し,また解決できない部分についてはその理由を考察せよ.
なお,問題「カードシャッフル」は難しい. 問題「カードシャッフル」を解いてレポートを書いた場合は他の問題のレポートを書いた場合よりも高く評価する.
- 問題:フクイ国の両替
- ヒント
- シンプルな五重ループで全探索が書ける.
- 各硬貨を何枚ずつ使うかをすべてのパタンを試し,合計金額が両替金額 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 アップロード.