新人女子の書いたコードを直すだけの簡単なお仕事です!応募期間:12月2日(月)から1月8日(水)まで paiza paiza

どなたか効率のよいアルゴリズムを教えてください!

私、ECサイトのキャンペーンでプログラムを開発しています。納期は連休明け。プログラムを途中まで書いたものの、コードが長く、効率が悪いような気がするし、納期に間に合わないかも…。センパイ!助けてください!

参加者から3名様に、エンジニアに大人気エナジードリンクロック・スター(30本入り)をプレゼント!!

Share!

開発したいプログラム

ECサイト内の2つの異なる商品(値段は同じでも構わない)を購入し、その合計価格が指定の価格以内で最大になる組み合せを探してください。 →問題詳細

新人女子プログラマの野田さんが途中まで書いたプログラム

Item_a_b = 4500 // a+bの価格
Item_a_c = 500 // a+cの価格
Item_a_d = 2300 // a+dの価格
Item_b_a = 1240 // b+aの価格
Item_b_c = 5020 // b+cの価格
(中略)
if Item_a_b == campaign_price
  print “AとBの組み合わせが最大!”
if Item_a_b == campaign_price -10
  print “AとBの組み合わせは-10円差でおしい!”
if Item_a_c == campaign_price
(以下略) 

paizaオンラインハッカソン(略してPOH![ポー!]) 【結果発表】新人女子PGを最も助けたプログラミング言語とは?

受付期間は終了しましたがコードの実行は可能です。(プレゼント対象外、計測対象外になります)

直したコードによって昇進、あなたのプログラミング力が試される!

あなたの部署に配属された新人女子プログラマの野田さんのコードをより良いものに直してください。野田さんは実はあなたの会社の社長令嬢。効率の良いコードに書き換えて、プログラマとしてのスキルをアピールできれば昇進するチャンスです。

本ページ下記の「お仕事詳細」に従い、お好きな言語(Java,C,C++C#,PHP,Ruby,Python,Perl)で、効率の良いコードを実装してください。提出コードは複数のテストケースを入力し、正答数と解答の提出までに要した時間を測定し得点が決まります。

  • 提出いただいたコードは複数回実行され、一度の実行では1つのテストケースのみ入力。
  • 公開問題なので制限時間はありません。
  • ひとり何回でもチャレンジできます。
  • 回答をブログ等に書いていただいても問題ありません。
得点次第で新人女子の反応が変わる!?/提出コードの順位も分かる!/高得点がでたら友達に自慢しよう!

お仕事の流れ

STEP1 コードを書く

STEP2 動作確認する

STEP3 提出

STEP4 その場で採点結果発表!

STEP5 模範解答公開(paizaへの登録が必要)

希望者に日本未発売の大人気エナジードリンクロック・スター24本入りプレゼント

  • 提出コードのうち、優れたコード(実行速度が速い、可読性が高いもの)は、paiza事務局で選定し、ニックネームで他の挑戦者にも公開されます。プレゼントのロックスター・エナジードリンクは250ml×30本のセットに成ります。

言語別 最速・最遅実行時間 CASE1

あなたも参加して、最速タイム(実行時間)を競おう!

言語

最速実行時間

最遅実行時間

受験数

Java

0.06 秒

5.95 秒

2989

PHP

0.01 秒

9.80 秒

3258

Ruby

0.01 秒

9.47 秒

2213

Python2

0.08 秒

9.70 秒

2519

Perl

0.01 秒

9.42 秒

1937

C

0.01 秒

2.99 秒

3466

C++

0.01 秒

2.78 秒

3367

C#

0.01 秒

6.00 秒

2470

(2014/01/09更新)

最遅実行時間はLimitTime内で最も遅い実行時間だったものを表示しています。
※ テストケース1(全言語同一ケース)の実行時間です。実行する時間帯によっては実行時間が変わる可能性がございます。予めご了承ください。

言語別 最速・最遅実行時間 CASE2

あなたも参加して、最速タイム(実行時間)を競おう!

言語

最速実行時間

最遅実行時間

受験数

Java

0.06 秒

5.94 秒

2989

PHP

0.01 秒

9.05 秒

3258

Ruby

0.01 秒

8.14 秒

2213

Python2

0.08 秒

9.99 秒

2519

Perl

0.01 秒

7.98 秒

1937

C

0.01 秒

2.99 秒

3466

C++

0.01 秒

2.96 秒

3367

C#

0.01 秒

6.00 秒

2470

(2014/01/09更新)

最遅実行時間はLimitTime内で最も遅い実行時間だったものを表示しています。
※ テストケース2(全言語同一ケース)の実行時間です。実行する時間帯によっては実行時間が変わる可能性がございます。予めご了承ください。

言語別 最速・最遅実行時間 CASE3

あなたも参加して、最速タイム(実行時間)を競おう!

言語

最速実行時間

最遅実行時間

受験数

Java

0.06 秒

5.94 秒

2989

PHP

0.01 秒

9.93 秒

3258

Ruby

0.01 秒

9.48 秒

2213

Python2

0.08 秒

9.93 秒

2519

Perl

0.01 秒

9.96 秒

1937

C

0.01 秒

2.99 秒

3466

C++

0.01 秒

2.96 秒

3367

C#

0.01 秒

6.00 秒

2470

(2014/01/09更新)

最遅実行時間はLimitTime内で最も遅い実行時間だったものを表示しています。
※ テストケース3( C,C++のテストケースは実行速度差の関係でNが2.5倍、Dが4倍のサイズとなっています )の実行時間です。実行する時間帯によっては実行時間が変わる可能性がございます。予めご了承ください。

お仕事の納期、報酬(プレゼント)

スケジュール

応募期間
12月2日(月)~1月8日(水)
受付終了しました
審査期間
1月9日(木)~1月14日(火)
結果発表
1月15日(水)

報酬(プレゼント)

参加者の中から抽選で3名の方に、エンジニアに大人気のエナジードリンク「ロックスター」30本セットをプレゼント。

イベント規約

  •  本キャンペーンでは、会員登録をしないで公開問題を受験していただくことができます。ただし、ご利用にあたっては、以下の注意事項にご了承いただくことが前提となります。
  • *注意事項*
  • (1) 会員登録は必要ありませんが、メールアドレスのご登録が必要になります。ただし当社は、いただいたメールアドレスを本キャンペーン関連のご連絡以外には使用しないものとします。
  • (2) 既存会員の方も本キャンペーンでの受験にご参加いただけますが、ご自身のスキルランクには影響しませんので、予めご了承ください。
  • (3) ご提出いただいたコードの著作権は受験者にその権利が帰属しますが、当社はそのコードを当社のサイトやSNS上で公開したりなど、自由に利用できるものとします。詳しくは 当社利用規約 第5条2項に準じるものとします。
  • (4) ご提出いただいたコードは当社システム上において完全に保存されない場合がありますので、受験者ご自身において必要に応じてバックアップを取るなど、適切なご対応をお願いいたします。

お仕事の詳細

センパイのソースコード見てみたい!

あなたはとあるECサイトのプログラマです。このECサイトではたくさんの商品を取り扱っていて、 一番安いもので10円、高いものでは100万円の商品まで存在します。 今回、そのECサイトを運営しているあなたの会社は、サイトの集客キャンペーンとして、「組み合せで無料キャンペーン」と銘打って、設定金額に最も近い商品の組み合わせを購入すれば無料となるキャンペーンを開催することにしました。その内容は以下の通りです。

  • キャンペーン設定金額として毎日1つの設定金額(整数)mが決められます。
  • ECサイトの利用客は、 2つの異なる商品(値段は同じでも構わないが必ず二つ) を購入し、その 合計価格がキャンペーン設定金額m円以下で、かつ最大となるような商品の組合せだった場合、 その商品を無料で手に入れることができます。
    設定金額が23150円、商品は3つ(シュークリーム12,000円とスルメイカ17,000円、大根は11,120円)だった場合、シュークリームと大根(合計23,120円)の組み合わせが無料になります。
  • すべての商品の価格と、イベント期間中の 各日のキャンペーン設定金額m円(キャンペーン日数分) が与えられるので、各日のキャンペーン設定金額mに対し、上記ルールのもとでの最大値を計算するプログラムを作成する のがあなたの仕事です。
他のプログラマに教えよう!

入力される値

入力は以下のフォーマットで与えられる。

N D
p_1
p_2
...
p_N
m_1
m_2
...
m_D

N は商品の総数を表します。
D は、キャンペーンの日数を表します。 ※ D=与えられる m(キャンペーン設定金額)の個数。
p_i (1 ≦ i ≦ N) は商品i の価格を表す整数であり、改行区切りでN 個与えられます。
m_j (1 ≦ j ≦ D) はj日目のキャンペーン設定金額を表す整数であり、改行区切りでD 個与えられます。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください

条件

Java,C#,Perl,PHP,Python,Rubyは全テストケースで以下の条件を満たします。
N (1 ≦ N ≦ 200000) ※ 商品点数
D (1 ≦ D ≦ 75) ※ キャンペーン日数
p_i (10 ≦ p_i ≦ 1000000) ※ 商品の価格
m_j (10 ≦ m_j ≦ 1000000) ※ キャンペーン設定金額

C,C++は全テストケースで以下の条件を満たします。
N (1 ≦ N ≦ 500000) ※ 商品点数
D (1 ≦ D ≦ 300) ※ キャンペーン日数
p_i (10 ≦ p_i ≦ 1000000) ※ 商品の価格
m_j (10 ≦ m_j ≦ 1000000) ※ キャンペーン設定金額

※ C、C++はテストケースが一部異なります。

期待する出力

各キャンペーン日毎のキャンペーン設定金額(m)に最も近い最大値(組み合せ合計値)を1行づつ、
キャンペーン日数分(M)出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
入力例1
4 3  // 商品の総数は4個、キャンペーン日数は3日
8000 // 商品1の値段
4000 // 商品2の値段
9000 // 商品3の値段
6000 // 商品4の値段
3000 // 1日目のキャンペーン設定金額
14000 // 2日目のキャンペーン設定金額
10000 // 3日目のキャンペーン設定金額

※ 上記[ // ]以降はコメントアウトの意。

出力例1
0 // 1日目のキャンペーン設定金額(3000)に最も近い組み合せが無い場合0を出力
14000 // 2日目のキャンペーン設定金額(14000)に最も近い組み合せの合計金額
10000 // 3日目のキャンペーン設定金額(10000)に最も近い組み合せの合計金額

※ 上記[ // ]以降はコメントアウトの意。

入力例2
5 2
4000
3000
1000
2000
5000
10000
3000
出力例2
9000
3000
入力例3
4 1
1000
3000
7000
8000
10000
出力例3
10000

解答欄

上記の問題の解答コードを下記入力欄に記入し提出してください。
使用できる言語はJava,PHP,Ruby,Perl,Python,C,C#,C++,JavaScriptです。その他の言語(Beta)は、問題が解けない可能性があります。

標準入力の値の取得方法は下記ページのサンプルコードを参照ください。

Let’sチャレンジ!!得意な言語を選んでコードを書いてみよう

使用する言語(提出するコードの言語)

あなたの得意な言語を選択!

コード実行結果

応募期間終了いたしました。
コード実行は可能ですがプレゼント対象外、最速実行時間計測対象外に成ります。

提出すると複数のテストケースにより、バグの有無、実行速度を判定し点数化します。

ニックネーム (必須)
英数半角文字のみ。模範解答コード掲載時、プレゼント当選者発表時にサイトに掲載する事がございます。
メールアドレス (必須)
登録メールアドレスは、paiza オンラインハッカソン以外で利用する事はございません。
コードを提出頂くと解答結果ページをメールいたします。

Facebook

Twitter

関連イベント

POH Lite 天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」

POH Vol.2「女子大生とペアプロするだけの簡単なお仕事です!」

関連ページ

【POH Vol.1結果発表】新人女子を最も助けたコードとは?

【POH Vol.1ブログ】最速コードの裏側に迫る!

模範解答(会員登録が必要です)

POH Lite模範解答ページ

POH Vol.2模範解答ページ

POH Vol.1模範解答ページ

ページの先頭へ戻る