AtCoder参戦日記 ABC180 2020/11/01

AtCoder

2020/11/01にバーチャル参加したABC180の記録です。日程的に参加できなかったコンテストに後日バーチャル参加しました。

55分ぐらいで4完でした。終了後5分ぐらいで5問目ができました。

問題 結果 言語
A ○ Ruby
B ○ Scala
C ○ C++
D ○ Java
E 競技後にJava
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
2020/11/01 ABC180 4完 Ruby, Scala, C++, Java

A - box

問題へのリンク

簡単な問題なのでRubyで解きました。

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

B - Various distances

問題へのリンク

ロジック的に書きやすいScalaで解きました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val xs = Array.fill(n)(sc.nextInt());
  val r1 = xs.map(x => (x max (-x)).toLong).sum;
  val r2 = Math.sqrt(xs.map(x => x.toLong * x).sum);
  val r3 = xs.map(x => (x max (-x)).toLong).max;
  println(r1);
  println(r2);
  println(r3);
}

C - Cream puff

問題へのリンク

nの平方根を上限にループを回せばよいことまではわかりますが、それ以上の効率化が思いつかず、処理速度がネックになる可能性がわからなかったので、最速のC++で書きました。

#include <bits/stdc++.h>
using namespace std;

int main() {
  long n;
  cin >> n;
  int n2 = (int)sqrt((double)n);
  vector<int> vec = {};
  int last = 0;
  for (int i = 1; i <= n2; i++) {
    if (n % i == 0) {
      cout << i << endl;
      vec.push_back(i);
      last = i;
    }
  }
  for (int i = vec.size() - 1; i >= 0; i--) {
    long i2 = n / vec.at(i);
    if (i2 != last) {
      cout << i2 << endl;
    }
  }
}

D - Takahashi Unevolved

問題へのリンク

対数の計算が含まれる解法です。最初は浮動小数点数で対数を計算しましたが、WAになってしまいましたので、整数での計算に改良してACを取りました。言語はこのロジックを書きやすそうなJavaになりました。

以下は競技終了後にさらに少し改善したコードです。

import java.util.Scanner;

class Main {
  public static long log(long a, long max) {
    long acc = 0;
    while (true) {
      if (max < a) {
        return acc;
      }
      int n = 1;
      long s = a;
      while (true) {
        long s2 = s * s;
        if (s2 > max) break;
        s = s2;
        n <<= 1;
      }
      max = max / s;
      acc = acc + n;
    }
  }
  public static long pow(long a, long n) {
    long s = 1;
    while (n > 0) {
      if ((n & 1) != 0) s = s * a;
      a = a * a;
      n >>= 1;
    }
    return s;
  }
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    long x = sc.nextLong();
    long y = sc.nextLong();
    long a = sc.nextLong();
    long b = sc.nextLong();

    long th = b / (a - 1);
    if (th >= y) th = y - 1;
    long na = log(a, th / x);
    long x2 = x * pow(a, na);
    long nb = (y - x2 - 1) / b;

    long answer = na + nb;
    System.out.println(answer);
  }
}

E - Traveling Salesman among Aerial Cities

問題へのリンク

競技中40分考えて、コード書き途中で終わってしまいました。競技終了後5分ぐらいでAC取れました。前問に続き、このロジックを書きやすそうなJavaになりました。

import java.util.Scanner;

class Main {
  private static int cost(int[] x, int[] y, int[] z, int k, int j) {
    if (j == 16) j = 0; else j = j + 1;
    if (k == 16) k = 0; else k = k + 1;
    int rx = x[j] - x[k];
    int ry = y[j] - y[k];
    int rz = z[j] - z[k];
    if (rx < 0) rx = -rx;
    if (ry < 0) ry = -ry;
    if (rz < 0) rz = 0;
    return rx + ry + rz;
  }
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    var x = new int[n];
    var y = new int[n];
    var z = new int[n];
    for (int i = 0; i < n; i++) {
      x[i] = sc.nextInt();
      y[i] = sc.nextInt();
      z[i] = sc.nextInt();
    }

    var dp = new int[(1 << 16) * 16];
    int i_max = (1 << (n-1)) - 1;
    for (int i = 0; i <= i_max; i++) {
      for (int j = 0; j < 16; j++) {
        if ((i & (1 << j)) == 0) continue;
        int i2 = i ^ (1 << j);
        int cost = Integer.MAX_VALUE;
        for (int k = 0; k < 16; k++) {
          if ((i2 & (1 << k)) == 0) continue;
          int c = dp[i2 * 16 + k] + cost(x, y, z, k, j);
          if (c < cost) cost = c;
        }
        if (cost == Integer.MAX_VALUE) {
          cost = cost(x, y, z, 16, j);
        }
        dp[i * 16 + j] = cost;
      }
    }

    int cost = Integer.MAX_VALUE;
    for (int j = 0; j < (n-1); j++) {
      if ((i_max & (1 << j)) == 0) continue;
      int c = dp[i_max * 16 + j] + cost(x, y, z, j, 16);
      if (c < cost) cost = c;
    }
    System.out.println(cost);
  }
}