第 1 回 Asprova プログラミングコンテスト説明書
2018 年 8 月 9 日

Ver.1.0

アスプローバ株式会社

目次
1 はじめに ............................................................................................................................................................................................. 2
2 順位決定方法 ................................................................................................................................................................................... 3
3 禁止事項 ............................................................................................................................................................................................. 34 開発の進め方 ................................................................................................................................................................................... 4
5 プログラム提出と順位発表 ..................................................................................................................................................... 6
付録 A

入力データ .......................................................................................................................................................................... 7

付録 B

入力ファイルと出力ファイルのフォーマット ............................................................................................... 8

付録 C

開発用プロジェクト...................................................................................................................................................... 9

付録 D

評価用マシン ................................................................................................................................................................. 14

付録 E

Asprova を使った結果の確認方法 .................................................................................................................... 19

1

1 はじめにコンテストへの参加ありがとうございます。本説明書は、コンテスト参加者に向けた説明書です。不明な点がございましたら、HP 上に用意されている QA ページ(https://groups.google.com/forum/#!forum/proconqa)にて質問するか、procon@asprova.com までメールでお問い合わせください。QA ページでの質問の書き込みには Google アカウントが必要です。

なお、本コンテストで提出されたプログラムの権利については、以下のように定めさせていただきます。
「受賞者は賞金を受領すると同時に、受賞プログラムの著作権（著作権法第 27 条および第 28 条に規定する権利を含む）を主催者に移転し、著作者人格権を行使しないものとします。」
例えば第 2 回以降のコンテストにて過去の入賞者の参考プログラムとして使用させていただきます。

正式問題は、プロコン HP (https://www.asprova.com/jp/procon/procon1.html)をご覧ください。
以下は問題の理解を補足するための例です。

例：
M=2、L= 4 (下図 4 色で色分け)、N=13
下図の行は設備、列は時間、高さは C およびパンの個数 Q、赤字は納期遅れを表す。B 案の利益の方が高いため、B 案の勝ち。

粗利 = 24 個 × 10 円 =240 円

納期遅れペナルティ =(4 個×1) + (2 個×1) + (2 個×1)=8A案円
電気代 = 11 回 × 10 円 = 110 円
利益 = 売上 - 納期遅れペナルティ 電気代 = 122 円

粗利 = 24 個 × 10 円 = 240 円
納期遅れペナルティ = 0 円

B案

電気代 = 7 回 × 10 円 = 70 円
利益 = 売上 - 納期遅れペナルティ 電気代 = 170 円

22 順位決定方法
プログラムを公平に評価するため、Windows マシンで開発した人も Linux マシンで開発した人も、最終的には Microsoft Visual
Studio 2017 x64 Release 版でビルドした実行ファイルを弊社で用意した評価用マシン上で実行して評価します。開発手順については後述します。評価用マシンについては「付録 D 評価用マシン」をご覧ください。

プログラムを評価するために、異なる特徴を持つ 3 つの入力データ(A,B,C)を用意しています。この 3 つの入力データでプログラムを実行して順位を決定します。

<順位>
順位は 3 つの入力データ(A,B,C)それぞれの利益 P をそれぞれの最大利益 Pmax で割った値(利益達成率)の合計で決まります。
利益達成率合計 = PA/PAmax + PB/PBmax + PC/PCmax(小数点 8 桁以下切り捨て)

ただし、以下が起きた場合は利益達成率に関係なく、失格となり順位が出ません。
スケジューリング制約違反

詳細は問題文をお読みください。

プログラムのランタイムエラー
計算最大時間オーバー

制限時間は 5 分です。1msec でもオーバーした場合は失格です。

利益達成率合計が同値の場合は、予選時のプログラム提出が早い順で順位を決めます。

3 つの入力データは予選用、決勝用があり、それらは非公開です。詳細は「付録 A 入力データ」をご覧ください。

3 禁止事項
1.

C++標準ライブラリ、STL 以外のライブラリの使用。例：C++ Boost Library、OpenMP2.

第３者が作成したソルバーの使用。例：Google Optimization Tool

3.

プログラムを実行するマシン以外のマシンにリモートでアクセスすること。

C++標準ライブラリ、STL、マルチスレッドの使用は許可されています。
禁止事項に違反した場合は失格となり、順位は出ません。

34 開発の進め方
開発は参加者の皆さんのマシンで行ないます。順位を決めるための評価にはクラウド上にある評価用マシンを使用します。

評価用マシン(貸し出します)
Windows + Visual Studio 2017

実行ビルド、実行

決勝(大岡山会場)
Linux
プログラム提出
開発

決勝進出者 5 名決定

開発

Windows

以下に進め方を説明します。

① 開発ツールのダウンロード
コンテストの参加申込みをすると、以下の開発ツールがダウンロードできます。
1.

Microsoft Visual Studio 2017/2015 開発用プロジェクト(.sln、.h、.cpp など)、Linux 用の開発ファイル
データの入力処理、出力処理は実装済みです。サンプルプログラムもあります。このプロジェクトの使い方などが学べます。
このプログラムより良い結果を出すプログラムを作成してください。詳細は「付録 C 開発用プロジェクト」をご覧ください。

2.

練習用入力データ (1A.csv、1B.csv、1C.csv)×2 セット(データ量大小)

合計 6 個少量データ(N=100)はデバッグ用の少量データです。
大量データ(N=10,000)は練習用入力データです。
このデータは予選用、決勝用のデータと異なります。

3.

結果確認用 Asprova データ (data.aru)
実行結果を Asprova 上で確認するためのデータです。スケジュールをガントチャートで確認することができます。詳細は「付録 E Asprova を使った結果確認方法」をご覧ください。

4

② 開発環境の用意
Windows マシンを使用する場合は、Visual Studio 2017 をインストールしましょう。無償で使用できる Microsoft Visual
Studio2017 Community 版は以下からダウンロードできます。
https://visualstudio.microsoft.com/ja/downloads/

Linux マシンを使用する場合は基本的にお好きな環境で開発して良いですが、提供する Linux ソースコードに対して動作確認が済んでいるため、以下のツールを推奨します。
・

CMake

・

GCC( g++ 7.3 ) or Clang ( clang 6.0 )③ 開発
まずは開発用プロジェクトのサンプルプログラムを読んでみるのが良いでしょう。また、この問題の解法に関する手法は、例えば次のサイトなどを参考にすると良いでしょう。https://ja.wikipedia.org/wiki/組合せ最適化④ 提出準備Visual Studio 2017 64bit Release 版でビルドできる状態のソースコード ASProConPlayer.cpp を用意してください。

Visual Studio 2017 でビルドできないファイルの場合は原則として失格になります。Linux マシンで開発する人や Visual Studio2017 未満のバージョンで開発する人は、評価用マシンにログインし、Visual Studio 2017 に移植してビルドができる状態にしてください。評価用マシンでのビルド確認、実行については「付録 D 評価用マシン」をご覧ください。

55 プログラム提出と順位発表
サンプルプログラムより良い結果になるプログラムが出来たらアスプローバ社が指定する URL に Visual Studio 2017 64bit
Release 版でビルドできる状態のソースコード ASProConPlayer.cpp をアップロードしてください。アップロードには Google アカウントが必要です。

プログラムを提出すると、弊社にて評価用マシンでプログラムをビルドし、予選用入力データを使って実行します。
その結果は HP にて順位をつけて公開します。この順位は毎週火曜日に更新する予定です。可能であれば平日、毎日更新いたしま
す。

イメージ順

名前/ハンドル

利益達成率合計

利益達成率 A

利益達成率 B

利益達成率 C

提出日位

ネーム

1Saeki2.87515546

0.97066978

0.92113677

0.98334890

18/8/18

2ゴリ

2.85202064

0.96208835

0.90892974

0.98100255

18/8/163清水 太郎

2.81038646

0.96374272

0.91726855

0.92937520

18/8/284加藤 ゆうこ2.51997855

0.77621114

0.91302661

0.83074080

18/8/14

5Seb

2.49927285

0.75550544

0.83074080

0.91302661

18/9/2

6

サンプル 12.38508175

0.64131434

0.91302661

0.83074080

18/8/9…

…

…

…

…

…

備考

参考記録

プログラムの提出は原則、1 日 1 回を上限とし、合計で 10 回までです。11 回以上提出したい場合はご相談ください。
プログラムの最終提出期限は 2018/9/6 9:00 です。

6

付録 A 入力データ異なる特徴を持つ 3 つの入力データを用意しています。

ABN

オーダ(注文)件数

10,000

粗利合計(練習用)

P1

粗利合計(予選用)

C

粗利合計(決勝用)¥2,932,670¥348,330¥2,762,160\2,944,420\346,860\2,774,370\2,928,240\345,380\2,774,810

設備(パン焼き器)台数

M202040

同時に焼けるパンの最大個数の範囲

Cn

50

5301001050500

30100

1,000

100

200200Ln

パンの種類
パンの種類とオーダ件数

10010030

大量生産品+少量生産品の混合

平準化

以下の範囲でランダムに分布

20 種 20 件

100 種 100 件

267-410 件(練習用)

20 種 40 件

271-450 件(予選用)

60 種 150 件

271-450 件(決勝用)

10-196 (練習用)

Qn

10-50

1-6

1 オーダあたりのパンの個数の範囲
納期-最早開始日時

10-200 (予選用)
10-200(決勝用)

Dn-En

Dn

3-7

1-7

En < Dn <= 100000

納期と最早開始日時の範囲

入力データは、練習用、予選用、決勝用があります。練習用、予選用、決勝用データはそれぞれ Dn 、En が違います。

練習用入力データ(A,B,C)

コンテスト申込み時にお渡しします。順位の決定には用いません。

予選用入力データ(A,B,C)

非公開です。予選で弊社が順位を決めるために使用します。

決勝用入力データ(A,B,C)

非公開です。決勝で弊社が順位を決めるために使用します。

7付録 B入力ファイルと出力ファイルのフォーマット

入力ファイル
テストの際、データを書き換えてテストすることは自由です。
行番号

データ

1

T_LIMIT

2INT

3P14M

5

C1…

CM
N
O1,I1,q1,E1,D1…

ON,IN.qN,EN,DN

出力ファイル
開発プロジェクトにて、以下の出力ファイルは自動で出力されるようになっています。
行番号

データ

説明

1

P,P/Pmax

利益と利益達成率2
3

3 行目以降に対する各列の説明

O1,S1,S1+1,R1,1,

5 番目は Asprova でインポートするための予約フィールドです。

…

…

On,Sn,Sn+1,Rn,1,

5 番目は Asprova でインポートするための予約フィールドです。

T_LIMIT = 計算最大時間= 5 (分) 固定
P1 = 粗利合計
P = 利益Rn = オーダ n が割り付いた設備の番号(1,2,3…)
Sn = オーダ n の開始時刻(0,1,2,3…)
dn = オーダ n の納期遅れ時間、遅れていない場合は 0
INT = 実行中に途中経過を出力するインターバル時間(秒)

8

付録 C

開発用プロジェクト問題を解くための開発に専念できるようにするため、データの入出力処理の実装が済んでいるソースコードを用意しています。また、このプログラムには、解法の例としてサンプルのソースコードを用意しています。

ソースコードは Windows 用と Linux 用のものがあります。
Windows(ダイアログ）版

windows/AsProCon1

Windows(コンソール）版

windows/AsProCon1Console

Linux 版

linux/AsProCon1

決勝では、Windows(ダイアログ）版を使用する予定です。

主なファイルASProConPlayer.h /cpp

皆さんがプログラムする CASProConPlayer クラスの実装があります。cpp ファイルのコメントに入力データや残り実行時間の取得方法などの説明があります。

IASProConPlayer.h/cpp

CASProConPlayer クラスが継承する IASProConPlayer クラスの実装があります。
CASProConPlayer から使用できるメソッドの実装があります。

ASOrder.h

オーダ情報を格納する構造体が定義されています。

ASResource.h

設備情報を格納する構造体が定義されています。

実装は全て ASProConPlayer.cpp ファイル内に記述して、ファイルの追加や、他の既存ファイルの変更はしないでください。
プログラムを実行すると、自動的に入力データがロードされます。その後、CASProConPlayer::Execute 関数が呼ばれますので、この関数の中にプログラムを実装し、かつ、Execute 関数内の処理が 5 分以内に終了するようにプログラムしてください。

出力ファイルプログラムを実行すると、入力ファイルに応じて実行ファイルと同じフォルダに result1A.csv、result1B.csv、result1C.csv が出力されます。詳細は「付録 B入力ファイルと出力ファイルのフォーマット」をご覧ください。

サンプルコード
開発用プロジェクトには、サンプルのプログラムを用意しています。それぞれのプログラムによる入力データ A、B、C の利益はHP にて公開しています。この結果よりも高い利益を出すプログラムを開発してください。
CASProConPlayerSample1.h/cpp

オーダを納期昇順でソートして、この順番で各オーダのスケジュールを決めていく

CASProConPlayerSample2.h/cpp

オーダを納期昇順でソートした後、オーダ順をランダムに入れ替えながら、制限時間の限り何度も計算する。そしてその処理をマルチスレッドで行う。

9Windows(ダイアログ）版
Visual Studio2017 で AsProCon1_vs2017.slnを開きます。Visual Studio 2015 で開発する人は AsProCon1_vs2015.sln を開きます。

Microsoft Visual Studio 2015 未満の sln ファ
イルが必要な方は、ご相談ください。

ASProConPlayer.cpp ファイルの CASProConPlayer::Execute 関数を実装します。

マルチスレッド実装をする場合は std::thread を使用してください。

ビルドすると AsProCon1.exe が生成されます。このexe を実行すると右図のダイアログが起動します。

※

ビルドを実行すると、以下のようなエラーが出ることがあります。

10

error MSB8036: The Windows SDK version 8.1 was not found. Install the required version of Windows SDK or change theSDK version in the project property pages or by right-clicking the solution and selecting "Retarget solution".
この場合、メニュー⇒「プロジェクト」 ⇒「プロパティ」でプロパティダイアログを起動して、Windows SDK バージョンを選択可能な他のもの(何でもよいです）に変更してください。

実行●データのファイルパスを指定
右図の EditBox に入力用 csv ファイルのファイルパスを記述します
実行対象で、CASProConPlayer::Execute()に実装した自作プログラムを実行するか、サンプルプログラム(1～2)
を選ぶことが出来ます。

●実行：実行ボタンを押す

実行ボタンを押すと、実行時間と利益達成率などが表示されます。

実行時間が 300 秒を超えないようにし、利益達成率が高くなるように改善しましょう

11

Windows(コンソール）版

基本的にはダイアログ版と同じです。

入力データの csv ファイルのパスはAsProCon1.exe の一つ目の引数に指定してください。

CASProConPlayer::Execute()に実装した自作プログラムを実行する
か、サンプルプログラム(1～2)を実行するかは、AsProCon1.cpp ファイルの wmain 関数にて、実行したいプログラム以外はコメントアウトしてビルドし直す必要があります。

Release 版と Debug 版
Visual Studio ではビルドするときに Release 版か Debug 版を指定します。
Release 版

実行速度が速い。

Debug 版

実行速度が遅い。デバッグのために使用する。ソースコード上にブレークポイントを設置して実行を一時的に止め、プログラムを 1 行もしくは複数行ごとに手動で実行するステップ実行をしたり、実行中の変数をウォッチウィンドウなどで確認したりできる。

予選用の出力データを実行するときは Release 版でビルドした実行ファイルで実行してください。
Debug 版を使用すると効率的に開発ができます。デバッグ方法などの詳細は Web ページや書籍などを参照してください。

12

Linux 版
推奨するツール(動作確認済み)
・CMake・GCC( g++ 7.3 ) or Clang ( clang 6.0 )コンパイル方法
source/Linux/AsProCon1 $ mkdir build
source/Linux/AsProCon1 $ cd build
source/Linux/AsProCon1/build $ cmake ..
source/Linux/AsProCon1/build $ make

実行方法
source/Linux/AsProCon1/build $ ./main <data file path>

13

付録 D

評価用マシン

評価用マシンには Microsoft Visual Studio 2017 がインストールされてあり、ビルド、実行環境が整っています。また、生産スケ
ジューラ Asprova がインストールされており、実行結果をガントチャートなどで確認することが出来ます。評価用マシンは無料で貸し出しますので、リモートデスクトップにログインしてビルドし、予選用入力データで実行したてテスト出来ます。

ハードディスクに保存されたデータはコンテスト決勝日まで残っています。

評価用マシンのスペック
OS = Windows Server 2012
CPU= Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz
論理プロセッサ数=4
メモリ=8GB

評価用マシンの貸出
評価用マシンは無料で貸し出します。一人あたりの合計使用時間の上限は 24 時間です。基本的に 6 時間単位で 4 枠貸し出します。こまめにシャットダウンしていただければ合計 24 時間の範囲内で枠数を増やすことが可能です。その場合はご相談ください。シャットダウンについての詳細は、この後の「評価用マシンのシャットダウンについて」をお読みください。

評価用マシンの予約マシンの予約は土日祝日を除いた平日 2 日前までに

https://select-type.com/rsv/?id=nYtuDWf5Li0&c_id=40675

以下のサイトで行なってください。1 回の予約は 6時間の枠になります。

予約した後、アスプローバ社からメールで以下をお送りしますので、ログイン時にご使用ください。
IP アドレス、ログインアカウント名、ログインパスワード、Windows 用リモートデスクトップ rdp ファイル14

評価用マシンのログイン方法(Windows マシンから)

アスプローバ社から送られてきた rdp ファイルをダブルクリックし、パスワードを入力してください。

評価用マシンのログイン方法(Linux マシンから)最初に、次のコマンドで rdesktop をインストールします。
$ sudo apt update$ sudo apt install rdesktop

次に、評価用マシンの IP アドレスを指定し、かつ、ASProConPlayer.cpp があるフォルダもしくはその上位のフォルダを<共有フォルダの絶対パス>に指定して rdesktop を起動します。
$ rdesktop <IP_ADDRESS> -r disk:share=<共有フォルダの絶対パス>

下図左のような画面になりますので、アスプローバから通知されたユーザ名、パスワードでログインします。ログイン時に下図右のようなシャットダウンイベントの追跡ツールが起動することがありますが、キャンセルボタンを押して閉じて下さい。

15評価用マシンの使用方法

評価用マシンにログインすると、以下のような画面になります。「コンテスト概要フォルダ」に必要なファイルへのショートカットなどがまとめられています。

コンテスト概要フォルダの中身
1.

Q&A ウェブリンク：Q&A のウェブページに飛ぶ2.

ファイル投稿ウェブリンク：完成したファイルをアップロードするページに飛ぶ3.

「ソースコードをこのフォルダに貼り付け」フォルダ：このフォルダに自分の ASProConPlayer.cpp をコピー＆ペーストしてください

4.

EXE フォルダ：ビルドした 64bit Release 版の EXE のフォルダ

5.

データフォルダ：予選用入力データファイルのフォルダ

ビルド確認方法「ソースコードをこのフォルダに貼り付け」フォルダを開いて、自分が書いた
ASProConPlayer.cpp をコピー＆ペーストしてください。

Linux マシンからログインしている場合は、<共有フォルダの絶対パス>で指定したフォルダは「PC」 から参照することができます。右図の「〇〇の share」という名前のものがそれです。Linux マシンの ASProConPlayer.cpp を評価用マシンの Windows ダイアログ版のソースコードフォルダにコピー&ペーストして置き換えてください。

16

ファイルをコピーしたら概要フォルダに戻って「ソリューションファイル」をダブルクリックし、Visual Studio 2017 を起動してください。
Visual Studio 2017 が起動したら、Release、x64 になっていることに注意してメニュー[ビルド][AsProCon1_vs2017 のビルド]を選択するとビルドが始まります。
コンパイルエラー、リンカエラーが出たら修正してください。

実行「コンテスト概要」フォルダにある「EXE フォルダ」へのショートカットを選択すると、ビルドされた AsProCon1.exe がありますので、これをダブルクリックして実行します。

実行前

実行後

4

1
3

2
1.

上の「…」ボタンをクリック、テストしたいデータ(csv)を選びましょう。データのパスは概要フォルダの「データフォルダ」と同じです。

2.

データ選択したら、下の「実行対象」に“自作“を選択する。

3.

「実行」ボタンをクリック。出力メッセージがダイアログ内に出ます。

4.

実行終わったら、結果を確認するために「データフォルダを開く」をクリックしましょう。

17

評価用マシンのシャットダウンについて開始指定時間から 6 時間すると自動的にマシンがシャットダウンします。作成したデータはプロコン決勝日まで残っていますが、念の為自分のマシンにコピーしてバックアップを取ってください。

指定時間の 6 時間までに余裕がある場合は、可能であれば自分でシャットダウンしてください。
左隅のウィンドウズボタンをクリックし、右上の電源ボタンから「シャットダウン」を選択してください。

18

付録 E

Asprova を使った結果の確認方法

生産スケジューラ Asprova を使用すると、結果をガントチャートなどで確認できます。また、これでどのようにプログラムを改良したら良いのか、検討することができます。

評価用マシンには Asprova がインストールされています。以下に評価用マシンでの確認方法を説明します。
1.

プログラムの出力ファイル result1A.csv ファイルを data.aru と同じフォルダに置きます。

2.

データフォルダの data.aru をダブルクリックすると、Asprova が起動し、自動的に result1A.csv を読み込み、以下のようになります。

縦軸は設備、横軸は時刻のガントチャートです。パンを焼く時間は 1 日に、時刻は以下のように変換されています。
02020/1/1 00:00:00

12020/1/2 00:00:00

22020/1/3 00:00:00…
バーの 1 つ 1 つはオーダです。オーダ内の文字列は、パンの種類、パンの個数、最早開始日時から経過した時刻(日数)、納期遅れ時刻(日数)です。納期遅れを起こすと文字の色が赤くなります。カーソルをあてると詳細情報がデータチップで表示されます。

スケジュール評価結果テーブルでは利益達成率、利益 P やスケジューリング制約違反の有無(合否)などが確認できます。

※

評価用マシンではなく、皆さんの Windows マシンに Asprova 体験版をインストールして確認することもできます。
以下のページから Asprova 会員登録を行なってください。
https://www.asprova.com/jp/usage_jp/applyasmember.html
ただし、体験版ではオーダ数は 100 件までしか実行できません。(つまり少量データでしか使えません)

19