C++ の動作確認をしてみた（１４）

C++の練習を兼ねて, AtCoder Beginner Contest 108 の問題D（All Your Paths are Different Lengths）を解いてみた.

■感想.
1. 解説を読んだものの, 正確に理解できている自信は無い.
2. とりあえず, テストケース(01.txt ～ s2.txt)は, 全て通過した.
3. 解説にある “頂点 i -> 頂点 i + 1 へ, 長さ 2 の i乗の辺を張る” は, “頂点 i -> 頂点 i + 1 へ, 長さ 2 の (i – 1)乗の辺を張る” に読み替えて実装した.
4. 解説にある長さX の辺に関する記述が, 何を指しているか, 理解出来なかったので, 読み飛ばしている.

本家のサイトARC 102 解説をご覧下さい.

■C++版プログラム

// 解き直し.
// ARC 102 解説.
// https://img.atcoder.jp/arc102/editorial.pdf
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(a); i>(b); --i)

struct graph {
  int s; // 始点.
  int e; // 終点.
  int l; // 長さ.
};

int main() {

    // 1. 入力情報取得.
    int L;
    cin >> L;
    
    // 2. 2 の r乗 が, L 以下となる r を取得.
    // L <= 1000000 なので, r <= 19.
    int r = 0;
    int l = L;
    while(l /= 2) r++;
    // cout << r << endl;
    
    // 3. (r + 1)個 の頂点を用意し, 条件を満たすグラフを作成.
    int N = r + 1;
    vector<graph> graphs;
    FOR(i, 1, N) {
        graph g;
        // 頂点 i -> 頂点 i + 1 へ, 長さ 0 の 辺を張る.
        g.s = i;
        g.e = i + 1;
        g.l = 0;
        graphs.push_back(g);
        // 頂点 i -> 頂点 i + 1 へ, 長さ 2 の (i - 1)乗 の 辺を張る.
        g.s = i;
        g.e = i + 1;
        g.l = (1 << (i - 1));
        graphs.push_back(g);
    }

    // 4. 頂点 N - 1 ～ 頂点 1 の 順に, 一定の条件のもとに, 辺を張る.
    FORR(i, N - 1, 0) {
        // L - (2 の (t - 1)乗) >= (2 の r乗) なら, 頂点 i -> 頂点 N へ, 長さ L - (2 の (t - 1)乗) の 辺を張る.
        int l2 = (1 << (i - 1));
        int r2 = (1 << r);
        if(L - l2 >= r2) {
            graph g;
            g.s = i;
            g.e = N;
            g.l = L - l2;
            // 01.txt - 02.txt, 04.txt - 05.txt, 08.txt - 09.txt, 12.txt - 20.txt の テストケースで失敗.
            // -> 辺を張った後, L を (2 の (t - 1)乗) だけ小さくする(※解説通り).
            L -= l2;
            graphs.push_back(g);
        }
    }
    
    // 5. グラフの頂点数, 辺数を保存.
    int vc = N;
    int ec = graphs.size();

    // 6. 出力 ～ 後処理.
    cout << vc << " " << ec << endl;
    for(auto i = graphs.begin(); i != graphs.end(); ++i) cout << i->s << " " << i->e << " " << i->l << endl;
    return 0;

}

// 解き直し.

// ARC 102 解説.

// https://img.atcoder.jp/arc102/editorial.pdf

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)

#define FORR(i, a, b) for(int i=(a); i>(b); --i)

struct graph {

int s; // 始点.

int e; // 終点.

int l; // 長さ.

};

int main() {

// 1. 入力情報取得.

int L;

cin >> L;

// 2. 2 の r乗が, L 以下となる r を取得.

// L <= 1000000 なので, r <= 19.

int r = 0;

int l = L;

while(l /= 2) r++;

// cout << r << endl;

// 3. (r + 1)個の頂点を用意し, 条件を満たすグラフを作成.

int N = r + 1;

vector<graph> graphs;

FOR(i, 1, N) {

graph g;

// 頂点 i -> 頂点 i + 1 へ, 長さ 0 の辺を張る.

g.s = i;

g.e = i + 1;

g.l = 0;

graphs.push_back(g);

// 頂点 i -> 頂点 i + 1 へ, 長さ 2 の (i - 1)乗の辺を張る.

g.s = i;

g.e = i + 1;

g.l = (1 << (i - 1));

graphs.push_back(g);

}

// 4. 頂点 N - 1 ～頂点 1 の順に, 一定の条件のもとに, 辺を張る.

FORR(i, N - 1, 0) {

// L - (2 の (t - 1)乗) >= (2 の r乗) なら, 頂点 i -> 頂点 N へ, 長さ L - (2 の (t - 1)乗) の辺を張る.

int l2 = (1 << (i - 1));

int r2 = (1 << r);

if(L - l2 >= r2) {

graph g;

g.s = i;

g.e = N;

g.l = L - l2;

// 01.txt - 02.txt, 04.txt - 05.txt, 08.txt - 09.txt, 12.txt - 20.txt のテストケースで失敗.

// -> 辺を張った後, L を (2 の (t - 1)乗) だけ小さくする(※解説通り).

L -= l2;

graphs.push_back(g);

}

// 5. グラフの頂点数, 辺数を保存.

int vc = N;

int ec = graphs.size();

// 6. 出力～後処理.

cout << vc << " " << ec << endl;

for(auto i = graphs.begin(); i != graphs.end(); ++i) cout << i->s << " " << i->e << " " << i->l << endl;

return 0;

}

[出力例]

① L = 4 の とき

3 4
1 2 0
1 2 1
2 3 0
2 3 2

→ パス 1 -> 2 -> 3 で, 長さを 0, 1, 2, 3 となるように取ることが出来る.

② L = 5 の とき

3 5
1 2 0
1 2 1
2 3 0
2 3 2
1 3 4

→ パス 1 -> 2 -> 3 で, 長さを 0, 1, 2, 3, 4 となるように取ることが出来る.

③ L = 6 の とき

3 5
1 2 0
1 2 1
2 3 0
2 3 2
2 3 4

→ パス 1 -> 2 -> 3 で, 長さを 0, 1, 2, 3, 4, 5 となるように取ることが出来る.

① L = 4 のとき

3 4

1 2 0

1 2 1

2 3 0

2 3 2

→ パス 1 -> 2 -> 3 で, 長さを 0, 1, 2, 3 となるように取ることが出来る.

② L = 5 のとき

3 5

1 2 0

1 2 1

2 3 0

2 3 2

1 3 4

→ パス 1 -> 2 -> 3 で, 長さを 0, 1, 2, 3, 4 となるように取ることが出来る.

③ L = 6 のとき

3 5

1 2 0

1 2 1

2 3 0

2 3 2

2 3 4

→ パス 1 -> 2 -> 3 で, 長さを 0, 1, 2, 3, 4, 5 となるように取ることが出来る.

■参照サイト
AtCoder Beginner Contest 108

C++の練習を兼ねて, AtCoder Beginner Contest 108 の 問題D（All Your Paths are Different Lengths）を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 108 の問題D（All Your Paths are Different Lengths）を解いてみた.

コメントを残すコメントをキャンセル