結果

問題 No.3032 ホモトピー入門
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-01-31 20:57:37
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1,472 ms / 2,000 ms
コード長 4,461 bytes
コンパイル時間 2,094 ms
コンパイル使用メモリ 133,908 KB
実行使用メモリ 52,116 KB
最終ジャッジ日時 2025-01-31 20:57:52
合計ジャッジ時間 13,972 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std.algorithm, std.array, std.container, std.conv, std.math, std.range, std.stdio, std.typecons;
/**********************
Point
**********************/
struct Vector {
    long x, y;
    
    this (long x, long y) {
        this.x = x;
        this.y = y;
    }
    
    Vector opBinary(string op)(Vector rhs) {
        static if (op == "+" || op == "-")
            mixin("return Vector(this.x"~op~"rhs.x, this.y"~op~"rhs.y);");
        else static assert(0);
    }
    
    // lexicographic order
    int opCmp(Vector rhs) {
        if (this.x < rhs.x)
            return -1;
        else if (this.x > rhs.x)
            return 1;
        else {
            if (this.y < rhs.y)
                return -1;
            else if (this.y > rhs.y)
                return 1;
            else
                return 0;
        }
    }
    
    string toString() {
        return "("~x.to!string~", "~y.to!string~")";
    }
}
long det(Vector v, Vector w) {
    return v.x * w.y - v.y * w.x;
}
// 0 : on the same line
// 1 : counterclockwise
// -1 : clockwise
long tri_sgn(Vector a, Vector b, Vector c) {
    return det(b-a, c-a).sgn;
}
// if the point p is between (allow to be the same point) the line segment ab
bool between(Vector a, Vector p, Vector b) {
    return
        tri_sgn(a, p, b) == 0
     && sgn(p.x - a.x) * sgn(p.x - b.x) <= 0
     && sgn(p.y - a.y) * sgn(p.y - b.y) <= 0;
}
// determine whether line segments ab and cd intersect
bool intersect(Vector a, Vector b, Vector c, Vector d) {
    if (between(a, c, b) || between(a, d, b) || between(c, a, d) || between(c, b, d)) return true;
    auto sign1 = tri_sgn(a, b, c) * tri_sgn(a, b, d);
    auto sign2 = tri_sgn(c, d, a) * tri_sgn(c, d, b);
    if (sign1 < 0 && sign2 < 0) return true;
    return false;
}
/*********************
 *********************/
bool in_A(Vector p, int M) {
    return
           tri_sgn(Vector(-2*(M+1), M+1), Vector(-1, 1), p) > 0
        && tri_sgn(Vector(-1, 1), Vector(0, M+1), p) > 0
        && tri_sgn(Vector(0, M+1), Vector(-2*(M+1), M+1), p) > 0;
}
bool in_B(Vector p, int M) {
    return
           tri_sgn(Vector(-2*(M+1), M+1), Vector(0, -M-1), p) > 0
        && tri_sgn(Vector(0, -M-1), Vector(-1, 1), p) > 0
        && tri_sgn(Vector(-1, 1), Vector(-2*(M+1), M+1), p) > 0;
}
bool in_C(Vector p, int M) {
    return
           tri_sgn(Vector(-1, 1), Vector(0, -M-1), p) > 0
        && tri_sgn(Vector(0, -M-1), Vector(1, 1), p) > 0
        && tri_sgn(Vector(1, 1), Vector(-1, 1), p) > 0;
}
bool in_D(Vector p, int M) {
    return
           tri_sgn(Vector(1, 1), Vector(0, -M-1), p) > 0
        && tri_sgn(Vector(0, -M-1), Vector(2*(M+1), M+1), p) > 0
        && tri_sgn(Vector(2*(M+1), M+1), Vector(1, 1), p) > 0;
}
bool in_E(Vector p, int M) {
    return
           tri_sgn(Vector(1, 1), Vector(2*(M+1), M+1), p) > 0
        && tri_sgn(Vector(2*(M+1), M+1), Vector(0, M+1), p) > 0
        && tri_sgn(Vector(0, M+1), Vector(1, 1), p) > 0;
}
bool in_F(Vector p, int M) {
    return
           tri_sgn(Vector(1, 1), Vector(0, M+1), p) > 0
        && tri_sgn(Vector(0, M+1), Vector(-1, 1), p) > 0
        && tri_sgn(Vector(-1, 1), Vector(1, 1), p) > 0;
}
bool in_l1(Vector p, int M) {
    return between(Vector(-2*(M+1), M+1), p, Vector(-1, 1));
}
bool in_l2(Vector p, int M) {
    return between(Vector(2*(M+1), M+1), p, Vector(-1, 1));
}
enum Triangle:ubyte {
    A = 1, B = 2, C = 3, D = 4, E = 5, F = 6
}
Triangle triangle(Vector p, int M) {
    if (p.in_A(M)) return Triangle.A;
    if (p.in_B(M)) return Triangle.B;
    if (p.in_C(M)) return Triangle.C;
    if (p.in_D(M)) return Triangle.D;
    if (p.in_E(M)) return Triangle.E;
    if (p.in_F(M)) return Triangle.F;
    assert(0);
}
bool solve(string loop, int M) {
    Triangle[] triangles = [Triangle.C];
    auto p = Vector(0, 0);
    foreach (c; loop) {
        switch (c) {
        case 'U': p.y += 2; break;
        case 'D': p.y -= 2; break;
        case 'L': p.x -= 2; break;
        case 'R': p.x += 2; break;
        default: assert(0);
        }
        auto next = triangle(p, M);
        with (Triangle)
        if      (triangles[$-1] == B && next == D)
            triangles ~= [C, D];
        else if (triangles[$-1] == D && next == B)
            triangles ~= [C, B];
        else if (triangles[$-1] == A && next == E)
            triangles ~= [F, E];
        else if (triangles[$-1] == E && next == A)
            triangles ~= [F, A];
        else
            triangles ~= next;
    }
    assert(p == Vector(0, 0), p.to!string);
    
    Triangle[] stack = [Triangle.C];
    foreach (t; triangles[1 .. $]) {
        if (stack[$-1] == t)
            continue;
        else if (stack.length > 1 && stack[$-2] == t)
            stack.length--;
        else
            stack ~= t;
    }
    assert(stack.length > 0 && stack[0] == Triangle.C);
    return stack.length == 1;
}
void main() {
    auto NM = readln.split.to!(uint[]);
    auto Cs = iota(NM[0]).map!(i => readln[0 .. $-1]).array;
    
    Cs.map!(x => solve(x, NM[1])).filter!(a => a).array.length.writeln;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0