AtCoder参戦日記 HHKB2020 2020/10/10 #5

AtCoder

AtCoderの5回目の参加となった2020/10/10 HHKB2020の記録です。

3完でした。

4問目(D)は解法はわかったものの、コードを書ききれずにあきらめてしまいました。

5問目(E)は後日解説を見ずに解けました。競技中Dを飛ばして先にEをやっていればよかったです。

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

過去の記録

A - Keyboard

問題

安易にScalaやJavaにせずに、他言語の練習のために1問目は他の言語にしようと思ってます。開始前にRubyのテンプレートを準備していたものの、文字の扱いが瞬時にはわからなくて、とっさにC言語になりました。入力部分だけC++です。

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

int main() {
  string s, t;
  cin >> s >> t;

  if (s[0] == 'Y') {
    printf("%c\n", (char)(t[0] - 32));
  } else {
    printf("%c\n", t[0]);
  }

}

B - Futon

問題

なにも考えずにScalaで書きました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val h, w = sc.nextInt();
  val ss = IndexedSeq.fill(h)(sc.next());
  val answer = (0 until h).map { i =>
    (0 until (w-1)).count { j =>
      ss(i)(j) == '.' && ss(i)(j+1) == '.'
    }
  }.sum + (0 until (h-1)).map { i =>
    (0 until w).count { j =>
      ss(i)(j) == '.' && ss(i+1)(j) == '.'
    }
  }.sum;
  println(answer);
}

C - Neq Min

問題

Scalaの処理速度が問題になるのかわからず、念のためJavaにしました。

import java.util.Scanner;
 
class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    var n = sc.nextInt();
    var ps = new int[n];
    for (int i = 0; i < n; i++) {
      ps[i] = sc.nextInt();
    }
    var flags = new boolean[n + 1];
    int prev = 0;
    for (int i = 0; i < n; i++) {
      int p = ps[i];
      if (p <= n) {
        flags[p] = true;
      }
      while (true) {
        if (!flags[prev]) {
          System.out.printf("%d\n", prev);
          break;
        }
        prev++;
      }
    }
  }
}

D - Squares

問題

これができなかったのは悔しかったです。競技中は細かい場合分けをして組み合わせ数を計算しようとして、コードを書ききれませんでした。

後で他の人の回答を見て、解法を理解しました。

解法がわかってしまえば、非常にシンプルな計算だけで済みます。整数演算に桁数を気にしなくてもよいRubyで書きました。

m = 1_000_000_007
t = gets.strip.to_i
t.times do
  n, a, b = gets.strip.split(" ").map(&:to_i)
  if n < a + b
    puts(0)
  else
    s1 = (n - a + 1) * (n - b + 1)
    s2 = (n - a - b + 2) * (n - a - b + 1)
    answer = (s1 * s1 - (s1 - s2) * (s1 - s2)) % m
    puts(answer)
  end
end

E - Lamps

問題

後日解説を見ずに解いたJavaのコードです。そんなに時間かからなかったので、競技中Dを飛ばして先にEをやっていればよかったです。

import java.util.Scanner;

class Main {
  private static int m = 1_000_000_007;
  private static int[] powTable;
  public static void initPow(int k, int m) {
    powTable = new int[k + 1];
    int p = 1;
    powTable[0] = p;
    for (int i = 1; i <= k; i++) {
      p = (int)(2L * p % m);
      powTable[i] = p;
    }
  }

  public static void main(String[] args) {
    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[i][j] = true;
        }
      }
    }
    int k = 0;
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        if (!ss[i][j]) k++;
      }
    }
    initPow(k, m);
    int max = powTable[k];
    int sum = 0;
    var iwTable = new int[h][w];
    for (int i = 0; i < h; i++) {
      int jw = -1;
      for (int j = 0; j < w; j++) {
        if (ss[i][j]) {
          jw = -1; continue;
        }
        if (jw < 0) {
          jw = 0; for (int j2 = j; j2 < w && !ss[i][j2]; j2++) jw++;
        }
        int iw = iwTable[i][j];
        if (iw == 0) {
          for (int i2 = i+1; i2 < h && !ss[i2][j]; i2++) iw++;
          for (int i2 = i; i2 < h && !ss[i2][j]; i2++) iwTable[i2][j] = iw;
        }
        sum = (int)(((long)m + sum + max - powTable[k - (iw + jw)]) % m);
      }
    }
    System.out.println(sum);
  }
}