ABC276参加記

5完1ペナ43分 919位

A問題

文字列の後ろからaが現れるところを探す。

import std;

void main() {
    string S;
    readf("%s\n", S);

    int res = -1;
    foreach_reverse (i, s; S) {
        if (s == 'a') {
            res = i.to!int + 1;
            break;
        }
    }

    res.writeln;
}

B問題

各都市毎に道路で直接結ばれた都市を列挙し、昇順にソートする。

import std;

void main() {
    int N, M;
    readf("%d %d\n", N, M);

    auto roads = new int[][](N+1);
    foreach (_; 0 .. M) {
        int A, B;
        readf("%d %d\n", A, B);

        roads[A] ~= B, roads[B] ~= A;
    }

    foreach (i; 1 .. N+1) {
        write(roads[i].length, " ");

        roads[i].sort;
        writefln("%(%s %)", roads[i]);
    }
}

C問題

$i (1 \leq i \leq N-1)$を後ろから見ていき、$P_{i} > P_{i+1}$を満たす$P_{i}$の値を$(P_{i+1},…,P_{N})$のうち$P_{i}$未満の1番大きな値$(=Q)$に置き換える。 $j (i+1 \leq i \leq N)$において$P_{j}$の値を$(P_{i},…,P_{N})$のうち$Q$を除いた数列を降順にしたものに置き換える。

import std;

void main() {
    int N;
    readf("%d\n", N);

    auto P = readln.chomp.split.to!(int[]);

    int[] list = [P[N-1]];
    int idx = N;
    foreach_reverse (i; 0 .. N-1) {
        list ~= P[i];

        if (P[i] > P[i+1]) {
            idx = i;
            break;
        }
    }

    auto S = list.sort;
    auto lb = S.lowerBound(P[idx]);
    int b = lb.back;

    int[] res = new int[](N);
    res[0..idx] = P[0..idx];
    res[idx++] = b;
    foreach_reverse (l; list) {
        if (l == b) continue;
        res[idx++] = l;
    }

    writefln("%(%s %)", res);
}

D問題

正整数列$A$の最大公約数を$G$とする。 $a_{i} / G$を2と3で割れるだけ割り、1になるか確認する。

import std;

void main() {
    int N;
    readf("%d\n", N);

    auto a = readln.chomp.split.to!(int[]);

    auto G = a.fold!((x, y) => gcd(x, y));

    bool isOK = true;
    int res;
    foreach (x; a) {
        int num = x / G;

        while (num > 1 && num % 2 == 0) {
            ++res;
            num /= 2;
        }

        while (num > 1 && num % 3 == 0) {
            ++res;
            num /= 3;
        }

        isOK &= (num == 1);
    }

    if(!isOK) res = -1;

    res.writeln;
}

E問題

DFSで長さ4以上の経路が存在するか判定する。

import std;

void main() {
    int H, W;
    readf("%d %d\n", H, W);

    int sx, sy;
    auto C = new string[](H);
    foreach (i; 0 .. H) {
        readf("%s\n", C[i]);

        foreach (j, c; C[i]) {
            if (c == 'S') {
                sx = i, sy = j.to!int;
            }
        }
    }

    bool isOK;

    int[] dx = [-1, 0, 1, 0], dy = [0, 1, 0, -1];
    auto seen = new bool[][](H, W);

    void f(int x, int y, int cnt = 0) {
        seen[x][y] = true;
        foreach (i; 0 .. 4) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || H <= nx || ny < 0 || W <= ny) continue;
            if (C[nx][ny] == '#') continue;
            if (seen[nx][ny]) {
                if (C[nx][ny] == 'S' && cnt >= 3) isOK = true;
                continue;
            }

            f(nx, ny, cnt+1);
        }
    }

    f(sx, sy);

    writeln(isOK ? "Yes" : "No");
}