H27年度 情報工学実験および演習２ 2015.4.30 MS(Ver.2)
ACMプログラミングコンテストを利用した実践的プログラミング （第一回）
本日分は，個人単位でプログラム開発を行い作った夫々のプログラムに関する解説「プログラム開発の基本戦略，高速化等の最適化戦略など工夫した点、感想」をレポートとして提出します．（国内予選を含む）2回目以降は チームをつくって問題を解きます．1回目と同様にプログラムの解説とともに，チーム内での自分の役割，貢献度を明記するとともに，チームプレイに関する考察をレポートとして提出します．
[実施形態] (4/30 個人戦)
3種類のプログラムを開発します．3時間目は1番目の問題をシステムになれるための練習課題として実施します．4時間目は2番目の問題．5時間目は3番目の問題を解きます．
(ステップ１) [プログラミング]
各問題には，入出力データの仕様とともに，サンプル入力とサンプル出力が提示されています．サンプル入力データを適当なテキストファイル(以下の例では, sample.txt)に保存し，作ったプログラム（本日の実験では，実行形式[バイナリファイル]は a.out に保存してください）に対してファイルからの標準入力として，以下のようにコマンド入力して実行した場合の標準出力がサンプル出力と一致するかを確認してください．一致しなければプログラムのデバッグを行ないます．
cat sample.txt | ./a.out
（最低限のチェックとして）サンプル入力に対して正しい結果が得られるようになったら，動作判定用の入力データをつかって動作検証を行ないます．なお，入力データ系列の終了条件を正しく判定しないと，プログラムは正常終了しません．cntl+cなどの強制終了コマンドで動作を止める必要のあるプログラムは正しく動くプログラムではありません．
（ステップ２）[動作検証]
動作検証では，皆さんのプログラム出力と正しい出力データとの差分(diff コマンドを使用)をとり，その出力を表示します．動作検証プログラムが「Passed」と表示した場合，少なくとも皆さんが使用している計算機上で動くプログラムが完成したと判断して結構です．完成した場合は，次の速度計測ステップに入ります．(/export/home2/scripts/ に pathが通っていることを確認して)以下の計測プログラムを実行してください．mondai_bangou の部分には(半角数字で)問題番号1~3の何れかを指定してください，皆さんが作ったプログラム（実行形式）は a.out にあることが前提です．
ex2acm mondai_bangou
プログラムに間違いがあると大量の差分データが表示されます．この場合，必要ならば cntl+c 等で実行を中断してもかまいません．逆に，この差分データをデバッグに使うことも不可能ではありません．(注：大量です！！)
（ステップ３）[性能解析]
速度計測に入る前に，再度プログラムをコンパイルしなおしてください．この際，コンパイラは gcc を使用し，コンパイルオプションは一切追加しないでください．以下のコマンドを入力し，実行速度を計測してください．実行速度は毎回変化します．12回計測を行い，測定したデータの最大，最小を除いた10回分のデータの平均を皆さんのプログラムの実行時間として記録し，投稿システムを使って開発したプログラムと自己申告の実行時間をシステムに登録してください．測定には
time ex2acm mondai_bangou
を使用します．実行結果は
ipc012:ex2acm[12] time ex2acm 1
Passed
4.796u 0.003s 0:04.82 99.3% 0+0k 0+0io 0pf+0w
のように表示されます．最初の数字（上記では 4.796）を皆さんのプログラムの実行時間と看做してください．単位は秒です．投稿システムに投稿する際の実行時間(Time)はミリ秒[ms]です（上の例では4796となります）
プログラム投稿システムのURL[1] は以下の通りです．学内からのみアクセスできます．
http://isv.fecs.eng.u-fukui.ac.jp/jikken/ex2acm/form.html
投稿システムをブラウザで開いたときの画面は以下の通りです．投稿時に使用するUIDは，皆さんのログインIDの下2桁と皆さんの名前のイニシャル姓名の順で入力してください．例えば ログインID i1389 姓：情報 名：太郎の場合，UIDは 89JT となります．入力する文字列は半角英数字のみにしてください．アップロードするファイルのファイル名も同様に半角英数字のみにしてください．問題番号を選択せずにアップロードすると sample の欄に投稿した結果が表示されます．
投稿した自己申告データは「自己申告」の欄に投稿時刻順で表示されます．「自己申告」のページには，
投稿時刻 UID 自己申告の実行時間(lap) 投稿したプログラムの名前
が時刻順で表示されます．最新情報を得るにはブラウザの「リロードボタン」を押してください．「仮ランキング」の欄には，自己申告情報を元に
1)実行時間の短い順
2)投稿時刻が早い順
の優先順位で自己申告ベースの仮ランキングが表示されます．また，仮ランキングにはUIDごとに１しかデータが表示されません．（注意）原則として，ここに示された時刻に投稿されたプログラムのみを「公式ランキング」決定時に使用します．なお，「コンパイル通過」，「コンパイルエラーのページ」には，投稿されたプログラムが公式ランキング決定用のサーバでコンパイルできたか否かの情報を表示しています．コンパイルできなかったプログラムは自動的に消去されます．
実際のコンテストとは異なり，「何回でもプログラムを登録して記録更新すること可能」です[2]．
「自己申告」のページは誰かがプログラムを登録する毎にサーバ上のデータが更新されます．それ以外のページは一定間隔でサーバ上のデータが更新されます．最新データを見るためにはブラウザの「リロード」を行なってください．
[以下は，指示があるまで作業を行なわないでください．]
（０）問題番号を選択せずに，次ページの練習問題のc言語のプログラムを
アップロードする練習を行なってください．動作検証時の問題番号は ４ を
入力してください．時間計測は不要です．時間の欄には１と入力してください．
（１）問題１（入力処理の練習用）を解いて，プログラムができたら
システムに投稿してください．
一回だけの計測データで登録してください．（時間計測の平均は不要）
他の人と相談してもかまいません．
（１）までは成績とは無関係です．
以下は，正規のルールで他人と相談せずに問題を解いてください．
（２）開始の合図で問題２を解いてください．（制限時間 XX分）
（３）開始の合図で問題３を解いてください．(制限時間 YY分)
問題１，問題２，問題３の問題自体，制限時間は別途指示します．なお，（２），（３）は開始後20分~30分経過後に，順にヒントを出していきます．（１）のプログラムは（２）、（３）の時間計測時の平均値計算に使えます。
[本日の提出物]
別途配布した自己申告用紙に必要事項を記入したものを提出してください．
この用紙の提出で 本日の出席とします．
[参考文献・資料]
・山口 文彦, 山口（繁富）利恵：「未来のコンピュータ好きを育てる: 3．国際大学対抗プログラミングコンテスト」，情報処理学会誌，Vol.50,No.10, pp.968-969, 2009.
・秋葉拓哉，岩田陽一，北川宜稔：「プログラミングコンテストチャレンジブック」，マイナビ，2012 (第2版第3刷)
・ACM ICPC OB-OG の会 http://acm-icpc.aitea.net/
・Observations on teamwork strategies in the ACM international collegiate programming contest, Saman Amirpour Amraii, ACM Crossroads, 2007
[練習問題]
三角形の面積を求める問題です．底辺Wと高さHがあたえられたときの三角形の面積を求めます．結果は小数点以下を切り捨てた整数で表現してください．
(注) ２１６＝６５５３６です．
[入力]
入力は複数のデータセットからなる． 各データセットは1行からなり，その行は空白で区切られた2つの整数 W, H からなる． Wは底辺，Hは高さであり単位は[m]である．
これらの整数は，0 ≦W ＜65536, 0 ≦H ＜65536, W≠Hを満たします．（本来はWやHが０の場合を含めるべきではありませんが，練習問題のために含めることにします．）
入力の終わりは，空白で区切られた3つのゼロからなる行によって示される．
[出力]
各データセットに対して面積[m2]を小数点以下を切り捨てた整数で表現してください．
Sample Input
10 20
3 5
32767 2
4 65535
5 0
9 7
0 5
54321 12345
65535 65535 65534
<<<<< 訂正
0 0
Sample Output
100
7
32767
131070
0
31
0
335296372
2147418112 2147385345 <<<<<
訂正
各問題が解けた人は、余った時間でレポート作成に取り掛かってください。