AtCoder参戦日記 ARC108 2020/11/21 10回目

AtCoderの10回目の参加となった2020/11/21のARC108の記録です。10か月も下書きのまま放置してしまっていましたが、久しぶりにAtCoderの感を取り戻したくて復習がてらブログ記事に公開します。

65分ほどでA, B, Dの3完でした。Cはとっかかりが全然わからず、早々にDに進みました。そのあとCに戻ってコードを書き始めましたが、時間切れとなりました。

パフォーマンス値が過去最高の1979になり、緑の上位半分に昇格しました。実力が上がってきたというわけではなく、今回はたまたま自分にとって簡単な問題だっただけなのだと思います。

問題	結果	言語	競技後
A	AC	Ruby	JavaScript
B	AC	Java
C
D	AC	Java
E
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
2020/11/21 #10	ARC108	3完 / 1979	Ruby, Java, Java

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

A - Sum and Product

問題へのリンク

最初は全探索しようと思って処理速度が必要だと思い、Javaで書き始めました。しかし全探索はだめなんじゃないかと思い、2次方程式で解を求める方法に変更しました。その方法で提出したものの、10の12乗をさらに2乗するところで long では桁数が足りなくてWAになってしまいました。Javaで手っ取り早い解決策が思いつかなかったので、整数の桁数を気にしなくてもよいRubyで書き直しました。

あとで解説を読んで全探索でもよかったのだとわかりました。

↓WAになったJavaのコード。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    long s = sc.nextLong();
    long p = sc.nextLong();

    long sq = s * s - 4 * p;
    int sqrt = (int)(Math.sqrt((double)p));
    if (sqrt * sqrt != sq) {
      sqrt++;
      if (sqrt * sqrt != sq) {
        System.out.println("No");
        return;
      }
    }
    if ((s - sqrt) % 2 == 0) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}

↓ACをとったRubyのコード。

s, p = gets.strip.split(" ").map(&:to_i)

sq = s * s - 4 * p
sqrt = Integer.sqrt(sq)
if sqrt * sqrt != sq
  puts("No")
  exit(0)
end
if (s - sqrt) % 2 == 0
  puts("Yes")
else
  puts("No")
end

後日JavaScriptでも書きました。Rubyと同じロジックでは正しい答えを出せず、全探索しました。Rubyと同じロジックができなかった理由は、巨大な整数を扱えないためと思われます。

const lines = require('fs').readFileSync('/dev/stdin', 'utf8').split("\n");
const [s, p] = lines[0].split(" ").map(s => Number(s));

const max = Math.sqrt(p);
for (let i = 1; i <= max; i++) {
    if (i * (s - i) == p) {
        console.log("Yes");
        process.exit(0);
    }
}
console.log("No");

B - Abbreviate Fox

問題へのリンク

この問題でも処理速度が必要だと思い、Javaで書きました。

長大な文字列を頻繁に書き換えながらの処理なので、Stringではなくchar<>を使いました。

size2という変数は処理速度を少しでも稼ぐためですが、意味があったのかどうかは不明です。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    var str = sc.next();
    var arr = new char[n+2];
    for (int i = 0; i < n; i++) {
      arr[n-1-i] = str.charAt(i);
    }
    int size = n;
    int size2 = n;
    int i = n-3;
    while (i >= 0) {
      if (arr[i] == 'x' && arr[i+1] == 'o' && arr[i+2] == 'f') {
        for (int j = i+3; j < size2; j++) {
          arr[j-3] = arr[j];
        }
        size -= 3;
        size2 -= 3;
      } else if (arr[i] == 'o' || arr[i] == 'f') {
        // nothing
      } else {
        size2 = i;
      }
      i--;
    }
    System.out.println(size);
  }
}

C - Keep Graph Connected

問題へのリンク

最初はぜんぜんわからず、Dに先に進みました。DのあとにCに戻ってコードを書き始めたものの、時間切れとなりました。

D - AB

問題へのリンク

規則性を見つければ難しくない問題です。ここまでの惰性でJavaになりました。

import java.util.Scanner;

class Main {
  static int m = 1_000_000_007;

  static int pow2(int n) {
    long s = 1;
    long a = 2;
    while (n > 0) {
      if ((n & 1) != 0) s = s * a % m;
      a = a * a % m;
      n >>= 1;
    }
    return (int)s;
  }

  static int com(int n) {
    int s1 = 1;
    int s2 = 1;
    for (int i = 0; i < n; i++) {
      int t = (s1 + s2) % m;
      s1 = s2;
      s2 = t;
    }
    return s2;
  }

  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    boolean caa = (sc.next().equals("B"));
    boolean cab = (sc.next().equals("B"));
    boolean cba = (sc.next().equals("B"));
    boolean cbb = (sc.next().equals("B"));
    int answer = 0;
    if (n == 2) {
      answer = 1;
    } else if (cab && cbb) {
      // ABBB
      answer = 1;
    } else if (!cab && !caa) {
      // AAAB
      answer = 1;
    } else if (cab && !cba) {
      answer = pow2(n-3);
    } else if (cab) {
      answer = com(n-3);
    } else if (!cab && cba) {
      answer = pow2(n-3);
    } else if (!cab) {
      answer = com(n-3);
    }
    System.out.println(answer);
  }
}