AtCoder Beginner Contest 197(Rated範囲外)

ABC

コンテスト前のレート：2030
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：311位（2100点、103分59秒）


DCBAEFの順で解こうとするが、Dがすぐにできる気がしなかったので、CBADEFになった。

A - Rotate

問題

思考過程
  1. S_1、S_2、S_0の順で出力する。最後だけ一応改行付き。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();

        System.out.print(s[1]);
        System.out.print(s[2]);
        System.out.println(s[0]);
    }
}

CBAと解いた時点で11分14秒＋0ペナ。235位。
（A問題だけだと0分47秒）


B - Visibility

問題

思考過程
  1. (X, Y)から4方向に向かって'.'が続く限りカウント。続かなくなったら探索打ち切り。
  2. (X, Y)を4回数えているので、3を引く。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int x = sc.nextInt() - 1;
        int y = sc.nextInt() - 1;
        char[][] s = new char[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();

        int ans = 0;
        for (int i = x; i < h; i++) {
            if (s[i][y] == '.') {
                ans++;
            } else {
                break;
            }
        }
        for (int i = x; i >= 0; i--) {
            if (s[i][y] == '.') {
                ans++;
            } else {
                break;
            }
        }
        for (int i = y; i < w; i++) {
            if (s[x][i] == '.') {
                ans++;
            } else {
                break;
            }
        }
        for (int i = y; i >= 0; i--) {
            if (s[x][i] == '.') {
                ans++;
            } else {
                break;
            }
        }
        System.out.println(ans - 3);
    }
}

CBと解いた時点で10分27秒＋0ペナ。219位。
（B問題だけだと3分26秒）


C - ORXOR

問題
ビット全探索で制約が20なのは厳しく感じる。17～18程度にしてほしさがある。

思考過程
  1. 一瞬どうすればいいのかさっぱりだったが、制約が小さいので区切り方を全部試せる。
  2. N-1箇所を区切るかどうか、2^{N-1}通り全探索する。
  3. 各区切り方の中では、ORやXORの性質等は何も考えずに問題文の通りの計算を行う。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int end = 1 << (n - 1);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < end; i++) {
            int xor = 0;
            int or = a[0];
            for (int j = 0; j < n - 1; j++) {
                // j、j+1の間で区切る場合
                if ((i >> j & 1) == 1) {
                    xor ^= or;
                    or = 0;
                }
                or |= a[j + 1];
            }
            xor ^= or;
            ans = Math.min(ans, xor);
        }
        System.out.println(ans);
    }
}

Cだけ解いた時点で7分01秒＋0ペナ。812位。


D - Opposite

問題
下記4.でr倍するのを忘れていてサンプルが合わず、数分悩んだ。

思考過程
  • 下図をイメージしながら、求められるところを順に求めていく。
    f:id:ks2m:20210328003612p:plain
  1. 正N角形の外接円の中心の座標(rx, ry)は、p_0とp_{N/2}の中点。
  2. p_0の角度at（ラジアン単位）はatan2関数で求められる。
  3. p_0とp_1の間の角度dは、360度（2\piラジアン）をNで割った値。
  4. 角度がわかれば、cosでx座標、sinでy座標が求められる。（cosでわかるのは、半径→x軸成分の比率なので、半径を掛ける）
  5. 外接円の半径rは、p_0と中心の座標を元に三平方の定理で求められる。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int x2 = sc.nextInt();
        int y2 = sc.nextInt();
        sc.close();

        // 1
        double rx = (x + x2) / 2.0;
        double ry = (y + y2) / 2.0;
        // 2
        double at = Math.atan2(y - ry, x - rx);
        // 3
        double d = Math.PI * 2 / n;

        // 5
        double r = Math.hypot(x - rx, y - ry);
        // 4
        double ax = rx + Math.cos(at + d) * r;
        double ay = ry + Math.sin(at + d) * r;
        System.out.println(ax + " " + ay);
    }
}

ここまで23分44秒＋0ペナ。264位。


E - Traveler

問題

思考過程
  1. 各色ごとに、座標が最も小さいものと大きいものだけを考慮する。
  2. ある色についての最適な回収順は、スタート地点→最小→最大か、スタート地点→最大→最小のいずれか。
  3. 前後の色を考慮しても、上記以外の移動方法で得するということはなさそう。
    　
  4. 各色について、上記2通りの移動方法を、スタート地点2通り（前色の最小と最大）試して良い方の値だけ残すようにしていく。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int inf = 1001001001;
        // 1
        int[] max = new int[n];
        int[] min = new int[n];
        Arrays.fill(max, -inf);
        Arrays.fill(min, inf);
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            int x = Integer.parseInt(sa[0]);
            int c = Integer.parseInt(sa[1]) - 1;
            max[c] = Math.max(max[c], x);
            min[c] = Math.min(min[c], x);
        }
        br.close();

        long il = 0; // 前色の座標最小
        long ir = 0; // 前色の座標最大
        long al = 0; // 前色を座標最小で終えた時の最小値
        long ar = 0; // 前色を座標最大で終えた時の最小値
        for (int i = 0; i < n; i++) {
            // 色iがない場合スキップ
            if (min[i] == inf) {
                continue;
            }
            long nl = Math.min(al + Math.abs(il - max[i]) + Math.abs(max[i] - min[i]),  // 前色最小→最大→最小
                               ar + Math.abs(ir - max[i]) + Math.abs(max[i] - min[i])); // 前色最大→最大→最小
            long nr = Math.min(al + Math.abs(il - min[i]) + Math.abs(max[i] - min[i]),  // 前色最小→最小→最大
                               ar + Math.abs(ir - min[i]) + Math.abs(max[i] - min[i])); // 前色最大→最小→最大
            il = min[i];
            ir = max[i];
            al = nl;
            ar = nr;
        }
        long ans = Math.min(al + Math.abs(il), ar + Math.abs(ir)); // 0に戻る
        System.out.println(ans);
    }
}

ここまで34分04秒＋0ペナ。106位。



F問題は解けず。
頂点1とNから同時にBFS（それぞれで作れる文字列のSetのようなものを持ちながら）をするのを、多分TLEなりMLEなりするだろうなと思いながらまったりと実装してみていた。
まったりしすぎて間に合わず、終了10分後くらいに一応提出。

本当に何の工夫もしなければ、毎回進むのと戻るので保持する文字列数が最低2倍（頂点の次数倍）になっていってしまうと思ったので、頂点1側かN側か、最低片方は未訪問頂点に進んだ場合の文字列だけ残すような枝刈りを入れてみたつもりだったが、32AC、13WA、1TLEだった。



最終結果：ABCDEの5完、34分04秒、379位、パフォーマンス1938相当
レート変動：2030（Unrated）


とりあえず最近のABC4完止まり地獄を4回目で脱出し、概ね順当な結果は出せた。（自分の本当の実力はやっぱり1900程度がいいところだと思うので）

黄色になる直前1ヶ月半ほどの間は青diff以下を全く落としていなかったのに、黄色になった翌週くらいから青diff以上は全滅の状態。
この調子だと、ARCやAGCに青diffが出た時点で青落ちしそう。
現状はたまたま茶diffだらけで早解きに負けていないので、なんとか生き延びているが。