#13045 (Java) No.154 市バス

• 問題: No.154 市バス
• ユーザー: ぴろず
• 提出日時: 2015-02-17 23:52:53
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 302 ms / 2,000 ms
• コード長: 5,412 bytes
• コンパイル時間: 2,125 ms
• コンパイル使用メモリ: 86,320 KB
• 実行使用メモリ: 45,276 KB
• 最終ジャッジ日時: 2024-10-13 06:29:57
• 合計ジャッジ時間: 4,816 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 1
other	AC * 8

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
package no154;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
public class Main {
    public static void main(String[] args) {
        IO io = new IO();
        int t = io.nextInt();
        for(int tt=0;tt<t;tt++) {
            String s = io.next();
            io.println(isValid(s) ? "possible" : "impossible");
        }
        io.flush();
    }
    public static boolean isValid(String s) {
        //明らかにおかしい場合を弾く
        int w = 0;
        int g = 0;
        int r = 0;
        int n = s.length();
        for(int i=0;i<n;i++) {
            if (s.charAt(i) == 'R') {
                r++;
            }else if(s.charAt(i) == 'G') {
                g++;
            }else{
                w++;
            }
        }
        if (r != g || w < r || g == 0 && w > 0) {
            return false;
        }
        //最も右のGに注目する。その右側にはRしかないはず。GとRを1つずつ取る。そのGの左側から、次のG(もしくは先頭
            )までのWを取るか、Wがない場合Wを1つ取る。
        //これを繰り返す。
        String[] t = (s+"$").split("G"); //末尾にGがある場合を対策
//      System.out.println(Arrays.toString(t));
        int m = t.length;
        int[] wnum = new int[m];
        int[] rnum = new int[m];
        for(int i=0;i<m;i++) {
            for(int j=0;j<t[i].length();j++) {
                if (t[i].charAt(j) == 'W') {
                    wnum[i]++;
                }else if(t[i].charAt(j) == 'R') {
                    rnum[i]++;
                }
            }
        }
        int rsum = 0;
        int wr = m-1;
        for(int i=m-1;i>=1;i--) {
            if (wnum[i] > 0) {
                return false;
            }
            rsum += rnum[i];
            if (rsum <= 0) {
                return false;
            }
            rsum--;
            wr = Math.min(wr,i-2);
            if (wnum[i-1] > 0) {
                wnum[i-1] = 0;
            }else{
                boolean flag = false;
                for(;wr>=0;wr--) {
                    if (wnum[wr] > 0) {
                        flag = true;
                        wnum[wr]--;
                        break;
                    }
                }
                if (!flag) {
                    return false;
                }
            }
        }
        return true;
    }
}
class IO extends PrintWriter {
    private final InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    public IO() { this(System.in);}
    public IO(InputStream source) { super(System.out); this.in = source;}
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private static boolean isNewLine(int c) { return c == '\n' || c == '\r';}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    private void skipNewLine() { while(hasNextByte() && isNewLine(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
    public boolean hasNextLine() { skipNewLine(); return hasNextByte();}
    public String next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public char[] nextCharArray(int len) {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        char[] s = new char[len];
        int i = 0;
        int b = readByte();
        while(isPrintableChar(b)) {
            if (i == len) {
                throw new InputMismatchException();
            }
            s[i++] = (char) b;
            b = readByte();
        }
        return s;
    }
    public String nextLine() {
        if (!hasNextLine()) {
            throw new NoSuchElementException();
        }
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(!isNewLine(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
            throw new NumberFormatException();
        }
        return (int) nl;
    }
    public char nextChar() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        return (char) readByte();
    }
    public double nextDouble() { return Double.parseDouble(next());}
    public int[] arrayInt(int n) { int[] a = new int[n]; for(int i=0;i<n;i++) a[i] = nextInt(); return a;}
    public long[] arrayLong(int n) { long[] a = new long[n]; for(int i=0;i<n;i++) a[i] = nextLong(); return a;}
    public double[] arrayDouble(int n) { double[] a = new double[n]; for(int i=0;i<n;i++) a[i] = nextDouble(); return a;}
    public void arrayInt(int[]... a) {for(int i=0;i<a[0].length;i++) for(int j=0;j<a.length;j++) a[j][i] = nextInt();}
    public int[][] matrixInt(int n,int m) { int[][] a = new int[n][]; for(int i=0;i<n;i++) a[i] = arrayInt(m); return a;}
    public char[][] charMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;}
    public void close() {
        super.close();
        try {
            in.close();
        } catch (IOException e) {}
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX