結果

問題 No.1924 3 color painting on a line
ユーザー 👑 tute7627tute7627
提出日時 2022-05-02 20:14:51
言語 Java21
(openjdk 21)
結果
RE  
実行時間 -
コード長 4,222 bytes
コンパイル時間 3,715 ms
コンパイル使用メモリ 75,988 KB
実行使用メモリ 58,196 KB
最終ジャッジ日時 2023-09-14 17:18:26
合計ジャッジ時間 13,739 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 126 ms
55,304 KB
testcase_01 AC 124 ms
55,444 KB
testcase_02 AC 123 ms
53,988 KB
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 AC 170 ms
57,044 KB
testcase_41 RE -
testcase_42 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

//from https://www.jianshu.com/p/c226b37b8e51

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Solution {
    static String st;
    static char[] ch;
    static char[][] chars;
    static int[][] pre,crt;
    static final int INF = (int)1e8,a = (int)'A';
    public static void main(String[] args) {
        chars = new char[6][7000];
        initCharArray();
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int tests = 1;
        for(int test=1;test<=tests;test++){
        	st = in.next();
            st = in.next();
            int len = st.length(),id = 0,index = 0;
            assert len <= 7000;
            st=st.replace('R','A');
            st=st.replace('G','C');
            ch = st.toCharArray();
            for(int i=1;i<len;i++){
                if(ch[i]!=ch[id]){
                    ch[++id] = ch[i];
                }
            }
            id++;
            pre = new int[6][1];
            for(int i=0;i<6;i++) pre[i][0] = INF;
            index = (int)ch[0]-a;
            pre[2*index][0] = pre[2*index+1][0] = 1;
            for(int i=1;i<id;i++){
                crt = new int[6][i+1];
                for(int l=0;l<6;l++) Arrays.fill(crt[l],INF);
                index = (int)ch[i] -a;
                for(int j=0;j<6;j++){
                    for(int k=0;k<i;k++){
                        if(pre[j][k]==INF) continue;
                        if(ch[i]==chars[j][k]){
                            crt[j][k] = Math.min(crt[j][k],pre[j][k]);
                        }else{
                            if(k>=1){
                                if(ch[i]==chars[j][k-1]){
                                    crt[j][k-1] = Math.min(crt[j][k-1],pre[j][k]);
                                    if(k-1==0) {
                                        crt[2 * index][0] = Math.min(crt[2 * index][0], pre[j][k]);
                                        crt[2 * index + 1][0] = Math.min(crt[2 * index + 1][0], pre[j][k]);
                                    }
                                }else{
                                    if(ch[i]==chars[j][k+1]) crt[j][k+1] = Math.min(crt[j][k+1],pre[j][k]+1);
                                    if(k>1){
                                        if(ch[i]==chars[j][k-2]) {
                                            crt[j][k-2] = Math.min(crt[j][k-2],pre[j][k]);
                                            if(k-2==0){
                                                crt[2*index][0] = Math.min(crt[2*index][0],pre[j][k]);
                                                crt[2*index+1][0] = Math.min(crt[2*index+1][0],pre[j][k]);
                                            }
                                        }
                                    }
                                }
                            }else{
                                if(ch[i]==chars[j][k+1]) crt[j][k+1] = Math.min(crt[j][k+1],pre[j][k]+1);
                            }
                        }
                    }
                }
                pre = crt;
            }
            int ans = Integer.MAX_VALUE,lth = pre[0].length;
            for(int i=0;i<6;i++){
                for(int j=0;j<lth;j++){
                    if(pre[i][j]==INF) continue;
                    ans = Math.min(ans,pre[i][j]);
                }
            }
            System.out.printf("%d\n",ans);
        }
        in.close();
    }
    static void initCharArray(){
        int len = chars[0].length;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(i==j) continue;
                for(int k=0;k<3;k++){
                    if(i==k) continue;
                    if(j==k) continue;
                    int id = 0;
                    if(j<k) id = 2*i;
                    else id = 2*i+1;
                    chars[id][0] = (char)(a+i);
                    chars[id][1] = (char)(a+j);
                    chars[id][2] = (char)(a+k);
                }
            }
        }
        for(int i=0;i<6;i++){
            for(int j=3;j<len;j++){
                chars[i][j] = chars[i][j-3];
            }
        }
    }
}
0