AtCoder参戦日記 ARC105 2020/10/11 #6

AtCoder

AtCoderの6回目の参加となった2020/10/11のARC105の記録です。

15分ぐらいで2完でした。

3問目と4問目を競技中考えましたが、解法を見いだせませんでした。

4問目(D)は解説を見て理解したときの衝撃が凄まじかったです。こんな簡単に解けるとは。

問題 結果 言語
A ○ Ruby
B ○ Java
C
D 競技後にScala
E
F

過去の参戦記録

参加日 # コンテスト名 結果 使用言語
2020/08/29 #1 ABC177 3完 Scala, Scala, Java
2020/09/13 #2 ABC178 5完 Python, Scala, Scala, C++, Scala
2020/09/19 #3 ABC179 3完 Java, Scala, Scala
2020/10/03 #4 ARC104 2完 Python, Scala
2020/10/10 #5 HHKB2020 3完 C++, Scala, Java
2020/10/11 #6 ARC105 2完 Ruby, Java

A - Fourtune Cookies

問題へのリンク

いろいろな言語の練習も兼ねて1問目は、安易にScalaやJavaを選ばず他の言語を使うようにしています。今回はRubyで書きました。シンプルに書く方法を思いつかず、だいぶ強引なやりかたになりました。

a, b, c, d = gets.strip.split(" ").map(&:to_i)

if a == b + c + d
  puts("Yes")
elsif a + b == c + d
  puts("Yes")
elsif a + c == b + d
  puts("Yes")
elsif a + b + c == d
  puts("Yes")
elsif a + d == b + c
  puts("Yes")
elsif a + b + d == c
  puts("Yes")
elsif a + c + d == b
  puts("Yes")
else
  puts("No")
end

B - MAX-=min

問題へのリンク

素直にユークリッドの互除法を使うのではなく、もっといいやりかたがあるのかを悩んでしまいました。素直なコードを試しに書いてみたらそれで正しかったようです。Javaで書きました。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    var as = new int[n];
    for (int i = 0; i < n; i++) {
      as[i] = sc.nextInt();
    }
    int a0 = as[0];
    for (int i = 1; i < n; i++) {
      int a1 = as[i];
      while (true) {
        if (a0 > a1) {
          a0 = (a0-1) % a1 + 1;
        } else if (a0 < a1) {
          a1 = (a1-1) % a0 + 1;
        } else {
          break;
        }
      }
    }
    System.out.println(a0);
  }
}

C - Camels and Bridge

問題へのリンク

さっぱりわからず。競技中早々にあきらめて4問目(D)に進みました。

D - Let's Play Nim

問題へのリンク

競技時間中ずっと考えて終わりました。

解説を見て衝撃を受けました。排他的論理和で戦略が組み立てられるのと、過半数を集めるという点が思いつけなかったです。

以下のコードは解説を見て理解したあとに書いたScalaのコードです。コード自体はシンプルすぎて、これを見ただけではまったくわからないです。

object Main extends App {
  def solve(as: Array[Int]): Boolean = {
    if (as.size % 2 != 0) {
      false;
    } else {
      val s = as.foldLeft(Set.empty[Int]) { (s, a) => if (s.contains(a)) s - a else s + a }
      !s.isEmpty;
    }
  }
  val sc = new java.util.Scanner(System.in);
  val t = sc.nextInt();
  (0 until t).foreach { _ =>
    val n = sc.nextInt();
    val as = Array.fill(n)(sc.nextInt());
    if (solve(as)) {
      println("First");
    } else {
      println("Second");
    }
  }
}