AtCoder参戦日記 ABC177 2020/08/29 #1 ― 初参加

AtCoder

8月終わりごろからAtCoderに参加しています。参加の記録を残しておこうと思い、この記事は初参加となった2020/08/29のABC177の記録です。

参加当日は、ペナルティのルールをよくわかっていなくて、C問題で適当に提出しすぎて、大量のペナルティで損をしました。

D問題はUnion-Findを知らなくて解けず、Cまでの3問解けたのみでした。

問題 結果 言語
A ○ Scala
B ○ Scala
C ○ Java
D Java
E
F

A - Don't be late

問題

パッと書ける言語としてScalaで書きましたが、Pythonのほうが早かったかも。

import java.util.Scanner;

object Main extends App {
  val sc = new Scanner(System.in);
  val d, t, s = sc.nextInt();

  if (d <= s * t) {
    println("Yes");
  } else {
    println("No");
  }
}

B - Substring

問題

パッと書ける言語としてScalaで書きました。

import java.util.Scanner;

object Main extends App {
  val sc = new Scanner(System.in);
  val s, t = sc.next();

  val answer = (0 to (s.length - t.length)).map { d =>
    t.length - (0 until t.length).count { i =>
      s(i + d) == t(i)
    }
  }.min;

  println(answer);
}

C - Sum of product of pairs

問題

最初バカ正直な処理に時間のかかる方法で書いてしまい、またミスも繰り返してペナルティをたくさん受け取ってしまいました。

ScalaではちょっとめんどくさそうだったのでJavaになりました。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {

    var m = 1000000007;

    var sc = new Scanner(System.in);

    var n = sc.nextInt();
    var a = new int[n];
    for (int i = 0; i < n; i++) {
      a[i] = sc.nextInt() % m;
    }

    long sum1 = 0;
    long sum2 = 0;
    for (int i = 0; i < n; i++) {
      sum1 += a[i];
      sum2 += (long)a[i] * a[i] % m;
    }
    sum1 = sum1 % m;
    sum2 = sum2 % m;

    long t = (sum1 * sum1 - sum2) % m;
    long answer;
    if (t % 2 == 0) {
      answer = t / 2;
    } else {
      answer = (t + m) / 2;
    }

    System.out.println(answer);
  }
}

D - Friends

問題

Union-Findというアルゴリズムを使います。

コンテスト中はUnion-Findを知らなくて、結局時間内に解けませんでした。以下のコードはコンテスト終了後に調べて書いたものです。

3問目(C)と同じくScalaではめんどくさそうだったのでJavaになりました。

class Main {
  public static int root(int[] root, int i) {
    int r = root[i];
    if (r == i) {
      return r;
    } else {
      int r2 = root(root, r);
      root[i] = r2;
      return r2;
    }
  }

  public static void main(String[] args) {

    var sc = new Scanner(System.in);

    int n = sc.nextInt();
    int m = sc.nextInt();

    var ab = new int[2 * m];
    for (int i = 0; i < m; i++) {
      int a = sc.nextInt() - 1;
      int b = sc.nextInt() - 1;
      if (a > b) {
        int t = b;
        b = a;
        a = t;
      }
      ab[2 * i    ] = a;
      ab[2 * i + 1] = b;
    }

    var count = new int[n];
    var root = new int[n];
    for (int i = 0; i < n; i++) {
      count[i] = 1;
      root[i] = i;
    }
    for (int i = 0; i < m; i++) {
      int a = ab[2 * i    ];
      int b = ab[2 * i + 1];
      int ra = root(root, a);
      int rb = root(root, b);
      if (ra != rb) {
        if (ra > rb) {
          int t = rb;
          rb = ra;
          ra = t;
        }
        root[rb] = ra;
        count[ra] += count[rb];
      }
    }

    int max = 0;
    for (int i = 0; i < n; i++) {
      int c = count[i];
      if (c > max) {
        max = c;
      }
    }

    System.out.println(max);

  }
}