M-SOLUTIONS プロコンオープン 2020

A - Kyu in AtCoder
- 思考過程
B - Magic 2
- 思考過程
- ペナルティ
C - Marks
- 思考過程
D - Road to Millionaire
- 思考過程
E - M's Solution
- 思考過程
F - Air Safety
- 思考過程

コンテスト前のレート：1805
レート通りのパフォーマンスが得られる順位：493位

A - Kyu in AtCoder

問題
こういう簡単な問題でも、解説を見たら下手さに気付かされる。

思考過程

if文を書くか計算するか。 $3$ ～ $4$ 個くらいまでならif文にしてもいいが、 $8$ 個はだるいと思ったので計算することにする。
約 $2000$ から $X$ を引いて $200$ で割れば、一発で求められそう。
$1799$ と $1800$ で商が変わるようにするためには、 $1999$ から引くと良さそう。
それだと $1800$ ～ $1999$ の場合に $0$ となるので割った後に $+1$ してもよいが、 $200$ 足して $2199$ から引くようにしても結果は同じ。
境界値を念入りにテストして提出する。

import java.util.Scanner;

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

        int ans = (2199 - x) / 200;
        System.out.println(ans);
    }
}

ここまで1分52秒＋0ペナ。719位。

B - Magic 2

問題
A問題に少し時間をかけ過ぎた焦りがあったのかも。
誤読というか問題文がまともに頭に入ってきていなかった。

思考過程

$K$ 個を $3$ つに分ける組み合わせを全探索する？
制約が小さいし判定するだけなので、重複とか気にせず $K^3$ 全探索しても問題ない。
$A$ を $X$ 回、 $B$ を $Y$ 回、 $C$ を $Z$ 回 $(0 \leq X, Y, Z \leq K)$ 操作するとし、 $X+Y+Z \leq K$ の場合に計算を行い、条件を満たすか判定する。

ペナルティ

計算をする部分を、 $A \times 2^X$ ではなく、 $A^X$ としたり $A^{X+1}$ としたりしていた。　→WA2回
ループ範囲が $0 \leq X, Y, Z \lt K$ になっていた。　→WA1回

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int k = sc.nextInt();
        sc.close();

        for (int x = 0; x <= k; x++) {
            for (int y = 0; y <= k; y++) {
                for (int z = 0; z <= k; z++) {
                    if (x + y + z <= k) {
                        int ax = a * (1 << x);
                        int by = b * (1 << y);
                        int cz = c * (1 << z);
                        if (ax < by && by < cz) {
                            System.out.println("Yes");
                            return;
                        }
                    }
                }
            }
        }
        System.out.println("No");
    }
}

ここまで10分25秒＋3ペナ。2866位。
ペナルティの影響で、C問題を通す直前には3721位まで下がったらしい。
もはや、4完でも比較的浅い傷で済むとかは期待できなそう。

C - Marks

問題
本当にこれだけでいいの？と少し不安になったが問題なかった。

思考過程

$i-1$ 学期の評点は、 $A_{i-K}$ ～ $A_{i-1}$ の積。
$i$ 学期の評点は、 $A_{i-K+1}$ ～ $A_i$ の積。
よって、 $A_{i-K}$ と $A_i$ を比較すれば大小関係がわかる。
$A_i$ に $0$ もマイナスもないので、上記の比較結果がそのまま大小関係にならないようなケースはない。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int k = Integer.parseInt(sa[1]);
        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = k; i < n; i++) {
            if (a[i - k] < a[i]) {
                pw.println("Yes");
            } else {
                pw.println("No");
            }
        }
        pw.flush();
    }
}

ここまで13分55秒＋3ペナ。1572位。

D - Road to Millionaire

問題
順位表を見たら水色でも4分程度で通している人がいたので、結構単純なのだろうと思って取り掛かった。

思考過程

例１ではわざわざ $2$ 日に分けて取引を行ったりしているが、取引を中途半端に行うよりも、必ず買えるだけ買うか、売れるだけ売るかした方が、利益or損失が増える。
DPでできそうな雰囲気も感じたが、ぱっと書けそうにない。
考え方を変えて、どんな時に買ってよいかを考えると、 $A_i \lt A_j (i \lt j)$ となる場合、 $i$ 日目に買って $j$ 日目に売れば利益を出せる。
ただし、 $A_i \gt A_k \lt A_j (i \lt k \lt j)$ となる場合は、 $i$ 日目はスルーして $k$ 日目に買った方が得する。
　
突き詰めていくと、買いについては、連続する $2$ 日を見たとき、 $1$ 日目 $\gt 2$ 日目なら、 $2$ 日目に買えばよく（下がり続ける場合は単調減少が止まるところで買うことになる）、 $1$ 日目 $\lt 2$ 日目なら、 $1$ 日目に買えばよい（ $2$ 日目に売れば確実にプラスにはなる）。
売りについても逆に、下がるなら初日売りで、上がり続ける限り待つのが最適。
$1$ 日目 $= 2$ 日目の場合は、判断不能だし、 $2$ 日目に行動すれば同じなので何もしない。
最終日は必ず売る。
$100$ と $200$ が交互にやってきた場合、 $2$ 日で倍になるため、 $1000 \times 2^{40}$ くらいが最大値。これはlong型に収まる。

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        long now = 1000; // 所持金
        long cnt = 0; // 所持株数
        for (int i = 0; i < n - 1; i++) {
            if (a[i] < a[i + 1]) {
                // 買い
                cnt += now / a[i];
                now %= a[i];
            }
            if (a[i] > a[i + 1]) {
                // 売り
                now += a[i] * cnt;
                cnt = 0;
            }
        }
        now += a[n - 1] * cnt; // 最終日：売り
        System.out.println(now);
    }
}

ここまで22分25秒＋3ペナ。565位。
ペナ分の時間が過ぎた頃には1300位くらい。その時点でEとFどちらもまだ20人も解いておらず、5完はかなり難しそうだが、片方解ければ救われそうだと思っていた。

E - M's Solution

問題
解けず。集落を通るところだけが候補とすらも気付かず。
10分ほどかけて例２までを吟味していたところで、とりあえずF問題も確認しておこうと見てみたら、F問題の方ができそうな気がしたので以後放置。

思考過程

$_{40000}C_i$ 全探索はよく考えなくても余裕でTLE。
$K=1$ の場合はなんとなくある程度絞れる気がしないでもないが、 $K \geq 2$ になったら何が最適なのか全然わからない。マラソンか？と思うくらい全く取っ掛かりもつかめない。（まさか本当に解説にマラソンがあるとは・・。）

F - Air Safety

問題
ABC168-Fで似たような実装を量産して破滅した経験を生かせているのかいないのか・・・。
回転させることで実装を1回で済ませるとかは、思いつかないわけではないけど、だいたいはコピペしてちょっと直した方が早いと思ってしまいがち。

思考過程

例１のように、向かい合っている場合は衝突する。
例３では、 $3$ 番目と $4$ 番目（111 198 D、121 188 L）が衝突する。このように、進行方向が $90$ 度違う場合にも衝突する可能性がある。
2つの飛行機の組み合わせ $_{200000}C_2$ 通りを全てチェックしたのではTLEなので、なんとかしてチェックする組み合わせを減らすなりまとめてチェックするなりしたい。
　
向かい合っているパターンを考える。
1. UとDの場合、x座標が同じ場合のみ衝突するので、まずx座標でグルーピングする。
2. あるUの飛行機 $O_1$ については、x座標が同一のDの飛行機の中から、y座標がUより大きい中で最小のもの $O_2$ を特定し、 $O_1$ と $O_2$ とのy座標の差 $\times 10 / 2$ を求める。
3. 上記を全てのUの飛行機について求める。
4. 計算量は、HashMap＜x座標、TreeSet＜y座標＞＞のような形でデータを持てば、グルーピングも計算も $O(NlogN)$ 。
5. RとLの場合は、xとyを入れ替えて同様。
  　
進行方向が度違うパターンを考える。
1. 例３のDやLの飛行機と衝突するものを増やすことを考えてみると、同じ斜め $45$ 度（ $y=-x+b$ ）の直線にいる飛行機が衝突することがわかる。
2. 同一直線上にいることの判定は、x座標とy座標の和 $(=b)$ が等しいかどうかでできそう。
3. 向かい合いのパターンと流れは同様だが、異なるのはまず $b$ でグルーピングするところ。
4. それから、あるDの飛行機 $O_1$ については、 $b$ が同一のLの飛行機の中から、x座標がDより大きい中で最小のもの $O_2$ を特定し、 $O_1$ と $O_2$ とのx座標の差 $\times 10$ を求める。
  　
UとRの場合については、同一直線上の判定はDとLの場合と同じ。各Uについて、x座標がUより小さい中で最大のRを特定するところが異なる。
DとRの場合、UとLの場合は、逆向きの斜め $45$ 度（ $y=x+b$ ）の直線上にいる飛行機が衝突するので、 $b=y-x$ でグルーピングする。
各Dについてx座標がDより小さい中で最大のRを、各Uについてx座標がUより大きい中で最小のLを特定する。

コンテスト中は、ここまでのグルーピングの仕方（ $x+y$ か $y-x$ か）の考察が雑すぎて1WA。また、HashMapで十分なところをTreeMapにして、計算量にlogを余計につけていた。TLEにはならなかったが。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.x = Integer.parseInt(sa[0]);
            o.y = Integer.parseInt(sa[1]);
            o.u = sa[2];
            arr[i] = o;
        }
        br.close();

        int ans = Integer.MAX_VALUE;

        // 上下
        Map<Integer, TreeSet<Obj>> map1 = new HashMap<>();
        Map<Integer, TreeSet<Obj>> map2 = new HashMap<>();
        for (Obj o : arr) {
            if ("U".equals(o.u)) {
                TreeSet<Obj> set = map1.get(o.x); // グルーピング：x
                if (set == null) {
                     set = new TreeSet<Obj>((o1, o2) -> o1.y - o2.y);
                     map1.put(o.x, set);
                }
                set.add(o);
            }
            if ("D".equals(o.u)) {
                TreeSet<Obj> set = map2.get(o.x); // グルーピング：x
                if (set == null) {
                     set = new TreeSet<Obj>((o1, o2) -> o1.y - o2.y);
                     map2.put(o.x, set);
                }
                set.add(o);
            }
        }
        for (Integer x : map1.keySet()) {
            TreeSet<Obj> set1 = map1.get(x);
            TreeSet<Obj> set2 = map2.get(x);
            if (set2 != null) {
                for (Obj o1 : set1) {
                    Obj o2 = set2.higher(o1); // Uより大きい最小のD
                    if (o2 != null) {
                        int val = (o2.y - o1.y) * 5;
                        ans = Math.min(ans, val);
                    }
                }
            }
        }

        // 左右（上下の場合のxとyを入れ替え）
        map1 = new HashMap<>();
        map2 = new HashMap<>();
        for (Obj o : arr) {
            if ("R".equals(o.u)) {
                TreeSet<Obj> set = map1.get(o.y); // グルーピング：y
                if (set == null) {
                     set = new TreeSet<Obj>((o1, o2) -> o1.x - o2.x);
                     map1.put(o.y, set);
                }
                set.add(o);
            }
            if ("L".equals(o.u)) {
                TreeSet<Obj> set = map2.get(o.y); // グルーピング：y
                if (set == null) {
                     set = new TreeSet<Obj>((o1, o2) -> o1.x - o2.x);
                     map2.put(o.y, set);
                }
                set.add(o);
            }
        }
        for (Integer y : map1.keySet()) {
            TreeSet<Obj> set1 = map1.get(y);
            TreeSet<Obj> set2 = map2.get(y);
            if (set2 != null) {
                for (Obj o1 : set1) {
                    Obj o2 = set2.higher(o1); // Rより大きい最小のL
                    if (o2 != null) {
                        int val = (o2.x - o1.x) * 5;
                        ans = Math.min(ans, val);
                    }
                }
            }
        }

        // 下左
        Map<Integer, TreeSet<Obj>> mapD = make(arr, "D", true); // グルーピング：y+x
        Map<Integer, TreeSet<Obj>> mapL = make(arr, "L", true); // グルーピング：y+x
        for (Integer v : mapD.keySet()) {
            TreeSet<Obj> set = mapD.get(v);
            TreeSet<Obj> set2 = mapL.get(v);
            if (set2 != null) {
                for (Obj o : set) {
                    Obj o2 = set2.higher(o); // Dより大きい最小のL
                    if (o2 != null) {
                        int val = (o2.x - o.x) * 10;
                        ans = Math.min(ans, val);
                    }
                }
            }
        }

        // 上右
        Map<Integer, TreeSet<Obj>> mapU = make(arr, "U", true); // グルーピング：y+x
        Map<Integer, TreeSet<Obj>> mapR = make(arr, "R", true); // グルーピング：y+x
        for (Integer v : mapU.keySet()) {
            TreeSet<Obj> set = mapU.get(v);
            TreeSet<Obj> set2 = mapR.get(v);
            if (set2 != null) {
                for (Obj o : set) {
                    Obj o2 = set2.lower(o); // Uより小さい最大のR
                    if (o2 != null) {
                        int val = (o.x - o2.x) * 10;
                        ans = Math.min(ans, val);
                    }
                }
            }
        }

        // 下右
        mapD = make(arr, "D", false); // グルーピング：y-x
        mapR = make(arr, "R", false); // グルーピング：y-x
        for (Integer v : mapD.keySet()) {
            TreeSet<Obj> set = mapD.get(v);
            TreeSet<Obj> set2 = mapR.get(v);
            if (set2 != null) {
                for (Obj o : set) {
                    Obj o2 = set2.lower(o); // Dより小さい最大のR
                    if (o2 != null) {
                        int val = (o.x - o2.x) * 10;
                        ans = Math.min(ans, val);
                    }
                }
            }
        }

        // 上左
        mapU = make(arr, "U", false); // グルーピング：y-x
        mapL = make(arr, "L", false); // グルーピング：y-x
        for (Integer v : mapU.keySet()) {
            TreeSet<Obj> set = mapU.get(v);
            TreeSet<Obj> set2 = mapL.get(v);
            if (set2 != null) {
                for (Obj o : set) {
                    Obj o2 = set2.higher(o); // Uより大きい最小のL
                    if (o2 != null) {
                        int val = (o2.x - o.x) * 10;
                        ans = Math.min(ans, val);
                    }
                }
            }
        }

        if (ans == Integer.MAX_VALUE) {
            System.out.println("SAFE");
        } else {
            System.out.println(ans);
        }
    }

    static Map<Integer, TreeSet<Obj>> make(Obj[] arr, String u, boolean plus) {
        Map<Integer, TreeSet<Obj>> map = new HashMap<>();
        for (Obj o : arr) {
            if (u.equals(o.u)) {
                if (plus) {
                    o.val = o.y + o.x;
                } else {
                    o.val = o.y - o.x;
                }
                TreeSet<Obj> set = map.get(o.val);
                if (set == null) {
                     set = new TreeSet<Obj>((o1, o2) -> o1.x - o2.x);
                     map.put(o.val, set);
                }
                set.add(o);
            }
        }
        return map;
    }

    static class Obj {
        int x, y, val;
        String u;
    }
}

ABCDFと解いた時点で94分52秒＋4ペナ。297位。

最終結果：ABCDFの5完、114分52秒、330位、パフォーマンス1952
レート変動：1805→1820

highestを2だけ更新。
F問題は重実装やり切れて良かったが、B問題のようにお粗末過ぎるのはないようにしたい。