AtCoder Beginner Contest 276を振り返る。


  • 結果
    2完。
    C問題が鬼門。なかなか解けない。。

  • Rate変動
    458 → 437


  • A問題 3分24秒でAC

文字列内の最後にある「a」の場所を出力する問題。

特に手が止まることもなく、一瞬でAC。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 入力読み込み
        Scanner sc = new Scanner(System.in);
        String n = sc.next();

        int ans = -1;

        for (int i = 0; i < n.length(); i++) {
            if(n.charAt(i) == 'a') {
                ans = i;
            }
        }
        if(ans == -1){
            System.out.println("-1");
        }else{
            System.out.println(ans+1);
        }

        sc.close();
    }
}
  • B問題 44分50秒でAC

点同士が線で繋がっている。各点に対してどの点と繋がっているか列挙する問題。
ソートをうまく使うことが大切。強引に後ろにくっつけてソートできる状態に持っていった。解説を見ると、各点ごとにどこの点と繋がっているかを持って、ソートする方法が書かれており、私も最初これをjavaで実現したかったが方法がわからなかった。。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 入力読み込み
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long[] a = new long[m*2];
        int[] s = new int[n];

        for (int i = 0; i < m; i++) {
            long ia = sc.nextLong();
            long ib = sc.nextLong();
            a[i] = ib * 1000000 + ia;
            a[i+m] = ia * 1000000 + ib;
            s[(int)ia-1]++;
            s[(int)ib-1]++;
        }
        Arrays.sort(a);

        int count = 0;
        for (int i = 0; i < n; i++) {
            System.out.println(s[i]);
            for (int j = 0; j < s[i]; j++) {
                System.out.println(a[j + count] % 1000000);
            }
            count += s[i];
        }
        sc.close();
    }
}
  • C問題 ACできず。。

与えられた順列に対して、ひとつ前の辞書順を答える問題。
順列というものの理解が甘く、正しく考察できていなかった。
swapして反転ね。。わからなかったなぁ。修行が足りぬ。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 入力読み込み
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] p = new int[n];

        for (int i = 0; i < n; i++) {
            p[i] = sc.nextInt();
        }

        int j = n - 2;
        while (p[j] < p[j+1]){
            j -=1;
        }
        int k = n -1;
        while (p[j] < p[k]){
            k -= 1;
        }

        int a = p[j];
        int b = p[k];
        p[j] = b;
        p[k] = a;
        for (int i = 0; i < n; i++) {
            if (i == j+1){
                for (int l = n-1; l > j; l--) {
                    System.out.println(p[l]);
                }
                return;
            }
            System.out.println(p[i]);
        }
        sc.close();
    }
}
  • D問題 以下、着手できず

  • E問題

  • F問題

  • G問題

  • EX問題


解説ではjavaの解法は載ってないことが多く、同じ標準ライブラリが使用できないことや、代替ライブラリを探す手間がかかる。
今回を境に、javaをやめて、C++に移民して競プロを行なっていこうと思う。

来週は、C問題も解いてやるぞおおお。


この記事が参加している募集

この記事が気に入ったらサポートをしてみませんか?