AtCoder参戦日記 ABC185 2020/12/13 12回目

AtCoder

AtCoderの12回目の参加となった2020/12/13のABC185の記録です。9か月も下書きのまま放置してしまっていましたが、前回記事に引き続き、AtCoderの感を取り戻すための復習記事です。

100分の競技時間ぎりぎりで5完でした。

Dまでは35分ほどで完了しました。Eは問題文を1回読んですぐにあきらめ、Fに進みました。Fはコードを書くのに時間がかかってしまいましたが、ぎりぎりACを取れました。

パフォーマンスは1160で、AtCoder Beginner Contestとしては過去2番目にいい成績ではありました。

問題 結果 言語 競技後
A AC JavaScript
B AC Java Scala
C AC Ruby C++
D AC Scala
E
F AC C++ Java

5問できたのもめずらしいのですが、5言語使ったのは初めてです。1問目の言語選択は理由はないのですが、他は問題ごとに最適な言語を選んだつもりです。

過去の参戦記録

参加日 # コンテスト名 結果 使用言語
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
2020/11/15 9 ABC183 4完 / 871 Ruby, Ruby, Java, Java
2020/11/21 10 ARC108 3完 / 1979 Ruby, Java, Java
2020/12/05 11 ARC110 3完 / 1562 Ruby, Scala, Java
2020/12/13 12 ABC185 5完 / 1160 JavaScript, Java, Ruby, Scala, C++

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

A - ABC Preparation

問題へのリンク

言語の練習のためにJavaScriptにしました。競技本番でJavaScriptを書いたのは初めてです。

const lines = require('fs').readFileSync('/dev/stdin', 'utf8').split("\n");
const [a1, a2, a3, a4] = lines[0].split(" ").map(s => Number(s));
console.log(Math.min(a1, a2, a3, a4));

B - Smartphone Addiction

問題へのリンク

手続き型で書きたかったので関数型のScalaではなくJavaで書きました。

class Main {
  public static void main(String[] args) {
    var sc = new java.util.Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int t = sc.nextInt();

    var abs = new int[2*m];
    for (int i = 0; i < m; i++) {
      abs[2*i  ] = sc.nextInt();
      abs[2*i+1] = sc.nextInt();
    }

    int c = n;
    int ct = 0;
    for (int i = 0; i < m; i++) {
      int a = abs[2*i ];
      int b = abs[2*i+1];
      c -= a - ct;
      if (c <= 0) {
        System.out.println("No");
        return;
      }
      c += b - a;
      if (c > n) c = n;
      ct = b;
    }
    c -= t - ct;
    if (c <= 0) {
      System.out.println("No");
      return;
    }
    System.out.println("Yes");
  }
}

9か月後のいま、Scalaで書き直しました。

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

  var n1: Int = n;
  var t1: Int = 0;
  var result: Boolean = true;
  (0 until m).foreach { _ =>
    val a, b = sc.nextInt();
    n1 = n1 - (a - t1);
    if (n1 <= 0) {
      result = false;
    }
    n1 = n1 + (b - a);
    if (n1 > n) {
      n1 = n;
    }
    t1 = b;
  }
  n1 = n1 - (t - t1);
  if (n1 <= 0) {
    result = false;
  }
  if (result) {
    System.out.println("Yes");
  } else {
    System.out.println("No");
  }
}

C - Duodecim Ferra

問題へのリンク

組み合わせ数を計算するだけですが、64bit整数でオーバーフローを回避する方法がすぐには思いつかず、Rubyの整数で計算しました。

l = gets.strip.to_i

s = 1
for i in 12..(l-1)
  s = s * i
end
for i in 2..(l-12)
  s = s / i
end
puts(s)

9か月後のいま、他の人の回答を見て、演算の順序を気にすればいいとわかって、書いたコードが以下です。

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

int main() {
  int l;
  cin >> l;

  long long result = 1;
  for (int i = 1; i <= 11; i++) {
    result *= l - i;
    result /= i;
  }
  cout << result << endl;
}

D - Stamp

問題へのリンク

関数型で書くのが楽そうだったのでScalaにしました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n, m = sc.nextInt();
  val as = Array.fill(m)(sc.nextInt());

  val as_sorted = as.sorted;

  val intervals = (0 to m).map { i =>
    if (m == 0) {
      n;
    } else if (i == m) {
      n - as_sorted(i-1);
    } else if (i == 0) {
      as_sorted(i) - 1;
    } else {
      as_sorted(i) - as_sorted(i-1) - 1;
    }
  }.filter(_ > 0);

  val answer = if (intervals.size == 0) {
    0;
  } else {
    val min = intervals.min;
    intervals.map { d =>
      (d-1) / min + 1;
    }.sum;
  }
  println(answer);
}

E - Sequence Matching

問題へのリンク

問題文を1回読んで、すぐにあきらめました。

F - Range Xor Query

問題へのリンク

少し考えて解法を思いついたものの、コードを書くのに時間がかかってしまいました。解法はあとで解説を読んで、セグメント木というらしいです。最後につまらないバグにもはまってしまい、問題文を読み始めてからAC取るまでに1時間近くかかってしまいました。

解法を思いついた時点で、処理速度の勝負だと思ったので、C++にしました。

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

int main() {
  int n, q;
  cin >> n >> q;

  int count = 1 << 19 + 1;
  int as[count];
  for (int i = 0; i < n; i++) {
    cin >> as[i];
  }
  for (int i = n; i < count; i++) {
    as[i] = 0;
  }
  int *ass[19];
  for (int di = 0; di < 19; di++) {
    int d = 1 << di;
    int c = count >> (di+1);
    ass[di] = new int[c];
    for (int i = 0; i < c; i++) {
      int id = i << (di+1);
      int xo = 0;
      for (int j = 0; j < d; j++) {
        xo = xo ^ as[id + j];
      }
      ass[di][i] = xo;
    }
  }

  for (int i = 0; i < q; i++) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1) {
      int z = x - 1;
      for (int di = 0; di < 19; di++) {
        if (((z >> di) & 1) == 0) {
          int zi = z >> (di+1);
          ass[di][zi] = ass[di][zi] ^ y;
        }
      }
    } else {
      int zo = 0;
      int z = y;
      for (int di = 0; di < 19; di++) {
        if (((z >> di) & 1) != 0) {
          zo = zo ^ ass[di][z >> (di+1)];
        }
      }
      z = x - 1;
      for (int di = 0; di < 19; di++) {
        if (((z >> di) & 1) != 0) {
          zo = zo ^ ass[di][z >> (di+1)];
        }
      }
      cout << zo << endl;
    }
  }
}

9か月後のいま、ゼロベースで考えてJavaで書いたコードが以下です。上記とたぶん同じロジックだと思うのですが、上記を今となっては読み解けません。

class Main {
  public static void main(String[] args) {
    var sc = new java.util.Scanner(System.in);
    int n = sc.nextInt();
    int q = sc.nextInt();

    int max = 1 << 19;
    int[] segment = new int[max];
    int[] buf = new int[20];

    for (int i = 0; i < n; i++) {
      int a = sc.nextInt();
      updateSegment(i, a, segment, buf, max);
    }

    for (int i = 0; i < q; i++) {
      int t = sc.nextInt();
      int x = sc.nextInt();
      int y = sc.nextInt();
      if (t == 1) {
        x = x - 1;
        updateSegment(x, y, segment, buf, max);
      } else {
        x = x - 1;
        y = y - 1;
        int ax = fetchSegment(x, segment, buf);
        int ay = fetchSegment(y + 1, segment, buf);
        int answer = ay ^ ax;
        System.out.println(answer);
      }
    }

  }

  private static void updateSegment(int idx, int x, int[] segment, int[] buf, int max) {
    indexOfUpdateSegment(idx + 1, buf, max);
    int i = 0;
    while (true) {
      int s = buf[i];
      if (s < 0) break;
      segment[s] ^= x;
      i++;
    }
  }

  private static int fetchSegment(int idx, int[] segment, int[] buf) {
    indexOfFetchSegment(idx, buf);
    int i = 0;
    int ret = 0;
    while (true) {
      int s = buf[i];
      if (s < 0) break;
      ret ^= segment[s];
      i++;
    }
    return ret;
  }

  // 13 -> 13, 14, 16, 32, 64, 128
  private static void indexOfUpdateSegment(int idx, int[] buf, int max) {
    int offset = 0;
    while (idx < max) {
      int lastBit = idx & -idx;
      buf[offset] = idx;
      offset++;
      idx = idx + lastBit;
    }
    buf[offset] = -1;
  }

  // 13 -> 13, 12, 8
  private static void indexOfFetchSegment(int idx, int[] buf) {
    int offset = 0;
    while (idx != 0) {
      buf[offset] = idx;
      offset++;
      int lastBit = idx & -idx;
      idx = idx - lastBit;
    }
    buf[offset] = -1;
  }
}