CS Academy Round 84 に参加した感想

CS Academy Round 84

csacademy.com

初めて海外の競技プログラミングのコンテストに参加しました。

AtCoderのC問題に苦戦する僕にとって、海外のコンテストに参加するのは背伸びしすぎたかもしれません。

結果は1問だけ解くことができました。このコンテストの中で一番優しい問題だったんですが、AtCoderの配点でいうと200点位だと思います。yukicoderで換算すると、1.5レベルくらいでしょうか。

問題

https://csacademy.com/contest/round-84

Douchebag Parking

”Douchebag” とは「嫌な奴」という意味のスラングだそうです。つまり、嫌な奴の駐車という意味でしょうか。

内容

問題は長さ の車が駐車可能なときの最も番号が小さい駐車場を答えよというものです。

駐車場の状態は が駐車不可、 が駐車可能で、駐車場のスペースは ということです。

もし、駐車可能な駐車場が連続している場合、駐車スペースは となります。複数の駐車スペースにまたがって駐車することができるので、嫌な奴の駐車ということなんですかね。

コード

import java.util.Scanner;

public class DouchebagParking {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int W = scan.nextInt();
        int [][] state = new int[N][2];
        for(int i = 0; i < N; i++) {
            state[i][0] = scan.nextInt();
            state[i][1] = scan.nextInt();
        }
        scan.close();
        int len = 0;
        int ans = 0;
        int cnt = 0;
        for(int i = 0; i < N; i++) {
            if(state[i][0] == 1) {
                len += state[i][1];
                cnt ++;
            }else {
                len = 0;
                cnt = 0;
            }
            if(W <= len) {
                ans = i + 2 - cnt;
                System.out.println(ans);
                System.exit(0);
            }
        }
        System.out.println(-1);
    }
}

Three Ones

最初の問題が解けてからずっとこの問題を考えていましたが、結局解くことはできませんでした。

問題文の意味と解く方針は分かったんですが、実装することは叶いませんでした。

内容

0と1の文字列が与えられて、その長さが部分文字列が少なくとも1を3つ以上含むような最小の を求めよという問題です。

計算量がとなるのは予測がつくんですが、アルゴリズムが分かりませんでした。

多分、典型的な問題なので、理解はせずとも覚えないといけませんね。

コード

公式の解答をパクったもの。こりゃ思いつかんね。

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class ThreeOnes {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        String s = scan.next();
        scan.close();

        int max = 0;
        Queue<Integer> queue1 = new ArrayDeque<Integer>();
        queue1.add(-1);
        for(int i = 0; i < N; i++) {
            char c = s.charAt(i);
            if(c == '1') {
                queue1.add(i);
                if(queue1.size() == 4) {
                    queue1.poll();
                }
            }
            max = Math.max(max, i - queue1.peek() + 1);
        }
        System.out.println(max);
    }
}