paiza > パイザオンラインハッカソン・Lite

パイザ オンライン ハッカソン 略してポー(POH ! Lite)

天才火消しエンジニア霧島

模範解答Vol.2(動的計画法)を公開しました。

模範解答を見る(会員登録が必要です)(2014/8/26)

天才エンジニア霧島京子の運命やいかに!!

あなたは天才的頭脳で超人的な演算処理能力を持ち、幾多のデスマプロジェクトを鎮めてきた天才火消しエンジニア霧島 京子(26歳)。エンジニアの間で知らない者のいない伝説のエンジニアである。今回霧島に降りかかってきたミッションは、なんと史上最大級の20万人月プロジェクト。霧島の運命やいかに!!

リポビタンD 100ml×50本を3名様にプレゼント!!

応募受付終了いたしました。たくさんのご応募ありがとうございました。

Share!
天才火消しエンジニア霧島京子(26歳)

天才火消しエンジニアの天才的頭脳が炸裂する!!

今回のプロジェクトは期間3年、工数20万人!?

業界最大手SIerでPM職の火村氏。彼が取り仕切る案件は毎度炎上する事で有名で、 火村氏は別名“着火マン”とも呼ばれている ほど。今回そんな火村氏がとり仕切る事になったのが、プロジェクト期間3年、工数は20万人月とも言われる四菱USJ銀行の基幹システム統合作業です。すでに各タスクの仕様書作成、工数見積もりは終了し、下請けへの発注作業中。あまりにもタスクが多いため、スクリプトで発注先を割り振る事にした火村氏。しかし今回も火村氏は早速スケジュールが押していて、既に残り1ヶ月まで納期がせまり、絶賛炎上中です。

天才火消しエンジニアのミッションとは …

あなたは天才的頭脳で超人的な演算処理能力持ち、幾多のデスマプロジェクトを鎮めてきた天才火消しエンジニア霧島京子(26歳女)。エンジニアの間で知らない者のいない伝説のエンジニアです。今回のプロジェクトでは「二次請けのPM/SEとして火村氏のサポート」という名の丸投げを受ける事に。。

今回霧島(あなた)に与えられたのミッションは、下請けリストをもとに、どういう組み合わせの下請け企業に依頼すれば安くプロジェクトを上げられるかを計算する事です。

問題詳細を見る

ヒントモードで誰でもチャレンジ可能!!

霧島(あなた)のコードでプロジェクトの成否が変わる!

四菱USJ銀行の命運は霧島(あなた)にかかっています!本ページ下記の「ミッション詳細」に従い、お好きな言語(Java、C、C++、C#、PHP、Ruby、Python、Perl、JavaScript)で、効率の良いコードを実装してください。提出コードは複数のテストケースを入力し、正答数と解答の提出までに要した時間を測定し得点が決まります。

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

ミッションの流れ

STEP1 コードを書く

STEP2 動作確認する

STEP3 提出

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

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

参加者の中から抽選で3名様にリポビタンD 100ml×50本プレゼント!!

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

テストケース別通過率

あなたも参加して、全テストケースをクリアしよう!

テストケース番号

ケース通過率

通過数 / 受験数

TestCase: 1

88 %

5163 / 5867 提出

TestCase: 2

82 %

4866 / 5867 提出

TestCase: 3

79 %

4673 / 5867 提出

TestCase: 4

68 %

4016 / 5867 提出

TestCase: 5

61 %

3608 / 5867 提出

TestCase: 6

31 %

1827 / 5867 提出

TestCase: 7

25 %

1522 / 5867 提出

(2014/08/28更新)

各テストケース毎の通過率及び通過人数を表示しています。

▼ 集計結果を詳しく見る

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

テストケース4(中規模データ)の 最速・最遅実行時間です。

言語

最速実行時間

最遅実行時間

通過数 / 受験数

Java

0.01 秒

2.83 秒

572 / 767 提出

PHP

0.01 秒

14.97 秒

402 / 642 提出

Ruby

0.02 秒

0.57 秒

898 / 1223 提出

Python2

0.01 秒

2.75 秒

316 / 468 提出

Perl

0.01 秒

0.18 秒

78 / 116 提出

C

0.01 秒

2.68 秒

324 / 523 提出

C++

0.01 秒

0.91 秒

572 / 784 提出

C#

0.01 秒

0.89 秒

415 / 593 提出

JavaScript

0.03 秒

0.14 秒

246 / 380 提出

Objective-C

0.01 秒

0.01 秒

3 / 3 提出

Scala

0.28 秒

0.47 秒

36 / 97 提出

Go

0.01 秒

1.11 秒

54 / 70 提出

Haskell(Beta)

0.01 秒

0.01 秒

37 / 45 提出

CoffeeScript(Beta)

0.09 秒

0.11 秒

10 / 10 提出

Bash(Beta)

0.01 秒

0.12 秒

9 / 73 提出

Erlang(Beta)

1.16 秒

1.19 秒

8 / 12 提出

R(Beta)

0.10 秒

0.11 秒

4 / 23 提出

COBOL(Beta)

0.01 秒

0.01 秒

3 / 8 提出

VB(Beta)

0.01 秒

0.03 秒

25 / 26 提出

F#(Beta)

0.03 秒

0.05 秒

4 / 4 提出

(2014/08/28更新)

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

テストケース5(中規模データ)の 最速・最遅実行時間です。

言語

最速実行時間

最遅実行時間

通過数 / 受験数

Java

0.01 秒

4.21 秒

523 / 767 提出

PHP

0.01 秒

14.97 秒

363 / 642 提出

Ruby

0.02 秒

11.19 秒

806 / 1223 提出

Python2

0.01 秒

6.66 秒

279 / 468 提出

Perl

0.01 秒

12.68 秒

59 / 116 提出

C

0.01 秒

2.31 秒

306 / 523 提出

C++

0.01 秒

0.14 秒

508 / 784 提出

C#

0.01 秒

3.22 秒

385 / 593 提出

JavaScript

0.03 秒

0.29 秒

205 / 380 提出

Objective-C

0.01 秒

0.01 秒

3 / 3 提出

Scala

0.28 秒

1.01 秒

35 / 97 提出

Go

0.01 秒

0.66 秒

40 / 70 提出

Haskell(Beta)

0.01 秒

0.01 秒

35 / 45 提出

CoffeeScript(Beta)

0.09 秒

0.11 秒

10 / 10 提出

Bash(Beta)

0.01 秒

0.12 秒

8 / 73 提出

Erlang(Beta)

1.16 秒

1.18 秒

8 / 12 提出

R(Beta)

0.10 秒

0.19 秒

4 / 23 提出

COBOL(Beta)

0.01 秒

0.01 秒

3 / 8 提出

VB(Beta)

0.01 秒

0.03 秒

24 / 26 提出

F#(Beta)

0.03 秒

0.05 秒

4 / 4 提出

(2014/08/28更新)

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

テストケース6(大規模データ)の 最速・最遅実行時間です。

言語

最速実行時間

最遅実行時間

通過数 / 受験数

Java

0.01 秒

5.93 秒

275 / 767 提出

PHP

0.01 秒

14.97 秒

167 / 642 提出

Ruby

0.02 秒

6.90 秒

449 / 1223 提出

Python2

0.01 秒

6.83 秒

123 / 468 提出

Perl

0.01 秒

1.18 秒

18 / 116 提出

C

0.01 秒

2.91 秒

114 / 523 提出

C++

0.01 秒

2.64 秒

317 / 784 提出

C#

0.01 秒

4.29 秒

194 / 593 提出

JavaScript

0.03 秒

8.25 秒

63 / 380 提出

Objective-C

0.01 秒

0.01 秒

3 / 3 提出

Scala

0.28 秒

2.97 秒

16 / 97 提出

Go

0.01 秒

0.33 秒

22 / 70 提出

Haskell(Beta)

0.01 秒

2.72 秒

19 / 45 提出

CoffeeScript(Beta)

0.10 秒

0.89 秒

5 / 10 提出

Bash(Beta)

0.01 秒

0.80 秒

8 / 73 提出

Erlang(Beta)

1.16 秒

2.38 秒

5 / 12 提出

R(Beta)

0.10 秒

0.10 秒

1 / 23 提出

COBOL(Beta)

0.01 秒

0.32 秒

3 / 8 提出

VB(Beta)

0.01 秒

0.04 秒

21 / 26 提出

F#(Beta)

0.03 秒

0.05 秒

4 / 4 提出

(2014/08/28更新)

最遅実行時間はLimitTime内で最も遅い実行時間だったものを表示しています。
※ 実行する時間帯によっては実行時間が変わる可能性がございます。予めご了承ください。

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

テストケース7(大規模データ)の 最速・最遅実行時間です。

言語

最速実行時間

最遅実行時間

通過数 / 受験数

Java

0.01 秒

5.72 秒

210 / 767 提出

PHP

0.01 秒

14.97 秒

124 / 642 提出

Ruby

0.02 秒

14.43 秒

374 / 1223 提出

Python2

0.01 秒

11.36 秒

116 / 468 提出

Perl

0.01 秒

5.88 秒

15 / 116 提出

C

0.01 秒

2.49 秒

88 / 523 提出

C++

0.01 秒

2.79 秒

281 / 784 提出

C#

0.01 秒

5.41 秒

184 / 593 提出

JavaScript

0.03 秒

5.64 秒

49 / 380 提出

Objective-C

0.01 秒

0.01 秒

3 / 3 提出

Scala

0.28 秒

0.60 秒

6 / 97 提出

Go

0.01 秒

1.75 秒

21 / 70 提出

Haskell(Beta)

0.01 秒

2.19 秒

9 / 45 提出

CoffeeScript(Beta)

0.10 秒

0.19 秒

4 / 10 提出

Bash(Beta)

0.01 秒

2.34 秒

8 / 73 提出

Erlang(Beta)

1.16 秒

2.08 秒

2 / 12 提出

R(Beta)

0.10 秒

0.10 秒

1 / 23 提出

COBOL(Beta)

0.01 秒

1.73 秒

2 / 8 提出

VB(Beta)

0.01 秒

0.29 秒

21 / 26 提出

F#(Beta)

0.03 秒

0.08 秒

4 / 4 提出

(2014/08/28更新)

ミッションの納期、報酬(プレゼント)

スケジュール

応募期間
7月30日(水)~8月27日(水)

終了しました

抽選期間
8月28日(木)~9月2日(火)
結果発表
9月3日(水)

報酬(プレゼント)

参加者の中から抽選で3名の方に、リポビタンD(150ml×50本)をプレゼント。

イベント規約

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

ミッション詳細

あなた(霧島京子) は20万人月の巨大なプロジェクトを一ヶ月で終わらせるために無数の下請け会社から人員をかき集める仕事をすることになりました

プロジェクトを終わらせるのに必要な人員数 m 名 と、発注可能な下請け会社の数 n 社、各下請け会社のアサイン可能なエンジニア人員数 q_i 名 と、発注に必要な費用 r_i 万円が与えられます。

  • 各下請け会社の人員は、一部を使うなどは出来ず全員を使わなくてはいけません
  • プロジェクトに必要な人員数 m 以上を満たせる組み合わせで、最も安くすむ合計金額(単位:万円)を出力してください。
  • 各下請け会社の人員数の合計はプロジェクトの規模 m 人月以上になるものと します。
    ※ 1人月とは、1人が1ヶ月間かかる作業量を言います。
入力例1のイメージです。 Hint figure

※ 実際のプロジェクトではこの様には行きませんので、人員を増やす場合は慎重に検討する事をお勧めいたします。
※この物語はフィクションであり、実在の人物・団体とは一切関係ありません

他のプログラマに教えよう!

入力される値

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

m (プロジェクトに必要な人員数)
n (下請け会社の数)
q_1 r_1 (1番目の下請け会社の人員数 発注に必要な費用[単位:万円])
q_2 r_2 (2番目の下請け会社の人員数 発注に必要な費用[単位:万円])
・・・
q_i r_i (n 番目の下請け会社の人員数 発注に必要な費用[単位:万円])

条件

1 ≦ m ≦ 200000(プロジェクトに必要な人数:最大20万人)
1 ≦ n ≦ 50(下請け会社数:最大50社)
1 ≦ q_i ≦ 10000(各下請け会社の人員数:最大1万人)
1 ≦ r_i ≦ 5000000(各下請け会社のへの発注費用[単位:万円]:1万円〜最大500億円)
m ≦ q_1 + q_2 + q_3 ... + q_i(各下請け会社の人員数の合計はプロジェクトに必要な人数 m 人以上になる)

期待する出力

最もコストが安くなる組み合わせの総コストを出力して下さい。
最後は改行し、余計な文字、空行を含んではいけません。
入力例1
60
3
40 4300
30 2300
20 2400


出力例1
6600
入力例2
250
5
35 3640
33 2706
98 9810
57 5472
95 7790
出力例2
23072

解答欄

上記の問題の解答コードを下記入力欄に記入し提出してください。
使用できる言語はJava,PHP,Ruby,Perl,Python,C,C#,C++,JavaScriptです。
その他の言語(Beta)はβ版の位置づけですので、 解ける事を保証するものでは有りません。

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

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

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

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

コード実行結果

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

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

Facebook

Twitter

Share!

プログラミング・スキルチェックサイト(POH開催元)

paiza
paiza(パイザ)は、 コードを書いて自分のプログラミングスキルがわかる、
IT/Webエンジニア、プログラマのための新しいカタチの学習、転職サービスです。
匿名で誰にも知られず 「自分のスキルが他社で通用するのか」が判ります。
対応言語は Java,PHP,Ruby,Python2,Python3,Perl,C,C++,C#,JavaScript,Objective-C,Scala,Go,Swift に対応。

出題問題一覧をみる

※マンガ引用元:「ブラックジャックによろしく」作者:佐藤秀峰、漫画 on web http://mangaonweb.com/
※この物語はフィクションであり、実在の人物・団体とは一切関係ありません

ページの先頭へ戻る