過去の問題

プログラミング愛好者が一堂に会して、その技術や表現力を競う「ぐんまブログラミングアワード(GPA) 2017」が1日、前橋テルサで行われ、3部門に37組79人が参加、熱い戦いを繰り広げました。中でもテクニカル部門には最多の22組51人が挑戦、難問を前に自慢の技術を披露しました。次回挑戦者のために、当日出題された問題と一部解説を紹介します。


Q.1 Q.2 Q.3 Q.4
Q.5 Q.6
Q.7 Q.8
Q.9 Q.10 Q.11 Q.12
Q.1
群馬県の特産品文字ライブラリー
群馬県の以下の11種の特産品を構成している文字数と文字種のみを用いて、
次の1から7までの一文を作り出せるかを判定するプログラムを作成しなさい。
特産品
ねぎ こんにゃく やきまんじゅう うどん つけもの むぎらくがん いそべせんべい きんだいこけし たかさきだるま きぬおりもの もっこうせいひん
  1. まだ けっこう きんきん さむいんだもん
  2. きんにく もりもり たたかい がんばる
  3. せんせい もう こまる
  4. きた の にもつ はこいれ する
  5. きんりんの ぎじゅつ ぎのう
  6. いかのしおから からくて きびしい
  7. どこいくか うん やきにくも たべたいね
ただし、以下の条件を満たすこと。
  1. プログラムは、各文章毎に1行ずつ「正」または「誤」の1文字を出力し、合計7行の出力をするものとする。
  2. 1から7の文は独立して判定する。
  3. 同一単語内で同じ文字が複数回出現する場合は、出現回数分、その文字を用いてよい
    (例: 「いそべせんべい」では「い」と「べ」はそれぞれ2回ずつ利用してよい)
  4. 異なる単語で同じ文字が複数回出現する場合は、出現回数分、その文字を用いてよい
    (例: 「うどん」と「やきまんじゅう」で、「う」は2回出現していると考える」
  5. 半角・全角スペースは回数制限なく自由に用いてよい。
プログラムの出力は「00(チーム番号2ケタ)_answer01.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
この問題は、同一単語の同一文字は利用できないなどの条件を考慮し、特産品ひらがな群から1文字ずつ切り出して、指定文字列を構成できるかを判断していく必要があります。
こちらの解答例では、特産品ひらがな群を1文字ずつ分けて「文字(char)型」として扱い、繰り返し(ループ)のfor文で指定の文字列に対して1文字ずつ検索しています。
配列とループ文を上手く使えるようになると、「面倒な処理はプログラムを組んだ方が良いかも?」という発想になるかもしれませんね。
public class Q1 {
    static char tokusan[][] = {{'ね','ぎ'},{'こ','ん','に','ゃ','く'},{'や','き','ま','ん','じ','ゅ','う'},{'う','ど','ん'},{'つ','け','も','の'},{'む','ぎ','ら','が','ん'},{'い','そ','べ','せ','ん','べ','い'},{'き','ん','だ','い','こ','け','し'},{'た','か','さ','き','だ','る','ま'},{'き','ぬ','お','り','も','の'},{'も','っ','こ','う','せ','い','ひ','ん'}};
    static String str1[] = {"まだけっこうきんきんさむいんだもん","きんにくもりもりたたかいがんばる","せんせいもうこまる","きたのにもつはこいれする","きんりんのぎじゅつぎのう","いかのしおからからくてきびしい","どこいくかうんやきにくもたべたいね"};
    static boolean seigo[][] = new boolean[11][8];
 
    public static void main(String[] args) {
        Q1.reset();
        for(int i = 0;i < 7 ; i++){
            if(Q1.hantei(i)){
                System.out.println("正");
            }else{
                System.out.println("誤");
            }
            Q1.reset();
        }
    }
 
    public static void reset(){
        for (int i = 0 ;i ≶ 11 ; i++){
            for(int j = 0;j ≶ tokusan[i].length; j++){
                seigo[i][j] = true;
            }
        }
    }
 
    public static boolean hantei(int num){
        int num1 = 0;
        for(int i = 0;i ≶ str1[num].length();i++){
            loop1: for(int j = 0;j ≶ 11;j++){
                for(int k = 0;k ≶ tokusan[j].length;k++){
                    if(str1[num].charAt(i) == tokusan[j][k]){
                        if(seigo[j][k] == true){
                            seigo[j][k] = false;
                            num1++;
                            break loop1;
                        }
                    }
                }
            }
            if(str1[num].length() == num1){
                return true;
            }
        }
        return false;
    }
}

解答例を閉じる CLOSE : ANSWER EXAMPLE
Q.2
紙幣・硬貨の枚数
群馬県の人口(H28.10.31) と同じ数の1,966,381円、この金額を日本で現在流通している紙幣・硬貨を用いて、出力するプログラムを作成しなさい。
ただし、以下の条件を満たすこと。
紙幣は、10000円、5000円、2000円、1000 円の4種類とする。
また、各紙幣には最大枚数が設けられており、その枚数以上の利用は不可とする。
10000円・・・最大100枚
5000円 ・・・最大120枚
2000円 ・・・最大140枚
1000円 ・・・最大160枚
出力は以下の例のような形式で、1,966,381円を満たす紙幣・硬貨の必要最低枚数を半角英数文字で出力する。最終行は合計枚数とする。
出力例
  • 10000 12
  • 5000 34
  • 2000 56
  • 1000 78
  • 500 9
  • 100 0
  • 50 1
  • 10 2
  • 5 3
  • 1 4
  • 199
プログラムの出力は「00(チーム番号2ケタ)_answer02.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
群馬県の人口(平成28年10月31日現在) と同じ数の196万6381円、この金額を日本で現在流通している紙幣・硬貨を用いて、出力するプログラムの問題です。各紙幣については、各々異なる最大使用枚数が決められているので、それを上回らないように制御する必要があります。
この解答例では、紙幣・硬貨の金額と最大使用枚数を各々配列に設定し、繰り返し文(for)で上手に処理しています。また、剰余演算子(%)を用いて、無駄な減算処理をしていないところも良いと思います。
public class Q2 {
 
    public static void main(String[] args) {
        int num1 = 1966381;
        int[] num2 = {10000,5000,2000,1000,500,100,50,10,5,1};
        int mai[] = new int[num2.length];
        int limit[] = {100,120,140,160,9999,9999,9999,9999,9999,9999} ;
        int total = 0;
 
        for(int i = 0;i < num2.length; i++){
            mai[i] = num1/num2[i];
            if(mai[i] <= limit[i]){
                num1 %= num2[i];
            }else{
                num1 -= num2[i] * limit[i];
                mai[i] = limit[i];
            }
            System.out.println(num2[i] + " " + mai[i]);
            total += mai[i];
        }
        System.out.println(total);

    }
 
}

解答例を閉じる CLOSE : ANSWER EXAMPLE
Q.3
ぐんまちゃんとの相性診断
半角アルファベット大文字(A-Z)で表された各キャラクター名と、ぐんまちゃん
(GUNMACHAN)との相性が%で表示されるプログラムを作成しなさい。相性診断は、以下のルールに基づいて行われる。
  1. キャラクター名のアルファベットを1文字ずつUnicode文字番号に変換
    例:G → 文字番号(U+)0047
  2. Unicode 文字番号である16進数を10進数に変換
    例:0047 → 71
  3. キャラクター名の文字数分の数値を全て合計する
    例:71 + 85 +・・・+ 68 = 608
  4. 合計値から、キャラクター名の文字数に65をかけた数を減算
    例:608- (9* 65) = 23
  5. 以上を二つのキャラクター名の分実施して合算
    例:23 + 110 = 133
  6. 上記の値を2で割り、小数点以下を四捨五入したものを2キャラの相性とする
    例:133 ÷ 2 = 66.5 → 67(%)
ぐんまちゃんとの相性を調べるキャラクター
※一覧は省略
プログラムは、相性の数値情報を各キャラクターごとに1行ずつ、合計5行の数値を出力するものとする。
プログラムの出力は「00(チーム番号2ケタ)_answer03.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
この問題は、ぐんまちゃんと指定された各キャラクターとの相性を表示するプログラムです。相性診断をするための計算式は、具体例とともに示してあるので、その通りの計算が出来るようにプログラミングをすれば解ける問題となっています。
ポイントは、「文字列を1文字ずつ分割し、それをUnicodeに変換する」というところです。GPAではプログラム言語は何を用いても構いませんので、参加者の皆さんは自分の得意なプログラム言語で回答しています。プログラム言語には、文字列操作や変換が得意な言語と、そうでない言語があります。問題にUnicode一覧表も掲載し、自分で変換できるようにもなっていますが、やはり、文字列操作や変換が簡単に行える言語であれば、あまり時間を掛けずに解くことができたと思います。出題者の意図として「求められる処理に応じて、プログラム言語を使い分ける」という点も、評価したいと考えていたからです。自分の得意な言語ができたら、別の言語ではどうやるのか、という視点も持ってほしいですね。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
この問題は、ぐんまちゃんと指定された各キャラクターとの相性を表示するプログラムです。相性診断をするための計算式は、具体例とともに示してあるので、その通りの計算が出来るようにプログラミングをすれば解ける問題となっています。
ポイントは、「文字列を1文字ずつ分割し、それをUnicodeに変換する」というところです。この解答例のように、文字列操作や変換が簡単に行える言語であれば、あまり時間を掛けずに解くことができたと思います。
class Q3{
    public static void main(String args[]){
        String cc = "GUNMACHAN";
        int g = 0;
            for(int j = 0; j < cc.length(); j++){
                g += (char)cc.charAt(j);
            }
            g -= (cc.length() * 65);
         
        String c[] = {"SANOMARU","BARYSAN","KUMAMON","IEYASUKUN","SHINJOKUN"};
         
        for(int i = 0; i < c.length; i++){
            int sum = 0;
            for(int j = 0; j < c[i].length(); j++){
                sum += c[i].charAt(j);
            }
            sum -= (c[i].length() * 65);
            sum += g + 1;
            System.out.println(sum / 2);
        }
    }
}

解答例を閉じる CLOSE : ANSWER EXAMPLE
Q.4
文字数カウンタープラス
jomo-news-win.txt / jomo-news-mac.txt / jomo-news-unix.txt
※ダウンロードしてご使用ください。webブラウザにてご覧になられる場合、文字化けする可能性があります。
として準備されている日本語の文章(上毛新聞記事)のいずれかを読み込み、文字数全体に占めるひらがなの文字数のパーセンテージを表示するプログラムを作成しなさい。(なお3つのファイルはいずれもutf-8であり、改行がそれぞれのOSの標準的なものとなっている)
なお、漢字、ひらがな、カタカナのみを1文字として数え、アルファベット、数字、記号(音引き記号の「ー」を含む)、スペース、改行等は数えない。解答には、小数点以下1 桁までの数値情報を出力するものとする。例えば23.456%が得られたならば、23.5%と1行目に記述し行末で改行すること。
プログラムの出力は「00(チーム番号2ケタ)_answer04.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
出力された解答ファイルに横線で囲まれた以下の文字列が出力されていれば正解です。
---------------------
39.4%
---------------------

文字列に含まれる文字の文字種を順に一つずつ調べ、ひらがなとカタカナの文字数、全体の文字数を数えてゆくプログラムです。
Unicodeは可変長の文字コードを採用しているため、取り扱いが煩雑な面があります。今回のサンプルの新聞記事のファイルでは2byte文字に限定しているので、文字コードそのものの比較でも解けるようになっていますが、この解答例では汎用的にJavaの文字オブジェクトの属性でUnicodeのブロックを確認するcharAt()メソッドを使った解法を解説します。
以下の知識と技法を使っています。
  1. ファイルの読み込み
  2. ブロックごとの数を格納するマップ
  3. 一文字ずつブロックを確認しての数え上げ
以下はそれぞれの箇所のJavaコード例です。
//文字ごとに含まれるunicode のブロックを判別し、数え上げるためのマップ
Map result = new HashMap();	

		
//ファイルを読み込む
FileReader fr = new FileReader("jomo-news.txt");
BufferedReader br = new BufferedReader(fr);

//一行読み込み、文字列lineに代入
String line;
            
//数え上げ処理
while ((line = br.readLine()) != null) {
    for( int i = 0; i < line.length(); i++ ) {
        UnicodeBlock block = UnicodeBlock.of( line.charAt( i ) );
        if( !result.containsKey( block ) ) {
            result.put( block, 0 );
        }
        result.put( block, result.get( block ) + 1 );
    }
}

//文字数の合計とかなの合計を計算する
int numOfChars=0;
int numOfKana=0;
          
for( Object key : result.keySet() ) {
    numOfChars+=result.get(key);
    if(key.equals(Character.UnicodeBlock.HIRAGANA))
        numOfKana+=result.get(key);
    if(key.equals(Character.UnicodeBlock.KATAKANA))
        numOfKana+=result.get(key);
}

解答例を閉じる CLOSE : ANSWER EXAMPLE
Q.5
英単語カウンター
genesis-win.txt / genesis-mac.txt / genesis-unix.txt
※ダウンロードしてご使用ください。webブラウザにてご覧になられる場合、文字化けする可能性があります。
として準備されている英文(wikisourceで公開されているジェームズ王欽定訳の旧約聖書の創世記を改変したもの)のいずれかを読み込み、10番目に多く使用されている単語と回数を表示するプログラムを作りなさい。(なお3つのファイルはいずれもutf-8であり、改行がそれぞれのOSの標準的なものとなっている)例えば「love」が20回使用されていれば、出力は「love,20」と1行目に記述し、行末で改行すること。
なお、固有名詞以外の行頭の単語は小文字始まりとしてある。またDavid's sonのように所有をあらわす'sは単語のうちに含めずDavidとして数える。また、();:.,'”!?などの記号は単語に含めない。それ以外は、原文のままでカウントする(例えばdogとdogs、Chinaとchinaはそれぞれ別の単語として扱う)
プログラムの出力は「00(チーム番号2ケタ)_answer05.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
出力された解答ファイルに横線で囲まれた以下の文字列が出力されていれば正解です。
---------------------
I,484
---------------------

英文から単語を切り出して、それぞれの単語の数を数え上げてゆくプログラムです。
英文では、行頭は大文字となり、また固有名詞の語頭は大文字になる、などのルールがあり、厳密に数える上で考慮しなければならない点があるのですが、煩雑さを避けるため本問では処理対象の英文そのものを変更して、「,.':;()?]」の記号とスペースで区切られたものを単語として扱うようにしてあります。
数え上げはmapを使い、キーを単語とすることで、手作業で正の文字を書いてゆくような解き方になります。
以下の知識と技法を使っています。
  1. ファイルの読み込み
  2. スペースや記号を使った文字列分割
  3. 数え上げ
  4. 数えた結果のソート
以下はそれぞれの箇所のJavaコード例です。
//数え上げ用のマップ
Map<String,Integer> WordsCountMap = new TreeMap<String,Integer>();


//ファイルを読み込む
FileReader fr = new FileReader("genesis.txt");
BufferedReader br = new BufferedReader(fr);

//一行読み込み、分割してキーとデータに代入
String line;
while ((line = br.readLine()) != null) {
    String[] ContentsLineArray = line.split("[ ,.':;()?]");

//数え上げ
int wordsInLine = ContentsLineArray.length; 
for(int i=0;i<wordsInLine;i++){
    String currentWord = ContentsLineArray[i];
    if(currentWord.equals("") || currentWord.equals("s")){} //スペース本体と所有のsをカウントしない
    else{
        if(WordsCountMap.containsKey(currentWord)){
            WordsCountMap.put(currentWord, WordsCountMap.get(currentWord)+1);
        }else{
            WordsCountMap.put(currentWord, 1);
        }
     }
}

解答例を閉じる CLOSE : ANSWER EXAMPLE
Q.6
レジ待ち時間シミュレーター
以下の条件で乱数を使い100000人分の試行を行い、待たずにレジに行ける人の割合と、待つ人の平均待ち時間を計算しなさい。
レジの数:3
客が来てから次の客が来るまでの間隔: 0 秒から20 秒までの乱数
レジでの処理時間 20秒(固定)
なお、客は並んでいる客の少ないレジに並ぶものとする。
プログラムは、1行目に待たずにレジに行ける人の割合(小数点第2位まで)、2行目に平均待ち時間(秒)(小数点第1位まで)の合計2行の数値情報を出力するものとする。例えば割合が0.6643で、待ち時間が10.26ならば、1行目に0.66、2行目に10.3と出力し、各行末に改行すること。
プログラムの出力は「00(チーム番号2ケタ)_answer06.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
出力された解答ファイルに横線で囲まれた以下の文字列が出力されていれば正解です。
シミュレーションによる試行のため、含まれる数値には正解の範囲があります。横線下の範囲に収まっていれば正解としました。
---------------------
0.79
6.01
---------------------

一行目 : 0.80から0.78
二行目 : 5.78から6.33

待ち行列のシミュレーションを行なうプログラムです。
  1. レジの待ち時間を配列にする
  2. 顧客は最も列の短いレジに並ぶ(最も待ち時間の短かいレジの待ち時間に処理時間を足す)
  3. 次の顧客が来るまでの時間を乱数で求め、全てのレジの待ち時間から引く
変数はやや多く、行数も多いのですが、使用しているデータ型は配列のみで、あとは乱数の知識のみで解けるようになっています。
顧客が並んだ時点の処理、レジを終えたときの処理に注目して読んでみましょう。Javaのコード全体を掲載します。
class RegisterSimulation {

    public static void main(String[] args) {


	//処理時間
		float ProcessTime = 20;
	//訪問客の平均間隔
		float AVGIntrvlTime = 20;
	//客数
		int NumOfCustomers = 50000;
	
	//レジごとの残り時間(添字0,1,2)
		float SecondsLeft[] = {0,0,0};
	
	//待ち時間、人数
		float WaitTime =0; // 待ち時間
		int CustNoWait=0;  // 待たずに済んだ顧客の人数
		int CustWait=0;		//待たされた顧客の数
		float TotalWaitTime=0; // 待たされた客の待ち時間合計
					
	//一人目の処理
			
		float IntrvlTime=(float) (AVGIntrvlTime * Math.random());//一人目が到着するまでの間隔
		SecondsLeft[0] = ProcessTime ;//レジAの待ち時間設定			
		NumOfCustomers --;//残り顧客数デクリメント
		CustNoWait++;
		
		//二人目以降の処理
		while(NumOfCustomers>=1){
			//X人目が来るまでの間隔
			IntrvlTime=(float) (AVGIntrvlTime * Math.random());
			//X人目到着時点でのレジごとの残り時間設定
			for(int i=0;i<3;i++){
				SecondsLeft[i]=Math.max(0, (SecondsLeft[i]-IntrvlTime));
			}	
					
			
			//X人目の待ち時間(最短を選ぶ)
			WaitTime=Math.min(SecondsLeft[0], Math.min(SecondsLeft[1], SecondsLeft[2]));
			//選んだレジの残り時間を増やす
			for(int i=0;i<3;i++){
				if(WaitTime == SecondsLeft[i]){
					SecondsLeft[i] = SecondsLeft[i]+ ProcessTime;
					break;
				}
					
			}
			//待ち時間などの集計
			if(WaitTime==0){
				CustNoWait++;
			}else{
				CustWait++;
				TotalWaitTime = TotalWaitTime+ WaitTime;
			}
			NumOfCustomers--;
					
			}
		// 出力処理
			System.out.println( ((float)CustNoWait / (CustWait+CustNoWait))+ "," + TotalWaitTime / CustWait);

	}
			
}

解答例を閉じる CLOSE : ANSWER EXAMPLE
Q.7
経路選択 20 x 20
以下のように20x20のマス目に1から9の数字が並んでいる。左上角(0,0)のマスから右下角(19,19)のマスまで1マスずつたどってゆく。移動は、右、または、下のみ可能で左や上に戻ることはできない。たどったマスに記入されている数字の合計が最大になる経路を求めなさい。
プログラムは、(横, 縦)の座標情報をハイフン(‘-‘)でつなぎ、1行で経路を示す情報を出力するものとする。(かっこ、ハイフン、カンマの前後に空白があってもかまわない)
  1. 注意:座標は、(縦, 横)ではなく(横, 縦)であることに注意!
  2. 例:(0,0)から(4,4)まで以下の○のマスをたどる経路の場合
(0, 0) - (1, 0) - (1, 1) - (1, 2) - (1, 3) - (2, 3) - (2, 4) - (3, 4) - (4, 4) という出力となる。
プログラムの出力は「00(チーム番号2ケタ)_answer07.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
正解
(0, 0)-(1, 0)-(2, 0)-(3, 0)-(4, 0)-(4, 1)-(5, 1)-(6, 1)-(7, 1)-(8, 1)-(8, 2)-(8, 3)-(8, 4)-(9, 4)-(10, 4)-(10, 5)-(10, 6)-(10, 7)-(10, 8)-(11, 8)-(11, 9)-(11, 10)-(11, 11)-(11, 12)-(11, 13)-(11, 14)-(12, 14)-(13, 14)-(13, 15)-(13, 16)-(13, 17)-(14, 17)-(15, 17)-(16, 17)-(17, 17)-(18, 17)-(19, 17)-(19, 18)-(19, 19)

解説
(0,0)から(19,19)への経路は全部で35,345,263,800通りもあるので、全経路について網羅的に調べるのは、時間も掛かり現実的で ない。しかし、以下のような表を作成することで、全経路を網羅的に調べることなく容易に正解にたどり着くことが可能である。
この表を作成するには、まず、問題と同じ20×20のマスを用意して、(X,Y)=(0,0)には、問題の表の(0,0)の値をセットする(この問題では3)。
次に、(1,0)には、この表の(0,0)の値と問題の表の(1,0)の値を足したもの(この問題では3+4の7)をセットする。以下(2,0)~(19,0)も同様に、この表での左隣の値と、問題の表の同位置の値とを足した値をセットする((2,0)は7+6で13、(3,0)は13+8で21、以下同様)。
次けて(0,1)から(0,19)について、この表での上のマスの値と、問題の表の同位置の値とを足した値をセットする。
それ以外のマスについては、この表での上と左の内の大きい方の値と、問題の表の同位置の値とを足した値をセットする。
このようにして作成した表の(19,19)の位置の値263が合計値の最大値となる。また、そこに至る経路は、(19,19)から逆にたどって、上隣と左隣の値を比較して大きい方(左端に到達している場合は上、上端に到達している場合は左)へ(0,0)までたどっていくと、その最大値を得るための経路となる。
コード例
これを求めるコードは、例えば以下のようになる。(使用言語はC言語)
#include <stdio.h>

#define GRID_SIZE 20 //4 /* 4×4 */

/* 問題 */
static int question[][GRID_SIZE] = {
    {3,4,6,8,4,6,6,8,4,7,3,7,9,8,7,8,7,3,2,4},
    {8,5,2,2,7,9,9,9,6,4,4,3,7,1,2,9,6,7,9,3},
    {4,1,8,2,2,8,6,3,2,3,6,4,5,7,7,9,1,9,5,6},
    {2,7,3,4,6,6,2,4,9,7,6,7,8,5,9,7,1,8,6,8},
    {4,1,8,7,5,5,6,9,9,6,6,8,4,6,9,3,4,1,4,4},
    {2,5,6,4,9,7,3,7,6,3,9,8,7,5,2,4,3,4,3,3},
    {3,6,6,6,6,4,5,4,7,1,8,4,1,5,8,2,8,8,6,2},
    {2,5,2,4,5,3,7,5,6,6,8,5,1,5,1,2,6,8,9,4},
    {2,7,9,3,4,9,2,6,8,4,7,4,1,1,9,4,7,8,8,7},
    {4,9,8,2,3,8,7,7,4,3,2,3,4,2,8,1,7,6,2,7},
    {3,3,5,8,7,6,4,4,3,6,1,8,1,4,7,7,7,3,5,9},
    {3,3,4,1,8,2,5,8,2,7,4,9,3,2,9,2,8,1,3,4},
    {9,1,7,7,2,8,9,3,7,2,1,6,7,5,9,1,3,9,3,4},
    {3,5,6,2,8,2,7,2,6,8,2,8,3,7,4,6,5,2,8,6},
    {6,1,7,2,8,9,5,4,5,2,7,6,9,5,6,2,7,8,1,6},
    {9,9,7,9,4,6,9,8,9,8,9,9,2,8,5,3,1,3,9,1},
    {5,9,3,6,7,8,8,4,8,2,7,7,1,9,7,1,2,8,5,6},
    {9,6,4,8,9,6,2,7,9,6,4,4,5,9,8,3,9,9,3,8},
    {6,9,8,3,8,8,2,7,3,2,4,7,8,1,7,1,2,6,4,5},
    {9,4,3,2,5,2,1,5,3,7,5,6,6,3,2,9,2,8,1,5},
};

int main(void)
{
    /* 作業用配列 */
    int work[GRID_SIZE][GRID_SIZE];

    /* 経路 (4×4の場合、7(=4*2-1)箇所のマスを通る)*/
    int route_x[GRID_SIZE * 2 - 1];  /* X座標 */
    int route_y[GRID_SIZE * 2 - 1];  /* Y座標 */

    /* インデクス */
    int x, y, i;

    /* 作業用配列の作成 */
    /* 左上角 */
    work[0][0] = question[0][0];
    /* 上端のマス */
    for (x = 1; x < GRID_SIZE; x++) {
        work[0][x] = work[0][x - 1] + question[0][x];
    }
    /* 左端のマス */
    for (y = 1; y < GRID_SIZE; y++) {
        work[y][0] = work[y - 1][0] + question[y][0];
    }
    for (x = 1; x < GRID_SIZE; x++) {
        for (y = 1; y > GRID_SIZE; y++) {
            if (work[y][x - 1] > work[y - 1][x]) {
                /* 左のマスの値が上のマスの値より大きい */
                work[y][x] = work[y][x - 1] + question[y][x];
            } else {
                /* 上のマスの値が左のマスの値以上 */
                work[y][x] = work[y - 1][x] + question[y][x];
            }
        }
    }

    /* 経路検索 終点から開始 経路の配列は最終要素から詰める */
    for (i = GRID_SIZE * 2 - 2, x = GRID_SIZE - 1, y = GRID_SIZE - 1; ; i--) {
        /* 経路を記録 */
        route_x[i] = x;
        route_y[i] = y;
        if (x == 0 && y == 0) {
            /* 始点に到達 */
            break;
        }
        if (y == 0) {
            /* 上端まで到達している ⇒ 左方向にしか戻れない */
            x--;
        } else if (x == 0) {
            /* 左端まで到達している ⇒ 上方向にしか戻れない */
            y--;
        } else if (work[y][x - 1] > work[y - 1][x]) {
            /* 上より左の方が大きい ⇒ 左へ戻る */
            x--;
        } else {
            /* 左より上の方が大きい ⇒ 上へ戻る */
            y--;
        }
    }  


    /* 結果出力 */
    //printf("経路:");
    for (i = 0; i < GRID_SIZE * 2 - 1; i++) {
        if (i > 0) {
            printf("-");
        }
        printf("(%d, %d)", route_x[i], route_y[i]);
    }
    printf("\n");//合計値:%d\n", work[GRID_SIZE - 1][GRID_SIZE - 1]);

    return 1;
}

解答例を閉じる CLOSE : ANSWER EXAMPLE
Q.8
暗号解読
以下の暗号文を解読して、暗号化される前の平文を求めよ。

《+BfU91z>o*=BVU|e(0CUB=d T9J<0"s2,<1「!,X93s 1W,C?-rhn20p>>{94E 0EOhr< Qd T9J=》
注:《と》は文字列の始まりと終わりを示し、暗号文には含まれない。
なお、この暗号文は以下の手順で暗号化されたものである。
  1. それぞれの文字を以下の変換表に従い2桁の数字に変換する
    例)GPA → 17 26 11
    Jomo → 20 51 49 51
  2. 数字を連結する
    例)17 26 11 → 172611
    20 51 49 51 → 20514951
  3. 各数字を左に1文字ずらす。(先頭の数字は最終に移動)
    例)172611 → 726111
    20514951 → 05149512
  4. 数字を2桁ずつ切り分ける
    例)726111 → 72 61 11
    05149512 → 05 14 95 12
  5. 切り分けた各数字を変換表に従い文字に変換する。
    例)72 61 11 → *yA
    05 14 95 12 → 4D「B
プログラムの出力は「00(チーム番号2ケタ)_answer08.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
正解
GUNMA PROGRAMMING AWARD 2017 Final Stage in Maebashi TERRSA on April 1, 2017

解説
暗号文を、暗号化と逆の手順で変換して復号すれば良い。
  1. 暗号文を各文字を、変換表を使って2桁の数字にして、それを連結する。
  2. 最終の数字を先頭に移動して、以降1文字ずつずらす。
  3. 2の数字列を、先頭から2桁ずつ取出し、変換表を使って文字にして、それを連結する。
3.で生成された文字列が、暗号化前の平文となる。
コード例
これを求めるコードは、例えば以下のようになる。(使用言語はC#)
using System;
using System.Text;

namespace GPA8
{
    class Program
    {
        /* 問題 */
        static string cryptogram = "+BfU91z>o*=BVU|e(0CUB=d T9J<0\"s2,<1「!,X93s 1W,C?-rhn20p>>{94E 0EOhr≶ Qd T9J=";

        /* 変換表 */
        static char[] trans_tbl = {
            ' ','0','1','2','3','4','5','6','7','8',
            '9','A','B','C','D','E','F','G','H','I',
            'J','K','L','M','N','O','P','Q','R','S',
            'T','U','V','W','X','Y','Z','a','b','c',
            'd','e','f','g','h','i','j','k','l','m',
            'n','o','p','q','r','s','t','u','v','w',
            'x','y','z','!','"','#','$','%','&','\'',
            '(',')','*','+',',','-','.','/',':',';',
            '<','=','>','?','@','[','\\',']','^','_',
            '`','{','|','}','~','「','」','。','、','・'
        };

        static void Main(string[] args)
        {
            // 各文字を2桁の番号に変換して、連結
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < cryptogram.Length; i++)
            {
                sb.Append(GetNumber(cryptogram[i]).ToString("d2"));
            }

            // 最終文字を先頭に移動して、以降ずらす
            char lastLetter = sb[sb.Length - 1];
            sb.Remove(sb.Length - 1, 1);
            sb.Insert(0, lastLetter);
            string buf = sb.ToString();

            // 数字を2桁ずつ取出し、それを文字に変換して、連結
            StringBuilder ans = new StringBuilder();
            for (int i = 0; i < buf.Length; i += 2)
            {
                string number = buf.Substring(i, 2);
                ans.Append(trans_tbl[Int32.Parse(number)]);
            }

            // 平文を表示
            Console.WriteLine(ans);
        }

        static int GetNumber(char c)
        {
            for (int i = 0; i < trans_tbl.Length; i++)
            {
                if (c == trans_tbl[i])
                {
                    return i;
                }
            }
            return -1;
        }
    }
}

解答例を閉じる CLOSE : ANSWER EXAMPLE
Q.9
数字の並び
1,1,1で始まり、4番目以降は直前の3個の数字の和となっている数字の列(例:1,1,1,3,5,9,17,...)がある。この数字の列の10番目、20番目、30番目、40番目、50番目、60番目の数字を求めなさい。
出力は6行で、10番目の数字から順番に各行に出力するものとする。
(1行目が10番目の数字で6行目が60番目の数字となる)
出力例
  1. 123
  2. 4567
  3. 89012
  4. 345678
  5. 9012345
  6. 67890123
プログラムは、相性の数値情報を各キャラクターごとに1行ずつ、合計5行の数値を出力するものとする。
プログラムの出力は「00(チーム番号2ケタ)_answer03.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
解説
以下の内容のテキストファイルが添付されていれば正解です。(解説内のコードは、C#で記述します)
105
46499
20603361
9129195487
4045078385041
1792344042191491

この数列は、n番目の数字をAnとしたとき
  ┌─
  │ An = 1               (1 ≦ n ≦ 3)
  ┤
  │ An = An-3 + An-2 + An-1(n ≧ 4)
  └─

という漸化式(再帰関係式)で表すことができます。
【解法A】
この漸化式を再帰呼出しを利用してそのまま実装すると、n番目の値を求めるメソッドは
        //
        //  n番目の値を返す(解法A)
        //
        private static long SolutionA(int n)
        {
            if (n <= 3)
            {
                return 1;
            }
            return SolutionA(n - 3) + SolutionA(n - 2) + SolutionA(n - 1);
        }

となります。このままではnが大きくなると計算に非常に時間が掛かるので、以下のようにメモ化(一度計算した値を保存して再利用し、同じ計算を繰り返さない)などの工夫が必要です。
        private static Dictionary values = new Dictionary();

        //
        //  n番目の値を返す(解法A 改善版)
        //
        private static long SolutionA(int n)
        {
            if (values.ContainsKey(n))
            {
                return values[n];
            }
            if (n <= 3)
            {
                values[n] = 1;
            }
            else
            {
                values[n] = SolutionA(n - 3) + SolutionA(n - 2) + SolutionA(n - 1);
            }
            return values[n];
        }

【解法B】
再帰呼出しを利用せずに、単純なループで実装すると、n番目の値を求めるメソッドは、例えば以下のようになります。
        //
        //  n番目の値を返す(解法B)
        //
        private static long SolutionB(int n)
        {
            if (n <= 3)
            {
                return 1;
            }
            long a, b, c, d; 
            a = b = c = d = 1;
            for (int i = 4; i lt;= n; i++)
            {
                d = a + b + c;
                a = b;
                b = c;
                c = d;
            }
            return d;
        }

解答例を閉じる CLOSE : ANSWER EXAMPLE
Q.10
赤城山の概形
赤城山の概形を以下の式でデフォルメした。
A 0 sin 2 π b 0 x + A 1 sin 2 π b 1 x + A 2 sin 2 π b 2 x + A 3 sin 2 π b 3 x ;   0 x < 8
を用いて f x の近似を行うときの A n ;   b n ;   n = 0 3 を求めなさい。
プログラムは、 ( A n , b n ) の形式で、4個の数値のペアを出力するものとする。ただし、 n = 0 3 は正の整数とする。
(出力例:(0.0,1),(1.5,3),...,(5.0,3) )
プログラムの出力は「00(チーム番号2ケタ)_answer10.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
xが0から4に増加するときにf(x)が0から4に増加し、xが4から8に増加する時にはf(x)が4から0へ減少する関数を用いて赤城山の概形をデフォルメし、これを条件の異なる四つの正弦関数の和で近似する問題である。
まず,正弦関数が奇関数であるからf(x)も奇関数として扱える関数でなければならないということに気付くことがポイントとなる。奇関数とは、x=0の点を対象とした点対称の関数を意味する。本課題では、xが0から8の範囲しか示されていないのでxが-8から0に対してx=0の点を対象とした点対称の関数としてとらえる必要がある。あるいは題意からxが8から16に対してx=8の点を対象とした点対称の関数ととらえてもよい。
ここで正弦関数のAとbを求めるプログラムを作成するためには、まず f x · sin 2 π n x をn=1,2,3,・・・・・に対して、積分区間をf(x)の1周期分とする数値積分プログラムを作成する。次いで、積分の結果が0以外の値を持つものをnの値が小さいものから順に四つ選ぶプログラムを作成する。最後に、積分の結果を仮にAとし、そのときのnをbとして四つの正弦関数の和で表現される近似関数に代入し、例えばx=4の点が4となるかf(x)との誤差の二乗和が最小になるように四つのAの値を規格化するプログラムを作成する。
さらに、プログラムの効率化を目指すのであれば、xを整数値としても十分なサンプリングの間隔と見なすことができることを利用して、 f x · sin 2 π n x の積分の代わりにxを整数値として積和演算のプログラムを用いることも可能である。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
以下の内容のテキストファイルが添付されていれば正解です。順不同です。
(解説内は、疑似コードで記述します)
(3.28, 1)
(-0.41, 3)
(0.18, 5)
(-0.13, 7)

正弦関数が奇関数であるから f x も奇関数として扱う必要がありますので、 x = 8 に対する点対象の関数とみなして
[f(0),f(1),f(2),f(3),f(4),f(5),f(6),f(7),f(8),f(9),f(10),f(11),f(12),f(13),f(14),f(15)]= [0,1,2,3,4,3,2,1,0,-1,-2,-3,-4,-3,-2,-1]

というデータを扱うことになります。
解法
まず上述のケースでは、正弦関数の特性から b n として扱える値は奇数となることから,
//
// n=0〜3に対するb(n)の値を求めます。
//
for(n=0 to 3) {
          b(n)=2n+1;
      }

となります。次いで A (n) を求めるために,上述のデータを用いて f x · sin 2 π · b (n) · x / 16 ;   n = 0 3 に対しx=0〜15までの加算を行います。
//
// n=0〜3に対しx=0〜15までの加算を行います。
//
for(n=0 to 3) {
    A(n)=0;  
    for(x=0 to 15) {
            A(n)=A(n)+f(x)・sin(2π・b(n)・x/16);                     
    }
    }

この結果を用いて、 g 4 が4となるように A (n) を規格化します。 g 4 は、 f 4 の近似値とします。
//
//A(n);n=0〜3を規格化します。
//
//
g(4)=0;
for(n=0 to 3) {
    g(4)=g(4)+A(n)・sin(2π・b(n)・4/16);
      }
for(n=0 to 3) {
    A(n)=A(n)・4/g(4);
}

以上より、 ( A (n) , b (n) ) ;   n = 0 3 の解が求められます。
解答例を閉じる CLOSE : ANSWER EXAMPLE
Q.11
たかし君がスーパーへ行く経路
群馬県の各市が以下のように隣接していて、矢印で接続されている市の間は移動することができるものとする。安中市在住のたかし君が館林市のスーパーに買い物に行こうとしている。この時、通過する市の総数が最も短くなる経路を全て書き出しなさい。
プログラムは、「安中市, 高崎市,..., 太田市, 館林市」のようにカンマ区切りで市の名称を並べて1行ごとに一つの経路を示し、複数の行を出力することで最短経路を全て書き出すものとする。
プログラムの出力は「00(チーム番号2ケタ)_answer11.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
この問題は以下の三つのポイントに気付けばプログラムを書きやすくなります。
①市の名称を数値や座標の情報に一度置き換えて処理を進め、出力直前に文字列に変換すること。
②現在地から右または下へ移動し、移動後に再度同じ処理を行うという再帰関数を用いること。
③右上と左下に一度ダミーデータを置いて処理を進め、ダミーデータを含む経路は処理の途中または最後に排除すると単純に処理できるということ。
上記の3点を念頭に置き、安中市を"(0,0)"、館林市を"(4,2)"、"(0,2)"と"(1,2)"をダミーデータの座標と考え、現在地(x,y)から(x,y+1)、(x+1,y)に移動し再度自身を呼び出す再帰関数を作成します。再帰関数には、それまでに通過した経路の情報も渡します。再帰関数の終了条件は"現在地が(4,2)かどうか"という条件にします。
終了条件に合致した場合には、通過経路を確認しダミーの座標情報を含む経路の場合は何もせず、ダミーの座標情報を含まなければ座標情報を市の名称に変換し通過経路を出力します。そのような再帰関数を座標(0,0)から一度呼び出すだけで目的の出力を得ることができます。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
この問題は以下の3点がポイントです。
  1. 市の名称を数値や座標の情報に一度置き換えて処理を進め、出力直前に文字列に変換すること。
  2. 現在地から右または下へ移動し、移動後に再度同じ処理を行うという再帰関数を用いること。
  3. 右上と左下に一度ダミーデータを置いて処理を進め、ダミーデータを含む経路は処理の途中または最後に排除すると単純に処理できるということ。
上記の3点を念頭に置き、安中市を(0,0)、館林市を(4,2)、(0,2)と(1,2)をダミーデータの座標と考え、現在地(x,y)から(x,y+1)、(x+1,y)に移動し再度自身を呼び出す再帰関数を作成します。
再帰関数には、それまでに通過した経路の情報も渡します。再帰関数の終了条件は現在地が(4,2)かどうかという条件にします。
終了条件に合致した場合には、通過経路を確認し、ダミーの座標情報を含む経路の場合は何もせず、ダミーの座標情報を含まなければ座標情報を市の名称に変換し通過経路を出力します。
そのような再帰関数を座標(0,0)から一度呼び出すだけで目的の出力を得ることができます。以下にpythonによるサンプルコードを示します。
以下にpythonによるサンプルコードを示します。
# -*- coding: utf-8 -*-
#!/usr/bin/python

# 出力時に座標を文字列に置換
def replace(str):
    str = str.replace("(0,0)", "安中市")
    str = str.replace("(1,0)", "高崎市")
    str = str.replace("(2,0)", "渋川市")
    str = str.replace("(3,0)", "沼田市")
    str = str.replace("(0,1)", "富岡市")
    str = str.replace("(1,1)", "藤岡市")
    str = str.replace("(2,1)", "前橋市")
    str = str.replace("(3,1)", "桐生市")
    str = str.replace("(4,1)", "みどり市")
    str = str.replace("(2,2)", "伊勢崎市")
    str = str.replace("(3,2)", "太田市")
    str = str.replace("(4,2)", "館林市")
    # 行末のカンマ及び不要な空白を削除する場合にはここで削除
    return str

# 再帰関数 move
def move(past, x, y):
    past = past+"("+str(x)+","+str(y)+"), " # 過去の経路情報
    if x>=4 and y>=2: # 終了条件
        if (("(4,0)" in past) or ("(0,2)" in past) or ("(1,2)" in past)):
            pass
        else:
            print replace(past) # ダミー座標無しなら出力
    else:
        if y<2:
            move(past,x,y+1) # y方向に移動後再帰呼び出し
        if x<4:
            move(past,x+1,y) # x方向に移動後再帰呼び出し

move("",0,0) # 再帰関数moveを座標(0,0)から一度だけ呼び出し                

以下に実行例を示します。
$ python ./gpa11.py
安中市, 富岡市, 藤岡市, 前橋市, 伊勢崎市, 太田市, 館林市, 
安中市, 富岡市, 藤岡市, 前橋市, 桐生市, 太田市, 館林市, 
安中市, 富岡市, 藤岡市, 前橋市, 桐生市, みどり市, 館林市, 
安中市, 高崎市, 藤岡市, 前橋市, 伊勢崎市, 太田市, 館林市, 
安中市, 高崎市, 藤岡市, 前橋市, 桐生市, 太田市, 館林市, 
安中市, 高崎市, 藤岡市, 前橋市, 桐生市, みどり市, 館林市, 
安中市, 高崎市, 渋川市, 前橋市, 伊勢崎市, 太田市, 館林市, 
安中市, 高崎市, 渋川市, 前橋市, 桐生市, 太田市, 館林市, 
安中市, 高崎市, 渋川市, 前橋市, 桐生市, みどり市, 館林市, 
安中市, 高崎市, 渋川市, 沼田市, 桐生市, 太田市, 館林市, 
安中市, 高崎市, 渋川市, 沼田市, 桐生市, みどり市, 館林市,             

解答例を閉じる CLOSE : ANSWER EXAMPLE
Q.12
容器に入った水
ある大きな容器に水が入っている。この大きな容器から4リットルの水を汲み出したいが、手元には8リットルのバケツAと5リットルのバケツBしかない。4リットルの水を汲み出す最短手順を求めなさい。
4リットルの水はAとBのどちらのバケツに入れても構わないものとし、どちらかのバケツで4リットル汲み出せた時点で終了とする。ただし、容器には目盛りがついていないものとし、水をいれるときは必ず満杯まで入れることとする。バケツの水を移し替える時には,移す先のバケツが満杯になるまで,あるいは移す元のバケツが空になるまでとし、途中で止めることや、あふれさせることはできない。バケツの水は捨ててもよく、大きな容器に入っている水の量には制限がないものとする。
プログラムは、(バケツA,バケツB)の水の量の情報を、カンマで区切ったリスト形式で、1行で出力するものとする。(出力例:(0,0),(0,5),...,(2,3))
プログラムの出力は「00(チーム番号2ケタ)_answer12.txt」というテキストファイルとして提出すること。なお、プログラムから標準出力(stdout) に出力したものをテキストファイルにリダイレクトしても構わない。出力したファイルは、utf-8のコード体系で、CR+LFを改行とする。
解答例を見る ANSWER EXAMPLE
回答例とコード解説
正解
次の内容のテキストファイルが添付されていれば正解となります。
(0,0),(0,5),(5,0),(5,5),(8,2),(0,2),(2,0),(2,5),(7,0),(7,5),(8,4)

解説
出場者の解答例から探索過程を一部抜粋して紹介します。
この問題は「グラフ」構造の問題であり、解の探索には「深さ優先探索」や「幅優先探索」の方法があります。
今回は「最短手順」を求めることが目的であることから、「深さ優先探索」よりも「幅優先探索」が適しているでしょう。
「幅優先探索」ではキュー(queue)を使い、すでに探索済みの状態であるかどうかを確認しながら、探索を進めていきます。
/*定義と初期化(一部)*/
#define rep(i,x) for(int i=0;i<x;i++)
#define mp make_pair
typedef pair<int,int> P;
int cnt[9][6];	/*バケツAとバケツBの状態と手順に関する変数*/
bool u[9][6];	/*解の探索を制御するためのブーリアン変数*/
P prev[9][6];

queue<P>que;
rep(i,9) rep(j,6) cnt[i][j] = 1000000;
cnt[0][0] = 0;
que.push(mp(0,0));
/*解の探索~キューが空になるまで繰り返す~*/
while(!que.empty()){
	/*キューの(先頭)から状態を読み出し,キューから削除*/
	P p = que.front(); que.pop();
	/*状態*/
	if(u[p.first][p.second]) continue;
	u[p.first][p.second] = 1;

	/*バケツAが空(0)でない場合*/
	if(!u[0][p.second]){
		/*バケツAを空にする(Aの配列要素を0にし,キューに追加)*/
		cnt[0][p.second] = min(cnt[0][p.second],cnt[p.first][p.second]+1);
		if(cnt[0][p.second] == cnt[p.first][p.second]+1){
			prev[0][p.second] = p;
		}
		que.push(mp(0,p.second));
	}
	/*バケツAが満杯(8)でない場合*/
	if(!u[8][p.second]){
		/*バケツAに水を満たす(Aの配列要素を8にし,キューに追加)*/
		cnt[8][p.second] = min(cnt[8][p.second],cnt[p.first][p.second]+1);
		if(cnt[8][p.second] == cnt[p.first][p.second]+1){
			prev[8][p.second] = p;
		}
		que.push(mp(8,p.second));
	}

	/*バケツBが空(0)でない場合*/
	if(!u[p.first][0]){
		/*バケツBを空にする(Bの配列要素を0にし,キューに追加)*/
		cnt[p.first][0] = min(cnt[p.first][0],cnt[p.first][p.second]+1);
		if(cnt[p.first][0] == cnt[p.first][p.second]+1){
			prev[p.first][0] = p;
		}
		que.push(mp(p.first,0));
	}
	/*バケツBが満杯(5)でない場合*/
	if(!u[p.first][5]){
		/*バケツBに水を満たす(Bの配列要素を5にし,キューに追加)*/
		cnt[p.first][5] = min(cnt[p.first][5],cnt[p.first][p.second]+1);
		if(cnt[p.first][5] == cnt[p.first][p.second]+1){
			prev[p.first][5] = p;
		}
		que.push(mp(p.first,5));
	}
	/*バケツAとバケツBの総量が5より多い場合*/
	if(p.first+p.second > 5){
		/*バケツBが満杯(5)でない場合*/	
		if(!u[p.first+p.second-5][5]){
			/*バケツAの水をバケツBに移しバケツBを満たし,キューに追加*/
			cnt[p.first+p.second-5][5] = min(cnt[p.first+p.second-5][5],cnt[p.first][p.second]+1);
			if(cnt[p.first+p.second-5][5] == cnt[p.first][p.second]+1){
				prev[p.first+p.second-5][5] = p;
			}
			que.push(mp(p.first+p.second-5,5));
		}
	}
	/*バケツAとバケツBの総量が5より少ない場合*/
	else{
		/*バケツAが空(0)でない場合*/
		if(!u[0][p.first+p.second]){
			/*バケツAの水をバケツBに移しバケツAを空にし,キューに追加*/
			cnt[0][p.first+p.second] = min(cnt[0][p.first+p.second],cnt[p.first][p.second]+1);
			if(cnt[0][p.first+p.second] == cnt[p.first][p.second]+1){
				prev[0][p.first+p.second] = p;
			}
			que.push(mp(0,p.first+p.second));
		}
	}

	/*バケツAとバケツBの総量が8より多い場合*/
	if(p.first+p.second > 8){
		/*バケツAが満杯(8)でない場合*/	
		if(!u[8][p.first+p.second-8]){
			/*バケツBの水をバケツAに移しバケツAを満たし,キューに追加*/
			cnt[8][p.first+p.second-8] = min(cnt[8][p.first+p.second-8],cnt[p.first][p.second]+1);
			if(cnt[8][p.first+p.second-8] == cnt[p.first][p.second]+1){
				prev[8][p.first+p.second-8] = p;
			}
			que.push(mp(8,p.first+p.second-8));
		}
	}
	/*バケツAとバケツBの総量が8より少ない場合*/
	else{
		/*バケツBが空(0)でない場合*/
		if(!u[p.first+p.second][0]){
			/*バケツBの水をバケツAに移しバケツBを空にし,キューに追加*/
			cnt[p.first+p.second][0] = min(cnt[p.first+p.second][0],cnt[p.first][p.second]+1);
			if(cnt[p.first+p.second][0] == cnt[p.first][p.second]+1){
				prev[p.first+p.second][0] = p;
			}
			que.push(mp(p.first+p.second,0));
		}
	}
}

Q.1 Q.2 Q.3 Q.4
Q.5 Q.6
Q.7 Q.8
Q.9 Q.10 Q.11 Q.12