AtCoder参戦日記 ABC178 2020/09/13 #2 ― 奇跡的な好成績

AtCoderの2回目の参加となった2020/09/13のABC178の記録です。約1ヶ月前のことです。

5問目まで解法を偶然すぐに思いつくことができましたので、奇跡的に成績がよかった回となりました。

正答を出せた5問で使った言語はPythonScalaScalaC++Scalaでした。簡単な問題はPythonが短く書けてよさそう。ロジックが単純に繰り返し処理が中心の場合はC++もよさそう。

問題 結果 言語
A Python
B Scala
C Scala
D C++
E Scala
F

A - Not

問題

短く書けそうなPythonにしました。

a = int(input())
print(1 - a)

B - Product Max

問題

Pythonで完結に書ける自信がなく、パッと書けそうなScalaになりました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val a, b, c, d = sc.nextLong();
  val answer = List(a * c, a * d, b * c, b * d).max;
  println(answer);
}

C - Ubiquity

問題

惰性でScalaで書きました。

以下のコードはコンテスト中に書いたコードですが、自分にとってあまりきれいでなく、のちにElixirでABC178のC Ubiquityを解いてみるの記事でElixirとScalaで書き直しています。

object Main extends App {
  val m = 1000000007;
  def pow(a: Long, b: Int): Long = {
    var x: Long = 1;
    var a2: Long = a;
    var b2: Int = b;
    while (b2 > 0) {
      if ((b2 & 1) != 0) {
        x = x * a2 % m;
      }
      a2 = a2 * a2 % m;
      b2 = b2 >> 1;
    }
    x;
  }
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val a1 = pow(10, n); // all
  val a2 = pow(8, n);  // 0も9も存在しない
  val a3 = (pow(9, n) + m - a2) % m;  // 0は存在するけど9は存在しない
  val answer = (a1 + 3L * m - 2L * a3 - a2) % m;
  println(answer);
}

D - Redistribution

問題

ここで唐突にC++を選択しました。

あとで解説を見たら、2重ループにしなくてももうちょっと簡単に解ける方法があったようです。

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

int main() {
  long m = 1000000007;

  int s;
  cin >> s;

  if (s < 3) {
    cout << 0 << endl;
    return 0;
  }

  vector<long> series(s + 1);
  series[0] = 0;
  series[1] = 0;
  series[2] = 0;
  for (int i = 3; i <= s; i++) {
    long a = 1;
    for (int j = 0; j <= i - 3; j++) {
      a += series[j];
      a = a % m;
    }
    series[i] = a;
  }
  long answer = series[s];
  cout << answer << endl;
}

E - Dist Max

問題

解き方をちょっと悩みましたが、45度傾いた長方形で囲んで長いほうの辺の長さを求めればいいだけだと気が付けました。

簡潔に書ける言語としてScalaを選択しました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val xys = Array.fill(n)((sc.nextInt, sc.nextInt));
  val xys2 = xys.map { case (x, y) => (x + y, x - y) }
  val x_min = xys2.map(_._1).min;
  val x_max = xys2.map(_._1).max;
  val y_min = xys2.map(_._2).min;
  val y_max = xys2.map(_._2).max;
  val answer = (x_max - x_min) max (y_max - y_min);
  println(answer);
}

F - Contrast

問題

Yes/Noはわかるけど、そのあとの解法が思いつきませんでした。コンテスト中は無理やりScalaで書いたのですが、失敗するテストケースがあり、そのままわからずじまい。