9月, 2018 | 個人用メモ帳

2018年9月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 070 の問題C（Multiple Clocks）を解いてみた.

■感想.
1. 最小公倍数を計算するときの計算順序で, 途中躓いたが, 計算順序を変えてみる方法に気付いたので, ACとなった.
2. コーディング後, 解説を見たら, おおよそ同じ方針だったので, まずまずの結果だったと思う.

本家のサイトABC 070 解説をご覧下さい.

■C++版プログラム.

#include <iostream>

using namespace std;

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

typedef long long LL;

// 最大公約数を計算.
// https://cs.stackexchange.com/questions/1447/what-is-most-efficient-for-gcd
LL gcd (LL a, LL b) {
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}

int main() {
    
    // 1. 入力情報取得.
    LL N;
    cin >> N;
    
    // 2. T1 ～ TN までの最小公倍数を計算.
    LL LCM;
    cin >> LCM;
    
    FOR(i, 0, N - 1) {
        LL ti;
        cin >> ti;
        
        // 2-1. 最大公約数計算.
        LL GCD = gcd(LCM, ti);
        
        // 2-2. 最小公倍数更新(改善前).
        // -> -4927149226598858752 などと, おかしな値が出力されるケースがあったため, コメントアウト.
        // LCM = LCM * ti / GCD;
        
        // 2-3. 最小公倍数更新(改善後).
        // 入力値 ÷ 最大公約数 を先に計算してから, 最小公倍数 を算出させるように計算順序を変更.
        LL tigcd = ti / GCD;
        LCM *= tigcd;
    }
    
    // 3. 出力 ～ 後処理.
    cout << LCM << endl;
    return 0;
    
}

#include <iostream>

using namespace std;

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

typedef long long LL;

// 最大公約数を計算.

// https://cs.stackexchange.com/questions/1447/what-is-most-efficient-for-gcd

LL gcd (LL a, LL b) {

while(b) b ^= a ^= b ^= a %= b;

return a;

}

int main() {

// 1. 入力情報取得.

LL N;

cin >> N;

// 2. T1 ～ TN までの最小公倍数を計算.

LL LCM;

cin >> LCM;

FOR(i, 0, N - 1) {

LL ti;

cin >> ti;

// 2-1. 最大公約数計算.

LL GCD = gcd(LCM, ti);

// 2-2. 最小公倍数更新(改善前).

// -> -4927149226598858752 などと, おかしな値が出力されるケースがあったため, コメントアウト.

// LCM = LCM * ti / GCD;

// 2-3. 最小公倍数更新(改善後).

// 入力値 ÷ 最大公約数を先に計算してから, 最小公倍数を算出させるように計算順序を変更.

LL tigcd = ti / GCD;

LCM *= tigcd;

}

// 3. 出力～後処理.

cout << LCM << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 070
What is most efficient for GCD?

2018年9月9日2018年9月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 109 の問題D（Make Them Even）を解いてみた.

■感想.
1. 下記 C++版プログラム(RE版) は, おそらくロジック的に間違ってないと思われるが, 時間内では, テストケース(C018_scrambled – C029_scrambled)で, Runtime Error となった.

2. Runtime Error の原因としては, ネット上の情報で, “vectorは要素数が数万くらいになるとデータ構造がぶっ壊れる？？？” との指摘をされている記事があったので, vector を使ったことが原因と推測した.
※参照URL② にあるように, vector よりも配列の方が, 処理は早いとのこと.

3. コンテスト終了後に, 解説を見たところ, 一筆書きによる解法が紹介されていたので, 下記 C++版プログラム(AC版) のような形で実装したところ, 全テストケースを通過出来た.
※但し, 一筆書きによるコイン情報の保存方法に, 一次元配列を使ったが, 不慣れなせいか, これを一筆書きの順で保存するロジックを構築するのに, 膨大な時間を使ってしまった(汗).

本家のサイトABC 109 解説をご覧下さい.

■C++版プログラム(RE版)

// C018_scrambled - C029_scrambled で, RE となった.
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
 
struct operation {
    int ys; // 始点(y1).
    int xs; // 始点(x1).
    int ye; // 終点(y'1).
    int xe; // 終点(x'1).
};
 
int main() {
 
    // 1. 入力情報取得.
    int H, W;
    cin >> H >> W;
    
    // 2. マス目に数字を保存.
    int A[500][500] = {};
    FOR(i, 1, H + 1) FOR(j, 1, W + 1) cin >> A[i][j];
    // FOR(i, 1, H + 1) FOR(j, 1, W + 1) cout << A[i][j] << endl;
    
    // 3. 偶数枚のコインが置かれたマス目の最大数は, コイン無しのマス目も含み, H * W 以下となることに注意.
    // 現在確認しているマスのコインが, 奇数枚だったら, 1枚次のマスへ移動.
    vector<operation> operations;
    FOR(i, 1, H + 1) {
        FOR(j, 1, W + 1) {
            int v = A[i][j];
            if(v % 2 != 0) {
                operation o;
                o.ys = i;
                o.xs = j;
                A[i][j]--;
                if(j < W) {
                    o.ye = i;
                    o.xe = j + 1;
                    A[i][j + 1]++;
                    operations.push_back(o);
                } else if(j == W && i < H) {
                    o.ye = i + 1;
                    o.xe = j;
                    A[i + 1][j]++;
                    operations.push_back(o);
                }
            }
        }
    }
 
    // 4. 出力 ～ 後処理.
    cout << operations.size() << endl;
    for(auto i = operations.begin(); i != operations.end(); ++i) {
        cout << i->ys << " " << i->xs << " " << i->ye << " " << i->xe << endl;
    }
    return 0;
 
}

// C018_scrambled - C029_scrambled で, RE となった.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

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

struct operation {

int ys; // 始点(y1).

int xs; // 始点(x1).

int ye; // 終点(y'1).

int xe; // 終点(x'1).

};

int main() {

// 1. 入力情報取得.

int H, W;

cin >> H >> W;

// 2. マス目に数字を保存.

int A[500][500] = {};

FOR(i, 1, H + 1) FOR(j, 1, W + 1) cin >> A[i][j];

// FOR(i, 1, H + 1) FOR(j, 1, W + 1) cout << A[i][j] << endl;

// 3. 偶数枚のコインが置かれたマス目の最大数は, コイン無しのマス目も含み, H * W 以下となることに注意.

// 現在確認しているマスのコインが, 奇数枚だったら, 1枚次のマスへ移動.

vector<operation> operations;

FOR(i, 1, H + 1) {

FOR(j, 1, W + 1) {

int v = A[i][j];

if(v % 2 != 0) {

operation o;

o.ys = i;

o.xs = j;

A[i][j]--;

if(j < W) {

o.ye = i;

o.xe = j + 1;

A[i][j + 1]++;

operations.push_back(o);

} else if(j == W && i < H) {

o.ye = i + 1;

o.xe = j;

A[i + 1][j]++;

operations.push_back(o);

}

// 4. 出力～後処理.

cout << operations.size() << endl;

for(auto i = operations.begin(); i != operations.end(); ++i) {

cout << i->ys << " " << i->xs << " " << i->ye << " " << i->xe << endl;

}

return 0;

}

■C++版プログラム(AC版)

// 解き直し.
// ABC 109 解説.
// https://img.atcoder.jp/abc109/editorial.pdf
#include <iostream>

using namespace std;

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

// 保存時インデックスに対応するマス目としての 座標(y1) を 返却.
// @param i: 保存時インデックス.
// @param W: 横方向サイズ.
// @return:  マス目としての 座標(y1) を 返却.
int getInputIndexY(int i, int W) {
    double y0 = (i + 0.0) / W;
    double y1 = i / W;
    int y = (y0 - y1 == 0.0) ? y1 : (y1 + 1);
    return y;
}

// 始点, 終点座標(y1, y'1) を 返却.
// @param i: 保存時インデックス.
// @param W: 横方向サイズ.
// @return:  マス目としての 始点, 終点座標(y1, y'1) を 返却.
int getIndexY(int i, int W) {
    double y0 = (i + 0.0) / W;
    double y1 = i / W;
    int y = (y0 - y1 == 0.0) ? y1 : (y1 + 1);
    return y;
}

// 始点, 終点座標(x1, x'1) を 返却.
// @param i: 保存時インデックス.
// @param y: マス目のインデックス(座標y).
// @param W: 横方向サイズ.
// @return:  マス目としての 始点, 終点座標(x1, x'1) を 返却.
int getIndexX(int i, int y, int W) {
    // 偶奇判定.
    bool b = (y % 2 == 0);
    int x = i - W * (y - 1);
    x = b ? (W - x + 1) : x;
    return x;
}

int main() {

    // 1. 入力情報取得.
    int H, W;
    cin >> H >> W;
    
    // 2. マス目に数字を保存.
    int A[250000] = {};    // 操作回数チェック用.
    int B[250000] = {};    // 実際の操作を出力するときに使用.
    // 一筆書きとなるように保管.
    int size = H * W + 1;
    bool isEven = false;
    FORN(i, 1, size, W) {
        int y = getInputIndexY(i, W);
        if(isEven)  FOR(j, 1, W + 1) cin >> A[y * W - j + 1];
        else        FOR(j, 1, W + 1) cin >> A[(y - 1) * W + j];
        isEven = !isEven;    // 偶奇切り替え.
    }
    FOR(i, 1, size) B[i] = A[i];
    // FOR(i, 1, size) cout << A[i] << endl;
    
    // 3. 偶数枚のコインが置かれたマス目の最大数は, コイン無しのマス目も含み, H * W 以下となることに注意.
    // 現在確認しているマスのコインが, 奇数枚だったら, 1枚次のマスへ移動.
    // -> 一筆書きで, 操作回数をカウント(解説通り).
    int count = 0;
    FOR(i, 1, size - 1) {
        int v = A[i];
        if(v % 2 != 0) {
            A[i]--;
            count++;
            A[i + 1]++;
        }
    }

    // 4. 出力 ～ 後処理.
    cout << count << endl;
    // -> 一筆書きで, 操作を出力(解説通り).
    FOR(i, 1, size - 1) {
        int v = B[i];
        if(v % 2 != 0) {
            B[i]--;

            // 一筆書き上の始点(y1).
            int ys = getIndexY(i, W);
            // 一筆書き上の始点(x1).
            int xs = getIndexX(i, ys, W);
            
            // 一筆書き上の終点(y'1).
            int ye = getIndexY(i + 1, W);
            // 一筆書き上の終点(x'1).
            int xe = getIndexX(i + 1, ye, W);
            cout << ys << " " << xs << " " << ye << " " << xe << endl;

            B[i + 1]++;
        }
    }

    return 0;

}

100

101

102

103

104

105

// 解き直し.

// ABC 109 解説.

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

#include <iostream>

using namespace std;

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

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

// 保存時インデックスに対応するマス目としての座標(y1) を返却.

// @param i: 保存時インデックス.

// @param W: 横方向サイズ.

// @return: マス目としての座標(y1) を返却.

int getInputIndexY(int i, int W) {

double y0 = (i + 0.0) / W;

double y1 = i / W;

int y = (y0 - y1 == 0.0) ? y1 : (y1 + 1);

return y;

}

// 始点, 終点座標(y1, y'1) を返却.

// @param i: 保存時インデックス.

// @param W: 横方向サイズ.

// @return: マス目としての始点, 終点座標(y1, y'1) を返却.

int getIndexY(int i, int W) {

double y0 = (i + 0.0) / W;

double y1 = i / W;

int y = (y0 - y1 == 0.0) ? y1 : (y1 + 1);

return y;

}

// 始点, 終点座標(x1, x'1) を返却.

// @param i: 保存時インデックス.

// @param y: マス目のインデックス(座標y).

// @param W: 横方向サイズ.

// @return: マス目としての始点, 終点座標(x1, x'1) を返却.

int getIndexX(int i, int y, int W) {

// 偶奇判定.

bool b = (y % 2 == 0);

int x = i - W * (y - 1);

x = b ? (W - x + 1) : x;

return x;

}

int main() {

// 1. 入力情報取得.

int H, W;

cin >> H >> W;

// 2. マス目に数字を保存.

int A[250000] = {}; // 操作回数チェック用.

int B[250000] = {}; // 実際の操作を出力するときに使用.

// 一筆書きとなるように保管.

int size = H * W + 1;

bool isEven = false;

FORN(i, 1, size, W) {

int y = getInputIndexY(i, W);

if(isEven) FOR(j, 1, W + 1) cin >> A[y * W - j + 1];

else FOR(j, 1, W + 1) cin >> A[(y - 1) * W + j];

isEven = !isEven; // 偶奇切り替え.

}

FOR(i, 1, size) B[i] = A[i];

// FOR(i, 1, size) cout << A[i] << endl;

// 3. 偶数枚のコインが置かれたマス目の最大数は, コイン無しのマス目も含み, H * W 以下となることに注意.

// 現在確認しているマスのコインが, 奇数枚だったら, 1枚次のマスへ移動.

// -> 一筆書きで, 操作回数をカウント(解説通り).

int count = 0;

FOR(i, 1, size - 1) {

int v = A[i];

if(v % 2 != 0) {

A[i]--;

count++;

A[i + 1]++;

}

// 4. 出力～後処理.

cout << count << endl;

// -> 一筆書きで, 操作を出力(解説通り).

FOR(i, 1, size - 1) {

int v = B[i];

if(v % 2 != 0) {

B[i]--;

// 一筆書き上の始点(y1).

int ys = getIndexY(i, W);

// 一筆書き上の始点(x1).

int xs = getIndexX(i, ys, W);

// 一筆書き上の終点(y'1).

int ye = getIndexY(i + 1, W);

// 一筆書き上の終点(x'1).

int xe = getIndexX(i + 1, ye, W);

cout << ys << " " << xs << " " << ye << " " << xe << endl;

B[i + 1]++;

}

return 0;

}

■参照サイト
【参照URL①】AtCoder Beginner Contest 109
【参照URL②】vectorの要素数上限とか

2018年9月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 072 の問題D（Derangement）を解いてみた.

■感想.
1. 解説の方針と, 多分おおよそ一致していると思うので, 良かったと思われる.
2. 隣り合う二つの数を選んでスワップするというシンプルな操作であるが, 個人的には, 面白い問題だったと思う.

本家のサイトABC072 / ARC082 解説をご覧下さい.

■C++版プログラム

#include <iostream>

using namespace std;

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    
    // 2. swap回数をカウントアップ.
    int bp = -99999;    // 前回出現した p の値.
    int swap = 0;       // swap回数を保存.
    FOR(i, 1, N + 1) {
        int p;
        cin >> p;
        // p = i なら, increment.
        // cout << "swap=" << swap << "  p=" << p << "  bp=" << bp << endl;
        if(p == i) swap++;
        // p = i かつ, 前回の p が, i - 1 だったら, decrement.
        if(p == i && bp == i - 1) {
            swap--;
            continue;    // 前回出現した p の値 は, 更新しない.
        }
        bp = p;
    }
    
    // 3. 出力 ～ 後処理.
    cout << swap << endl;
    return 0;
    
}

#include <iostream>

using namespace std;

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

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

// 2. swap回数をカウントアップ.

int bp = -99999; // 前回出現した p の値.

int swap = 0; // swap回数を保存.

FOR(i, 1, N + 1) {

int p;

cin >> p;

// p = i なら, increment.

// cout << "swap=" << swap << " p=" << p << " bp=" << bp << endl;

if(p == i) swap++;

// p = i かつ, 前回の p が, i - 1 だったら, decrement.

if(p == i && bp == i - 1) {

swap--;

continue; // 前回出現した p の値は, 更新しない.

}

bp = p;

}

// 3. 出力～後処理.

cout << swap << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 072

2018年9月3日

■感想.
1. Kaggle の Kernels で, プログラム実行すると, CSVファイル(results.csv) に, インデックス名 ‘ImageId’ が出力されず, 苦戦した.
2. 一つのセルで, プログラム実行(CSV出力まで)すると, 1. の現象が起こるらしいことが確認できた.
-> CSVファイル出力に関するプログラムだけ, 別セルで実行したところ, 1. の現象が解消した(※Kaggle の Kernels の bugか？).
-> 下記, Python版(Kaggle)プログラムは, 二つのセルで実行する版を転記している(※1. の現象が改善された版)
3. ちなみに, Google Colaboratory 上では, 一つのセルで, プログラム実行(CSV出力まで)しても, 想定通り, インデックス名 ‘ImageId’ が出力され, 1. の現象は起きなかった.

詳細は, 本家のサイトDigit Recognizerをご覧下さい.

■Python版(Google Colaboratory)プログラム

# 1. import library.
import pandas as pd
import matplotlib.pyplot as plt, matplotlib.image as mpimg
import numpy as np
from sklearn.model_selection import train_test_split
from sklearn import svm
from google.colab import files

# 2. Loading the data.
# The prefix is abbreviated as follows.
# Training data … a
# Test data     … b
data = pd.read_csv("drive/Machine Learning/DigitRecognizer/train.csv")
images = data.iloc[0:5000,1:]
labels = data.iloc[0:5000,:1]
aI, bI, aL, bL = train_test_split(images, labels, train_size=0.8, random_state=0)

# 3. How did our model do?
aI[aI > 0] = 1
bI[bI > 0] = 1

# 4. ReTraining our model.
clf = svm.SVC()
clf.fit(aI, aL.values.ravel())

# 5. Labelling the test data.
tdata = pd.read_csv("drive/Machine Learning/DigitRecognizer/test.csv")
tdata[tdata > 0] = 1
results = clf.predict(tdata[0:5000])
print(results)

# 6. Create CSV file of output result.
df = pd.DataFrame(results)
df.index+=1
df.index.name='ImageId'
df.columns=['Label']
df.to_csv('drive/Machine Learning/DigitRecognizer/results.csv', header=True)

# 1. import library.

import pandas as pd

import matplotlib.pyplot as plt, matplotlib.image as mpimg

import numpy as np

from sklearn.model_selection import train_test_split

from sklearn import svm

from google.colab import files

# 2. Loading the data.

# The prefix is abbreviated as follows.

# Training data … a

# Test data … b

data = pd.read_csv("drive/Machine Learning/DigitRecognizer/train.csv")

images = data.iloc[0:5000,1:]

labels = data.iloc[0:5000,:1]

aI, bI, aL, bL = train_test_split(images, labels, train_size=0.8, random_state=0)

# 3. How did our model do?

aI[aI > 0] = 1

bI[bI > 0] = 1

# 4. ReTraining our model.

clf = svm.SVC()

clf.fit(aI, aL.values.ravel())

# 5. Labelling the test data.

tdata = pd.read_csv("drive/Machine Learning/DigitRecognizer/test.csv")

tdata[tdata > 0] = 1

results = clf.predict(tdata[0:5000])

print(results)

# 6. Create CSV file of output result.

df = pd.DataFrame(results)

df.index+=1

df.index.name='ImageId'

df.columns=['Label']

df.to_csv('drive/Machine Learning/DigitRecognizer/results.csv', header=True)

■Python版(Kaggle)プログラム

# 1. import library.
import pandas as pd
import matplotlib.pyplot as plt, matplotlib.image as mpimg
import numpy as np
from sklearn.model_selection import train_test_split
from sklearn import svm

# 2. Loading the data.
# The prefix is abbreviated as follows.
# Training data … a
# Test data     … b
data = pd.read_csv("../input/train.csv")
images = data.iloc[0:5000,1:]
labels = data.iloc[0:5000,:1]
aI, bI, aL, bL = train_test_split(images, labels, train_size=0.8, random_state=0)

# 3. How did our model do?
aI[aI > 0] = 1
bI[bI > 0] = 1

# 4. ReTraining our model.
clf = svm.SVC()
clf.fit(aI, aL.values.ravel())

# 5. Labelling the test data.
tdata = pd.read_csv("../input/test.csv")
tdata[tdata > 0] = 1
results = clf.predict(tdata[0:28000])
print(results)    # [2 0 9 ... 1 7 3]

# 1. import library.

import pandas as pd

import matplotlib.pyplot as plt, matplotlib.image as mpimg

import numpy as np

from sklearn.model_selection import train_test_split

from sklearn import svm

# 2. Loading the data.

# The prefix is abbreviated as follows.

# Training data … a

# Test data … b

data = pd.read_csv("../input/train.csv")

images = data.iloc[0:5000,1:]

labels = data.iloc[0:5000,:1]

aI, bI, aL, bL = train_test_split(images, labels, train_size=0.8, random_state=0)

# 3. How did our model do?

aI[aI > 0] = 1

bI[bI > 0] = 1

# 4. ReTraining our model.

clf = svm.SVC()

clf.fit(aI, aL.values.ravel())

# 5. Labelling the test data.

tdata = pd.read_csv("../input/test.csv")

tdata[tdata > 0] = 1

results = clf.predict(tdata[0:28000])

print(results) # [2 0 9 ... 1 7 3]

# 6. Create CSV file of output result.
# -> This program was executed in next cell, because to avoid a bug on kaggle kernels 
# which the index name is not output to the CSV file when executed together with the above program.
df = pd.DataFrame(results)
df.index+=1
df.index.name='ImageId'
df.columns=['Label']
df.to_csv('results.csv', header=True)

# 6. Create CSV file of output result.

# -> This program was executed in next cell, because to avoid a bug on kaggle kernels

# which the index name is not output to the CSV file when executed together with the above program.

df = pd.DataFrame(results)

df.index+=1

df.index.name='ImageId'

df.columns=['Label']

df.to_csv('results.csv', header=True)

■ ■ ■ 提出手順(概要) ■ ■ ■
■エラー時
① CSVファイル確認（インデックス名が表示されなかった）

② 提出するためにボタン押下

③ CSVファイルアップロード、説明文追記など

④ エラー表示を確認

■OK時
① CSVファイル確認（インデックス名 ‘ImageId’ が表示された）

② 提出するためにボタン押下

③ CSVファイルアップロード、説明文追記など

④ 提出完了（チュートリアル完了、Leaderboard に掲載されることも確認できた）

■参照サイト
Digit Recognizer

2018年9月2日2018年9月3日

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

2018年9月1日2018年9月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 108 の問題C（Triangular Relationship）を解いてみた.

■感想.
1. 時間内で, テストケース C022_scrambled 以外まで通過出来た.
2. 時間後, 変数 N, K の型を int -> LL で動作確認したところ, 全テストケース通過出来た.
-> 時間内に, 変数の型が bug の原因だった点に, 気付けなかったのは残念だったが, 今後の注意点として, 覚えておくようにしたい.
3. テストケース 35897 932 -> 114191 = 54872 + 59319 = 38 * 38 * 38 + 39 * 39 * 39 に等しいことから着想を得て, 以下のようなソースコードとなったが, 個人的には, 解説されているロジックで実装するのが, 一番スマートだと思う.

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

■C++版プログラム

// 時間切れ.
#include <iostream>

using namespace std;

typedef long long LL;

int main() {
    
    // 1. 入力情報取得.
    // int N, K;
    // int -> LL に書き換えて動作確認したところ, 全テストケース通過したので, C022_scrambled も, 通過したと想定される.
    LL N, K;
    cin >> N >> K;
    
    // 2. N以下の正の整数(a, b, c)で, a + b, b + c, c + a が, Kの倍数となっているものの個数を計算.
    LL total = 0;
    // 
    // a + b = x * K, b + c = y * K, c + a = z * K (x, y, z は, 正の整数)として, 
    // a + b + c = (x + y + z) * K / 2 = t と置くと,
    // 
    // a = t - y * K = (x - y + z) * K / 2
    // b = t - z * K = (x + y - z) * K / 2
    // c = t - x * K = (- x + y + z) * K / 2
    // -> a, b, c は, いずれも, K / 2 の 倍数になっている筈.
    
    // b を K で割った余り mb. -> a, c を, K で 割った余り ma, mc は,
    // ma = K - mb, mc = K - mb だが, さらに, ma + mc が, Kの倍数になっている筈なので,
    // 2 * K - 2 * mb を K で割った余りは, ゼロの筈.
    
    // 2-1. C017_scrambled - C022_scrambled 通過出来なかったので, K == 1 のパターンを追加.
    // C017_scrambled だけ, 通過OK となった.
    if(K == 1) {
        total = N * N * N;
    }
    
    // 2-2. K = 2 の場合.
    if(K == 2) {
        LL even = N / 2;
        LL odd = N - even;
        total = (even * even * even) + (odd * odd * odd);
    }
    
    // 2-3. K > 2 の場合.
    // 10 8 -> 2 のパターンを対応するため, ロジック修正.
    if(K > 2) {
        if(K % 2 != 0) {
            LL multiplesOfK = N / K;
            total = multiplesOfK * multiplesOfK * multiplesOfK;
        } else {
            double e0 = (N + 0.0) / K;  // C022_scrambled 以外は, 通過した.
            LL e1 = N / K;
            LL e2 = e1;
            if (e0 - e1 >= 0.5) e2++;
            total = e1 * e1 * e1 + e2 * e2 * e2;
        }
    }
    
    // 3. 出力 ～ 後処理.
    cout << total << endl;
    return 0;
    
}

// 時間切れ.

#include <iostream>

using namespace std;

typedef long long LL;

int main() {

// 1. 入力情報取得.

// int N, K;

// int -> LL に書き換えて動作確認したところ, 全テストケース通過したので, C022_scrambled も, 通過したと想定される.

LL N, K;

cin >> N >> K;

// 2. N以下の正の整数(a, b, c)で, a + b, b + c, c + a が, Kの倍数となっているものの個数を計算.

LL total = 0;

// a + b = x * K, b + c = y * K, c + a = z * K (x, y, z は, 正の整数)として,

// a + b + c = (x + y + z) * K / 2 = t と置くと,

// a = t - y * K = (x - y + z) * K / 2

// b = t - z * K = (x + y - z) * K / 2

// c = t - x * K = (- x + y + z) * K / 2

// -> a, b, c は, いずれも, K / 2 の倍数になっている筈.

// b を K で割った余り mb. -> a, c を, K で割った余り ma, mc は,

// ma = K - mb, mc = K - mb だが, さらに, ma + mc が, Kの倍数になっている筈なので,

// 2 * K - 2 * mb を K で割った余りは, ゼロの筈.

// 2-1. C017_scrambled - C022_scrambled 通過出来なかったので, K == 1 のパターンを追加.

// C017_scrambled だけ, 通過OK となった.

if(K == 1) {

total = N * N * N;

}

// 2-2. K = 2 の場合.

if(K == 2) {

LL even = N / 2;

LL odd = N - even;

total = (even * even * even) + (odd * odd * odd);

}

// 2-3. K > 2 の場合.

// 10 8 -> 2 のパターンを対応するため, ロジック修正.

if(K > 2) {

if(K % 2 != 0) {

LL multiplesOfK = N / K;

total = multiplesOfK * multiplesOfK * multiplesOfK;

} else {

double e0 = (N + 0.0) / K; // C022_scrambled 以外は, 通過した.

LL e1 = N / K;

LL e2 = e1;

if (e0 - e1 >= 0.5) e2++;

total = e1 * e1 * e1 + e2 * e2 * e2;

}

// 3. 出力～後処理.

cout << total << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 108

月: 2018年9月

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

C++の練習を兼ねて, AtCoder Beginner Contest 070 の問題C（Multiple Clocks）を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 109 の問題D（Make Them Even）を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 072 の問題D（Derangement）を解いてみた.

Kaggle に挑戦してみた（１）

Kaggle の仕組みに慣れるため, Digit Recognizer (Competition）に挑戦してみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 108 の問題C（Triangular Relationship）を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 070 の 問題C（Multiple Clocks）を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 109 の 問題D（Make Them Even）を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 072 の 問題D（Derangement）を解いてみた.

Kaggle の仕組みに慣れるため, Digit Recognizer (Competition）に挑戦してみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 108 の 問題C（Triangular Relationship）を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 070 の問題C（Multiple Clocks）を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 109 の問題D（Make Them Even）を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 072 の問題D（Derangement）を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 108 の問題C（Triangular Relationship）を解いてみた.