読者です 読者をやめる 読者になる 読者になる

LoL/LJL好きのエンジニアのブログ

技術的な話やら、最近はLoLやLJLの話など。

AOJ 2243: Step Step Evolution

はじめに

問題文概訳

日本のゲーム会社が、Step Step Evolution というゲームを開発した。 このゲームのプレイ方法はシンプルだ。 プレイヤーはダンス台に立ち、スクリーンに表示された矢印にしたがってパネルを踏む。

Step Step Evolution には8個の矢印がある。 上、右上、右、右下、下、左下、左、左上である。 矢印は画面の下から上に向かって出てくる。 画面の一番上に矢印が来たら、それに合わせて図で示したようなパネルを踏むのである。

このゲームでは、以下の条件に従わなければならない

  • プレーの開始時を除き、あなたは指示されたパネル以外のパネルを踏んではいけない。
  • パネルを踏んだら、その足はそのままで、次の矢印が来るまで離してはいけない。
  • 左足は今右足があるパネルよりも右のパネルを踏めない。 また、右足は今左足があるパネルよりも左のパネルは踏めない。

例えば、図2において、最初の図と2つ目の図は、条件を満たした状態だが、 最後の図だけ、3つ目の条件を満たしていない状態となる。

プレイの最初は、右足と左足はどこに置いてあってもよい。 また、右足と左足、どちらからステップをはじめてもよい。

このゲームの美しいプレイとして、「Natural footstep style」というプレイスタイルが有名である。 これは、右足と左足で交互にパネルを踏むスタイルである。 しかし、矢印の並びが複雑になってくると、このプレースタイルは難しくなる。

あなたの友達は、あなたのためにこのゲームの譜面(矢印がどのような順番で出てくるか示すもの)を作った。 あなたは、この譜面で何箇所「Natural footstep style」が崩れるかに興味があった。 つまり、最も最適なステップをした場合、同じ足で2回連続ステップを踏まなければいけない箇所は、 何箇所まで減らせるか、ということだ。

入力

入力はいくつかのデータセットを含む。 それぞれのデータセットは1行で、5以外の1から9までの数字の列である。 それぞれの数字が示す矢印の方向は図3の通りである。

数字は1個以上100000個以下入力される。 同じ数字が連続することはない。 すべての入力の終わりは # で示される。

出力

それぞれのデータセットに対して、Natural footstep style が崩れる回数を1行で出力せよ。

方針

  • 交互に踏める限り貪欲に交互に踏んでいって問題ない。条件3の制約のため無理な場合だけ同じ足を使う
  • 最初にスタートする足も重要。これは右足からスタートした場合と左足からスタートした場合両方試して最小値を取る
  • 実装は頑張る(コード量はそんなに多くならない)

実装

class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            char[] seq = br.readLine().toCharArray();
            if(seq[0] == '#') break;
            System.out.println(Math.min(check(seq, 0), check(seq, 1)));
        }
    }
    
    static int check(char[] seq, int foot){
        int[] pannel_on_foot = {0, 2};
        int cnt = 0;
        for(int i = 0; i < seq.length; i++){
            int pannel = ((int)(seq[i] - '0') - 1) % 3;
            if(foot == 0){
                // 踏み出す足が左足の場合
                // 右足よりも右には行けない
                if(pannel_on_foot[1] < pannel){
                    cnt++;
                    pannel_on_foot[1] = pannel;
                }else{
                    pannel_on_foot[0] = pannel;
                    foot = (foot + 1) % 2;
                }
            }else{
                // 右足の場合
                // 左足よりも右には行けない
                if(pannel < pannel_on_foot[0]){
                    cnt++;
                    pannel_on_foot[0] = pannel;
                }else{
                    pannel_on_foot[1] = pannel;
                    foot = (foot + 1) % 2;
                }
            }
        }
        return cnt;
    }
}