プログラミングは芸術だ!

web系エンジニアの備忘録 「プログラミングは芸術」を座右の銘として日々勉強中 最近Androidもやってます

AOJ2001 Amida, the City of Miracle【競技プログラミング】

AOJ2001 Amida, the City of Miracle

Amida, the City of Miracle | Aizu Online Judge

あみだくじのシミュレーションをしよう!

という問題です。タイトルが秀逸。
日本語ならいいけど英語の問題で面白いけど全く意味のない前置きを一生懸命訳してしまったときって苛立つよね☆

解法
シミュレーション問題なので、やるだけなのだが、
ポイントしては"横線をどういう構造体で持つか"という部分かと思います

import java.util.Scanner;

public class AOJ2001 {
    void run(){
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int a = sc.nextInt();
            if(n+m+a == 0) break;
            boolean horizon[][][] = new boolean[1001][n+1][n+1];
            int hMax = 0;
            for(int i = 0; i<m; i++){
                int h = sc.nextInt();
                int p = sc.nextInt();
                int q = sc.nextInt();
                horizon[h][p][q] = true;
                hMax = Math.max(hMax, h);
            }
            int now = a;
            for(int i=hMax; 0<i; i--){
                if(1 <= now-1 && horizon[i][now-1][now]){
                    now--;
                }
                else if(now+1 < n+1 && horizon[i][now][now+1]){
                    now++;
                }
                else{
                    //nowのまま
                }
            }
            System.out.println(now);
        }
    }
    public static void main(String[] args) {
        new AOJ2001().run();
        //new Main().run();
    }
}

横線をどう持つかという前置きをしましたが、一番わかり易い形で持っています。

これはjavaだとnewを使ってメモリを確保するような変数やクラスの大域変数だと
初期化されるからできるのかなってかんじです。
これを毎回初期化しないといけないとすると1000*1000*1000のループになるので厳しい。

別解について

今回は横線があるかどうかさえ分かればいいので、setなどのcontainsができる構造体に、
h,p,qの3要素を配列か文字列の塊にして入れておいて、チェックするのが良さそう。
試してはないです。すみません。

あと今回入力の範囲を間違えてArrayIndexOutOfBoundsExceptionで落としてしまったので、
問題文はちゃんと読もう!