natsuumeのblog

プログラミングの話とか趣味の話を書くかも

AtCoder Begginer Contest 088 振り返り

元々就活のコーディングテストの練習にはじめたAtCoderですが、何だかんだ普通に面白いので就活の息抜きに用事がない日のコンテストで解けそうなのは参加するようにしてます。

研究で使うプログラムではあまり複雑な処理しない上にほとんど計算量とか気にせずに動けばいいや的な実装ばかりしていて、どうしてもこういう効率とかを求めるようなプログラムは書かないのでその辺の練習も兼ねてます。
やっぱり普段書かないプログラムは書けなくなっていくので、こういうちょっと複雑なのも多少は書いてやり方忘れないようにしたいですね。

あとAtCoderJobsとかいうのがそのうち始まるという話なので、それまでに最低限まともなrate(最低緑以上)までは上げておきたいところ。

AtCoder Begginer Contest 088

A - Infinite Coins

N円をA枚の1円硬貨と無限枚の500円硬貨で払えるかどうかなので単純に%500するだけ。
ここは問題なく解けた。

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        System.out.println((n % 500) <= a ? "Yes" : "No");
    }
}

B - Card Game for Two

N枚のカードから交互にその時点の最大点のカードを取っていくので差分を取るだけ。
ここもさすがに余裕。
可算するか減算するかにboolean変数1個作って判定してるけど、普通にarray.length-1-iを%2したほうが手っ取り早かった気も。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for(int i=0; i < n;i++){
            array[i] = sc.nextInt();
        }
        Arrays.sort(array);
        int score = 0;
        boolean b = true;
        for(int i = array.length-1;i>=0;i--){
            int x = b ? array[i] : -array[i];
            b = !b;
            score += x;
        }
        System.out.println(score);
    }
}

C - Takahashi's Information

3*3のグリッドの(i,j)マスがa_i+b_jで表せるかどうかの判定。
ここで無駄に1時間以上時間を使ってしまった。

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[][] grid = new int[3][3];
        for(int i =0; i < 3;i++){
            for(int j =0;j<3;j++){
                grid[i][j] = sc.nextInt();
            }
        }
        boolean b = true;
        for(int i =0; i < 3; i++){
            int x = 0;
            int y = 0;
            for(int j =0;j<3;j++){
                int bX = grid[j][i] - grid[j][((i+1) % 3)];
                int bY = grid[i][j] - grid[((i+1) % 3)][j];
                if(j ==0){
                    x = bX;
                    y = bY;
                }else{
                    b &= x == bX;
                    b &= y == bY;
                }
                if(!b) break;
            }
            if(!b) break;
        }
        System.out.println(b ? "Yes" : "No");
    }
}

主に1回の2重ループの中でaとb両方の判定を一気にやろうとして、結果的に配列の添字間違いで時間を使ってしまった感じ。
1回のループ内で2つの内容を一気に判定しようとすると、どっちがどっちだか混乱してよく添字間違いやらかす。
ループ2回に分けても計算量ほぼ変わらないしミス防止のために分けたほうが早く解けた気がする。

D - Grid Repainting

とりあえず何かいい感じに経路探索して、そのあとゴールから逆順に辿りながら最短経路を塗りつぶして、それ以外の白マスをカウントした。
C問題に1時間くらいかけてしまったせいで時間内に解けなかった。
一応自力でも制限時間+30分くらいで解けたので、C問題を普段通りの時間でACできてれば時間内に解けたはず。

import java.util.ArrayList;
import java.util.List;
import java.util.Map.Entry;
import java.util.Scanner;

public class Main {
    static int[][] lengthGrid;
    static int[][] grid;
    static int h;
    static int w;

    static List> pairList = new ArrayList<>();

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        h = Integer.parseInt(s[0]);
        w = Integer.parseInt(s[1]);
        grid = new int[h][w];
        lengthGrid = new int[h][w];
        for(int i = 0;i < h;i++){
            char[] array = sc.nextLine().toCharArray();
            for(int j =0; j < w;j++){
                grid[i][j] = array[j] == '.' ? 1 : 0;
                lengthGrid[i][j] = -1;
            }
        }
        searchRoute(0,0,0);
        if(lengthGrid[h-1][w-1] == -1){
            System.out.println(-1);
            return;
        }
        paintRoute(h-1,w-1, lengthGrid[h-1][w-1]);
        int score = 0;
        for(int i = 0;i < h;i++){
            for(int j = 0; j < w;j++){
                score += grid[i][j];
            }
        }
        System.out.println(score-1);
    }

    public static void paintRoute(int i, int j, int length){
        if(i == 0 && j == 0) return;
        grid[i][j] = 0;
        length--;
        if(i != h-1 && lengthGrid[i+1][j] == length) paintRoute(i+1,j,length);
        else if(j != w-1 && lengthGrid[i][j+1] == length) paintRoute(i,j+1,length);
        else{
            if(i > 0 && lengthGrid[i-1][j] == length) paintRoute(i-1,j,length);
            else if(j > 0)paintRoute(i,j-1,length);
        }
    }

    public static void searchRoute(int i, int j, int length){
        if(i == h || j == w) return;
        if(lengthGrid[i][j] != -1 && lengthGrid[i][j] <= length) return;
        if(grid[i][j] == 0) return;
        lengthGrid[i][j] = length;
        if(i == h-1 && j == w-1) return;
        length++;
        if(i != 0) searchRoute(i-1,j,length);
        if(j != 0) searchRoute(i,j-1,length);
        searchRoute(i+1,j,length);
        searchRoute(i,j+1,length);
    }
}

アルゴリズムはあまりちゃんと勉強してないので、これより効率的な方法あるかもしれないけど解けたからOKということで。
雰囲気でプログラミングしてるので記述に無駄がある気がしないでもない。
あとややコードが汚いので見づらい。

まとめ

今回で自分が参加したratedのコンテストは4回目ですが、4回目にして一番パフォーマンスが下がってしまってつらい。
今までのコンテストのパフォーマンス的には緑までは何もしなくても行けるかな―、と思っていたのですがもう少し練習しないと駄目ですね。

今回はC問題に時間かかったのが完全に失敗。
一応400点問題までは時間かければなんとか解けるので、今後は300点問題までを詰まらずに素早く解けるようにすることと、500点問題を解けるようにするのが目標。
あと早く緑までレート上げたい。