AtCoder参戦日記 ARC110 2020/12/05 11回目

AtCoder

AtCoderの11回目の参加となった2020/12/05のARC110の記録です。9か月も下書きのまま放置してしまっていましたが、前回記事に引き続き、AtCoderの感を取り戻すための復習記事です。

65分ほどでA, B, Cの3完でした。

20分ぐらいでA, Bまで終わったところで、C以降がとても難しそうだったので、解けそうな問題を探そうと、C, D, Eの問題を読みました。C -> E -> D の順に取り掛かろうと判断し、Cを65分ぐらいでできました。残り時間はEを考えたものの、さっぱりわからずあきらめました。

パフォーマンスは1562で前回に続き奇跡的にいい成績でした。ABCよりもARCのほうがパフォーマンスが出やすい気がします。

問題 結果 言語 競技後
A AC Ruby
B AC Scala
C AC Java
D
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
2020/12/05 11 ARC110 3完 / 1562 Ruby, Scala, Java

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

A - Redundant Redundancy

問題へのリンク

n = gets.strip.to_i

p = 1
i = n
while i >= 2
  p = p.lcm(i)
  i -= 1
end

puts(p + 1)

B - Many 110

問題へのリンク

かなりの力技です。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val t = sc.next();

  val c = 10_000_000_000L;

  val answer = if (t == "1") {
    c * 2;
  } else if (t == "0") {
    c;
  } else if (t == "00") {
    0;
  } else if (t == "01") {
    c - 1;
  } else if (t == "10") {
    c;
  } else if (t == "11") {
    c;
  } else {
    val pre = t.substring(0, 3);
    val n3 = n / 3;
    val nm = n % 3;
    if ((1 until n3).exists(i => !t.startsWith(pre, i * 3))) {
      0;
    } else {
      val suf = t.substring(n3 * 3);
      if (!pre.startsWith(suf)) {
        0;
      } else {
        if (pre == "110") {
          if (nm == 0) {
            c - n3 + 1;
          } else {
            c - n3;
          }
        } else if (pre == "101") {
          c - n3;
        } else if (pre == "011") {
          if (nm <= 1) {
            c - n3;
          } else {
            c - n3 - 1;
          }
        } else {
          0;
        }
      }
    }
  }
  println(answer);
}

もう少しシンプルな方法はないかと、他の人の回答を参考に書き直したのが以下です。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val t = sc.next();

  val c = 10_000_000_000L;

  val answer = if (t == "1") {
    c * 2;
  } else if (t == "11") {
    c;
  } else {
    if (("110" * (n / 3 + 3)).indexOf(t) < 0) {
      0;
    } else {
      def count(str: String, pattern: String): Int = {
        @scala.annotation.tailrec
        def sub(offset: Int, result: Int): Int = {
          val p = str.indexOf(pattern, offset);
          if (p < 0) result else sub(p + 1, result + 1);
        }
        sub(0, 0);
      }
      if (t.endsWith("0")) {
        c - count(t, "0") + 1;
      } else {
        c - count(t, "0");
      }
    }
  }
  println(answer);
}

C - Exoswap

問題へのリンク

コンテスト当時にAC取ったコードです。

class Main {
  public static void main(String[] args) {
    var sc = new java.util.Scanner(System.in);
    int n = sc.nextInt();
    var ps = new int[n];
    for (int i = 0; i < n; i++) {
      ps[i] = sc.nextInt() - 1;
    }

    var fsa1 = new boolean[n];
    var fsa2 = new boolean[n];
    var fsb1 = new boolean[n];
    var fsb2 = new boolean[n];
    for (int i = 0; i < n; i++) {
      var p = ps[i];
      if (p > i) {
        for (int j = i; j < p; j++) {
          if (fsa1[j]) {
            System.out.println(-1);
            return;
          }
          fsa1[j] = true;
        }
        fsa2[i] = true;
      } else if (p < i) {
        for (int j = i-1; j >= p; j--) {
          if (fsb1[j]) {
            System.out.println(-1);
            return;
          }
          fsb1[j] = true;
        }
        fsb2[p] = true;
      } else {
        System.out.println(-1);
        return;
      }
    }
    for (int i = 0; i < n-1; i++) {
      if (!fsa1[i]) {
        System.out.println(-1);
        return;
      }
      if (!fsb1[i]) {
        System.out.println(-1);
        return;
      }
    }
    for (int i = n-2; i >= 0; i--) {
      if (fsa2[i]) {
        System.out.println(i+1);
      }
    }
    for (int i = 0; i < n-1; i++) {
      if (!fsa2[i]) {
        System.out.println(i+1);
      }
    }
  }
}

これを9か月後のいま見ても、よくわからなかったので、もう一度書き直しました。1時間ではできなかったし、なかなかバグが取れず大量にWAを出してしまいました。衰えています。

class Main {
  public static void main(String[] args) {
    var sc = new java.util.Scanner(System.in);
    int n = sc.nextInt();
    var ps = new int[n];
    for (int i = 0; i < n; i++) {
      ps[i] = sc.nextInt() - 1;
    }

    var f1 = new boolean[n]; // 右を先に交換
    var f2 = new boolean[n]; // 左を先に交換

    for (int i = 0; i < n; i++) { // 0 - 3
      var p = ps[i];
      if (p < i) {
        for (int j = p + 1; j < i; j++) {
          if (f2[j]) {
            System.out.println(-1);
            return;
          }
          f1[j] = true;
        }
        if (p > 0) {
          if (f1[p]) {
            System.out.println(-1);
            return;
          }
          f2[p] = true;
        }
        if (i < n - 1) {
          if (f1[i]) {
            System.out.println(-1);
            return;
          }
          f2[i] = true;
        }
      } else if (p > i) {
        for (int j = i + 1; j < p; j++) {
          if (f1[j]) {
            System.out.println(-1);
            return;
          }
          f2[j] = true;
        }
        if (i > 0) {
          if (f2[i]) {
            System.out.println(-1);
            return;
          }
          f1[i] = true;
        }
        if (p < n - 1) {
          if (f2[p]) {
            System.out.println(-1);
            return;
          }
          f1[p] = true;
        }
      } else {
        System.out.println(-1);
        return;
      }
    }

    int i = 1;
    while (i < n) {
      if (f1[i]) {
        int j = i + 1;
        while (f1[j]) {
          j++;
        }
        int j0 = j;
        while (j >= i) {
          System.out.println(j);
          j--;
        }
        i = j0 + 1;
      } else {
        System.out.println(i);
        i++;
      }
    }

  }