ZONeエナジー プログラミングコンテスト “HELLO SPACE”

だめだめのだめだめでした，残念．

A - UFO襲来

各添え字 に対して愚直にチェックする．100 点だけど実質的に for 文が必要でびっくりした．

実装 (Python)

Python だと部分文字列の切り出しが簡単．

S = input()
T = "ZONe"
ans = 0
for i in range(len(S) - 4 + 1):
    ans += S[i:i + 4] == T
print(ans)

B - 友好の印

二分探索をやった (200 点とは)．高さ を決め打つと，これが ok である必要十分条件は次の図のように考えられる．

実装 (Python)

N, D, H = map(int, input().split())
p = []
for _ in range(N):
    d, h = map(int, input().split())
    p.append((d, h))
p.sort()
l = 0
r = H
for _ in range(50):
    X = (l + r) / 2
    ok = True
    for d, h in p:
        ok &= h <= (H - X) * d / D + X
    if ok:
        r = t
    else:
        l = t
print(f'{r:.10f}')

C - MAD TEAM

またまた二分探索．以下はスキルの種類数を として を達成できるかを考える． となる の集合を とする．他も同様にして まで定める．すると，この問題は次のように言い換えられる．

問題:「 なる であって， を満たすものは存在するか？」

以降はこの判定問題を解くことを考える．まず，各 に対して を計算する．ここで， を固定すると，問題は更に次のように言い換えられる．

問題:「 が与えられる． を満たす は存在するか？」

従って，すべての に対して，

を予め計算しておけば を固定したときの問題に高速に答えることが出来る．

の計算は ， の計算は で可能なので，結局全体 でこの問題を解くことが出来た．

実装 (C++)

// マクロなどは省略
int main() {
    int n;
    read(n);
    vec<vec<int>> params(n, vec<int>(5));
    rep(i, n) read(params[i]);
    int l = 0, r = 1000000001;
    while (r - l > 1) {
        int x = (l + r) >> 1;
        vec<int> ss(n);
        vec<bool> ex(1 << 5, false);
        rep(i, n) {
            int s = 0;
            rep(j, 5) {
                int t = (params[i][j] >= x);
                s |= t << j;
            }
            ss[i] = s;
            ex[s] = true;
        }
        rrep(s, 1 << 5) {
            rep(j, 5) {
                if ((s >> j) & 1) continue;
                int t = s | (1 << j);
                ex[s] = ex[s] or ex[t];
            }
        }
        bool ok = false;
        rep(i, n) {
            repl(j, i + 1, n) {
                int s = ((1 << 5) - 1) ^ (ss[i] | ss[j]);
                if (ex[s]) {
                    ok = true;
                    break;
                }
            }
            if (ok) break;
        }
        if (ok) {
            l = x;
        } else {
            r = x;
        }
    }
    print(l);
    return 0;
}

D - 宇宙人からのメッセージ

反転クエリは今反転しているかどうかのフラグを持つことで対処する．そして，反転されている場合は文字列の先頭に，反転されていない場合は文字列の末尾に文字を追加すればよい．このような操作を高速に行えるデータ構造として Deque が存在する．ここで，Deque は先頭/末尾への要素の追加/削除がならし定数時間で行えるデータ構造である．

なお，本問では連続する文字を削除する必要がある．これは，追加する文字が，その時点の文字列における追加しようとしている側の端の文字と同じ文字であった場合に追加の代わりに削除を行うようにすればよい (日本語が下手ですみません) ．

実装 (C++)

// マクロなどは省略
int main() {
    string s;
    read(s);
    deque<char> t;
    bool rev = false;
    for (char c : s) {
        if (c == 'R') {
            rev = not rev;
        } else {
            if (rev) {
                if (t.size() and t.front() == c) {
                    t.pop_front();
                } else {
                    t.push_front(c);
                }
            } else {
                if (t.size() and t.back() == c) {
                    t.pop_back();
                } else {
                    t.push_back(c);
                }
            }
        }
    }
    while (t.size()) {
        if (rev) {
            cout << t.back();
            t.pop_back();
        } else {
            cout << t.front();
            t.pop_front();
        }
    }
    cout << '\n';
    return 0;
}

E - 潜入

ただの最短経路問題に見えるが， から への移動についてすべての辺を張ってしまうと辺の数が最大で 本程度になってしまい，TL に間に合わない可能性が高い (間に合ったという人もいるみたいですが)．

を減らす方向の移動は，初めに のコストを払った後， が 減るたびにコストを だけ払うと考えられる．これは，例えば「入場料」を支払って電車に乗るようなものである．この考え方に従って，今入場しているかどうかで頂点の状態を場合分けをすると，次の図のように辺を張ることが出来る．

実装 (Java)

// ライブラリなどは省略
public static void solve(ExtendedScanner sc, FastPrintStream pw) {
    int n = sc.nextInt();
    int m = sc.nextInt();
    Digraph<SimpleEdge> g = new Digraph<>(2 * n * m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m - 1; ++j) {
            int a = sc.nextInt();
            g.addEdge(new SimpleEdge(i * m + j, i * m + j + 1, a));
            g.addEdge(new SimpleEdge(i * m + j + 1, i * m + j, a));
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m; ++j) {
            int b = sc.nextInt();
            g.addEdge(new SimpleEdge(i * m + j, (i + 1) * m + j, b));
            g.addEdge(new SimpleEdge(n * m + (i + 1) * m + j, n * m + i * m + j, 1));
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            g.addEdge(new SimpleEdge(i * m + j, n * m + i * m + j, 1));
            g.addEdge(new SimpleEdge(n * m + i * m + j, i * m + j, 0));
        }
    }
    Dijkstra<SimpleEdge> dij = new Dijkstra<>(g, 0);
    pw.println(dij.distance(n * m - 1));
}

F - 出会いと別れ

と定義する．

頂点 から頂点 へとたどり着けるための必要十分条件は，ある整数 と長さ の整数列 であって， を満たすものが存在することである．ここで， は bit 毎の排他的論理和を取る演算である．つまり， の線形結合によってすべての を表示できるか？という判定問題を考えればよいことになる．あとは， 個の基底を取り出し (取り出せなかったら -1 を出力して終了する)， 頂点 辺のグラフで適当な全域木を取ってやればよい．

実装 (Java)

public static void solve(ExtendedScanner sc, FastPrintStream pw) {
    int n = sc.nextInt();
    int m = sc.nextInt();
    boolean[] ok = new boolean[n];
    Arrays.fill(ok, true);
    for (int i = 0; i < m; ++i) {
        int a = sc.nextInt();
        ok[a] = false;
    }
    IntArrayList bases = new IntArrayList();
    IntArrayList xs = new IntArrayList();
    for (int i = 0; i < n; ++i) {
        if (!ok[i]) continue;
        int e = i;
        PrimitiveIterator.OfInt iter = bases.iterator();
        while (iter.hasNext()) e = Math.min(e, e ^ iter.nextInt());
        if (e != 0) {
            bases.add(e);
            xs.add(i);
        }
    }
    if (bases.size() != Integer.numberOfTrailingZeros(n)) {
        pw.println(-1);
        return;
    }
    boolean[] vis = new boolean[n];
    IntDeque dq = new IntDeque(n);
    vis[0] = true;
    dq.addLast(0);
    while (dq.size() > 0) {
        int u = dq.removeFirst();
        for (var iter = xs.iterator(); iter.hasNext();) {
            int x = iter.nextInt();
            int v = u ^ x;
            if (!vis[v]) {
                vis[v] = true;
                dq.addLast(v);
                pw.print(u).print(' ').println(v);
            }
        }
    }
}