AtCoder ABC 054 C - One-stroke Path (水色, 300 点)

グラフの探索を頑張る問題。現代の AtCoder であまり見ないけど、教育的な全探索問題！！！

問題へのリンク

問題概要

頂点数 、辺数 の無向グラフが与えられる。このグラフ上で頂点 1 から出発するハミルトンパスが何本あるかを数え上げよ。

なおハミルトンパスとは、グラフの各頂点をちょうど一度ずつ通るパスのことである。

制約

• 

解法 1：DFS

とにかく頂点 1 からスタートして各頂点を一度ずつ通るようなパスを全探索しよう！！！！！！以下の記事に書いたような DFS で頑張ることができる。

qiita.com

再帰関数の終端条件としては、「 すべての頂点を探索したことがわかったら答えをインクリメントした上でリターンする」としている。

#include <iostream>
#include <vector>
using namespace std;

using Graph = vector<vector<int> >;
Graph G;

void dfs(int v, vector<bool> &seen, int &res) {
    bool end = true;
    for (int i = 0; i < seen.size(); ++i) if (!seen[i] && i != v) end = false;
    if (end) {
        ++res;
        return;
    }

    seen[v] = true;
    for (auto nv : G[v]) {
        if (seen[nv]) continue;
        dfs(nv, seen, res);
    }
    seen[v] = false;
}

int main() {
    int N, M; cin >> N >> M;
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    vector<bool> seen(N, false);
    int res = 0;
    dfs(0, seen, res);
    cout << res << endl;
}

解法 2：next_permutaion

この問題は本質的に 通りの全探索をする問題であるといえる。このように順列を全探索する方法として、next_permutaion を使う方法がある。

そして各順列に対して、その順番に辺が存在するかどうかを判定して、最後まで行き着くことができたら答えをインクリメントすれば OK。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

// グラフを隣接行列で管理する
bool G[10][10];

int main() {
    int N, M; cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a][b] = G[b][a] = true;
    }

    // 順列
    vector<int> ord(N);
    for (int i = 0; i < N; ++i) ord[i] = i;

    // 順列を全部試すa
    int res = 0;
    do {
        if (ord[0] != 0) break;

        bool ok = true;
        for (int i = 0; i + 1 < N; ++i) {
            int from = ord[i];
            int to = ord[i+1];
            if (!G[from][to]) ok = false;
        }
        if (ok) ++res;
    } while (next_permutation(ord.begin(), ord.end()));

    cout << res << endl;
}

AtCoder ABC 057 C - Digits in Multiplication (緑色, 300 点)

整数に関する問題でまずは直面する典型的な事柄を学べる教育的問題！！

例えば整数 が素数かどうかを判定するのは、実は から まで順に試し割りすればよいという話など。

ただ、現代の ABC なら灰色 diff になりそうである。

問題へのリンク

問題概要

正の整数 が与えられる。 を満たす正の整数 の組をすべて考えたときの、「 の桁数と の桁数のうちの最大値」の最小値を求めよ。

制約

• 

考えたこと

を満たすような を全探索すれば OK！！！！！

そしてそれは、基本的には の約数をすべて求めてください、というのとほとんど同じ問題。実は

• まで考えて
• % == 0 であれば
• として、 が候補になる

という感じ。なぜ までで良いか？それは、 と との間に暗黙の大小関係として が成立していると考えても差し支えない。そうすると とすると となるので矛盾する。

#include <iostream>
using namespace std;
const long long INF = 1LL<<60;

int calc_digit(long long n) {
    int res = 0;
    while (n > 0) {
        ++res;
        n /= 10;
    }
    return res;
}

int main() {
    long long N; cin >> N;
    long long res = INF;
    for (long long a = 1; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long b = N/a;
        long long tmp = max(calc_digit(a), calc_digit(b));
        res = min(res, tmp);
    }
    cout << res << endl;
}

AtCoder ABC 064 C - Colorful Leaderboard (茶色, 300 点)

あるあるあるある。

問題へのリンク

問題概要

人がいてそれぞれの AtCoder レーティングが与えれている。1 以上 4800 以下で、400 ごとに色が変わるという設定。

今、レーティング 3200 以上の人は自由に色を変えることができる。このとき、 人の中に存在する色の種類数の最大値と最小値を求めよ。

制約

• 

考えたこと

こういう問題は何系というんだろう...なんか「上手いことやってある値を最大にしたり最小にしたりする系」。。。ちょっと数学的思考が絡む感じではあるけど、落ち着いて丁寧に考えれば解ける。

最大値について

明らかに、3200 以上の人が全員別々の色 (しかも 3200 未満の人たちの色とも別の色) にすればよい。

よって、(0〜3200 の範囲で登場している色の個数) + (3200 以上の人数) が最大値

最小値について

今度は 3200 以上の人がなるべく一致するようにさせたい。ここで罠があって、全員が 3200 以上だったら「1 通り」になる。このケースを見落としがちな気がする。

3200 未満の人が一人でもいたら、3200 以上の人は全員その人に色を合わせればよくて、(0〜3200 の範囲で登場している色の個数) が答えになる。

#include <iostream>
#include <set>
using namespace std;

int main() {
    int N; cin >> N;

    set<int> se; // 3200 以下で登場する色の種類数
    int over_num = 0; // 3200 以上の人数
    for (int i = 0; i < N; ++i) {
        int a; cin >> a;
        if (a >= 3200) ++over_num;
        else se.insert(a/400);
    }
        
    int Max = (int)se.size() + over_num;
    int Min = 0;
    if (se.size() == 0) Min = 1;
    else Min = (int)se.size();
        
    cout << Min << " " << Max << endl;
}

AtCoder ABC 141 F - Xor Sum 3 (黄色, 600 点)

Xor Sum シリーズしゃん。典型てんこ盛り！！！

• XOR は各桁ごとに独立に考えるとよい
• XOR に関する問題は mod. 2 での方程式みたいになることも多い
• であることから上位の桁から辞書順的に優先で考えるような貪欲が決まる

などなど。

問題へのリンク

問題概要

個の非負整数 が与えられる。これらの値を赤と青に塗り分ける方法のうち、「それぞれの色のグループの XOR 和」の和の最大値を求めよ。

制約

• 
• 

考えたこと

XOR に関する問題は、多くの場合「各桁ごとに独立に考える」という戦法がはまることが多い。今回も各桁ごとに様子を観察することにする。

まず、 個のうち 桁目が 1 になっているものが奇数個のとき、どのように 2 グループに分けたとしても、「片方の XOR 和は 1」で「他方の XOR 和は 0」という感じになり、最終的に総和に寄与する分は になる。つまり最適化の余地は一切なく、常に一定である。

よって 桁目が 1 になっているやつが偶数個であるような のみに考察を絞って良い。たとえば 6 個だったとき

• 1 個と 5 個みたいに (奇数個) | (奇数個) に分割したときは、それぞれ XOR 和は 1 になるので、最終的な結果に寄与する分は
• 2 個と 4 個みたいに (偶数個) | (偶数個) に分割したときは、それぞれ XOR 和は 0 になるので、最終的な結果に寄与する分は

という感じになって、最終的な結果に寄与する分は か かのどちらかになる。

理想的には、1 の個数が偶数個であるようなすべての桁 について、それを (奇数個) | (奇数個) になるように分割できたらよいが、そうはできないこともある。サンプル 1 がまさにそう。どの桁を優先したらよいか...？

上位桁から辞書順に Greedy

こういう状況で、桁 による寄与分が とかに関係ある量であるとき、最上位桁から Greedy にやると良いみたいなことはよくある！！！

理由は、 桁目をとったときに の利得が得られるとして、仮に 桁目ですべて利得が 0 であったとしても、　

　

が成立することから、 桁目の利得を獲得しないよりは絶対に獲得した方がよい！！！！！！！！

mod. 2 での連立方程式

さて、1 の個数が奇数個であるような桁 について、1 のやつが (奇数個) | (奇数個) に分けられるような条件を上手に数式で表現してみよう。そもそも XOR な問題では mod. 2 の連立方程式が立ちそうという印象は結構ある。

さて、 個の整数のうち 番目の整数を赤色にぬるとき [tex: x{i} = 1 として青色にぬるときは [tex: x{i} = 0] とするような変数 を用意してみる。そうすると、 桁目の 1 のあるやつが (奇数個) と (奇数個) に色分けする条件は、 桁目が 1 であるやつを抜き取って としたとき、

• 

という風に綺麗に表現することができる！！！！！ これを各桁について方程式を立てると、最大 60 本の mod. 2 上での連立方程式となるわけだ。mod. 2 上での連立方程式の解き方は以下の記事に書いた。

drken1215.hatenablog.com

もちろんすべての桁について方程式を立てたときに解があるとは限らない。しかし、掃き出し法を行うときにダメになった桁 (掃き出した後の拡大係数行列の該当する桁の行が (0 0 0 | 1) となる桁) については、無視すれば OK。ここでなるべく上位の桁を優先的に無視されないようにするために、普段は掃き出し法で pivot を上に運ぶように swap しているところを止めればピッタリ。

よって一回の掃き出し法で解くことができて、bitset 高速化なども行うと、 とかして、計算量は になる。

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

// Bit Matrix
const int MAX_ROW = 110; // to be set appropriately
const int MAX_COL = 110000; // to be set appropriately
struct BitMatrix {
    int H, W;
    bitset<MAX_COL> val[MAX_ROW];
    BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}
    inline bitset<MAX_COL>& operator [] (int i) {return val[i];}
};

// 掃き出し法
void GaussJordan(BitMatrix &A, bool is_extended = false) {
    vector<bool> used(A.H, 0);
    for (int col = 0; col < A.W; ++col) {
        if (is_extended && col == A.W - 1) break;
        int pivot = -1;
        for (int row = 0; row < A.H; ++row) {
            if (used[row]) continue;
            if (A[row][col]) {
                pivot = row;
                break;
            }
        }
        if (pivot == -1) continue;
        for (int row = 0; row < A.H; ++row) {
            if (row != pivot && A[row][col]) A[row] ^= A[pivot];
        }
        used[pivot] = true;
    }
}

const int MD = 60;
int main() {
    int N; cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    // 方程式を立てる
    long long res = 0;
    BitMatrix B(MD+1, N+1);
    vector<bool> cannot(MD+1, 0);
    for (long long d = MD; d >= 0; --d) {
        // d 桁目が 1 が何個か
        int num = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] & (1LL<<d)) ++num;
        }
        if (num == 0) {
            cannot[d] = 1;
            continue;
        }
        else if (num & 1) {
            cannot[d] = 1;
            res += (1LL<<d);
            continue;
        }

        for (int i = 0; i < N; ++i) {
            if (A[i] & (1LL<<d)) B[MD-d][i] = 1;
        }
        B[MD-d][N] = 1;
    }
    GaussJordan(B, true);

    // 集計
    for (int d = MD; d >= 0; --d) {
        if (cannot[d]) continue;

        // d 行目が (0 0 0 ... 0 | 1) だったらダメ
        bool ok = false;
        for (int i = 0; i < N; ++i) if (B[MD-d][i]) ok = true;
        if (!B[MD-d][N]) ok = true;

        // 結果に 2 × 2^d が寄与
        if (ok) res += (2LL<<d);
    }
    cout << res << endl;
}

AtCoder ABC 140 C - Maximal Value (灰色, 300 点)

数学嫌いの方は問題文読んだ瞬間に一瞬敬遠心が生まれてしまうかもしれない...でも落ち着けば難しくはない

問題へのリンク

問題概要

長さ の数列 (具体的な値はわからない) に対して

• 

を満たす数列 が与えられます。 の総和として考えられる最大値を求めてください。

制約

• 

考えたこと: まずは手で様子をつかむ

こういう一見してよくわからないな...と感じた問題は、あれこれ手で実験してみるに限る。

たとえば とかだったら、

• 
• 
• 
• 
• 
• 

でなければならないことがわかる。よってこれを満たす範囲で をできるだけ大きくしようと思うと となる。

一般化

この時点で、 の各要素は両端を除くと「 の隣り合う要素の最小値以下である」ということがわかる。上の例だと、 は のうちの と の最小値以下であったし、 は と の最小値以下であった。

同様に の両端も、 の両端の値以下であることがわかる。

そして、 の両端の値を の両端の値そのものにして、 の両端以外の値も の隣り合う二要素の最小値そのものにしても、条件を満たしているので、それが最適解である。

まとめると

• 
• 
• 
• ...
• 
• 

とすれば OK。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> B(N-1);
    for (int i = 0; i < N-1; ++i) cin >> B[i];

    long long res = B[0] + B.back();
    for (int i = 0; i + 1 < B.size(); ++i) {
        res += min(B[i], B[i+1]);
    }
    cout << res << endl;
}