SRM668 Div1

結果

oxx 1285 -> 1366

Arenaの問題文が改行されずに表示されるというのが直らなくてツライです．
easyは良く分からずに通ったので反省です．medは間違った方針を立ていて解けませんでした．hardは見ていません．
medは他の人のを見て復習をしたのですが何故正しいか分かりませんので後で考えます．

[Easy 250: PaintTheRoom ]

問題

R行C列の格子グラフが与えられる．それぞれの頂点をちょうどK回通るような道が存在するか答えよ．

1 <= R, C, K <= 50

方針

まずKが1ならどんな格子グラフでもちょうど1回通る道が存在します．
次にK>1の場合なのですが，R * C が偶数なら次のようにしてちょうどK回通る道が存在します．

R * C が奇数の場合はちょうどK回通る道は存在しません．格子グラフは二部グラフであり二部グラフには奇数長の閉路が存在しないので奇数個の頂点をちょうどK回通る道は存在しません．（正しいか分かりませんが通りました）

ソースコード

#include <bits/stdc++.h>

using namespace std;

class PaintTheRoom {
public:
	string canPaintEvenly(int R, int C, int K) {
        if (K == 1)
            return "Paint";

        if ((R * C) % 2 == 0)
            return "Paint";
        else
            return "Cannot paint";
	}
};

[Medium 450: WalkingToSchool ]

問題

頂点数N，弧数Mの単純有向グラフ（頂点は0からN-1でラベル付け）が与えられる．このとき，十分大きなkに対してk-tourが存在するかを判定せよ．
k-tourとは頂点0から頂点1へのk-walkが存在しかつ頂点1から頂点0へのk-walkが存在することである．
頂点sから頂点tへのk-walkとは頂点sから始まり頂点tへちょうどk個の弧を使う道のことである．このとき，各々の頂点や弧は何回でも通って良い．

2 <= N <= 2000, 0 <= M <= 2000

方針

十分大きなkに対して頂点sから頂点tへk-walkが存在するかを判定します．
これは，頂点sから頂点tへの道があり，かつ頂点sの閉路の組（C1, C2）でgcd(|C1|, |C2|)==1 を満たすものが存在するか判定することに等しいです．

なぜ，gcd(|C1|,|C2|)==1となるものがあれば十分大きなKに対して頂点sから頂点tへの道が存在するのかは分かりません．
拡張されたユークリッドの互除法を使って，ある整数x,yが存在して
　　　　x * |C1| + y * |C2| = gcd(|C1|, |C2|)
　　=>　x * |C1| + y * |C2| = 1
を満たすから両辺k倍して(k * x, k * y)とすれば良いのかなと思ったのですが，xとyが整数なので負も許すので閉路C1をk*x回，閉路C2をk*y回使うと解釈すると意味が分からないです．

分かったら後で書き直します．

ソースコード

#include <bits/stdc++.h>

using namespace std;

class WalkingToSchool {
    int N, M;
    vector<int> from, to;
public:
	string canWalkExactly(int _N, vector <int> _from, vector <int> _to) {
		N = _N;
        M = _from.size();
        from = _from;
        to = _to;

        if (Check(0, 1) && Check(1, 0))
            return "Freedom";
        else
            return "Chores";
	}

    bool Check(int s, int g) {
        const int MAX_LOOP = 2 * N + 1;
        vector<vector<bool>> visit(MAX_LOOP, vector<bool>(N, false));
        visit[0][s] = true;

        for (int l = 0; l < MAX_LOOP - 1; ++l)
            for (int m = 0; m < M; ++m)
                if (visit[l][from[m]])
                    visit[l + 1][to[m]] = true;

        bool is_path = false;
        for (int l = 0; l < MAX_LOOP; ++l)
            if (visit[l][g]) {
                is_path = true;
                break;
            }

        if (!is_path)
            return false;
                
        for (int l1 = 0; l1 < MAX_LOOP; ++l1)
            if (visit[l1][s])
                for (int l2 = l1 + 1; l2 < MAX_LOOP; ++l2)
                    if (visit[l2][s] && __gcd(l1, l2) == 1)
                        return true;
                    
        return false;
    }
};