2016.09.29Scratch で始める小学生からのプログラミング
スクラッチで日本情報オリンピックのプログラミングに挑戦（予選問題導入編）
みなさま、こんにちは。今回は、スクラッチのプログラミングに関するネタとして、情報オリンピックを取り上げてみました。情報オリンピックは、国際組織があり、高校生以下を対象とした７つの国際科学オリンピックの一つです。
実際は、CやC++などを用いて問題を解くのですが、あえてスクラッチで解答を作ってみようということです。この情報オリンピックで求められている素養としては、アルゴリズムを考えて、効率の良い（処理時間が短く、メモリ使用量が少ない）プログラムを作るということです。アルゴリズムを設計するための高い数理的能力が求められています。
ここでアルゴリズムというのは、コンピュータにおいて解を導くための計算の手順を表現したものです。コンピュータ言語が何であれ、同じアルゴリズムを使えば、誰でも同じ解答が導けます。このアルゴリズム次第で、計算の公立の良し悪しが決まります。情報オリンピックではこのアルゴリズムをどう作るかを評価するということです。
2014年に行われた予選問題を題材に、やってみることにします。
問題1
https://www.ioi-jp.org/joi/2014/2015-yo/2015-yo-t1/2015-yo-t1.html
より
「JOI 君が住んでいる地域には水道会社が X 社と Y 社の 2 つある．2 つの会社の 1 ヶ月の水道料金は，1 ヶ月の水道の使用量に応じて次のように決まる．
• X 社： 1 リットル あたり A 円かかる．
• Y 社： 基本料金は B 円である．使用量が C リットル以下ならば，料金は基本料金 B 円のみがかかる．使用量が C リットルを超えると基本料金 B 円に加えて追加料金がかかる．追加料金は使用量が C リットルを 1 リットル超えるごとに D 円である．
JOI 君の家では 1 ヶ月の水道の使用量が P リットルである．
水道料金ができるだけ安くなるように水道会社を選ぶとき，JOI 君の家の 1 ヶ月の水道料金を求めよ．」
みなさま、どうやるとよいか分かりますでしょうか？問題1は、情報オリンピックの出題者的には、ウォーミングアップという位置づけらしく、すぐ解ける問題を出しているようです。
アルゴリズム
この問題は、問題文で記載されているX社、Y社の水道料金をそれぞれ計算し、計算した結果を比較して料金が小さい方を解答とするというのが素直な解き方だと思います。
X社の料金は1リットルあたりA円ですので次のようになります。
料金X ＝ A × P
Y社の料金は条件が設定されており、使用量PがCリットル以下であれば、基本料金B円、Cリットルよりも大きければ、基本料金に加え、超過した分にDをかけた値になります。そのため、次の式になります。
もし C よりも P が大きいならば、
料金Y ＝ B + ( D × ( P – C ) )
そうでなければ、（すなわち、PがCリットル以下ならば）
料金Y ＝ B
スクラッチでどうするか？
スクラッチで実現しようとした場合、実は手間がかかる部分があります。それがデータの入力部分です。情報オリンピックでは、入力はテキストであると定められており、入力のテキストが5つ用意されています。それぞれの解答が導けて初めて正解です。
入力仕様
入力は 5 行からなり，1 行に 1 つずつ整数が書かれている．
1 行目には X 社の 1 リットルあたりの料金 A が書かれている．
2 行目には Y 社の基本料金 B が書かれている．
3 行目には Y 社の料金が基本料金のみになる使用量の上限 C が書かれている．
4 行目には Y 社の 1 リットルあたりの追加料金 D が書かれている．
5 行目には JOI 君の家の 1 ヶ月の水道の使用量 P が書かれている．
書かれている整数 A, B, C, D, P はすべて 1 以上 10000 以下である．
上記の仕様を見ればおわかりですが、それぞれの行にA, B, C, D, P の値が順番に書かれているということです。これをどうやってスクラッチに取り込むか思案してみましたが、一つ方法がありました。リストを使う方法です。
リストを作成して、左側に表示されているリストの部分にマウスカーソルをあわせます。そして、右クリックをするとメニューが表示され、読み込みができるので、そこで読み込ませるテキストファイルを指定すると読み込んでくれます。
改行ごとに値として取ってくれるので、このまま使えそうです。
リストとは
さて、サラッとリストと言う言葉を使っていましたが、リストというのは、データを順番に並べたものです。コンピュータのデータ構造の代表的なものの一つです。リストでは、データに順番があり、取り出したいデータの順番を指定すると該当するデータを取得できます。今回の使用例では、1行ごとにデータが作られているので、行の順番にデータを保存したということです。順番が変わってしまうと意味が変わってしまうので、今回のような使い方ではリストである必要があります。
各社の水道料金の計算
各社の計算の部分は、それぞれ「新しいブロック」を使って作ると見通しが良いと思います。新しいブロックを作るときに、A, B, C, D, P のそれぞれの値を数値の引数として利用できるようにすると、一つのブロックで該当するデータの計算ができるようになります。
新しいブロックを作るときにオプションを指定し、一番上にある数値の引数を追加の部分をクリックすると、枠が現れます。その枠に名前として、A, B, C, D, Pを作ることで使用できるようになります。
そして、先程示したアルゴリズムに沿ってそれぞれの計算式を作ることで料金を求めることができます。求めた料金はそれぞれ、料金X、料金Yとしてデータに保存しておきます。計算結果を次に比べるためです。
水道料金を求める
ここまで来るとほぼ終りに近いのですが、水道料金を求めるブロックを作ります。アルゴリズムとしては、次のようになります。
X社の料金を求める
Y社の料金を求める
もし X社の料金がY社よりも小さいならば、
X社の料金を出力
そうでなければ、
Y社の料金を出力
スクラッチで書くと図のようになります。アルゴリズムで私が書いたのとほぼ同じですよね。そして、実際に入力データから回答を得るためには、水道料金のA, B, C, D, P の値をそれぞれ入力する必要があります。リストのデータを使ってこの部分を作ってあげれば良いことになります。スクラッチで書くと下記になります。
入力のリストを読み替えれば、違う答えを次々求めていくことができるはずです。
まとめ
今回は、情報オリンピックの問題を題材に、スクラッチのプログラミングをしてみました。このレベルの問題を高校生が解くのは想像つくのですが、どの程度年下の子がこれに対応できるのか？というのは興味があります。数学の知識としては、加減乗除、比較演算は理解する必要があります。それに加え、条件文の理解ということになります。どれだけ早くても小学校の高学年からでしょうか。CやC++で解くためには、データの入出処理などの理解度が進まないと難しいのですが、アルゴリズムに着眼するという趣旨であれば、スクラッチのレベルでもそれなりにできるのかと思います。（ただ、それなりに、と書いているのには理由があります。それは次回にでも）
これはまだ簡単な問題の部類ですので、違う問題も試してみようと思います。お楽しみに。
東京都文京区小石川で小学生、中学生、高校生を対象としたプログラミング＆ロボット教室を開校しています。コース概要のページで説明しております。創造性や協調性などこれからの時代に必要となる素養を育てるコースです。ご興味ありましたらぜひお問い合わせください。
お問い合わせはこちら！
]]>
