AtCoderの4回目の参加となった2020/10/03 ARC104の記録です。

2完でした。

2問目のACまでに20分も消費してしまいました。

その後約40分をCに時間かけ、コードを書きましたが、最後まで書ききれずに、提出することなくあきらめてDに移りました。

Dでも残り時間約40分かけて、コードを書いて提出までしましたが、細かいバグ取りと処理時間の問題を解決できずに時間切れとなりました。Scalaで取り組んだのですが、無理でした。

問題	結果	言語
A	○	Python (競技後にRuby)
B	○	Scala
C		競技後にJava
D		競技後にScala, Java, C++, Ruby, Perl, Elixir
E
F

A - Plus Minus
B - DNA Sequence
C - Fair Elevator
D - Multiset Mean

過去の記録

2020/08/29 ABC177 3完: Scala, Scala, Java
2020/09/13 ABC178 5完: Python, Scala, Scala, C++, Scala
2020/09/19 ABC179 3完: Java, Scala, Scala
2020/10/03 ARC104 2完: Python, Scala

A - Plus Minus

問題

競技中はPythonで書きました。あとで他言語の練習としてRubyでも書きました。

[a, b] = input().split(" ")
a = int(a)
b = int(b)

print("%d %d" % ((a + b) / 2, (a - b) / 2))

a, b = gets.strip.split(" ").map(&:to_i)
printf("%d %d\n", (a + b) / 2, (a - b) / 2)

B - DNA Sequence

問題

Scalaで書きましたが、とても汚いコードです。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val s = sc.next();

  val answer = (1 to (n/2)).map(2 * _).map { m =>
    var k1 = (0 until m).count(i => s(i) == 'A');
    var k2 = (0 until m).count(i => s(i) == 'T');
    var k3 = (0 until m).count(i => s(i) == 'C');
    var k4 = (0 until m).count(i => s(i) == 'G');
    (0 to (n-m)).count { i =>
      if (i > 0) {
        s(i - 1) match {
          case 'A' => k1 -= 1;
          case 'T' => k2 -= 1;
          case 'C' => k3 -= 1;
          case 'G' => k4 -= 1;
          case _ => ;
        }
        s(i + m - 1) match {
          case 'A' => k1 += 1;
          case 'T' => k2 += 1;
          case 'C' => k3 += 1;
          case 'G' => k4 += 1;
          case _ => ;
        }
      }
      k1 == k2 && k3 == k4;
    }
  }.sum;

  println(answer);

}

C - Fair Elevator

問題

競技中は40分ぐらい考えましたが、いい解法が思いつきませんでした。無理やりな解法は考えてコードを書いたのですが、コードが複雑すぎて書ききれずでした。

以下は競技後に解説を見てから書いたコードです。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    int n2 = 2 * n;
    var abs = new int[n2];
    for (int i = 0; i < n; i++) {
      abs[2 * i    ] = sc.nextInt();
      abs[2 * i + 1] = sc.nextInt();
    }
    var table = new int[n2];
    var table2 = new boolean[n];
    for (int i = 0; i < n; i++) {
      var a = abs[2 * i    ];
      var b = abs[2 * i + 1];
      if (a > 0 && b > 0 && a >= b || a > 0 && table[a-1] != 0 || b > 0 && table[b-1] != 0) {
        System.out.println("No");
        return;
      }
      if (a > 0) table[a-1] = i + 1;
      if (b > 0) table[b-1] = -(i + 1);
      if (a > 0 && b > 0) table2[i] = true;
    }
    var dp = new boolean[n];
    for (int i = 0; i < n; i++) {
      for (int j = -1; j < i; j++) {
        boolean flag = (j < 0) || dp[j];
        if (!flag) continue;
        int ij2 = i - j;
        int l = 0;
        for (int k = 0; k < ij2; k++) {
          int a = table[2 * (j+1) + k];
          int b = table[2 * (j+1) + k + ij2];
          if (a < 0) {
            flag = false; break;
          } else if (b > 0) {
            flag = false; break;
          } else if (a > 0 && b < 0 && a + b != 0) {
            flag = false; break;
          }
          if (a > 0 && b == 0 && table2[a-1]) {
            flag = false; break;
          } else if (a == 0 && b < 0 && table2[-b-1]) {
            flag = false; break;
          }
        }
        if (l != 0) flag = false;
        if (flag) {
          dp[i] = flag;
          break;
        }
      }
    }
    if (dp[n-1]) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}