AtCoderの8回目の参加となった2020/11/08のABC182の記録です。

25分ほどで4完でした。5問目は少し考えて計算量を抑える方法を思いつかずあきらめました。6問目は解法がわからないままタイムアップでした。

そろそろ後半の難しい問題も解けるようにならないと伸び悩みそうです。

問題	結果	言語	競技後
A	AC	Ruby	Elixir
B	AC	Scala	Python, Ruby
C	AC	Scala
D	AC	Java
E			Java
F

A - twiblr
B - Almost GCD
C - To 3
D - Wandering
E - Akari

過去の参戦記録

参加日	コンテスト名	結果	使用言語
2020/08/29 #1	ABC177	3完 / 614	Scala, Scala, Java
2020/09/13 #2	ABC178	5完 / 1466	Python, Scala, Scala, C++, Scala
2020/09/19 #3	ABC179	3完 / 1004	Java, Scala, Scala
2020/10/03 #4	ARC104	2完 / 1067	Python, Scala
2020/10/10 #5	HHKB2020	3完 / 902	C++, Scala, Java
2020/10/11 #6	ARC105	2完 / 1069	Ruby, Java
2020/11/01	ABC180	4完 / (937)	Ruby, Scala, C++, Java
2020/11/01 #7	ABC181	4完 / 1136	C++, Scala, Java, Java
2020/11/07	ABC171	5完 / (1557)	C++, Scala, Ruby, Java, Java
2020/11/08 #8	ABC182	4完 / 1072	Ruby, Scala, Scala, Java

※結果欄は、時間内にAC取れた問題数とパフォーマンスです。パフォーマンスの括弧の数字はバーチャル参加の推定値です。

A - twiblr

問題へのリンク

1問目は言語の練習として私の馴染みの薄いRubyで書きました。

a, b = gets.strip.split(" ").map(&:to_i)
puts(a * 2 + 100 - b)

後日Elixirでも書きました。

defmodule Main do
  def main do
    [a, b] = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
    IO.puts(a * 2 + 100 - b)
  end
end

B - Almost GCD

問題へのリンク

手早く書くことを優先してScalaで書きました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val as = Array.fill(n)(sc.nextInt());
  val max = as.max;
  var gcd: Int = 0;
  var answer: Int = 0;
  (2 to max).foreach { i =>
    val c = as.count(_ % i == 0);
    if (c > gcd) {
      gcd = c;
      answer = i;
    }
  }
  println(answer);
}

後日PythonとRubyでも書きました。

n = int(input())
ass = list(map(int, input().split(" ")))
gcd = 0
answer = 0
for i in range(2, max(ass)+1):
    c = 0
    for j in ass:
        if j % i == 0: c += 1
    if c > gcd:
        gcd = c
        answer = i
print(answer)

n = gets.strip.to_i
as = gets.strip.split(" ").map(&:to_i)
gcd = 0
answer = 0
for i in 2..as.max
  c = 0
  for j in as
    c+=1 if j % i == 0
  end
  if c > gcd
    gcd = c
    answer = i
  end
end
puts(answer)

C - To 3

問題へのリンク

手早く書くことを優先してScalaで書きました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextLong();
  val set = n.toString.map {ch: Char => (ch - '0') % 3};
  val count1 = set.count(_ == 1);
  val count2 = set.count(_ == 2);
  val sum = set.sum % 3;
  sum match {
    case 0 =>
      println(0);
    case 1 =>
      if (count1 >= 1 && set.size > 1) {
        println(1);
      } else if (count2 >= 2 && set.size > 2) {
        println(2);
      } else {
        println(-1);
      }
    case 2 =>
      if (count2 >= 1 && set.size > 1) {
        println(1);
      } else if (count1 >= 2 && set.size > 2) {
        println(2);
      } else {
        println(-1);
      }
  }
}

D - Wandering

問題へのリンク

Javaになりました。Scalaにしなかったのは、関数型ではなく、変数に代入しながら処理する手続き的なやりかたが考えやすかったためです。

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();
    }
    long pos = 0L;
    long sum = 0L;
    long max1 = 0L;
    long max2 = 0L;
    for (int i = 0; i < n; i++) {
      sum += as[i];
      if (sum > max1) max1 = sum;
      long p = pos + max1;
      pos += sum;
      if (p > max2) max2 = p;
    }
    System.out.println(max2);
  }
}

E - Akari

問題へのリンク

競技中は、少し考えて計算量を抑える方法を思いつかずあきらめました。

以下は後日解説を読んでから書いたJavaのコードです。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    int n = sc.nextInt();
    int m = sc.nextInt();
    int hw = h * w;
    var table = new int[hw];
    var as = new int[n];
    var bs = new int[n];
    for (int i = 0; i < n; i++) { // 電球
      int a = sc.nextInt()-1;
      int b = sc.nextInt()-1;
      as[i] = a;
      bs[i] = b;
    }
    for (int i = 0; i < m; i++) { // ブロック
      int c = sc.nextInt()-1;
      int d = sc.nextInt()-1;
      table[w*c+d] = 8;
    }
    for (int i = 0; i < n; i++) {
      int a = as[i];
      int b = bs[i];
      int g = w*a+b;
      if ((table[g] & 0x1) == 0) {
        int k = g;
        for (int b2 = b-1; b2 >= 0; b2--) {
          k--;
          if (table[k] == 8) break;
          table[k] |= 0x1;
        }
        k = g;
        for (int b2 = b+1; b2 < w; b2++) {
          k++;
          if (table[k] == 8) break;
          table[k] |= 0x1;
        }
      }
      if ((table[g] & 0x2) == 0) {
        int k = g;
        for (int a2 = a-1; a2 >= 0; a2--) {
          k-=w;
          if (table[k] == 8) break;
          table[k] |= 0x2;
        }
        k = g;
        for (int a2 = a+1; a2 < h; a2++) {
          k+=w;
          if (table[k] == 8) break;
          table[k] |= 0x2;
        }
      }
      table[g] |= 0x3;
    }
    int answer = 0;
    for (int i = 0; i < hw; i++) {
      if ((table[i] & 0x3) != 0) answer++;
    }
    System.out.println(answer);
  }
}

suzuki-navi’s blog

AtCoder参戦日記 ABC182 2020/11/08 #8

A - twiblr

B - Almost GCD

C - To 3

D - Wandering

E - Akari