AtCoder参戦日記 ABC181 2020/11/01 #7 ― 緑色になる

AtCoder

AtCoderの7回目の参加となった2020/11/01のABC181の記録です。

今回初めて、いまさらではありますが、atcoder-cliを使用しました。

30分ほどで4完でした。残り1時間あまり5問目に取り組みましたが、疲れてきてコードを書ききれませんでした。

問題 結果 言語
A ○ C++ (競技後にRuby, Elixir)
B ○ Scala (競技後にRuby, JavaScript)
C ○ Java
D ○ Java
E 競技後にScala
F

過去の参戦記録

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

※結果欄は、時間内にAC取れた問題数とパフォーマンスです。

緑色になる

今回のコンテストで緑色になりました。伸びが緩やかになってきたので、果たして次の色に進めるのかはわかりません。しばらくがんばろうと思います。

f:id:suzuki-navi:20201107114149p:plain

ここまでの感想を手短に。

難しい問題を解けるかどうかを競うものだと思ってましたが、実際にやってみると、AC(正解)取れる程度の品質のコードをいかに手早く書くかというのも重要ですね。前半の解ける問題は時間勝負です。ACを取れればいいので、競技中はきれいなコード、読みやすいコードよりも書くのが早いコードになります。競技プログラミング特有のノウハウが必要です。

後半の難しい問題をどう攻略するかはもう少し先の話になりそうです。

競技プログラミングで使用する言語は、ほとんどの人は1つかせいぜい2つに集約しているかと思いますが、私は言語の勉強を兼ねて、意識的にいろいろな言語を使うようにしています。Scalaが私にとって一番書きやすいので、気を抜けば全部Scalaになってしまいます。問題ごとにScala以外どの言語で書けるかを考える時間が発生しています。

言語の使い分けとしては最近は↓こんな感じです。

  • ループや配列すら不要な単純な問題は勉強兼ねて馴染みのない言語
  • 計算量が多く処理速度が不安な問題
  • ロジックが複雑な問題

言語を迷い、さらに書きながら言語でわからないところを調べる時間が発生しているので、時間勝負の局面では損をしています。言語が分散することで、テンプレート整備の投資効率が悪いです。

A - Heavy Rotation

問題へのリンク

1問目はRubyの勉強のためにRubyにしようと思ってたのですが、剰余の計算がパッと書けなくて、C++になりました。

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

int main() {
  int n;
  cin >> n;
  if (n % 2 == 0) {
    cout << "White\n";
  } else {
    cout << "Black\n";
  }
}

後日、以下の自分の記事を見てRubyとElixirで書きました。

n = gets.strip.to_i
if n % 2 == 0
  puts("White")
else
  puts("Black")
end

defmodule Main do
  def main do
    n = IO.read(:line) |> String.trim() |> String.to_integer
    if rem(n, 2) == 0 do
      IO.puts("White")
    else
      IO.puts("Black")
    end
  end
end

B - Trapezoid Sum

問題へのリンク

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val abs = Array.fill(n)((sc.nextInt(), sc.nextInt()));
  val sum = abs.map { case (a, b) =>
    (b.toLong * (b + 1) - a.toLong * (a - 1)) / 2;
  }.sum;
  println(sum);
}

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

n = gets.strip.to_i
answer = 0
n.times do
  a, b = gets.strip.split(" ").map(&:to_i)
  answer += b * (b+1) - a * (a-1)
end
answer /= 2
puts(answer)

const input = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = input.split("\n");
const n = Number(lines[0]);
let answer = 0;
for (let i = 0; i < n; i++ ){
    const [a, b] = lines[i + 1].split(" ").map(s => Number(s));
    answer += b * (b+1) - a * (a-1);
}
answer /= 2;
console.log(answer);

C - Collinearity

問題へのリンク

3点選んでの外積が0かどうかのチェックを総当りで探します。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    var xys = new int[2 * n];
    for (int i = 0; i < n; i++) {
      xys[2 * i + 0] = sc.nextInt();
      xys[2 * i + 1] = sc.nextInt();
    }
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
          int x1 = xys[2 * j + 0] - xys[2 * i + 0];
          int x2 = xys[2 * k + 0] - xys[2 * i + 0];
          int y1 = xys[2 * j + 1] - xys[2 * i + 1];
          int y2 = xys[2 * k + 1] - xys[2 * i + 1];
          if (x1 * y2 - x2 * y1 == 0) {
            System.out.println("Yes");
            System.exit(0);
          }
        }
      }
    }
    System.out.println("No");
  }
}

D - Hachi

問題へのリンク

きれいな解き方がわからず、力技で解いてます。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    var s = sc.next();
    int len = s.length();
    var table = new int[10];
    for (int i = 0; i < len; i++) {
      int c = (int)(s.charAt(i) - '0');
      table[c]++;
    }
    int is = 0;
    int ie = 125;
    if (len == 1) {
      ie = 2;
    } else if (len == 2) {
      is = 2;
      ie = 13;
    } else {
      is = 13;
      ie = 125;
    }
    for (int i = is; i < ie; i++) {
      String s2 = String.format("%d", 8 * i);
      int s2len = s2.length();
      var table2 = new int[10];
      for (int j = 0; j < s2len; j++) {
        int c = (int)(s2.charAt(j) - '0');
        table2[c]++;
      }
      boolean f = true;
      for (int j = 0; j < 10; j++) {
        if (table[j] < table2[j]) {
          f = false;
        }
      }
      if (f) {
        System.out.println("Yes");
        System.exit(0);
      }
    }
    System.out.println("No");
  }
}

E - Transformable Teacher

問題へのリンク

コードが複雑になりすぎたら、落ち着いて一歩引いてみて、もう少しシンプルな解法がないかを考えてみることが大事。全体の解法があっていても、細かいところが改善できる場合もある。自分への戒めです。

以下コードは、後日落ち着いて一歩引いてみて考えたら書けたコードです。解説等見ずに一発でAC取れました。競技中はコードが複雑になってきて、疲れて書ききれませんでした。

Scalaの処理速度が不安だったので、極めてJavaっぽいコードです。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n, m = sc.nextInt();
  val size = n + m;
  val hs = IndexedSeq.fill(n)(sc.nextInt());
  val ws = IndexedSeq.fill(m)(sc.nextInt());
  val list: Array[(Int, Boolean)] = (hs.map(h => (h, true)) ++ ws.map(w => (w, false))).sortBy(_._1).toArray;
  val dis: Array[Int] = new Array[Int](size);
  val flags: Array[Boolean] = new Array[Boolean](size);
  var w_index: Int = -1;
  var minimumCost: Long = 0;
  var cost: Long = 0;
  {
    var f: Boolean = true;
    if (!list(0)._2) w_index = 0;
    (1 until size).foreach { i =>
      dis(i) = list(i)._1 - list(i-1)._1;
      flags(i) = f;
      if (f) cost += dis(i);
      if (list(i)._2) {
        f = !f;
      } else if (w_index < 0) {
        w_index = i;
        f = !f;
      }
    }
    minimumCost = cost;
  }
  while (w_index < size) {
    var w_index2 = w_index + 1;
    while (w_index2 < size && list(w_index2)._2) w_index2 += 1;
    if (w_index2 < size) {
      var i: Int = w_index + 1;
      while (i <= w_index2) {
        if (flags(i)) {
          flags(i) = false;
          cost -= dis(i);
        } else {
          flags(i) = true;
          cost += dis(i);
        }
        i += 1;
      }
      if (cost < minimumCost) minimumCost = cost;
    }
    w_index = w_index2;
  }
  println(minimumCost);
}