paiza開発日誌

IT/Webエンジニア向け総合求人・学習サービス「paiza」(https://paiza.jp ギノ株式会社)の開発者が開発の事、プログラミングネタ、ITエンジニアの転職などについて書いています。

【10万登録突破Wキャンペーン】結果発表!そしてプログラミング問題解説


秋山です。
paizaでは先日、10万登録突破記念として、プログラミング問題を解くと抽選で10万円分のAmazonギフト券が当たるキャンペーンなど2つの企画を実施しました。たくさんのご挑戦ありがとうございました!

今回は、このキャンペーンで出題したプログラミング問題と、解き方についての解説、そして、記事の最後には、改めてキャンペーンの当選者発表などをしたいと思います。

キャンペーンページは↓こちら(キャンペーンは終了していますが、問題には何度でも挑戦できます)
paiza.jp

■キャンペーン問題と解法

◆問題文

f:id:paiza:20170605175203j:plain

あなたは商品を詰める箱の設計をしています。 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さんが「欲しい!」とつぶやいたのはこちら。

というわけで、全力で白米をご用意しました。

f:id:paiza:20170606132922j:plain
(弊社社長です。全力でお届けします)

hogeover30さん、到着を楽しみにお待ちください。

改めて、両キャンペーンへのたくさんの挑戦ありがとうございました! そして、これからもpaizaをよろしくお願いいたします!



paiza新卒」は、ITエンジニアを目指す人たちのための、IT/Webエンジニア求人に100%特化した就職サービスです。プログラミングスキルチェック(コーディングのテスト)を受けて、スコアが一定基準を超えれば、ES選考なしで複数の企業へ応募ができます。
paiza.jp
まずはスキルチェックだけ、という使い方もできます。自分のプログラミングスキルを客観的に知ることができますので、興味がある方はぜひ一度ご覧ください。
paiza.jp
また、paiza新卒をご利用いただいている企業や、paiza新卒を使って就職に成功した方へのインタビューもございます。こちらもぜひチェックしてみてください。

paiza新卒:企業インタビュー&就活成功者の声

ITプログラマ・エンジニア向け転職・就活・学習サービスのpaiza


プログラミング入門講座|paizaラーニング

PHP入門編Ruby入門編Python入門編Java入門編JavaScript入門編C言語入門編C#入門編アルゴリズム入門編