スクラッチで日本情報オリンピックのプログラミングに挑戦（文字列処理編）

みなさま、こんにちは。今回は、前回の内容に引き続き、情報オリンピックの問題をスクラッチでやってみました。前回の記事では簡単な問題を取り上げていたので、プログラムで計算しなくてもすぐに答えが出せるレベルの内容でしたが、今回の問題は、プログラムを使わないと回答を導くのに時間がかかってしまう内容になっています。

 

問題２(2015年12月実施予選より)

https://www.ioi-jp.org/joi/2014/2015-yo/2015-yo-t2/2015-yo-t2.html

問題

「JOI 君は友達 1 から友達 N までの N 人の友達を招いてクリスマスパーティーを行った．クリスマスパーティーも盛り上がってきたところで，友達と一緒に次のようなゲームを行うことになった．

最初に JOI 君は N 人の友達の中から 1 人を選ぶ．以降はその友達をターゲットと呼ぶことにする．

JOI 君は，ターゲットとして選んだ友達に，その人がターゲットであることをこっそり伝える．ターゲット以外の友達は，誰がターゲットかを知ることはできない．

ターゲット以外の友達はそれぞれ，ターゲットが誰かを予想して，その人の名前を紙に記入する．ターゲットは自分自身の名前を紙に記入する．

すべての人の記入が終わった後，JOI 君はターゲットの名前を発表する．

予想が当たった人は 1 点を得る．なお，ターゲットは自分自身の名前を紙に記入しているので，必ず 1 点を得る．予想が外れた人には得点は与えられない．

それに加えて，予想が外れた人の人数を X 人としたとき，ターゲットは追加で X 点を得る．

JOI 君たちはこのゲームを M 回行った．それぞれの友達に対して，M 回のゲームにおける合計得点を求めよ．」

入力

入力は 3 + M 行からなる．

1 行目には，友達の人数 N (3 ≦ N ≦ 100) が書かれている．

2 行目には，JOI 君たちが行ったゲームの回数 M (3 ≦ M ≦ 100) が書かれている．

3 行目には，M 個の整数 A1, A2, ..., AM が空白を区切りとして書かれている．これは，i 回目 (1 ≦ i ≦ M) のゲームのターゲットが友達 Ai (1 ≦ Ai ≦ N) であることを表す．

続く M 行のうちの i 行目 (1 ≦ i ≦ M) には，N 個の整数 Bi,1, Bi,2, ..., Bi,N が空白を区切りとして書かれている．これは，i 回目のゲームにおいて友達 j (1 ≦ j ≦ N) が友達 Bi,j (1 ≦ Bi,j ≦ N) の名前を紙に記入したことを表す．ターゲットは自分自身の名前を紙に記入するので，j = Ai のとき，常に Bi,j = j である．

問題の整理

この問題ですが、問題の意味を理解するのが最初の山場かもしれません。ターゲットになった人を当てるというゲームですが、次の条件があります。

• ターゲットは、JOI君（ゲームとは関係のない人）が、（予想できないように）無作為に決めてその人に伝える。（同じ人がターゲットになる可能性もある）


• ターゲットとなった人は、自分自身の名前を書く


• それ以外の人は、予想して書く


• 予想が当たれば１点、外れた人は０点。（そのため、ターゲットとなった人は必ず１点は取れる）


• ターゲットとなった人は、予想が外れた人数分の点数の得点を更に得ることができる

入力となるデータとしては、次のとおりになっています。

• ゲームの参加人数N


• ゲームの回数M


• それぞれの回のターゲットの番号


• それぞれのゲームにおいてそれぞれの人が予測したターゲットの番号

この手の処理をするときは大まかに次のような流れになります。

1. 入力データを読み込む


2. 入力データに従って、それぞれのゲームを施行し、得点を計算する


3. 結果を書き出す

結果を書き出す部分はスクラッチでは、リストにデータを書き込む以上のことができないので、次以降は、１，２に関してそれぞれ書いていきます。

入力を読み込む

入力を読み込んでそれぞれのデータを取得する部分が、実は一番スクラッチで向いていない不得意な部分です。もとの問題のように、CやC++などの言語を使う場合は、文字列を処理するためのライブラリが存在しています。そのため、ライブラリを使うことで取得したい文字を抜き出すのは比較的簡単です。ところが、スクラッチは文字列を処理するための機能が殆どありません。そのため、効率が少々悪い方法で文字を拾っていくしか方法がないのです。具体的にどのようにするかを次に述べます。

スクラッチで使うことができる、文字列処理のブロックは次の3つです。

• 文字列をくっつけるブロック（join）
  
  
  
  • 翻訳された日本語版のほうは訳が悪く、「(hello) と (world)」 と書かれたブロックになります。
  
  
  
  


• 文字列の中で、前から何番目の文字かを示すブロック
  
  
  
  • 「(1) 番目(world)の文字」
  
  
  
  


• 文字列の長さ
  
  
  
  • 「(world) の長さ」
  
  
  
  

そのため、入力された文字を１文字ずつ読み出し、それぞれが数字か空白かを判定して、値を取り出す処理を書くことになります。簡単に書くと次のようになります。

 

数字の文字を記録する変数tmpを用意する

   「文字列の長さ」の数だけ繰り返す

  　　もし、今読んでいる文字が空白だったら

　　　　　　　tmpの中の数字をデータとして保存

  　　　　　tmpの文字をクリアする（なくす）

  　　そうでなければ（数字だったら）

  　　　　　tmpの中の文字と数字の文字を合わせる

   　　　　次の文字を見る

これは、いわゆる文字列処理の典型的な方法なのですが、１文字ずつ読み込んでその文字がどういう文字かで処理を変えるというものです。

実際に、ターゲットのデータを読み出す処理はスクラッチで書くと次のようになります。

それぞれのゲームを施行し、得点を計算

　それぞれのゲームを施行する場合は、先程述べた条件の中で、次の２つの内容に留意する必要があります。

• 予想が当たれば１点、外れた人は０点。（そのため、ターゲットとなった人は必ず１点は取れる）


• ターゲットとなった人は、予想が外れた人数分の点数の得点を更に得ることができる

予想が当たるということは、ターゲットの番号と同じ番号であることを意味合します。そのため、次のような処理になります。

当たった人を数える変数（正解数）を用意する

　もし、ターゲット番号 = 人iが予想した番号　ならば

　　　i の得点を１増やす

　　正解数を１増やす

すべての計算が終わった後、ターゲットの得点に、(N – 正解数)を足す

実際に得点計算をする部分は次のようになります。文字を読み込んだ直後に、それぞれの人の予想があっているかどうかをその都度判定し、結果を格納しています。これは極力繰り返しの回数を減らすために、そのようにしています。

まとめ

　実際にスクラッチで実行させてみると、たしかに計算できることは確認できるのですが、入力として用意されているデータを読み込み、動かす場合、スクラッチの文字列処理のスピードが遅く、たいへん時間がかかる処理になってしまっています。入力データを１文字ずつ読み込まないといけないのが処理のボトルネックになっています。CやC++でも本質的な部分は大きく変わらないものの、ビジュアルで見せているスクラッチと比較して、一つ一つの処理が大変軽いため、Cなどのプログラミング言語を使ったほうが処理時間は断然早いです。そのため、スクラッチでこの手の問題をやるのは無理があると思います。ただ、基礎的な考え方を理解する上で、ビジュアルプログラミングで試せるというのは、それはそれで参考になるのではないかと思い、書いてみました。ご感想をお聞かせいただければ幸いです。

---

東京都文京区小石川で小学生、中学生、高校生を対象としたプログラミング＆ロボット教室を開校しています。コース概要のページで説明しております。創造性や協調性などこれからの時代に必要となる素養を育てるコースです。ご興味ありましたらぜひお問い合わせください。

お問い合わせはこちら！

問い合わせをする

]]>