結果

問題 No.1924 3 color painting on a line
ユーザー tute7627
提出日時 2022-05-02 20:14:51
言語 Java
(openjdk 23)
結果
RE  
実行時間 -
コード長 4,222 bytes
コンパイル時間 3,946 ms
コンパイル使用メモリ 79,472 KB
実行使用メモリ 42,492 KB
最終ジャッジ日時 2024-07-02 00:26:17
合計ジャッジ時間 13,301 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 RE * 39
権限があれば一括ダウンロードができます

ソースコード

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