AtCoder参戦日記 ABC183 2020/11/15 #9

AtCoderの9回目の参加となった2020/11/15のABC183の記録です。

パフォーマンスは、まだ勝手のわかっていなかった初参加を除くと最悪値になってしまいました。時間がかかってしまったのが敗因です。

2問目は書いたコードが違うディレクトリに保存されていることに気が付かず、テストが通らなくて時間を費やしてしまいました。3問目はコードをすぐに書くことができず、飛ばして先に4問目に進みました。4問目も思いのほか時間を費やしてしまいました。その後3問目に戻りました。4完までに約1時間もかかってしまいました。5問目は処理高速化の手法を思いつけずに終了になりました。

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

過去の参戦記録

参加日	コンテスト名	結果	使用言語
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

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

A - ReLU

問題へのリンク

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

x = gets.strip.to_i
if x >= 0
  puts(x)
else
  puts(0)
end

後日書いた以下のようなコードのほうが短いです。

x = gets.strip.to_i
puts([0, x].max)

同じようにJavaScriptでも書きました。

const lines = require('fs').readFileSync('/dev/stdin', 'utf8').split("\n");
const a = Number(lines[0])
console.log(Math.max(a, 0));

B - Billiards

問題へのリンク

1問目に引き続きRubyで書き始めたものの、Rubyの除算が整数なのか浮動小数点数なのかのあたりがわからなくて、自分の過去の記事を参照しました。

• 整数同士の除算演算子の挙動 (C言語、C++、Scala、Java、Rust、Go言語、PHP、JavaScript、Perl、Python、Ruby、Elixir)

sx, sy, gx, gy = gets.strip.split(" ").map(&:to_i)
answer = sy * (gx - sx).to_f / (sy + gy) + sx
puts(answer)

後日JavaScriptでも書きました。

const lines = require('fs').readFileSync('/dev/stdin', 'utf8').split("\n");
const [sx, sy, gx, gy] = lines[0].split(" ").map(s => Number(s));
const answer = sx + (gx - sx) * sy / (sy + gy);
console.log(answer);

C - Travel

問題へのリンク

順列の総当りをするコードを手早く書く方法が思いつかなくて、先にD問題に進みました。Dが完了後にCに戻って、コードを書いています。nが整数のビット数よりも小さいことを利用して、順列の総当りにビット演算を使っています。Javaのコードです。後述しますが、これは順列の列挙の一般的なアルゴリズムではなさそうです。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    var ts = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        ts[i][j] = sc.nextInt();
      }
    }
    int answer = 0;
    var order = new int[n-1];
    var flags = new int[n-1];
    order[0] = 2;
    flags[0] = 0x00;
    for (int i = 1; i < n-1; i++) {
      order[i] = i + 2;
      flags[i] = flags[i-1] | (0x1 << (i-1));
    }
    while (true) {
      long cost = 0;
      int p = 1;
      for (int i = 0; i < n-1; i++) {
        int p2 = order[i];
        cost += ts[p-1][p2-1];
        p = p2;
      }
      cost += ts[p-1][0];
      if (cost == k) answer++;

      int i = n-2;
      for (; i >= 0; i--) {
        int x = order[i] + 1;
        for (; x <= n; x++) {
          if ((flags[i] & (0x1 << (x-2))) == 0) break;
        }
        if (x <= n) {
          order[i] = x;
          break;
        }
      }
      if (i < 0) break;
      for (i++; i < n-1; i++) {
        flags[i] = flags[i-1] | (0x1 << (order[i-1]-2));
        int x = 2;
        for (; x <= n; x++) {
          if ((flags[i] & (0x1 << (x-2))) == 0) break;
        }
        order[i] = x;
      }
    }
    System.out.println(answer);
  }
}

競技後に解説を見て、順列の列挙をするスマートなアルゴリズムを知りました。それを使って後日JavaScriptで書き直しました。順列列挙は「順列の全探索をするプログラム」でC++, Scala, Ruby, Python, C言語, Java, JavaScript, Elixirでも書きました。

function next_permutation(arr) {
    const len = arr.length;
    let left = len - 2;
    while (left >= 0 && arr[left] >= arr[left+1]) left--;
    if (left < 0) return false;
    let right = len - 1;
    while (arr[left] >= arr[right]) right--;
    { const t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
    left++;
    right = len - 1;
    while (left < right) {
        { const t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
        left++;
        right--;
    }
    return true;
}

const lines = require('fs').readFileSync('/dev/stdin', 'utf8').split("\n");
const [n, k] = lines[0].split(" ").map(s => Number(s));
const ts = [];
for (let i = 0; i < n; i++) {
    ts.push(lines[i + 1].split(" ").map(s => Number(s)));
}
const n1 = n - 1;
const arr = [];
for (let i = 1; i < n; i++) arr.push(i);
let answer = 0;
do {
    let cost = 0;
    let prev = 0;
    for (let i = 0; i < n1; i++) {
        const curr = arr[i];
        cost += ts[prev][curr];
        prev = curr;
    }
    cost += ts[prev][0];
    if (cost == k) answer++;
} while (next_permutation(arr));

console.log(answer);

D - Water Heater

問題へのリンク

最初Scalaで書いたもののWAになってしまいました。WAの原因はすぐに気がついたものの、WAのほかによく見るとTLEも含まれていました。Scalaでは処理速度が厳しいかと思い、Javaで書き直してACを取りました。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    int w = sc.nextInt();
    var list = new int[2 * n][2];
    for (int i = 0; i < n; i++) {
      int s = sc.nextInt();
      int t = sc.nextInt();
      int p = sc.nextInt();
      list[2 * i][0] = s;
      list[2 * i][1] = p;
      list[2 * i + 1][0] = t;
      list[2 * i + 1][1] = -p;
    }
    java.util.Arrays.sort(list, java.util.Comparator.comparingInt(x -> x[0]));
    long max = 0;
    long curr = 0;
    int prevTime = 0;
    int n2 = 2 * n;
    for (int i = 0; i < n2; i++) {
      int time = list[i][0];
      int delta = list[i][1];
      if (time != prevTime) {
        if (curr > max) max = curr;
        prevTime = time;
      }
      curr += delta;
    }
    if (curr > max) max = curr;
    if (max > w) {
      System.out.println("No");
    } else {
      System.out.println("Yes");
    }
  }
}

競技後にScalaのコードを改善して、ScalaでもAC取れました。処理速度改善をした結果、極めてJavaっぽいScalaになってしまいました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n, w = sc.nextInt();
  val n2 = n * 2;
  val list = new Array[(Int, Int)](n2);
  {
    var i: Int = 0;
    while (i < n) {
      val s, t, p = sc.nextInt();
      list(2*i  ) = (s, p);
      list(2*i+1) = (t, -p);
      i += 1;
    }
  }
  val list2 = list.sortBy(_._1);
  var max: Long = 0;
  {
    var curr: Long = 0;
    var prevTime: Int = -1;
    var i: Int = 0;
    while (i < n2) {
      val (time, delta) = list2(i);
      if (time != prevTime) {
        if (curr > max) {
          max = curr;
        }
        prevTime = time;
      }
      curr += delta;
      i += 1;
    }
    if (curr > max) {
      max = curr;
    }
  }
  if (max > w) {
    println("No");
  } else {
    println("Yes");
  }
}

E - Queen on Grid

問題へのリンク

競技中は処理高速化の手法を思いつかず、TLEのまま時間切れとなってしまいました。競技後に解説を読んで書いたのが以下のJavaコードです。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    int m = 1_000_000_007;

    var sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    var ss = new boolean[h*w];
    for (int i = 0; i < h; i++) {
      var t = sc.next();
      for (int j = 0; j < w; j++) {
        if (t.charAt(j) == '#') ss[w*i+j] = true;
      }
    }

    var table  = new int[h*w];
    var table1 = new int[h*w];
    var table2 = new int[h*w];
    var table3 = new int[h*w];
    table[0] = 1;
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        int g = w*i+j;
        if (ss[g]) continue;
        if (g == 0) continue;
        long x = 0;
        if (i > 0) {
          int k = g - w;
          int x1 = (table[k] + table1[k]) % m;
          table1[g] = x1;
          x += x1;
        }
        if (j > 0) {
          int k = g - 1;
          int x2 = (table[k] + table2[k]) % m;
          table2[g] = x2;
          x += x2;
        }
        if (i > 0 && j > 0) {
          int k = g - w - 1;
          int x3 = (table[k] + table3[k]) % m;
          table3[g] = x3;
          x += x3;
        }
        table[g] = (int)(x % m);
      }
    }
    int answer = table[h*w-1];
    System.out.println(answer);
  }
}