秋山です。
paizaでは先日、10万登録突破記念として、プログラミング問題を解くと抽選で10万円分のAmazonギフト券が当たるキャンペーンなど2つの企画を実施しました。たくさんのご挑戦ありがとうございました！
今回は、このキャンペーンで出題したプログラミング問題と、解き方についての解説、そして、記事の最後には、改めてキャンペーンの当選者発表などをしたいと思います。
キャンペーンページは↓こちら（キャンペーンは終了していますが、問題には何度でも挑戦できます）
paiza.jp
■キャンペーン問題と解法
◆問題文
あなたは商品を詰める箱の設計をしています。 1辺の長さ 1 の正方形の商品を詰める箱の設計を任されました。
作る箱の数は M 個で、それぞれの箱に詰めたい商品の個数 s_i (i は 1 から M) が与えられます。
材料は N 種類あり、それぞれの材料の長さ p_i (i は 1 から N) が与えられます。
材料から縦横2種類選び、s_i 個の商品を全て積める事が出来る長方形の箱を作ります。
空いている箇所の最も少ない箱の空きの個数を計算するプログラムを作成してください。
この時、商品の高さ、材料の厚みは考慮しないものと、縦と横で同一の種類の材料を選び箱を作ることも可能とします。 材料の在庫は無限にあり、同じ材料を重複して何度も使用できます。
図は入力例1 の s = 16 の例になります。
◆解法
もっとも単純な解き方として「s_i 個の商品を詰めるにはN種類の材料から2個選び順に検証していき最も空いている箇所が小さくなる箱を探す」という方法があります。
Python3でコードを書くとこんな感じですね。
でも、このまま提出してもテストケースは1ケースしか通りません…。ということで、計算量を考えてみましょう。
s_i 個の商品に対して、 N × N 種類の組み合わせを検証していくので、 1000 × 1000 × 1000 で10億回の検証が必要となります。
箱の最も空いている箇所が小さい状態のうち、空きが 0 の場合はそれ以上探しても無駄なので、そこで打ち切る…などどいったちょっとした工夫もできますが、その場合、絶対に空きが0でないパターンばかりだった場合は無意味ですね。
他の工夫としては、同じ容量の箱は同じ空き数なので除外して探すことで、s_i 個の商品に対して、N × N 種類の組み合わせのうち、縦横が反転した分は同じ容量なので 1000 × (1000 × 1000) / 2 と5億回まで削除できたりします。
ただ、こんな感じで細かいチューニングを繰り返していっても限度があるので、計算量の削減を考えていきましょう。
作られ得る箱の最大総種類は 1000 × 1000 で 100万通りです。
100万通りの箱を作り、それをソートして100万通りの箱容量の配列とし、M 種類の箱に詰めたい商品数を二分探索することで、計算量が削減されます。
各処理の計算量は、ソートの計算量が作られ得る箱の数を n とし、一般的なソートアルゴリズムでは O(n log n) 、M種類の箱に詰めたい商品数を二分探索する処理は、ソート済みの箱の容量の配列の長さを n として O(M log n) となります。
Python3でコードを書くとこんな感じですね。これで全てのテストケースが通るようになります。
さらに少しチューニングをするなら、 1000 × 1000 の組み合わせのうち、箱は縦と横で材料の長さが変わっても同じ箱ですから、一方の箱のみのリストにしてしまうこともできます。
Python3でコードを書くとこんな感じですね。
このチューニングをして実際にキャンペーンページで提出したところ、最後のテストケースの実行時間が0.72秒から0.41秒へと短縮されました。(※この実行時間数は実行ごとに前後します)
このように、大きく計算量を削減して、そこからさらにチューニングして工夫することで、計算量を半減することができます。
■まとめ＆2つのキャンペーンの当選者発表！
「もっといろいろなプログラミング問題を解いてみたい」という方は、paizaのスキルチェック問題にぜひ挑戦してみてください。
スキルチェック問題はこちら
途中でブログパーツとして使ったオンライン実行環境サービス「paiza.IO (パイザ・アイオー)」はこちら
そして最後に、今回の「10万登録ありがとうキャンペーン」の当選者発表です。
※すでにTwitter上で発表しているものの再掲となります。
まずは、今回解説したプログラミング問題の正解者から抽選で9名様に10万円分のAmazonギフト券をプレゼントするキャンペーン。当選者はこちらの方々でした。
@der_loffel
@nanaminekomushi
@haraitter20
@pingval
@arika_nashika
@kanibuku
@y_mazun
@TobiasGSmollett
@dolpen
みなさん、おめでとうございます！
そして、同時に行った「10万円あったら何を買う！？」のお題のもと、面白いツイートをした1名に実際に欲しいものをあげるキャンペーン。当選者はこちらの方でした！
@hogeover30
おめでとうございます！
なお、hogeover30さんが「欲しい！」とつぶやいたのはこちら。
精白米200kgほしい
— hogeover30 (@hogeover30) 2017年4月20日
｢そのユメ！｣ が ｢そのコメ！｣ に見えたので
https://t.co/kyvKOaVf4u #もし10万円あったら_paiza pic.twitter.com/VLCMtoDwQR
というわけで、全力で白米をご用意しました。
（弊社社長です。全力でお届けします）
hogeover30さん、到着を楽しみにお待ちください。
改めて、両キャンペーンへのたくさんの挑戦ありがとうございました！ そして、これからもpaizaをよろしくお願いいたします！
paizaは、技術を追い続けることが仕事につながり、スキルのある人がきちんと評価される場を作ることで、日本のITエンジニアの地位向上を目指したいと考えています。
「paiza転職」は、自分のプログラミング力が他社で通用するか（こっそり）腕試しができる、IT／Webエンジニアのための転職サービスです。プログラミングスキルチェック（コーディングのテスト）を受けて、スコアが一定基準を超えれば、書類選考なしで複数の会社へ応募ができます。
まずはスキルチェックだけ、という使い方もできます。すぐには転職を考えていない方でも、自分のプログラミングスキルを客観的に知ることができますので、興味がある方はぜひ一度ご覧ください。
また、paiza転職をご利用いただいている企業の人事担当や、paiza転職を使って転職を成功した方々へのインタビューもございます。こちらもぜひチェックしてみてください。
詳しくはこちら
