C++ | 個人用メモ帳

2019年3月15日2019年3月15日

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

C++の練習を兼ねて, AtCoder Beginner Contest 121 の問題D (D – XOR World) を解いてみた.

■感想.
1. 問題D は, yukicoder の No.524 コインゲームで解答した内容を, 一部改変して対応したものである.
2. なお, yukicoder の No.524 コインゲームを解こうとしたときに, 解答方針が見えなかったので, 石取りゲームと排他的論理和に関する解説サイトがあったため, そのロジックを, プログラムとして再構築したものである.

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

■C++版プログラム(問題D／AC版).

// yukicoder(No.524 コインゲーム)
// https://yukicoder.me/submissions/321850
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

// n桁の0埋めの数字を作る.
// https://gin0606.hatenablog.com/entry/2013/12/24/134138
// @param s: 0埋めしたい文字列(※d桁より多い場合は, 0埋め出来ないので何もしない).
// @param d: 0埋め後の桁数.
string fillText(string s, LL d) {
    string ret = s;
    while(ret.size() < d) ret = "0" + ret;
    return ret;
}

// Use of dynamic bitset to convert decimal numbers.
// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers
// 10進数 → 2進数.
// @param n: 2進数へ変換したい10進数.
// @param d: 2進数表記する桁数.
// @return: 2進数.
string decimalToBinary(LL n, LL d) {
    if(n == 0) return fillText("0", d);
    string ret;
    LL ln = abs(n);
    while(ln) {
        ret = string((ln & 1) ? "1" : "0") + ret;
        ln /= 2;
    }
    ret = fillText(ret, d);
    if(n < 0) ret = "-" + ret;
    return ret;
}

// 1 ～ N までの排他的論理和の合計を計算.
// @param N: 上限(整数).
// @param pow2: 2 の 冪乗.
// @param D: 桁数.
// @param nXor: 排他的論理和の合計.
// @return: 排他的論理和の合計の更新結果.
void xorSum(LL N, LL pow2[], LL D, LL nXor[]) {
    
    // 0. 1 ～ N までの 排他的論理和 を計算し, その各桁の mod 2 を確認する方針とする.
    // ex. 15 までの排他的論理和の合計.
    // 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
    // -> 8888
    // 
    // ex. 他のケースについての排他的論理和の合計.
    // 19 = 16 + 0 + 0 + 2 + 1
    //    = 18888 + 00000 + 00000 + 20011 + 10011
    //    = 4, 8, 8, 10, 10
    // 27 = 16 + 8 + 0 + 2 + 1
    //    = 18888 + 81444 + 00000 + 22011 + 11011
    //    = 12, 12, 12, 14, 14
    // 29 = 16 + 8 + 1 + 0 + 1
    //    = 18888 + 81444 + 44122 + 00000 + 11101
    //    = 14, 14, 14, 14, 15

    // 1. N の 2進数表現取得.
    LL ret = 0;
    string nStr = decimalToBinary(N, D);

    // 2. N までの 排他的論理和 の 合計 に向けた準備.
    // ex. 29 ならば, nXorStock に, 以下の値を保存.
    // 1 8 8 8 8 
    // 8 1 4 4 4 
    // 4 4 1 2 2 
    // 0 0 0 0 0 
    // 1 1 1 0 1 
    LL nXorStock[D][D];
    for(LL i = 0; i < D; i++){
        int ci = nStr[i] - '0';
        for(LL j = 0; j < D; j++){
            int cj = nStr[j] - '0';
            // cj を 乗ずる必要あり(ex. N = 29 の 1 1 1 0 1 を 作成するパターンなど).
            if(j <  i) nXorStock[i][j] = (pow2[D - 1 - i]) * ci * cj;
            if(j == i) nXorStock[i][j] = 1 * ci;
            if(j >  i) nXorStock[i][j] = (pow2[D - 1 - i] / 2) * ci;
        }
    }
    
    // 3. N までの 排他的論理和 の 合計 を, 各桁ごとに(※mod 2で)取得.
    for(LL i = 0; i < D; i++) nXor[i] = 0;
    for(LL j = 0; j < D; j++) for(LL i = 0; i < D; i++) nXor[j] += nXorStock[i][j], nXor[j] %= 2;

}

int main() {
    
    // 1. 入力情報取得.
    LL A, B;
    cin >> A >> B;
    
    // 2. 2 の べき乗を保存.
    // 2 の 40乗 = 1099511627776 (> 1e12) なので, 40bitで考えてみる.
    const int LIMIT = 40;
    LL pow2[LIMIT];
    pow2[0] = 1;
    for(LL i = 1; i < LIMIT; i++) pow2[i] = 2 * pow2[i - 1];
    
    // 3. A - 1, B の 排他的論理和の合計.
    LL xorA[LIMIT], xorB[LIMIT];
    
    // [入力例]
    // 0 0
    // [出力例]
    // 549755813888
    // -> なぜか, 上記のような, おかしな結果が表示された.
    // -> 上記から, A = 0 は, A-- は行わないようにする必要があるらしい(testcase_19, testcase_20 の WA と推定).
    // A--;
    if(A > 0) A--;
    xorSum(A, pow2, LIMIT, xorA);
    xorSum(B, pow2, LIMIT, xorB);
    // for(int i = 0; i < LIMIT; i++) cout << "xorA[" << i << "]=" << xorA[i] << " xorB[" << i << "]=" << xorB[i] << endl;
    
    // 4. 後処理.
    LL ans = 0;
    for(int i = 0; i < LIMIT; i++) if(xorA[i] != xorB[i]) ans += pow2[LIMIT - 1 - i];
    cout << ans << endl;
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

// yukicoder(No.524 コインゲーム)

// https://yukicoder.me/submissions/321850

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

// n桁の0埋めの数字を作る.

// https://gin0606.hatenablog.com/entry/2013/12/24/134138

// @param s: 0埋めしたい文字列(※d桁より多い場合は, 0埋め出来ないので何もしない).

// @param d: 0埋め後の桁数.

string fillText(string s, LL d) {

string ret = s;

while(ret.size() < d) ret = "0" + ret;

return ret;

}

// Use of dynamic bitset to convert decimal numbers.

// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers

// 10進数 → 2進数.

// @param n: 2進数へ変換したい10進数.

// @param d: 2進数表記する桁数.

// @return: 2進数.

string decimalToBinary(LL n, LL d) {

if(n == 0) return fillText("0", d);

string ret;

LL ln = abs(n);

while(ln) {

ret = string((ln & 1) ? "1" : "0") + ret;

ln /= 2;

}

ret = fillText(ret, d);

if(n < 0) ret = "-" + ret;

return ret;

}

// 1 ～ N までの排他的論理和の合計を計算.

// @param N: 上限(整数).

// @param pow2: 2 の冪乗.

// @param D: 桁数.

// @param nXor: 排他的論理和の合計.

// @return: 排他的論理和の合計の更新結果.

void xorSum(LL N, LL pow2[], LL D, LL nXor[]) {

// 0. 1 ～ N までの排他的論理和を計算し, その各桁の mod 2 を確認する方針とする.

// ex. 15 までの排他的論理和の合計.

// 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

// -> 8888

// ex. 他のケースについての排他的論理和の合計.

// 19 = 16 + 0 + 0 + 2 + 1

// = 18888 + 00000 + 00000 + 20011 + 10011

// = 4, 8, 8, 10, 10

// 27 = 16 + 8 + 0 + 2 + 1

// = 18888 + 81444 + 00000 + 22011 + 11011

// = 12, 12, 12, 14, 14

// 29 = 16 + 8 + 1 + 0 + 1

// = 18888 + 81444 + 44122 + 00000 + 11101

// = 14, 14, 14, 14, 15

// 1. N の 2進数表現取得.

LL ret = 0;

string nStr = decimalToBinary(N, D);

// 2. N までの排他的論理和の合計に向けた準備.

// ex. 29 ならば, nXorStock に, 以下の値を保存.

// 1 8 8 8 8

// 8 1 4 4 4

// 4 4 1 2 2

// 0 0 0 0 0

// 1 1 1 0 1

LL nXorStock[D][D];

for(LL i = 0; i < D; i++){

int ci = nStr[i] - '0';

for(LL j = 0; j < D; j++){

int cj = nStr[j] - '0';

// cj を乗ずる必要あり(ex. N = 29 の 1 1 1 0 1 を作成するパターンなど).

if(j < i) nXorStock[i][j] = (pow2[D - 1 - i]) * ci * cj;

if(j == i) nXorStock[i][j] = 1 * ci;

if(j > i) nXorStock[i][j] = (pow2[D - 1 - i] / 2) * ci;

}

// 3. N までの排他的論理和の合計を, 各桁ごとに(※mod 2で)取得.

for(LL i = 0; i < D; i++) nXor[i] = 0;

for(LL j = 0; j < D; j++) for(LL i = 0; i < D; i++) nXor[j] += nXorStock[i][j], nXor[j] %= 2;

}

int main() {

// 1. 入力情報取得.

LL A, B;

cin >> A >> B;

// 2. 2 のべき乗を保存.

// 2 の 40乗 = 1099511627776 (> 1e12) なので, 40bitで考えてみる.

const int LIMIT = 40;

LL pow2[LIMIT];

pow2[0] = 1;

for(LL i = 1; i < LIMIT; i++) pow2[i] = 2 * pow2[i - 1];

// 3. A - 1, B の排他的論理和の合計.

LL xorA[LIMIT], xorB[LIMIT];

// [入力例]

// 0 0

// [出力例]

// 549755813888

// -> なぜか, 上記のような, おかしな結果が表示された.

// -> 上記から, A = 0 は, A-- は行わないようにする必要があるらしい(testcase_19, testcase_20 の WA と推定).

// A--;

if(A > 0) A--;

xorSum(A, pow2, LIMIT, xorA);

xorSum(B, pow2, LIMIT, xorB);

// for(int i = 0; i < LIMIT; i++) cout << "xorA[" << i << "]=" << xorA[i] << " xorB[" << i << "]=" << xorB[i] << endl;

// 4. 後処理.

LL ans = 0;

for(int i = 0; i < LIMIT; i++) if(xorA[i] != xorB[i]) ans += pow2[LIMIT - 1 - i];

cout << ans << endl;

return 0;

}

[入力例]
2 4

[出力例]
5
※AtCoderテストケースより


[入力例]
123 456

[出力例]
435
※AtCoderテストケースより


[入力例]
123456789012 123456789012

[出力例]
123456789012
※AtCoderテストケースより


[入力例]
111111111111 222222222222

[出力例(debug版)]
xorA[0]=0 xorB[0]=0
xorA[1]=0 xorB[1]=0
xorA[2]=0 xorB[2]=1
xorA[3]=1 xorB[3]=1
xorA[4]=1 xorB[4]=0
xorA[5]=0 xorB[5]=0
xorA[6]=0 xorB[6]=1
xorA[7]=1 xorB[7]=1
xorA[8]=1 xorB[8]=1
xorA[9]=1 xorB[9]=0
xorA[10]=0 xorB[10]=1
xorA[11]=1 xorB[11]=1
xorA[12]=1 xorB[12]=1
xorA[13]=1 xorB[13]=1
xorA[14]=1 xorB[14]=0
xorA[15]=0 xorB[15]=1
xorA[16]=1 xorB[16]=0
xorA[17]=0 xorB[17]=1
xorA[18]=1 xorB[18]=1
xorA[19]=1 xorB[19]=1
xorA[20]=1 xorB[20]=1
xorA[21]=1 xorB[21]=0
xorA[22]=0 xorB[22]=1
xorA[23]=1 xorB[23]=0
xorA[24]=0 xorB[24]=0
xorA[25]=0 xorB[25]=0
xorA[26]=0 xorB[26]=0
xorA[27]=0 xorB[27]=0
xorA[28]=0 xorB[28]=0
xorA[29]=0 xorB[29]=0
xorA[30]=0 xorB[30]=1
xorA[31]=1 xorB[31]=1
xorA[32]=1 xorB[32]=1
xorA[33]=1 xorB[33]=0
xorA[34]=0 xorB[34]=0
xorA[35]=0 xorB[35]=0
xorA[36]=0 xorB[36]=1
xorA[37]=1 xorB[37]=1
xorA[38]=1 xorB[38]=1
xorA[39]=1 xorB[39]=1
182062613064


[入力例]
12345654321 1000000000000

[出力例(debug版)]
xorA[0]=0 xorB[0]=1
xorA[1]=0 xorB[1]=1
xorA[2]=0 xorB[2]=1
xorA[3]=0 xorB[3]=0
xorA[4]=0 xorB[4]=1
xorA[5]=0 xorB[5]=0
xorA[6]=1 xorB[6]=0
xorA[7]=0 xorB[7]=0
xorA[8]=1 xorB[8]=1
xorA[9]=1 xorB[9]=1
xorA[10]=0 xorB[10]=0
xorA[11]=1 xorB[11]=1
xorA[12]=1 xorB[12]=0
xorA[13]=1 xorB[13]=1
xorA[14]=1 xorB[14]=0
xorA[15]=1 xorB[15]=0
xorA[16]=1 xorB[16]=1
xorA[17]=1 xorB[17]=0
xorA[18]=0 xorB[18]=1
xorA[19]=1 xorB[19]=0
xorA[20]=1 xorB[20]=0
xorA[21]=0 xorB[21]=1
xorA[22]=1 xorB[22]=0
xorA[23]=1 xorB[23]=1
xorA[24]=1 xorB[24]=0
xorA[25]=0 xorB[25]=0
xorA[26]=1 xorB[26]=0
xorA[27]=1 xorB[27]=1
xorA[28]=1 xorB[28]=0
xorA[29]=1 xorB[29]=0
xorA[30]=0 xorB[30]=0
xorA[31]=0 xorB[31]=0
xorA[32]=0 xorB[32]=0
xorA[33]=0 xorB[33]=0
xorA[34]=1 xorB[34]=0
xorA[35]=1 xorB[35]=0
xorA[36]=0 xorB[36]=0
xorA[37]=0 xorB[37]=0
xorA[38]=0 xorB[38]=0
xorA[39]=0 xorB[39]=0
1005215198256

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

2 4

[出力例]

※AtCoderテストケースより

[入力例]

123 456

[出力例]

435

※AtCoderテストケースより

[入力例]

123456789012 123456789012

[出力例]

123456789012

※AtCoderテストケースより

[入力例]

111111111111 222222222222

[出力例(debug版)]

xorA[0]=0 xorB[0]=0

xorA[1]=0 xorB[1]=0

xorA[2]=0 xorB[2]=1

xorA[3]=1 xorB[3]=1

xorA[4]=1 xorB[4]=0

xorA[5]=0 xorB[5]=0

xorA[6]=0 xorB[6]=1

xorA[7]=1 xorB[7]=1

xorA[8]=1 xorB[8]=1

xorA[9]=1 xorB[9]=0

xorA[10]=0 xorB[10]=1

xorA[11]=1 xorB[11]=1

xorA[12]=1 xorB[12]=1

xorA[13]=1 xorB[13]=1

xorA[14]=1 xorB[14]=0

xorA[15]=0 xorB[15]=1

xorA[16]=1 xorB[16]=0

xorA[17]=0 xorB[17]=1

xorA[18]=1 xorB[18]=1

xorA[19]=1 xorB[19]=1

xorA[20]=1 xorB[20]=1

xorA[21]=1 xorB[21]=0

xorA[22]=0 xorB[22]=1

xorA[23]=1 xorB[23]=0

xorA[24]=0 xorB[24]=0

xorA[25]=0 xorB[25]=0

xorA[26]=0 xorB[26]=0

xorA[27]=0 xorB[27]=0

xorA[28]=0 xorB[28]=0

xorA[29]=0 xorB[29]=0

xorA[30]=0 xorB[30]=1

xorA[31]=1 xorB[31]=1

xorA[32]=1 xorB[32]=1

xorA[33]=1 xorB[33]=0

xorA[34]=0 xorB[34]=0

xorA[35]=0 xorB[35]=0

xorA[36]=0 xorB[36]=1

xorA[37]=1 xorB[37]=1

xorA[38]=1 xorB[38]=1

xorA[39]=1 xorB[39]=1

182062613064

[入力例]

12345654321 1000000000000

[出力例(debug版)]

xorA[0]=0 xorB[0]=1

xorA[1]=0 xorB[1]=1

xorA[2]=0 xorB[2]=1

xorA[3]=0 xorB[3]=0

xorA[4]=0 xorB[4]=1

xorA[5]=0 xorB[5]=0

xorA[6]=1 xorB[6]=0

xorA[7]=0 xorB[7]=0

xorA[8]=1 xorB[8]=1

xorA[9]=1 xorB[9]=1

xorA[10]=0 xorB[10]=0

xorA[11]=1 xorB[11]=1

xorA[12]=1 xorB[12]=0

xorA[13]=1 xorB[13]=1

xorA[14]=1 xorB[14]=0

xorA[15]=1 xorB[15]=0

xorA[16]=1 xorB[16]=1

xorA[17]=1 xorB[17]=0

xorA[18]=0 xorB[18]=1

xorA[19]=1 xorB[19]=0

xorA[20]=1 xorB[20]=0

xorA[21]=0 xorB[21]=1

xorA[22]=1 xorB[22]=0

xorA[23]=1 xorB[23]=1

xorA[24]=1 xorB[24]=0

xorA[25]=0 xorB[25]=0

xorA[26]=1 xorB[26]=0

xorA[27]=1 xorB[27]=1

xorA[28]=1 xorB[28]=0

xorA[29]=1 xorB[29]=0

xorA[30]=0 xorB[30]=0

xorA[31]=0 xorB[31]=0

xorA[32]=0 xorB[32]=0

xorA[33]=0 xorB[33]=0

xorA[34]=1 xorB[34]=0

xorA[35]=1 xorB[35]=0

xorA[36]=0 xorB[36]=0

xorA[37]=0 xorB[37]=0

xorA[38]=0 xorB[38]=0

xorA[39]=0 xorB[39]=0

1005215198256

■参照サイト
AtCoder Beginner Contest 121
No.524 コインゲーム
 ニム（複数山の石取りゲーム）の必勝法

2019年2月23日2019年2月23日

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

C++の練習を兼ねて, AtCoder Beginner Contest 096 の問題C（Grid Repainting 2) ～問題D (Five, Five Everywhere) を解いてみた.

■感想.
1. 問題C は, 結構前に解いた内容を記載した(※Pythonで記載してる理由).
2. 問題D は, 素数p の中で, p = 5 × n + 1 の形となっているものを探索すれば十分なことに気付いたので, 解答に辿り着いた.
-> 解説と全く同じ方針だったので, 及第点は取れたと思われる.

本家のサイトAtCoder Beginner Contest 096 解説をご覧下さい.

■Python版プログラム(問題C／AC版).

# -*- coding: utf-8 -*-
# 1. 入力情報取得.
H, W = map(int, input().split())
board = []
for i in range(H):
    board.append(list(input()))

# 2. 黒色着色時に, 'P' を置くことにするが, 可能であるかチェックする関数.
def checkP(i, j, b, t):

    # 2-1. vertor [1, 0] 方向でチェック.
    if i < H - 1 and (t == '#' or t == 'P'):
        x = b[i + 1][j]
        if x == '#' or x == 'P':
            return True

    # 2-2. vertor [-1, 0] 方向でチェック.
    if i > 0 and (t == '#' or t == 'P'):
        x = b[i - 1][j]
        if x == '#' or x == 'P':
            return True

    # 2-3. vertor [0, 1] 方向でチェック.
    if j < W - 1 and (t == '#' or t == 'P'):
        x = b[i][j + 1]
        if x == '#' or x == 'P':
            return True

    # 2-4. vertor [0, -1] 方向でチェック.
    if j > 0 and (t == '#' or t == 'P'):
        x = b[i][j - 1]
        if x == '#' or x == 'P':
            return True

    # 2-5. 上記以外は, 'P' と置けない.
    return False

# 3. 黒色着色('P' or '#' で, 黒色着色(※'P'に置き換え)).
for i, r in enumerate(board):
    for j, c in enumerate(r):
        if c == 'P' or c == '#':
            if checkP(i, j, board, c):
	            board[i][j] = 'P'

# 4. 未着色の'#'が, 0個ならば, 'YES', 1個以上あれば, 'NO'.
# Making a flat list out of list of lists in Python.
# https://stackoverflow.com/questions/952914/making-a-flat-list-out-of-list-of-lists-in-python/952952#952952
board = [item for sublist in board for item in sublist]
answer = ','.join(board)
if answer.count('#') == 0:
    print('Yes')
else:
    print('No')

# -*- coding: utf-8 -*-

# 1. 入力情報取得.

H, W = map(int, input().split())

board = []

for i in range(H):

board.append(list(input()))

# 2. 黒色着色時に, 'P' を置くことにするが, 可能であるかチェックする関数.

def checkP(i, j, b, t):

# 2-1. vertor [1, 0] 方向でチェック.

if i < H - 1 and (t == '#' or t == 'P'):

x = b[i + 1][j]

if x == '#' or x == 'P':

return True

# 2-2. vertor [-1, 0] 方向でチェック.

if i > 0 and (t == '#' or t == 'P'):

x = b[i - 1][j]

if x == '#' or x == 'P':

return True

# 2-3. vertor [0, 1] 方向でチェック.

if j < W - 1 and (t == '#' or t == 'P'):

x = b[i][j + 1]

if x == '#' or x == 'P':

return True

# 2-4. vertor [0, -1] 方向でチェック.

if j > 0 and (t == '#' or t == 'P'):

x = b[i][j - 1]

if x == '#' or x == 'P':

return True

# 2-5. 上記以外は, 'P' と置けない.

return False

# 3. 黒色着色('P' or '#' で, 黒色着色(※'P'に置き換え)).

for i, r in enumerate(board):

for j, c in enumerate(r):

if c == 'P' or c == '#':

if checkP(i, j, board, c):

board[i][j] = 'P'

# 4. 未着色の'#'が, 0個ならば, 'YES', 1個以上あれば, 'NO'.

# Making a flat list out of list of lists in Python.

# https://stackoverflow.com/questions/952914/making-a-flat-list-out-of-list-of-lists-in-python/952952#952952

board = [item for sublist in board for item in sublist]

answer = ','.join(board)

if answer.count('#') == 0:

print('Yes')

else:

print('No')

■C++版プログラム(問題D／AC版).

#include <bits/stdc++.h>
using namespace std;
#define FORN(i, a, b, n) for(int i = (a); i < (b); i += n)

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;

    // 2. 素数を用意する.
    map<int, int> m;
    m[2]++;
    FORN(i, 3, 55555, 2) {
        bool isPrime = true;
        FORN(j, 3, sqrt(i) + 1, 2) {
            if(i % j == 0){
                isPrime = false;
                break;
            }
        }
        if(isPrime) m[i]++;
    }
    
    // 3. 素数p の中で, p = 5 × n + 1 の形となっているものを探索.
    // ex.
    // 素数11 の 場合は, 11 = 5 * 2 + 1 -> OK
    // 素数13 の 場合は, 13 = 5 * 2 + 3 -> NG
    // 素数41 の 場合は, 41 = 5 * 8 + 1 -> OK
    // ...
    // -> 55個以上存在することが判明した.
    // 11 31 41 61 71 101 131 151 181 191 
    // 211 241 251 271 281 311 331 401 421 431 
    // 461 491 521 541 571 601 631 641 661 691 
    // 701 751 761 811 821 881 911 941 971 991 
    // 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 
    // 1291 1301 1321 1361 1381 1451 ...
    // for(auto & p : m) if((p.first - 1) % 5 == 0) cout << p.first << " ";
    
    // 4. 出力.
    // -> 3. の 条件 に絞りこんで出力.
    int counter = 0;
    for(auto &p : m){
        int n = p.first;
        if((n - 1) % 5 == 0){
            counter++;
            cout << n << " ";
        }
        if(counter >= N) break;
    }
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

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

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

// 2. 素数を用意する.

map<int, int> m;

m[2]++;

FORN(i, 3, 55555, 2) {

bool isPrime = true;

FORN(j, 3, sqrt(i) + 1, 2) {

if(i % j == 0){

isPrime = false;

break;

}

if(isPrime) m[i]++;

}

// 3. 素数p の中で, p = 5 × n + 1 の形となっているものを探索.

// ex.

// 素数11 の場合は, 11 = 5 * 2 + 1 -> OK

// 素数13 の場合は, 13 = 5 * 2 + 3 -> NG

// 素数41 の場合は, 41 = 5 * 8 + 1 -> OK

// ...

// -> 55個以上存在することが判明した.

// 11 31 41 61 71 101 131 151 181 191

// 211 241 251 271 281 311 331 401 421 431

// 461 491 521 541 571 601 631 641 661 691

// 701 751 761 811 821 881 911 941 971 991

// 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231

// 1291 1301 1321 1361 1381 1451 ...

// for(auto & p : m) if((p.first - 1) % 5 == 0) cout << p.first << " ";

// 4. 出力.

// -> 3. の条件に絞りこんで出力.

int counter = 0;

for(auto &p : m){

int n = p.first;

if((n - 1) % 5 == 0){

counter++;

cout << n << " ";

}

if(counter >= N) break;

}

return 0;

}

[入力例]
5
※AtCoderテストケースより

[出力例]
11 31 41 61 71 

[入力例]
6
※AtCoderテストケースより

[出力例]
11 31 41 61 71 101 

[入力例]
8
※AtCoderテストケースより

[出力例]
11 31 41 61 71 101 131 151 

[入力例]
55

[出力例]
11 31 41 61 71 101 131 151 181 191 211 241 251 271 281 311 331 401 421 431 461 491 521 541 571 601 631 641 661 691 701 751 761 811 821 881 911 941 971 991 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 1291 1301 1321 1361 1381 

[入力例]
100

[出力例]
11 31 41 61 71 101 131 151 181 191 211 241 251 271 281 311 331 401 421 431 461 491 521 541 571 601 631 641 661 691 701 751 761 811 821 881 911 941 971 991 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 1291 1301 1321 1361 1381 1451 1471 1481 1511 1531 1571 1601 1621 1721 1741 1801 1811 1831 1861 1871 1901 1931 1951 2011 2081 2111 2131 2141 2161 2221 2251 2281 2311 2341 2351 2371 2381 2411 2441 2521 2531 2551 2591 2621 2671 2711 2731 2741 2791 2801

[入力例]

※AtCoderテストケースより

[出力例]

11 31 41 61 71

[入力例]

※AtCoderテストケースより

[出力例]

11 31 41 61 71 101

[入力例]

※AtCoderテストケースより

[出力例]

11 31 41 61 71 101 131 151

[入力例]

[出力例]

[入力例]

100

[出力例]

11 31 41 61 71 101 131 151 181 191 211 241 251 271 281 311 331 401 421 431 461 491 521 541 571 601 631 641 661 691 701 751 761 811 821 881 911 941 971 991 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 1291 1301 1321 1361 1381 1451 1471 1481 1511 1531 1571 1601 1621 1721 1741 1801 1811 1831 1861 1871 1901 1931 1951 2011 2081 2111 2131 2141 2161 2221 2251 2281 2311 2341 2351 2371 2381 2411 2441 2521 2531 2551 2591 2621 2671 2711 2731 2741 2791 2801

■参照サイト
AtCoder Beginner Contest 096

2019年2月10日2019年2月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 117 の問題C（Streamline) ～問題D (XXOR) を解いてみた.

■感想.
1. 問題D は, 方針が掴めなかったので, 解説を確認して, おそらく, こんな感じと思った内容でコーディングしたものである.

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

■C++版プログラム(問題C／AC版).

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
const int LIMIT = 1e5;

int main() {
    
    // 1. 入力情報取得.
    int N, M;
    cin >> N >> M;
    int X[M];
    FOR(i, 0, M) cin >> X[i], X[i] += LIMIT;
    
    // 2. 駒の移動回数をカウント.
    // 2-1. N >= M なら, 移動回数はゼロ回.
    LL ans = 0;
    if(N >= M){
        cout << ans << endl;
        return 0;
    }
    
    // 2-2. 区間の距離を保存.
    sort(X, X + M);
    int DIFF[M - 1];
    DIFF[0] = X[1] - X[0];
    FOR(i, 1, M) DIFF[i] = X[i + 1] - X[i];
    // FOR(i, 0, M) cout << X[i] << " ";
    // cout << endl;
    
    // 3. 区間の距離を降順sort.
    sort(DIFF, DIFF + M - 1);
    // FOR(i, 0, M - 1) cout << DIFF[i] << " ";
    
    // 4. 回数の最小値を計算.
    FOR(i, 0, M - N) ans += DIFF[i];
    
    // 5. 後処理.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

const int LIMIT = 1e5;

int main() {

// 1. 入力情報取得.

int N, M;

cin >> N >> M;

int X[M];

FOR(i, 0, M) cin >> X[i], X[i] += LIMIT;

// 2. 駒の移動回数をカウント.

// 2-1. N >= M なら, 移動回数はゼロ回.

LL ans = 0;

if(N >= M){

cout << ans << endl;

return 0;

}

// 2-2. 区間の距離を保存.

sort(X, X + M);

int DIFF[M - 1];

DIFF[0] = X[1] - X[0];

FOR(i, 1, M) DIFF[i] = X[i + 1] - X[i];

// FOR(i, 0, M) cout << X[i] << " ";

// cout << endl;

// 3. 区間の距離を降順sort.

sort(DIFF, DIFF + M - 1);

// FOR(i, 0, M - 1) cout << DIFF[i] << " ";

// 4. 回数の最小値を計算.

FOR(i, 0, M - N) ans += DIFF[i];

// 5. 後処理.

cout << ans << endl;

return 0;

}

■C++版プログラム(問題D／AC版).

// 解き直し.
// ABC 117 解説.
// https://img.atcoder.jp/abc117/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL DIGIT = 40;

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

// n桁の0埋めの数字を作る.
// https://gin0606.hatenablog.com/entry/2013/12/24/134138
// @param s: 0埋めしたい文字列(※d桁より多い場合は, 0埋め出来ないので何もしない).
// @param d: 0埋め後の桁数.
string fillText(string s, LL d) {
    string ret = s;
    while(ret.size() < d) ret = "0" + ret;
    return ret;
}

// Use of dynamic bitset to convert decimal numbers.
// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers
// 10進数 → 2進数.
// @param n: 2進数へ変換したい10進数.
// @param d: 2進数表記する桁数.
// @return: 2進数.
string decimalToBinary(LL n, LL d) {
    if(n == 0) return fillText("0", d);
    string ret;
    LL ln = abs(n);
    while(ln) {
        ret = string((ln & 1) ? "1" : "0") + ret;
        ln /= 2;
    }
    ret = fillText(ret, d);
    if(n < 0) ret = "-" + ret;
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    // 以下, 解説通り.
    LL N, K;
    cin >> N >> K;
    string A[N];
    FOR(i, 0, N){
        LL a;
        cin >> a;
        // 40桁で設定.
        A[i] = decimalToBinary(a, DIGIT);
    }
    // ex.
    // 6 -> "0000000000000000000000000000000000000110"
    // FOR(i, 0, N) cout << A[i] << " ";
    // cout << endl;
    
    // 2. 2のべき乗を保存.
    LL pow2[DIGIT] = {};
    pow2[DIGIT - 1] = 1;
    FOR(i, 2, DIGIT + 1) pow2[DIGIT - i] = (2 * pow2[DIGIT - i + 1]);
    // ex.
    // pow2[0] = 549755813888, pow2[1] = 274877906944, ..., pow2[38] = 2, pow2[39] = 1
    // FOR(i, 0, DIGIT) cout << pow2[i] << " ";
    // cout << endl;
    
    // 3. A[0] ～ A[N - 1] の各桁について, 1の個数をカウント.
    LL bit1[DIGIT] = {};
    FOR(i, 0, DIGIT) FOR(j, 0, N) if(A[j][i] == '1') bit1[i]++;
    // FOR(i, 0, DIGIT) cout << bit1[i] << " ";
    // cout << endl;
    
    // 4. f の 最大値 を 計算.
    string bitK = decimalToBinary(K, DIGIT);
    string maxX  = "0000000000000000000000000000000000000000";
    LL ans = 0LL;
    FOR(i, 0, DIGIT){
        
        // i桁目で, maxX[i] を '0', '1' の場合で比較.
        // 4-1. maxX[i] = '0' の場合.
        string X0 = maxX;
        X0[i] = '0';
        LL inc0 = pow2[i] * bit1[i];
        
        // 4-2. maxX[i] = '1' の場合.
        string X1 = maxX;
        X1[i] = '1';
        LL inc1 = pow2[i] * (N - bit1[i]);
        
        // 4-3. 更新.
        if(X1 <= bitK && inc0 < inc1)  ans += inc1, maxX = X1;
        if(X1 <= bitK && inc0 >= inc1) ans += inc0, maxX = X0;
        if(X1 >  bitK)                 ans += inc0, maxX = X0;
        
    }
    
    // 5. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;

}

100

101

// 解き直し.

// ABC 117 解説.

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL DIGIT = 40;

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

// n桁の0埋めの数字を作る.

// https://gin0606.hatenablog.com/entry/2013/12/24/134138

// @param s: 0埋めしたい文字列(※d桁より多い場合は, 0埋め出来ないので何もしない).

// @param d: 0埋め後の桁数.

string fillText(string s, LL d) {

string ret = s;

while(ret.size() < d) ret = "0" + ret;

return ret;

}

// Use of dynamic bitset to convert decimal numbers.

// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers

// 10進数 → 2進数.

// @param n: 2進数へ変換したい10進数.

// @param d: 2進数表記する桁数.

// @return: 2進数.

string decimalToBinary(LL n, LL d) {

if(n == 0) return fillText("0", d);

string ret;

LL ln = abs(n);

while(ln) {

ret = string((ln & 1) ? "1" : "0") + ret;

ln /= 2;

}

ret = fillText(ret, d);

if(n < 0) ret = "-" + ret;

return ret;

}

int main() {

// 1. 入力情報取得.

// 以下, 解説通り.

LL N, K;

cin >> N >> K;

string A[N];

FOR(i, 0, N){

LL a;

cin >> a;

// 40桁で設定.

A[i] = decimalToBinary(a, DIGIT);

}

// ex.

// 6 -> "0000000000000000000000000000000000000110"

// FOR(i, 0, N) cout << A[i] << " ";

// cout << endl;

// 2. 2のべき乗を保存.

LL pow2[DIGIT] = {};

pow2[DIGIT - 1] = 1;

FOR(i, 2, DIGIT + 1) pow2[DIGIT - i] = (2 * pow2[DIGIT - i + 1]);

// ex.

// pow2[0] = 549755813888, pow2[1] = 274877906944, ..., pow2[38] = 2, pow2[39] = 1

// FOR(i, 0, DIGIT) cout << pow2[i] << " ";

// cout << endl;

// 3. A[0] ～ A[N - 1] の各桁について, 1の個数をカウント.

LL bit1[DIGIT] = {};

FOR(i, 0, DIGIT) FOR(j, 0, N) if(A[j][i] == '1') bit1[i]++;

// FOR(i, 0, DIGIT) cout << bit1[i] << " ";

// cout << endl;

// 4. f の最大値を計算.

string bitK = decimalToBinary(K, DIGIT);

string maxX = "0000000000000000000000000000000000000000";

LL ans = 0LL;

FOR(i, 0, DIGIT){

// i桁目で, maxX[i] を '0', '1' の場合で比較.

// 4-1. maxX[i] = '0' の場合.

string X0 = maxX;

X0[i] = '0';

LL inc0 = pow2[i] * bit1[i];

// 4-2. maxX[i] = '1' の場合.

string X1 = maxX;

X1[i] = '1';

LL inc1 = pow2[i] * (N - bit1[i]);

// 4-3. 更新.

if(X1 <= bitK && inc0 < inc1) ans += inc1, maxX = X1;

if(X1 <= bitK && inc0 >= inc1) ans += inc0, maxX = X0;

if(X1 > bitK) ans += inc0, maxX = X0;

}

// 5. 出力～後処理.

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 117

2019年1月27日2019年1月27日

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

C++の練習を兼ねて, AtCoder Beginner Contest 084 の問題C（Special Trains) ～問題D (2017-like Number) を解いてみた.

■感想.
1. 問題C は, いったん解いてみたが, ロジックのバグを直すことが出来なかったため, 解答を参照して, 復習した.
2. 問題D は, いったん解いて, TLE版まで持ってこれたので, 2017に似た数のテーブルを持たせたりして, 計算量を減らすように修正したところ, AC版に到達出来た.

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

■C++版プログラム(問題C／WA版).

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

struct train {
    int c;  // 駅間にかかる列車時間(秒).
    int s;  // 開通式開始後(秒).
    int f;  // 列車の発車頻度(秒).
};

// 駅(start + 1) ～ 駅N までの 開通式開始秒後を計算.
// @param start: 駅番号 - 1.
// @param N: 駅情報のサイズ.
// @param v: 駅情報.
// @return : 計算結果.
int getTrainTime(int start, int N, vector<train> v){

    int buf[N] = {};
    FOR(i, start, N - 1){
        if(i == start) {
            buf[i + 1] = v[i].s + v[i].c;
            continue;
        }
        buf[i + 1] += buf[i];
        buf[i + 1] += v[i].c;
        int dt = buf[i] - v[i].s;
        cout << dt << endl;
        if(dt >= 0) buf[i + 1] += (dt % v[i].f);
        else        buf[i + 1] += (-dt);
    }
    return buf[N - 1];

}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<train> v;
    FOR(i, 0, N - 1) {
        train t;
        cin >> t.c >> t.s >> t.f;
        v.push_back(t);
    }

    // 2. 各駅 ～ 駅N の 開通式開始秒後を計算.
    int ans[N] = {};
    FOR(i, 0, N - 1) ans[i] = getTrainTime(i, N, v);
    
    // 3. 出力 ～ 後処理.
    FOR(i, 0, N) cout << ans[i] << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

struct train {

int c; // 駅間にかかる列車時間(秒).

int s; // 開通式開始後(秒).

int f; // 列車の発車頻度(秒).

};

// 駅(start + 1) ～駅N までの開通式開始秒後を計算.

// @param start: 駅番号 - 1.

// @param N: 駅情報のサイズ.

// @param v: 駅情報.

// @return : 計算結果.

int getTrainTime(int start, int N, vector<train> v){

int buf[N] = {};

FOR(i, start, N - 1){

if(i == start) {

buf[i + 1] = v[i].s + v[i].c;

continue;

}

buf[i + 1] += buf[i];

buf[i + 1] += v[i].c;

int dt = buf[i] - v[i].s;

cout << dt << endl;

if(dt >= 0) buf[i + 1] += (dt % v[i].f);

else buf[i + 1] += (-dt);

}

return buf[N - 1];

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

vector<train> v;

FOR(i, 0, N - 1) {

train t;

cin >> t.c >> t.s >> t.f;

v.push_back(t);

}

// 2. 各駅～駅N の開通式開始秒後を計算.

int ans[N] = {};

FOR(i, 0, N - 1) ans[i] = getTrainTime(i, N, v);

// 3. 出力～後処理.

FOR(i, 0, N) cout << ans[i] << endl;

return 0;

}

■C++版プログラム(問題C／AC版).

// 解き直し.
// ABC 084 解説.
// https://img.atcoder.jp/abc084/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

struct train {
    int c;  // 駅間にかかる列車時間(秒).
    int s;  // 開通式開始後(秒).
    int f;  // 列車の発車頻度(秒).
};

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<train> v;
    FOR(i, 0, N - 1) {
        train t;
        cin >> t.c >> t.s >> t.f;
        v.push_back(t);
    }

    // 2. 解説通り.
    int ans[N] = {};
    FOR(i, 0, N) {
        int t = 0;
        FOR(j, i, N - 1){
            train vj = v[j];
            if(t < vj.s) t = vj.s;
            else if(t % vj.f == 0);
            else t = t + vj.f - t % vj.f;
            t += vj.c;
        }
        cout << t << endl;
    }
    
    return 0;
    
}

// 解き直し.

// ABC 084 解説.

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

#include <bits/stdc++.h>

using namespace std;

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

struct train {

int c; // 駅間にかかる列車時間(秒).

int s; // 開通式開始後(秒).

int f; // 列車の発車頻度(秒).

};

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

vector<train> v;

FOR(i, 0, N - 1) {

train t;

cin >> t.c >> t.s >> t.f;

v.push_back(t);

}

// 2. 解説通り.

int ans[N] = {};

FOR(i, 0, N) {

int t = 0;

FOR(j, i, N - 1){

train vj = v[j];

if(t < vj.s) t = vj.s;

else if(t % vj.f == 0);

else t = t + vj.f - t % vj.f;

t += vj.c;

}

cout << t << endl;

}

return 0;

}

■C++版プログラム(問題D／TLE版).

// TLE版(01.txt - 07.txt).
#include <bits/stdc++.h>
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)

// 2017に似た数であるかの判定.
// @param m: 素数マップ.
// @param n: 与えられた奇数.
// @return: 2017に似た数 … true, そうでない場合 … false.
bool is2017Like(map<int, int> m, int n){
    int x = (n + 1) / 2;
    // cout << "n=" << n << " x=" << x << endl;
    if(m[n] == 1 && m[x] == 1) return true;
    else                       return false;
}

int main() {
    
    // 1. 入力情報取得.
    int Q;
    cin >> Q;
    int left[Q], right[Q];
    FOR(i, 0, Q) cin >> left[i] >> right[i];

    // 2. 素数を用意する.
    map<int, int> m;
    vector<int> v;
    m[2]++;
    v.push_back(2);
    FORN(i, 3, 100002, 2) {
        bool isPrime = true;
        FORN(j, 3, sqrt(i) + 1, 2) {
            if(i % j == 0){
                isPrime = false;
                break;
            }
        }
        if(isPrime) m[i]++, v.push_back(i);
    }
    
    // 3. 2017に似た数の個数を計算.
    FOR(i, 0, Q){
        // 3-1. 各変数初期化.
        int l = left[i];
        int r = right[i];
        int like2017 = 0;
        
        // 3-2. l ～ r で, 2017に似た数の個数をカウント.
        FORN(j, l, r + 1, 2) if(j % 2 == 1 && j >= l && j <= r && is2017Like(m, j)) like2017++;
        
        // 3-3. 出力.
        cout << like2017 << endl;
    }
    
    return 0;

}

// TLE版(01.txt - 07.txt).

#include <bits/stdc++.h>

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)

// 2017に似た数であるかの判定.

// @param m: 素数マップ.

// @param n: 与えられた奇数.

// @return: 2017に似た数 … true, そうでない場合 … false.

bool is2017Like(map<int, int> m, int n){

int x = (n + 1) / 2;

// cout << "n=" << n << " x=" << x << endl;

if(m[n] == 1 && m[x] == 1) return true;

else return false;

}

int main() {

// 1. 入力情報取得.

int Q;

cin >> Q;

int left[Q], right[Q];

FOR(i, 0, Q) cin >> left[i] >> right[i];

// 2. 素数を用意する.

map<int, int> m;

vector<int> v;

m[2]++;

v.push_back(2);

FORN(i, 3, 100002, 2) {

bool isPrime = true;

FORN(j, 3, sqrt(i) + 1, 2) {

if(i % j == 0){

isPrime = false;

break;

}

if(isPrime) m[i]++, v.push_back(i);

}

// 3. 2017に似た数の個数を計算.

FOR(i, 0, Q){

// 3-1. 各変数初期化.

int l = left[i];

int r = right[i];

int like2017 = 0;

// 3-2. l ～ r で, 2017に似た数の個数をカウント.

FORN(j, l, r + 1, 2) if(j % 2 == 1 && j >= l && j <= r && is2017Like(m, j)) like2017++;

// 3-3. 出力.

cout << like2017 << endl;

}

return 0;

}

■C++版プログラム(問題D／AC版).

#include <bits/stdc++.h>
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)

int main() {
    
    // 1. 入力情報取得.
    int Q;
    cin >> Q;
    int left[Q], right[Q];
    FOR(i, 0, Q) cin >> left[i] >> right[i];

    // 2. 素数を用意する.
    map<int, int> m;
    vector<int> v;
    m[2]++;
    v.push_back(2);
    FORN(i, 3, 100002, 2) {
        bool isPrime = true;
        FORN(j, 3, sqrt(i) + 1, 2) {
            if(i % j == 0){
                isPrime = false;
                break;
            }
        }
        if(isPrime) m[i]++, v.push_back(i);
    }
    
    // 3. 2017に似た数を用意する.
    // ex. 3, 5, 13, 37, 61, 73, 157, 193, 277, 313
    vector<int> v2017;
    for(auto &p : v) {
        int x = (p + 1) / 2;
        if(m[x] == 1) v2017.push_back(p);
    }
    // FOR(i, 0, 10) cout << v2017[i] << endl;
    
    // 4. 2017に似た数の個数を計算.
    FOR(i, 0, Q){
        // 4-1. 各変数初期化.
        int l = left[i];
        int r = right[i];
        int like2017 = 0;
        
        // 4-2. l ～ r で, 2017に似た数の個数をカウント.
        vector<int>::iterator lItr, rItr;
        lItr = lower_bound(v2017.begin(), v2017.end(), l);
        rItr = upper_bound(v2017.begin(), v2017.end(), r);
        int lIndex = distance(v2017.begin(), lItr);
        int rIndex = distance(v2017.begin(), rItr);
        // cout << "l=" << l << " r=" << r << " lIndex=" << lIndex << " rIndex=" << rIndex << endl;
        int diff = rIndex - lIndex;
        like2017 += diff;
        
        // 4-3. 出力.
        cout << like2017 << endl;
    }
    
    return 0;

}

#include <bits/stdc++.h>

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)

int main() {

// 1. 入力情報取得.

int Q;

cin >> Q;

int left[Q], right[Q];

FOR(i, 0, Q) cin >> left[i] >> right[i];

// 2. 素数を用意する.

map<int, int> m;

vector<int> v;

m[2]++;

v.push_back(2);

FORN(i, 3, 100002, 2) {

bool isPrime = true;

FORN(j, 3, sqrt(i) + 1, 2) {

if(i % j == 0){

isPrime = false;

break;

}

if(isPrime) m[i]++, v.push_back(i);

}

// 3. 2017に似た数を用意する.

// ex. 3, 5, 13, 37, 61, 73, 157, 193, 277, 313

vector<int> v2017;

for(auto &p : v) {

int x = (p + 1) / 2;

if(m[x] == 1) v2017.push_back(p);

}

// FOR(i, 0, 10) cout << v2017[i] << endl;

// 4. 2017に似た数の個数を計算.

FOR(i, 0, Q){

// 4-1. 各変数初期化.

int l = left[i];

int r = right[i];

int like2017 = 0;

// 4-2. l ～ r で, 2017に似た数の個数をカウント.

vector<int>::iterator lItr, rItr;

lItr = lower_bound(v2017.begin(), v2017.end(), l);

rItr = upper_bound(v2017.begin(), v2017.end(), r);

int lIndex = distance(v2017.begin(), lItr);

int rIndex = distance(v2017.begin(), rItr);

// cout << "l=" << l << " r=" << r << " lIndex=" << lIndex << " rIndex=" << rIndex << endl;

int diff = rIndex - lIndex;

like2017 += diff;

// 4-3. 出力.

cout << like2017 << endl;

}

return 0;

}

[入力例]
1
3 7

[出力例(debug版)]
l=3 r=7 lIndex=0 rIndex=2
2
※AtCoderのテストケースより

[入力例]
4
13 13
7 11
7 11
2017 2017

[出力例(debug版)]
l=13 r=13 lIndex=2 rIndex=3
1
l=7 r=11 lIndex=2 rIndex=2
0
l=7 r=11 lIndex=2 rIndex=2
0
l=2017 r=2017 lIndex=35 rIndex=36
1
※AtCoderのテストケースより

[入力例]
6
1 53
13 91
37 55
19 51
73 91
13 49

[出力例(debug版)]
l=1 r=53 lIndex=0 rIndex=4
4
l=13 r=91 lIndex=2 rIndex=6
4
l=37 r=55 lIndex=3 rIndex=4
1
l=19 r=51 lIndex=3 rIndex=4
1
l=73 r=91 lIndex=5 rIndex=6
1
l=13 r=49 lIndex=2 rIndex=4
2
※AtCoderのテストケースより

[入力例]

3 7

[出力例(debug版)]

l=3 r=7 lIndex=0 rIndex=2

※AtCoderのテストケースより

[入力例]

13 13

7 11

2017 2017

[出力例(debug版)]

l=13 r=13 lIndex=2 rIndex=3

l=7 r=11 lIndex=2 rIndex=2

l=2017 r=2017 lIndex=35 rIndex=36

※AtCoderのテストケースより

[入力例]

1 53

13 91

37 55

19 51

73 91

13 49

[出力例(debug版)]

l=1 r=53 lIndex=0 rIndex=4

l=13 r=91 lIndex=2 rIndex=6

l=37 r=55 lIndex=3 rIndex=4

l=19 r=51 lIndex=3 rIndex=4

l=73 r=91 lIndex=5 rIndex=6

l=13 r=49 lIndex=2 rIndex=4

※AtCoderのテストケースより

■参照サイト
AtCoder Beginner Contest 084

2019年1月27日2019年1月27日

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

C++の練習を兼ねて, AtCoder Beginner Contest 083 の問題C（Multiple Gift) ～問題D (Wide Flip) を解いてみた.

■感想.
1. 問題D は, 解答方針が見えなかったので, 解説を参照して確認した.

本家のサイトARC 088/ABC 083 解説をご覧下さい.

■C++版プログラム(問題C／AC版).

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
    
    // 1. 入力情報取得.
    LL X, Y;
    cin >> X >> Y;
    
    // 2. 条件を満たす数列を計算.
    LL curA = X;    // 今回の計算結果保存用.
    LL befA = curA; // 前回の計算結果保存用.
    LL ans = 1;     // 数列の長さ.
    while(true) {
       curA = 2 * befA;
       befA = curA;
       ans++;
       if(curA > Y) {
           ans--;
           break;
       }
    }
    
    // 3. 後処理.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {

// 1. 入力情報取得.

LL X, Y;

cin >> X >> Y;

// 2. 条件を満たす数列を計算.

LL curA = X; // 今回の計算結果保存用.

LL befA = curA; // 前回の計算結果保存用.

LL ans = 1; // 数列の長さ.

while(true) {

curA = 2 * befA;

befA = curA;

ans++;

if(curA > Y) {

ans--;

break;

}

// 3. 後処理.

cout << ans << endl;

return 0;

}

■C++版プログラム(問題D／AC版).

// 解き直し.
// ARC 088/ABC 083 解説.
// https://img.atcoder.jp/arc088/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

int main() {
    
    // 1. 入力情報取得.
    string S;
    cin >> S;
    
    // 2. 解説通り.
    // S の k文字目 と k + 1文字目が, 異なる箇所で, max(k, n - k) の最小値をT(S).
    int L    = S.size();  // 文字列長.
    int ans  = S.size();  // T(S).
    char cur = S[0];      // 今回出現する文字.
    char bef = S[0];      // 前回出現した文字.
    FOR(k, 1, L + 1) {
        // 今回出現する文字を設定.
        cur = S[k - 1];
        
        // k文字目 と k + 1 文字目を比較.
        if(cur != bef) ans = min(ans, max(k - 1, L - k + 1));
        
        // 前回出現文字を更新.
        bef = cur;
    }
    
    // 3. 後処理.
    cout << ans << endl;
    return 0;

}

// 解き直し.

// ARC 088/ABC 083 解説.

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

#include <bits/stdc++.h>

using namespace std;

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

int main() {

// 1. 入力情報取得.

string S;

cin >> S;

// 2. 解説通り.

// S の k文字目と k + 1文字目が, 異なる箇所で, max(k, n - k) の最小値をT(S).

int L = S.size(); // 文字列長.

int ans = S.size(); // T(S).

char cur = S[0]; // 今回出現する文字.

char bef = S[0]; // 前回出現した文字.

FOR(k, 1, L + 1) {

// 今回出現する文字を設定.

cur = S[k - 1];

// k文字目と k + 1 文字目を比較.

if(cur != bef) ans = min(ans, max(k - 1, L - k + 1));

// 前回出現文字を更新.

bef = cur;

}

// 3. 後処理.

cout << ans << endl;

return 0;

}

[入力例]
010

[出力例]
2
※AtCoderテストケースより

[入力例]
100000000

[出力例]
8
※AtCoderテストケースより

[入力例]
100010001

[出力例]
5
※例えば, 以下のような変換が考えられる.
(10001)0001 -> (01110)0001  (1文字目 ～ 5文字目までの5文字を変換)
0111(00001) -> 0111(11110)  (5文字目 ～ 9文字目までの5文字を変換)
0(1111111)0 -> 0(0000000)0  (2文字目 ～ 8文字目までの7文字を変換)
-> K = 5 と分かる.

[入力例]
100010001100010001

[出力例]
10
※例えば, 以下のような変換が考えられる.
(1000100011)00010001 -> (0111011100)00010001  (1文字目 ～ 10文字目までの10文字を変換)
0(111011100000)10001 -> 0(000100011111)10001  (2文字目 ～ 13文字目までの12文字を変換)
0000(10001111110001) -> 0000(01110000001110)  (5文字目 ～ 18文字目までの14文字を変換)
00000(111000000111)0 -> 00000(000111111000)0  (6文字目 ～ 17文字目までの12文字を変換)
00000000(1111110000) -> 00000000(0000001111)  (9文字目 ～ 18文字目までの10文字を変換)
(00000000000000)1111 -> (11111111111111)1111  (1文字目 ～ 14文字目までの14文字を変換)
(111111111111111111) -> (000000000000000000)  (1文字目 ～ 18文字目までの18文字を変換)
-> K = 10 と分かる.

[入力例]

010

[出力例]

※AtCoderテストケースより

[入力例]

100000000

[出力例]

※AtCoderテストケースより

[入力例]

100010001

[出力例]

※例えば, 以下のような変換が考えられる.

(10001)0001 -> (01110)0001 (1文字目～ 5文字目までの5文字を変換)

0111(00001) -> 0111(11110) (5文字目～ 9文字目までの5文字を変換)

0(1111111)0 -> 0(0000000)0 (2文字目～ 8文字目までの7文字を変換)

-> K = 5 と分かる.

[入力例]

100010001100010001

[出力例]

※例えば, 以下のような変換が考えられる.

(1000100011)00010001 -> (0111011100)00010001 (1文字目～ 10文字目までの10文字を変換)

0(111011100000)10001 -> 0(000100011111)10001 (2文字目～ 13文字目までの12文字を変換)

0000(10001111110001) -> 0000(01110000001110) (5文字目～ 18文字目までの14文字を変換)

00000(111000000111)0 -> 00000(000111111000)0 (6文字目～ 17文字目までの12文字を変換)

00000000(1111110000) -> 00000000(0000001111) (9文字目～ 18文字目までの10文字を変換)

(00000000000000)1111 -> (11111111111111)1111 (1文字目～ 14文字目までの14文字を変換)

(111111111111111111) -> (000000000000000000) (1文字目～ 18文字目までの18文字を変換)

-> K = 10 と分かる.

■参照サイト
AtCoder Beginner Contest 083

2019年1月26日2019年1月27日

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

C++の練習を兼ねて, AtCoder Beginner Contest 081 の問題C（Not so Diverse) ～問題D (Non-decreasing) を解いてみた.

■感想.
1. 問題D は, 解答方針が見えなかったので, 解説を参照して確認した.

本家のサイトAtCoder Beginner Contest 081 / AtCoder Regular Contest 086 解説をご覧下さい.

■C++版プログラム(問題C／AC版).

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define max(x, y) ((x > y) ? x : y)

int main() {
    
    // 1. 入力情報取得.
    int N, K;
    cin >> N >> K;
    map<int, int> m;
    FOR(i, 0, N) {
        int ai;
        cin >> ai;
        m[ai]++;
    }
    
    // 2. map の 値 で, 昇順ソート.
    // [入力値]
    // 10 3
    // 5 1 3 2 4 1 1 2 3 4
    // (整数, 出現回数) = (5, 1), (2, 2), (3, 2), (4, 2), (1, 3) なので, 
    // 5 … 1回, 2 … 2回 の 合計3回書き換えれば 3種類以下となる.
    int size = m.size();
    int A[size] = {};
    int index = 0;
    for(auto i = m.begin(); i != m.end() ; ++i) A[index++] = i->second;
    sort(A, A + size);
    
    // 3. 書き換え回数をカウント.
    int rewrites = 0;
    FOR(i, 0, size) if(size - i > K) rewrites += A[i];

    // 4 . 出力 ～ 後処理.
    cout << rewrites << endl;
    return 0;
    
}

#include <iostream>

#include <map>

#include <algorithm>

using namespace std;

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

#define max(x, y) ((x > y) ? x : y)

int main() {

// 1. 入力情報取得.

int N, K;

cin >> N >> K;

map<int, int> m;

FOR(i, 0, N) {

int ai;

cin >> ai;

m[ai]++;

}

// 2. map の値で, 昇順ソート.

// [入力値]

// 10 3

// 5 1 3 2 4 1 1 2 3 4

// (整数, 出現回数) = (5, 1), (2, 2), (3, 2), (4, 2), (1, 3) なので,

// 5 … 1回, 2 … 2回の合計3回書き換えれば 3種類以下となる.

int size = m.size();

int A[size] = {};

int index = 0;

for(auto i = m.begin(); i != m.end() ; ++i) A[index++] = i->second;

sort(A, A + size);

// 3. 書き換え回数をカウント.

int rewrites = 0;

FOR(i, 0, size) if(size - i > K) rewrites += A[i];

// 4 . 出力～後処理.

cout << rewrites << endl;

return 0;

}

■C++版プログラム(問題D／AC版).

// 解き直し.
// AtCoder Beginner Contest 081 / AtCoder Regular Contest 086 解説.
// https://img.atcoder.jp/arc086/editorial.pdf
#include <bits/stdc++.h>
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)

int main() {

    // 1. 入力情報取得.
    int N;
    cin >> N;
    int A[N + 1];
    // pair の 第一成分: インデックス(1 ～ N), 第二成分: 値.
    pair<int, int> aMax = {-1, -1e6};
    pair<int, int> aMin = {-1,  1e6};
    FOR(i, 1, N + 1) {
        int a;
        cin >> a;
        if(aMax.second < a) aMax.first = i, aMax.second = a;
        if(aMin.second > a) aMin.first = i, aMin.second = a;
        A[i] = a;
    }
    
    // 2. 解説通り.
    int iMax = aMax.first;
    int vMax = aMax.second;
    int iMin = aMin.first;
    int vMin = aMin.second;
    
    // 2-1. 配列A が, 非負整数の場合.
    // a(2) += a(1), a(3) += a(2), ..., a(N) += a(N - 1) の操作で実現できる.
    if(vMin >= 0) {
        cout << N - 1 << endl;
        FOR(i, 1, N) cout << i << " " << i + 1 << endl;
    }

    // 2-2. 配列A に, 負整数が混在する(abs(vMin) <= abs(vMax))場合.
    // すべての配列A の要素に, vMax を 加算後, 2-1. と同じ操作を追加すれば実現できる.
    if(vMin < 0 && abs(vMin) <= abs(vMax)) {
        cout << N * 2 - 1 << endl;
        FOR(i, 1, N + 1) cout << iMax << " " << i << endl;
        FOR(i, 1, N) cout << i << " " << i + 1 << endl;
    }
    
    // 2-3. 配列A に, 負整数が混在する(abs(vMin) > abs(vMax))場合.
    // すべての配列A の要素に, vMin を 加算後, 2-1. と類似の操作を追加すれば実現できる.
    if(vMin < 0 && abs(vMin) > abs(vMax)) {
        cout << N * 2 - 1 << endl;
        FOR(i, 1, N + 1) cout << iMin << " " << i << endl;
        FORR(i, N, 1)    cout << i << " " << i - 1 << endl;
    }
    
    return 0;

}

// 解き直し.

// AtCoder Beginner Contest 081 / AtCoder Regular Contest 086 解説.

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

#include <bits/stdc++.h>

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)

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

int A[N + 1];

// pair の第一成分: インデックス(1 ～ N), 第二成分: 値.

pair<int, int> aMax = {-1, -1e6};

pair<int, int> aMin = {-1, 1e6};

FOR(i, 1, N + 1) {

int a;

cin >> a;

if(aMax.second < a) aMax.first = i, aMax.second = a;

if(aMin.second > a) aMin.first = i, aMin.second = a;

A[i] = a;

}

// 2. 解説通り.

int iMax = aMax.first;

int vMax = aMax.second;

int iMin = aMin.first;

int vMin = aMin.second;

// 2-1. 配列A が, 非負整数の場合.

// a(2) += a(1), a(3) += a(2), ..., a(N) += a(N - 1) の操作で実現できる.

if(vMin >= 0) {

cout << N - 1 << endl;

FOR(i, 1, N) cout << i << " " << i + 1 << endl;

}

// 2-2. 配列A に, 負整数が混在する(abs(vMin) <= abs(vMax))場合.

// すべての配列A の要素に, vMax を加算後, 2-1. と同じ操作を追加すれば実現できる.

if(vMin < 0 && abs(vMin) <= abs(vMax)) {

cout << N * 2 - 1 << endl;

FOR(i, 1, N + 1) cout << iMax << " " << i << endl;

FOR(i, 1, N) cout << i << " " << i + 1 << endl;

}

// 2-3. 配列A に, 負整数が混在する(abs(vMin) > abs(vMax))場合.

// すべての配列A の要素に, vMin を加算後, 2-1. と類似の操作を追加すれば実現できる.

if(vMin < 0 && abs(vMin) > abs(vMax)) {

cout << N * 2 - 1 << endl;

FOR(i, 1, N + 1) cout << iMin << " " << i << endl;

FORR(i, N, 1) cout << i << " " << i - 1 << endl;

}

return 0;

}

■参照サイト
AtCoder Beginner Contest 081

2019年1月20日2019年1月20日

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

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題C（C – Knot Puzzle) を解いてみた.

■感想.
1. いったん実装してみた(下記, WA版)が, ロジックの修正方法が分からなかったので, 解説を見て, 再度やり直ししたものである.
解説を見て, 本問についても, なるほどと感心させられた.

本家のサイトAtCoder Grand Contest 002 解説をご覧下さい.

■C++版プログラム(問題C／WA版).
※テストケース(1_04.txt, 1_08.txt, 1_10.txt, 1_18.txt, 1_21.txt, 1_22.txt, 1_24.txt, 1_26.txt, 1_27.txt, 1_29.txt)で,
WA判定となった.

// WA版.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<string, int> P;

bool comp1(const P& f, const P& s) { return f.second < s.second; }
bool comp2(const P& f, const P& s) { return (f.first < s.first && f.second > s.second); }

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    LL L;
    cin >> N >> L;
    vector<P> knots;
    
    // 結び目情報(前回, 今回).
    LL bef, cur;
    int ok = 0;
    cin >> bef;
    FOR(i, 1, N) {
        string s;
        cin >> cur;
        if(cur + bef >= L)  s = "OK", ok++;
        else                s = "NG";
        knots.push_back(make_pair(s, i));
        // 前回結び目情報を更新.
        bef = cur;
    }
    // for(auto &p : knots) cout << "status: " << p.first << "  knot index:" << p.second << endl;
    
    // 2. OK が 一つもない場合は, 終了.
    string ans = "Impossible";
    if(ok == 0) {
        cout << ans << endl;
        return 0;
    }
    
    // 3. 各区間に, "OK" が, 一つずつ含まれるように分割.
    vector<vector<P>> setOfKnots;
    priority_queue<P> q;
    ok = 0;
    for(auto &p : knots) {
        
        string status = p.first;
        int knotIndex = p.second;
        // 3-1. status が "OK" なら, ok を increment.
        if(status == "OK") ok++;
        // cout << "status: " << status << "  knot index:" << knotIndex << " q.size()=" << q.size() << " ok=" << ok << endl;
        // 3-2. ok == 1 の 場合は, setOfKnots に 登録.
        if(ok == 1) {
            // priority queue を 空にする.
            vector<P> v;
            while(!q.empty()) {
                v.push_back(q.top());
                q.pop();
            }
            setOfKnots.push_back(v);
            ok = 0;
        }
        q.push(make_pair(status, knotIndex));
    }
    // 3-3. 残りを setOfKnots に 登録.
    vector<P> v;
    while(!q.empty()) {
        v.push_back(q.top());
        q.pop();
    }
    setOfKnots.push_back(v);
    
    // 4. 各区間について, 出力.
    // setOfKnots の 各区間の先頭が, status: OK になっているはず.
    // -> 最初の区間は, status: OK が含まれてないはずなので,2番目の区間に合わせて出力.
    ans = "Possible";
    cout << ans << endl;
    int nKnot = 1;
    for(auto &knots : setOfKnots) {
        // cout << "--- start this set ---" << endl;
        if(nKnot == 1) sort(knots.begin(), knots.end(), comp1);
        else           sort(knots.begin(), knots.end(), comp2);
        for(auto &p : knots) {
            // cout << "status: " << p.first << "  knot index:" << p.second << endl;
            cout << p.second << endl;
        }
        // cout << "---- end this set ----" << endl;
        nKnot++;
    }
    return 0;
    
}

// WA版.

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<string, int> P;

bool comp1(const P& f, const P& s) { return f.second < s.second; }

bool comp2(const P& f, const P& s) { return (f.first < s.first && f.second > s.second); }

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

int main() {

// 1. 入力情報取得.

int N;

LL L;

cin >> N >> L;

vector knots;

// 結び目情報(前回, 今回).

LL bef, cur;

int ok = 0;

cin >> bef;

FOR(i, 1, N) {

string s;

cin >> cur;

if(cur + bef >= L) s = "OK", ok++;

else s = "NG";

knots.push_back(make_pair(s, i));

// 前回結び目情報を更新.

bef = cur;

}

// for(auto &p : knots) cout << "status: " << p.first << " knot index:" << p.second << endl;

// 2. OK が一つもない場合は, 終了.

string ans = "Impossible";

if(ok == 0) {

cout << ans << endl;

return 0;

}

// 3. 各区間に, "OK" が, 一つずつ含まれるように分割.

vector<vector> setOfKnots;

priority_queue q;

ok = 0;

for(auto &p : knots) {

string status = p.first;

int knotIndex = p.second;

// 3-1. status が "OK" なら, ok を increment.

if(status == "OK") ok++;

// cout << "status: " << status << " knot index:" << knotIndex << " q.size()=" << q.size() << " ok=" << ok << endl;

// 3-2. ok == 1 の場合は, setOfKnots に登録.

if(ok == 1) {

// priority queue を空にする.

vector v;

while(!q.empty()) {

v.push_back(q.top());

q.pop();

}

setOfKnots.push_back(v);

ok = 0;

}

q.push(make_pair(status, knotIndex));

}

// 3-3. 残りを setOfKnots に登録.

vector v;

while(!q.empty()) {

v.push_back(q.top());

q.pop();

}

setOfKnots.push_back(v);

// 4. 各区間について, 出力.

// setOfKnots の各区間の先頭が, status: OK になっているはず.

// -> 最初の区間は, status: OK が含まれてないはずなので,2番目の区間に合わせて出力.

ans = "Possible";

cout << ans << endl;

int nKnot = 1;

for(auto &knots : setOfKnots) {

// cout << "--- start this set ---" << endl;

if(nKnot == 1) sort(knots.begin(), knots.end(), comp1);

else sort(knots.begin(), knots.end(), comp2);

for(auto &p : knots) {

// cout << "status: " << p.first << " knot index:" << p.second << endl;

cout << p.second << endl;

}

// cout << "---- end this set ----" << endl;

nKnot++;

}

return 0;

}

■C++版プログラム(問題C／AC版).

// 解き直し.
// AtCoder Grand Contest 002 解説.
// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    LL L;
    cin >> N >> L;
    vector<LL> a;
    FOR(i, 0, N) {
        LL k;
        cin >> k;
        a.push_back(k);
    }
    
    // 2. 解説通り.
    // a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.
    LL knotInfo[N - 1] = {};
    int lastKnotIndex = -1;
    FOR(i, 0, N - 1) {
        LL x = a[i] + a[i + 1];
        knotInfo[i] = x;
        if(x >= L) {
            lastKnotIndex = i + 1;
            break;
        }
    }
    
    // 3. 解説通り.
    // 最後にほどく結び目が, 一つもない場合は, 終了.
    if(lastKnotIndex == -1) {
        cout << "Impossible" << endl;
        return 0;
    }
    
    // 4. 解説通り.
    cout << "Possible" << endl;
    // 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.
    FOR(l, 1, lastKnotIndex)      cout << l << endl;
    // 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.
    FORR(r, N - 1, lastKnotIndex) cout << r << endl;
    // 4-3. 最後に，結び目 i をほどく.
    cout << lastKnotIndex << endl;

    return 0;
    
}

// 解き直し.

// AtCoder Grand Contest 002 解説.

// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

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

int main() {

// 1. 入力情報取得.

int N;

LL L;

cin >> N >> L;

vector<LL> a;

FOR(i, 0, N) {

LL k;

cin >> k;

a.push_back(k);

}

// 2. 解説通り.

// a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.

LL knotInfo[N - 1] = {};

int lastKnotIndex = -1;

FOR(i, 0, N - 1) {

LL x = a[i] + a[i + 1];

knotInfo[i] = x;

if(x >= L) {

lastKnotIndex = i + 1;

break;

}

// 3. 解説通り.

// 最後にほどく結び目が, 一つもない場合は, 終了.

if(lastKnotIndex == -1) {

cout << "Impossible" << endl;

return 0;

}

// 4. 解説通り.

cout << "Possible" << endl;

// 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.

FOR(l, 1, lastKnotIndex) cout << l << endl;

// 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.

FORR(r, N - 1, lastKnotIndex) cout << r << endl;

// 4-3. 最後に，結び目 i をほどく.

cout << lastKnotIndex << endl;

return 0;

}

■C++版プログラム(問題C／AC版).
上記のプログラムが, 冗長に感じたので, 修正.

// 解き直し(その②).
// AtCoder Grand Contest 002 解説.
// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    LL L;
    cin >> N >> L;
    
    // 2. 解説通り.
    // a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.
    int lastKnotIndex = -1;  // 最後にほどく結び目.
    LL bef;                  // 前回ロープ長.
    cin >> bef;
    FOR(i, 1, N) {
        LL cur;    // 今回ロープ長.
        cin >> cur;
        if(bef + cur >= L) {
            lastKnotIndex = i;
            break;
        }
        // 前回ロープ長を更新.
        bef = cur;
    }
    
    // 3. 解説通り.
    // 最後にほどく結び目が, 一つもない場合は, 終了.
    if(lastKnotIndex == -1) {
        cout << "Impossible" << endl;
        return 0;
    }
    
    // 4. 解説通り.
    cout << "Possible" << endl;
    // 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.
    FOR(l, 1, lastKnotIndex)      cout << l << endl;
    // 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.
    FORR(r, N - 1, lastKnotIndex) cout << r << endl;
    // 4-3. 最後に，結び目 i をほどく.
    cout << lastKnotIndex << endl;

    return 0;
    
}

// 解き直し(その②).

// AtCoder Grand Contest 002 解説.

// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

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

int main() {

// 1. 入力情報取得.

int N;

LL L;

cin >> N >> L;

// 2. 解説通り.

// a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.

int lastKnotIndex = -1; // 最後にほどく結び目.

LL bef; // 前回ロープ長.

cin >> bef;

FOR(i, 1, N) {

LL cur; // 今回ロープ長.

cin >> cur;

if(bef + cur >= L) {

lastKnotIndex = i;

break;

}

// 前回ロープ長を更新.

bef = cur;

}

// 3. 解説通り.

// 最後にほどく結び目が, 一つもない場合は, 終了.

if(lastKnotIndex == -1) {

cout << "Impossible" << endl;

return 0;

}

// 4. 解説通り.

cout << "Possible" << endl;

// 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.

FOR(l, 1, lastKnotIndex) cout << l << endl;

// 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.

FORR(r, N - 1, lastKnotIndex) cout << r << endl;

// 4-3. 最後に，結び目 i をほどく.

cout << lastKnotIndex << endl;

return 0;

}

■参照サイト
AtCoder Grand Contest 002

2019年1月20日

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

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題B（Box and Ball) を解いてみた.

■感想.
1. 解答方針が, 全く見えなかったので, 解答を確認したところ, なるほどと感心させられた.

本家のサイトAtCoder Grand Contest 002 解説をご覧下さい.

■C++版プログラム(問題B／AC版).

// 解き直し.
// AtCoder Grand Contest 002 解説.
// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

struct Box {
    int x;    // 移動元(箱).
    int y;    // 移動先(箱).
};

int main() {
    
    // 1. 入力情報取得.
    int N, M;
    cin >> N >> M;
    vector<Box> v;
    FOR(i, 0, M) {
        Box b;
        cin >> b.x >> b.y;
        b.x--;
        b.y--;
        v.push_back(b);
    }
    
    // 2. 各箱について, ボールの個数を設定(解説通り.).
    int balls[N] = {};
    FOR(i, 0, N) balls[i]++;
    bool red[N] = {};
    red[0] = true;
    
    // 3. 赤いボールの移動を確認(解説通り).
    FOR(i, 0, M) {
        Box b = v[i];
        if(red[b.x]) red[b.y] = true;
        balls[b.x]--;
        balls[b.y]++;
        if(balls[b.x] == 0) red[b.x] = false;
    }
    
    // 4. 出力.
    int ans = 0;
    FOR(i, 0, N) if(red[i]) ans++;
    cout << ans << endl;
    return 0;
    
}

// 解き直し.

// AtCoder Grand Contest 002 解説.

// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

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

struct Box {

int x; // 移動元(箱).

int y; // 移動先(箱).

};

int main() {

// 1. 入力情報取得.

int N, M;

cin >> N >> M;

vector<Box> v;

FOR(i, 0, M) {

Box b;

cin >> b.x >> b.y;

b.x--;

b.y--;

v.push_back(b);

}

// 2. 各箱について, ボールの個数を設定(解説通り.).

int balls[N] = {};

FOR(i, 0, N) balls[i]++;

bool red[N] = {};

red[0] = true;

// 3. 赤いボールの移動を確認(解説通り).

FOR(i, 0, M) {

Box b = v[i];

if(red[b.x]) red[b.y] = true;

balls[b.x]--;

balls[b.y]++;

if(balls[b.x] == 0) red[b.x] = false;

}

// 4. 出力.

int ans = 0;

FOR(i, 0, N) if(red[i]) ans++;

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Grand Contest 002

2019年1月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 113 の問題C（ID) ～問題D (Number of Amidakuji) を解いてみた.

■感想.
1. 問題C は, かなりゴリゴリ実装せざるを得なかった.
2. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
但し, おおよそ, このような内容を解答で説明されているだろう, との推測が多分に含まれていると思われる.

本家のサイトAtCoder Beginner Contest 113 解説をご覧下さい.

■C++版プログラム(問題C／AC版).

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {
    
    // 1. 入力情報取得.
    LL N, M;
    cin >> N >> M;
    
    // Map of int and vector<int> in c++
    // https://stackoverflow.com/questions/15192534/map-of-int-and-vectorint-in-c
    // map の key:   県番号(Pi).
    // map の value: vector<pair<LL, LL>>: 誕生年(Yi), 市の番号.
    map<LL, vector<pair<LL, LL>>> m;
    FOR(i, 0, M) {
        LL p, y;
        cin >> p >> y;
        m[p].push_back(make_pair(y, i));
    }
    
    // ex.
    // [input]
    // 2 3
    // 1 32
    // 2 63
    // 1 12
    // 
    // [output]
    // city: 0 -> year: 32 belongs to Prefecture: 1
    // city: 2 -> year: 12 belongs to Prefecture: 1
    // city: 1 -> year: 63 belongs to Prefecture: 2
    // for(auto &p : m) for(auto &i : p.second) cout << "city: " << i.second << " -> year: " << i.first << " belongs to " << "Prefecture: " << p.first << endl;

    // 2. ID生成 ～ 出力.
    map<LL, string> ans;    // 市の番号, 市の認識番号 を 保存.
    for(auto &p : m) {
        
        // 2-1. 誕生年 で 昇順sort.
        vector<pair<LL, LL>> v = p.second;
        sort(v.begin(), v.end());
        
        // 2-2. 市の認識番号を作成.
        for(auto i = v.begin(); i != v.end(); ++i) {
            LL x = i - v.begin() + 1;
            ostringstream ss;
            // 上6桁: 県(Pi)
            ss << std::setw(6) << std::setfill('0') << p.first;
            // 下6桁: 市が, 県(Pi) で, x番目に誕生した
            ss << std::setw(6) << std::setfill('0') << x;
            string id(ss.str());
            // map に 保管して, 市の番号順に, 自動で昇順sort.
            ans[i->second] = id;
        }
    }
    
    // 3. 後処理.
    for(auto &a : ans) cout << a.second << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {

// 1. 入力情報取得.

LL N, M;

cin >> N >> M;

// Map of int and vector<int> in c++

// https://stackoverflow.com/questions/15192534/map-of-int-and-vectorint-in-c

// map の key: 県番号(Pi).

// map の value: vector<pair<LL, LL>>: 誕生年(Yi), 市の番号.

map<LL, vector<pair<LL, LL>>> m;

FOR(i, 0, M) {

LL p, y;

cin >> p >> y;

m[p].push_back(make_pair(y, i));

}

// ex.

// [input]

// 2 3

// 1 32

// 2 63

// 1 12

// [output]

// city: 0 -> year: 32 belongs to Prefecture: 1

// city: 2 -> year: 12 belongs to Prefecture: 1

// city: 1 -> year: 63 belongs to Prefecture: 2

// for(auto &p : m) for(auto &i : p.second) cout << "city: " << i.second << " -> year: " << i.first << " belongs to " << "Prefecture: " << p.first << endl;

// 2. ID生成～出力.

map<LL, string> ans; // 市の番号, 市の認識番号を保存.

for(auto &p : m) {

// 2-1. 誕生年で昇順sort.

vector<pair<LL, LL>> v = p.second;

sort(v.begin(), v.end());

// 2-2. 市の認識番号を作成.

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

LL x = i - v.begin() + 1;

ostringstream ss;

// 上6桁: 県(Pi)

ss << std::setw(6) << std::setfill('0') << p.first;

// 下6桁: 市が, 県(Pi) で, x番目に誕生した

ss << std::setw(6) << std::setfill('0') << x;

string id(ss.str());

// map に保管して, 市の番号順に, 自動で昇順sort.

ans[i->second] = id;

}

// 3. 後処理.

for(auto &a : ans) cout << a.second << endl;

return 0;

}

■C++版プログラム(問題D／AC版).

// 解き直し.
// ABC 113 解説.
// https://img.atcoder.jp/abc113/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;

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

int main() {
    
    // 1. 入力情報取得.
    LL H, W, K;
    cin >> H >> W >> K;
    
    // 2. 解説通り.
    // DP を 使うとのこと.
    // DP(h, x): 縦から h 列目を通過した(横棒を通った場合も含む)直後に, 左から x本目の縦棒にいる場合の数.
    // DP(h, x) の 遷移先は, DP(h + 1, x - 1), DP(h + 1, x), DP(h + 1, x + 1) の 3種類.
    LL DP[H + 1][W + 1] = {};
    DP[0][1] = 1;
    
    // 2-1. (h + 1)列目の横棒の全配置は, 何通り？
    // W本の縦棒から, 正しいあみだくじの条件を満たすように横棒を配置することに注意.
    // ex.
    // 
    // W = 0 -> 1通り.
    // W = 1 -> 1通り.
    // W = 2 -> 2通り.
    // W = 3 -> 3通り.
    // W = 4 -> 5通り(※横棒:"_", 横棒無し: "." とすると, ... _.. ._. .._ _._ の5通り).
    // ...
    // -> 解説通り, フィボナッチ数列と同じになっていることが分かる.
    LL BAR[W + 1] = {};
    BAR[0] = 1;
    BAR[1] = 1;
    FOR(i, 2, W + 1) BAR[i] = BAR[i - 1] + BAR[i - 2];
    
    // 2-2. DP更新.
    FOR(h, 1, H + 1) {
        FOR(x, 1, W + 1) {
            // 2-2-1. DP(h, x) -> DP(h + 1, x - 1)
            // 左から, x本目 -> (x - 1)本目に遷移するには, 
            // x > 1 の場合で, 
            // ① (x - 1)本目 と x本目       との間に, 横棒が必要.
            // ② (x - 2)本目 と (x - 1)本目 との間は, 横棒が無い状態.
            // ③ (x + 1)本目 と x本目       との間は, 横棒が無い状態.
            // -> 場合の数としては, 左から(x - 2)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数 なので,
            // X = BAR[x - 2] × BAR[W - (x + 1) + 1] と分かる.
            if(x > 1) {
                LL X = BAR[x - 2] * BAR[W - x];
                DP[h][x - 1] += X * DP[h - 1][x];
                DP[h][x - 1] %= MOD;
            }
            
            // 2-2-2. DP(h, x) -> DP(h + 1, x)
            // 左から, x本目 -> x本目のように留まるためには, 
            // (x - 1)本目 と x本目, x本目 と (x + 1)本目 との間に, それぞれ横棒が無い状態.
            // x == 1 または x == W の場合.
            // -> 場合の数としては, (W - 1)本についての横棒配置数 なので, Y = BAR[W - 1] と分かる.
            if(x == 1 || x == W) {
                LL Y = BAR[W - 1];
                DP[h][x] += Y * DP[h - 1][x];
                DP[h][x] %= MOD;
            }
            // x > 1 かつ x < W の場合.
            // -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数 なので,
            // Y = BAR[x - 1] × BAR[W - (x + 1) + 1] と分かる.
            if(x > 1 && x < W) {
                LL Y = BAR[x - 1] * BAR[W - x];
                DP[h][x] += Y * DP[h - 1][x];
                DP[h][x] %= MOD;
            }

            // 2-2-3. DP(h, x) -> DP(h + 1, x + 1)
            // 左から, x本目 -> (x + 1)本目に遷移するには, 
            // x < W の場合で, 
            // ① (x + 1)本目 と x本目       との間に, 横棒が必要.
            // ② (x + 2)本目 と (x + 1)本目 との間は, 横棒が無い状態.
            // ③ (x - 1)本目 と x本目       との間に, 横棒が無い状態.
            // -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 2)本目以降の横棒配置数 なので,
            // Z = BAR[x - 1] × BAR[W - (x + 2) + 1] と分かる.
            if(x < W) {
                LL Z = BAR[x - 1] * BAR[W - x - 1];
                DP[h][x + 1] += Z * DP[h - 1][x];
                DP[h][x + 1] %= MOD;
            }
        }
    }
    
    // 3. 出力 ～ 後処理.
    // FOR(h, 0, H + 1) {
    //     FOR(x, 0, W + 1) {
    //         cout << DP[h][x] << " ";
    //     }
    //     cout << endl;
    // }
    LL ans = 0LL;
    FOR(i, 0, W + 1) {
        LL val = DP[H][i];
        if(i == K) {
            ans = val;
            break;
        }
    }
    cout << ans << endl;
    return 0;

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

// 解き直し.

// ABC 113 解説.

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;

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

int main() {

// 1. 入力情報取得.

LL H, W, K;

cin >> H >> W >> K;

// 2. 解説通り.

// DP を使うとのこと.

// DP(h, x): 縦から h 列目を通過した(横棒を通った場合も含む)直後に, 左から x本目の縦棒にいる場合の数.

// DP(h, x) の遷移先は, DP(h + 1, x - 1), DP(h + 1, x), DP(h + 1, x + 1) の 3種類.

LL DP[H + 1][W + 1] = {};

DP[0][1] = 1;

// 2-1. (h + 1)列目の横棒の全配置は, 何通り？

// W本の縦棒から, 正しいあみだくじの条件を満たすように横棒を配置することに注意.

// ex.

// W = 0 -> 1通り.

// W = 1 -> 1通り.

// W = 2 -> 2通り.

// W = 3 -> 3通り.

// W = 4 -> 5通り(※横棒:"_", 横棒無し: "." とすると, ... _.. ._. .._ _._ の5通り).

// ...

// -> 解説通り, フィボナッチ数列と同じになっていることが分かる.

LL BAR[W + 1] = {};

BAR[0] = 1;

BAR[1] = 1;

FOR(i, 2, W + 1) BAR[i] = BAR[i - 1] + BAR[i - 2];

// 2-2. DP更新.

FOR(h, 1, H + 1) {

FOR(x, 1, W + 1) {

// 2-2-1. DP(h, x) -> DP(h + 1, x - 1)

// 左から, x本目 -> (x - 1)本目に遷移するには,

// x > 1 の場合で,

// ① (x - 1)本目と x本目との間に, 横棒が必要.

// ② (x - 2)本目と (x - 1)本目との間は, 横棒が無い状態.

// ③ (x + 1)本目と x本目との間は, 横棒が無い状態.

// -> 場合の数としては, 左から(x - 2)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数なので,

// X = BAR[x - 2] × BAR[W - (x + 1) + 1] と分かる.

if(x > 1) {

LL X = BAR[x - 2] * BAR[W - x];

DP[h][x - 1] += X * DP[h - 1][x];

DP[h][x - 1] %= MOD;

}

// 2-2-2. DP(h, x) -> DP(h + 1, x)

// 左から, x本目 -> x本目のように留まるためには,

// (x - 1)本目と x本目, x本目と (x + 1)本目との間に, それぞれ横棒が無い状態.

// x == 1 または x == W の場合.

// -> 場合の数としては, (W - 1)本についての横棒配置数なので, Y = BAR[W - 1] と分かる.

if(x == 1 || x == W) {

LL Y = BAR[W - 1];

DP[h][x] += Y * DP[h - 1][x];

DP[h][x] %= MOD;

}

// x > 1 かつ x < W の場合.

// -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数なので,

// Y = BAR[x - 1] × BAR[W - (x + 1) + 1] と分かる.

if(x > 1 && x < W) {

LL Y = BAR[x - 1] * BAR[W - x];

DP[h][x] += Y * DP[h - 1][x];

DP[h][x] %= MOD;

}

// 2-2-3. DP(h, x) -> DP(h + 1, x + 1)

// 左から, x本目 -> (x + 1)本目に遷移するには,

// x < W の場合で,

// ① (x + 1)本目と x本目との間に, 横棒が必要.

// ② (x + 2)本目と (x + 1)本目との間は, 横棒が無い状態.

// ③ (x - 1)本目と x本目との間に, 横棒が無い状態.

// -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 2)本目以降の横棒配置数なので,

// Z = BAR[x - 1] × BAR[W - (x + 2) + 1] と分かる.

if(x < W) {

LL Z = BAR[x - 1] * BAR[W - x - 1];

DP[h][x + 1] += Z * DP[h - 1][x];

DP[h][x + 1] %= MOD;

}

// 3. 出力～後処理.

// FOR(h, 0, H + 1) {

// FOR(x, 0, W + 1) {

// cout << DP[h][x] << " ";

// }

// cout << endl;

// }

LL ans = 0LL;

FOR(i, 0, W + 1) {

LL val = DP[H][i];

if(i == K) {

ans = val;

break;

}

cout << ans << endl;

return 0;

}

[入力例]
1 3 2

[出力例(debug版)]
0 1 0 0 
0 2 1 0 
1
※AtCoderテストケースより

[入力例]
1 3 1

[出力例(debug版)]
0 1 0 0 
0 2 1 0 
2
※AtCoderテストケースより

[入力例]
2 3 3

[出力例(debug版)]
0 1 0 0 
0 2 1 0 
0 5 3 1 
1
※AtCoderテストケースより

[入力例]
2 3 1

[出力例(debug版)]
0 1 0 0 
0 2 1 0 
0 5 3 1 
5
※AtCoderテストケースより

[入力例]
7 1 1

[出力例(debug版)]
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
1
※AtCoderテストケースより

[入力例]
2 5 1

[出力例(debug版)]
0 1 0 0 0 0 
0 5 3 0 0 0 
0 34 24 6 0 0 
34

[入力例]
2 5 2

[出力例(debug版)]
0 1 0 0 0 0 
0 5 3 0 0 0 
0 34 24 6 0 0 
24

[入力例]
15 8 5

[出力例(debug版)]
0 1 0 0 0 0 0 0 0 
0 21 13 0 0 0 0 0 0 
0 610 442 104 0 0 0 0 0 
0 18556 14508 5200 1040 0 0 0 0 
0 578280 471432 209664 67600 9360 0 0 0 
0 18272496 15323568 7802080 3194880 748800 93600 0 0 
0 582928800 499165472 279370624 132683200 40921920 8985600 748800 0 
0 730655810 302190416 790085697 152251485 897833593 558979200 81619200 9734400 
0 272247285 747686381 581409218 265131456 427559120 574956604 659430365 265471993 
0 437115833 910411283 935352977 639096009 549135846 750339658 623383374 147506500 
0 14779025 676149 639897790 882192358 492298204 483859826 24285514 201620285 
0 319149462 320099547 65697279 62546938 162802402 859023284 807653953 549737639 
0 863432743 835815293 237422192 60398457 595191235 833628041 518276800 43991654 
0 997686216 989601843 89261909 636919834 807734929 436175245 978514139 661423085 
0 816234264 548839857 714203523 716030842 210054737 884266168 808585704 610568410 
0 275837517 459591596 978283490 772990360 437760187 717491536 523132651 333550601 
437760187
※AtCoderテストケースより

[入力例]

1 3 2

[出力例(debug版)]

0 1 0 0

0 2 1 0

※AtCoderテストケースより

[入力例]

1 3 1

[出力例(debug版)]

0 1 0 0

0 2 1 0

※AtCoderテストケースより

[入力例]

2 3 3

[出力例(debug版)]

0 1 0 0

0 2 1 0

0 5 3 1

※AtCoderテストケースより

[入力例]

2 3 1

[出力例(debug版)]

0 1 0 0

0 2 1 0

0 5 3 1

※AtCoderテストケースより

[入力例]

7 1 1

[出力例(debug版)]

0 1

※AtCoderテストケースより

[入力例]

2 5 1

[出力例(debug版)]

0 1 0 0 0 0

0 5 3 0 0 0

0 34 24 6 0 0

[入力例]

2 5 2

[出力例(debug版)]

0 1 0 0 0 0

0 5 3 0 0 0

0 34 24 6 0 0

[入力例]

15 8 5

[出力例(debug版)]

0 1 0 0 0 0 0 0 0

0 21 13 0 0 0 0 0 0

0 610 442 104 0 0 0 0 0

0 18556 14508 5200 1040 0 0 0 0

0 578280 471432 209664 67600 9360 0 0 0

0 18272496 15323568 7802080 3194880 748800 93600 0 0

0 582928800 499165472 279370624 132683200 40921920 8985600 748800 0

0 730655810 302190416 790085697 152251485 897833593 558979200 81619200 9734400

0 272247285 747686381 581409218 265131456 427559120 574956604 659430365 265471993

0 437115833 910411283 935352977 639096009 549135846 750339658 623383374 147506500

0 14779025 676149 639897790 882192358 492298204 483859826 24285514 201620285

0 319149462 320099547 65697279 62546938 162802402 859023284 807653953 549737639

0 863432743 835815293 237422192 60398457 595191235 833628041 518276800 43991654

0 997686216 989601843 89261909 636919834 807734929 436175245 978514139 661423085

0 816234264 548839857 714203523 716030842 210054737 884266168 808585704 610568410

0 275837517 459591596 978283490 772990360 437760187 717491536 523132651 333550601

437760187

※AtCoderテストケースより

■参照サイト
AtCoder Beginner Contest 113

2019年1月3日2022年1月24日

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

C++の練習を兼ねて, AtCoder Beginner Contest 038 の問題C（単調増加) ～問題D (プレゼント) を解いてみた.

■感想.
1. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
2. Binary Indexed Tree について, そもそも知らなかったので, 後述の参照サイトを元に, サンプルプログラム(binary_indexed_sample.cpp) で, いったん動作確認してみた.
3. 組み立てた解答が, テストケースをほとんど通過しなかったので, 正解者のコーディングを参照したところ, update関数で, tree[idx] の更新処理が誤っていることが分かったので, 以下のように修正した.
[修正前]
値 k で更新.

[修正後]
値 k と tree[idx] のうち, 大きい方で更新.

本家のサイトAtCoder Beginnar Contest 038 解説をご覧下さい.
※感想として, 私見ではあるが, 以下の読み替えが必要となるように思われる.
解説(P.20): “列で1番目からk番目の最小値を求める操作” -> “列で1番目からk番目の最大値を求める操作”
解説(P.21): “update(i,a)を列のi番目をaで更新” -> “update(i,a)を列のi番目を a, BIT[i] の大きい方で更新”

■C++版プログラム(問題C／AC版).

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    
    // 2. 単調増加を調べる.
    LL ans = 1;
    LL inc = 0;  // 単調増加の連続項数.
    LL bef;      // 前回の数.
    cin >> bef;
    FOR(i, 1, N) {
        LL a;
        cin >> a;
        if(bef < a) {
            inc = inc + 1;
            ans += inc;
        } else {
            inc = 0;
        }
        bef = a;
        ans++;
    }
    
    // 3. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

// 2. 単調増加を調べる.

LL ans = 1;

LL inc = 0; // 単調増加の連続項数.

LL bef; // 前回の数.

cin >> bef;

FOR(i, 1, N) {

LL a;

cin >> a;

if(bef < a) {

inc = inc + 1;

ans += inc;

} else {

inc = 0;

}

bef = a;

ans++;

}

// 3. 出力～後処理.

cout << ans << endl;

return 0;

}

■C++版プログラム(問題D／AC版).

// 解き直し.
// AtCoder Beginnar Contest 038解説
// http://abc038.contest.atcoder.jp/data/abc/038/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

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

struct box {
    int h; // 高さ.
    int w; // 幅.
};

// How do i sort a pair increasing based on first element then decreasing based on second element?
// https://stackoverflow.com/questions/35776189/how-do-i-sort-a-pair-increasing-based-on-first-element-then-decreasing-based-on
struct boxCompareHeight {
    bool operator()(const box &a, const box &b) {
        if (a.h == b.h) return a.w > b.w;
        else            return a.h < b.h;
    }
};

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the maximum from index 1 to idx
// @param idx: 指定された範囲におけるインデックスの最大値.
// @param tree: binary indexed tree の 構造を持った配列.
// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.
// -> @return ret: binary indexed tree の 構造を持った配列上で, インデックス 1 ～ idx までの最大値を計算.
int query(int idx, int tree[]) {
    int ret = 0;
    // Returns the sum from index 1 to idx
    // while(idx > 0) ret += tree[idx], idx -= LSB(idx);
    // -> 以下のように修正.
    while(idx > 0) ret = max(ret, tree[idx]), idx -= LSB(idx);
    return ret;
}

// Update each tree[idx] on the larger of k and tree[idx].
// @param idx: 通常の配列における更新対象要素のインデックス.
// @param k: 加算する値.
// @param tree: binary indexed tree の 構造を持った配列.
// @param size: 通常の配列についての配列サイズ.
// @return: none.
void update(int idx, int k, int tree[], int size) {
    // Adds k to element with index idx
    // while(idx < size) tree[idx] += k, idx += LSB(idx);
    // -> 以下のように修正.
    // Update k to element with index idx
    // while(idx < size) tree[idx] = k, idx += LSB(idx);
    // -> sample0.txt, sample1.txt, subtask0_10.txt, subtask0_11.txt, subtask1_10.txt, subtask1_11.txt 以外全てWA.
    // -> 正解者の方々のソースを参照して, 以下のように修正.
    while(idx < size) tree[idx] = max(k, tree[idx]), idx += LSB(idx);
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<box> v;
    FOR(i, 0, N) {
        box b;
        cin >> b.w >> b.h;
        v.push_back(b);
    }
    
    // 2. 解説通り.
    // プレゼントの入れ子の最大数を確認.
    // -> Binary Indexed Tree を使うとのこと.
    
    // 2-1. 高さで昇順sort.
    // -> 高さが同じ場合は, 幅の降順sortとする(※解説通り).
    boxCompareHeight bch;
    sort(v.begin(), v.end(), bch);
    // for(auto &p : v) cout << p.w << " " << p.h << endl;
    // cout << endl;

    // 2-2. dp, bit を 計算.
    // dp(i) == i番目の箱を, 最も外側とするとき, 最大何重の入れ子に出来るか.
    // int LIMIT = 10;  // Debug用.
    int LIMIT = 100000;
    int dp[LIMIT + 1] = {};
    // bit(i) == 最も外側の箱の横の長さが, iとなる入れ子の数の最大値.
    int bit[LIMIT + 1] = {};
    dp[0] = 0;
    bit[0] = 0;
    FOR(i, 1, N + 1) {
        dp[i] = query(v[i - 1].w - 1, bit) + 1;
        update(v[i - 1].w, dp[i], bit, LIMIT + 1);
    }
    // FOR(i, 0, LIMIT + 1) cout << "dp=" << dp[i] << " bit=" << bit[i] << endl;
    
    // 3. 出力 ～ 後処理.
    int ans = 0;
    FOR(i, 1, LIMIT + 1) ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
    
}

100

101

102

103

// 解き直し.

// AtCoder Beginnar Contest 038解説

// http://abc038.contest.atcoder.jp/data/abc/038/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

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

struct box {

int h; // 高さ.

int w; // 幅.

};

// How do i sort a pair increasing based on first element then decreasing based on second element?

// https://stackoverflow.com/questions/35776189/how-do-i-sort-a-pair-increasing-based-on-first-element-then-decreasing-based-on

struct boxCompareHeight {

bool operator()(const box &a, const box &b) {

if (a.h == b.h) return a.w > b.w;

else return a.h < b.h;

}

};

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the maximum from index 1 to idx

// @param idx: 指定された範囲におけるインデックスの最大値.

// @param tree: binary indexed tree の構造を持った配列.

// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.

// -> @return ret: binary indexed tree の構造を持った配列上で, インデックス 1 ～ idx までの最大値を計算.

int query(int idx, int tree[]) {

int ret = 0;

// Returns the sum from index 1 to idx

// while(idx > 0) ret += tree[idx], idx -= LSB(idx);

// -> 以下のように修正.

while(idx > 0) ret = max(ret, tree[idx]), idx -= LSB(idx);

return ret;

}

// Update each tree[idx] on the larger of k and tree[idx].

// @param idx: 通常の配列における更新対象要素のインデックス.

// @param k: 加算する値.

// @param tree: binary indexed tree の構造を持った配列.

// @param size: 通常の配列についての配列サイズ.

// @return: none.

void update(int idx, int k, int tree[], int size) {

// Adds k to element with index idx

// while(idx < size) tree[idx] += k, idx += LSB(idx);

// -> 以下のように修正.

// Update k to element with index idx

// while(idx < size) tree[idx] = k, idx += LSB(idx);

// -> sample0.txt, sample1.txt, subtask0_10.txt, subtask0_11.txt, subtask1_10.txt, subtask1_11.txt 以外全てWA.

// -> 正解者の方々のソースを参照して, 以下のように修正.

while(idx < size) tree[idx] = max(k, tree[idx]), idx += LSB(idx);

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

vector<box> v;

FOR(i, 0, N) {

box b;

cin >> b.w >> b.h;

v.push_back(b);

}

// 2. 解説通り.

// プレゼントの入れ子の最大数を確認.

// -> Binary Indexed Tree を使うとのこと.

// 2-1. 高さで昇順sort.

// -> 高さが同じ場合は, 幅の降順sortとする(※解説通り).

boxCompareHeight bch;

sort(v.begin(), v.end(), bch);

// for(auto &p : v) cout << p.w << " " << p.h << endl;

// cout << endl;

// 2-2. dp, bit を計算.

// dp(i) == i番目の箱を, 最も外側とするとき, 最大何重の入れ子に出来るか.

// int LIMIT = 10; // Debug用.

int LIMIT = 100000;

int dp[LIMIT + 1] = {};

// bit(i) == 最も外側の箱の横の長さが, iとなる入れ子の数の最大値.

int bit[LIMIT + 1] = {};

dp[0] = 0;

bit[0] = 0;

FOR(i, 1, N + 1) {

dp[i] = query(v[i - 1].w - 1, bit) + 1;

update(v[i - 1].w, dp[i], bit, LIMIT + 1);

}

// FOR(i, 0, LIMIT + 1) cout << "dp=" << dp[i] << " bit=" << bit[i] << endl;

// 3. 出力～後処理.

int ans = 0;

FOR(i, 1, LIMIT + 1) ans = max(ans, dp[i]);

cout << ans << endl;

return 0;

}

[入力例]
5
8 8
5 3
2 2
4 2
2 1
※AtCoderテストケースより

[出力例]
4

[入力例]
8
3 1000
2 3
3 4
2 999
4 7
5 4
1 998
1 2

[出力例]
4

[入力例]
10
1 2
2 3
5 6
3 4
4 3
4 7
8 9
10 12
7 8
4 4

[出力例]
7
※(1, 2) -> (2, 3) -> (3, 4) -> (5, 6) -> (7, 8) -> (8, 9) -> (10, 12) で, 7重と分かる.

[入力例]

8 8

5 3

2 2

4 2

2 1

※AtCoderテストケースより

[出力例]

[入力例]

3 1000

2 3

3 4

2 999

4 7

5 4

1 998

1 2

[出力例]

[入力例]

1 2

2 3

5 6

3 4

4 3

4 7

8 9

10 12

7 8

4 4

[出力例]

※(1, 2) -> (2, 3) -> (3, 4) -> (5, 6) -> (7, 8) -> (8, 9) -> (10, 12) で, 7重と分かる.

■Binary Indexed Tree とは？

// Fenwick tree.
// https://en.wikipedia.org/wiki/Fenwick_tree
// Fenwick (Binary Indexed) Trees.
// https://www.hackerearth.com/ja/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/
// Binary Indexed Tree のはなし.
// http://hos.ac/slides/20140319_bit.pdf
#include <bits/stdc++.h>

using namespace std;

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the sum from index 1 to idx
// @param idx: 指定された範囲におけるインデックスの最大値.
// @param tree: binary indexed tree の 構造を持った配列.
// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.
int query(int idx, int tree[]) {
    int ret = 0;
    while(idx > 0) ret += tree[idx], idx -= LSB(idx);
    return ret;
}

// Adds k to element with index idx
// @param idx: 通常の配列における更新対象要素のインデックス.
// @param k: 加算する値.
// @param tree: binary indexed tree の 構造を持った配列.
// @param size: 通常の配列についての配列サイズ.
// @return: none.
void update(int idx, int k, int tree[], int size) {
    while(idx < size) tree[idx] += k, idx += LSB(idx);
}

int main() {
    
    // 1. 変数初期化など.
    int N = 10;
    int tree[N + 1] = {};
    
    // 2. 配列 tree を, 通常の配列として初期化.
    // ex.
    // 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
    FOR(i, 1, N + 1) tree[i] = (1 << (i - 1));
    cout << "---------- initialize as an array -----------------------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;
    
    // 3. 配列 tree を, binary indexed tree の 構造を持った配列として初期化.
    // ex.
    // 1, 3(= 1 + 2), 4, 15(= 1 + 2 + 4 + 8), 16, 48(= 16 + 32), 64, 
    // 255(= 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128), 256, 768(= 256 + 512)
    FOR(i, 1, N + 1) tree[i + LSB(i)] += tree[i];
    cout << "---------- initialize as a binary indexed tree ----------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;
    
    // 4. 累積和確認.
    int a = query(3, tree);
    int b = query(7, tree);
    int c = query(9, tree);
    cout << "---------- check sum as a binary indexed tree -----------" << endl;
    cout << "a=" << a << " b=" << b << " c=" << c << endl;
    
    // 5. 更新確認.
    update(1, 5, tree, 10);
    cout << "---------- updated as a binary indexed tree -------------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;
    update(3, 2, tree, 10);
    cout << "---------- updated as a binary indexed tree -------------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

    return 0;

}

// Fenwick tree.

// https://en.wikipedia.org/wiki/Fenwick_tree

// Fenwick (Binary Indexed) Trees.

// https://www.hackerearth.com/ja/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/

// Binary Indexed Tree のはなし.

// http://hos.ac/slides/20140319_bit.pdf

#include <bits/stdc++.h>

using namespace std;

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the sum from index 1 to idx

// @param idx: 指定された範囲におけるインデックスの最大値.

// @param tree: binary indexed tree の構造を持った配列.

// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.

int query(int idx, int tree[]) {

int ret = 0;

while(idx > 0) ret += tree[idx], idx -= LSB(idx);

return ret;

}

// Adds k to element with index idx

// @param idx: 通常の配列における更新対象要素のインデックス.

// @param k: 加算する値.

// @param tree: binary indexed tree の構造を持った配列.

// @param size: 通常の配列についての配列サイズ.

// @return: none.

void update(int idx, int k, int tree[], int size) {

while(idx < size) tree[idx] += k, idx += LSB(idx);

}

int main() {

// 1. 変数初期化など.

int N = 10;

int tree[N + 1] = {};

// 2. 配列 tree を, 通常の配列として初期化.

// ex.

// 1, 2, 4, 8, 16, 32, 64, 128, 256, 512

FOR(i, 1, N + 1) tree[i] = (1 << (i - 1));

cout << "---------- initialize as an array -----------------------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

// 3. 配列 tree を, binary indexed tree の構造を持った配列として初期化.

// ex.

// 1, 3(= 1 + 2), 4, 15(= 1 + 2 + 4 + 8), 16, 48(= 16 + 32), 64,

// 255(= 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128), 256, 768(= 256 + 512)

FOR(i, 1, N + 1) tree[i + LSB(i)] += tree[i];

cout << "---------- initialize as a binary indexed tree ----------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

// 4. 累積和確認.

int a = query(3, tree);

int b = query(7, tree);

int c = query(9, tree);

cout << "---------- check sum as a binary indexed tree -----------" << endl;

cout << "a=" << a << " b=" << b << " c=" << c << endl;

// 5. 更新確認.

update(1, 5, tree, 10);

cout << "---------- updated as a binary indexed tree -------------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

update(3, 2, tree, 10);

cout << "---------- updated as a binary indexed tree -------------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

return 0;

}

※値の変化が目立つように, 出力結果に, コメント(<--- +5, <--- +2) を追加している.
---------- initialize as an array -----------------------
i=1 tree[1]=1
i=2 tree[2]=2
i=3 tree[3]=4
i=4 tree[4]=8
i=5 tree[5]=16
i=6 tree[6]=32
i=7 tree[7]=64
i=8 tree[8]=128
i=9 tree[9]=256
i=10 tree[10]=512
---------- initialize as a binary indexed tree ----------
i=1 tree[1]=1
i=2 tree[2]=3
i=3 tree[3]=4
i=4 tree[4]=15
i=5 tree[5]=16
i=6 tree[6]=48
i=7 tree[7]=64
i=8 tree[8]=255
i=9 tree[9]=256
i=10 tree[10]=768
---------- check sum as a binary indexed tree -----------
a=7 b=127 c=511
---------- updated as a binary indexed tree -------------
i=1 tree[1]=6    <--- +5
i=2 tree[2]=8    <--- +5
i=3 tree[3]=4
i=4 tree[4]=20   <--- +5
i=5 tree[5]=16
i=6 tree[6]=48
i=7 tree[7]=64
i=8 tree[8]=260  <--- +5
i=9 tree[9]=256
i=10 tree[10]=768
---------- updated as a binary indexed tree -------------
i=1 tree[1]=6
i=2 tree[2]=8
i=3 tree[3]=6    <--- +2
i=4 tree[4]=22   <--- +2
i=5 tree[5]=16
i=6 tree[6]=48
i=7 tree[7]=64
i=8 tree[8]=262  <--- +2
i=9 tree[9]=256
i=10 tree[10]=768

※値の変化が目立つように, 出力結果に, コメント(<--- +5, <--- +2) を追加している.

---------- initialize as an array -----------------------

i=1 tree[1]=1

i=2 tree[2]=2

i=3 tree[3]=4

i=4 tree[4]=8

i=5 tree[5]=16

i=6 tree[6]=32

i=7 tree[7]=64

i=8 tree[8]=128

i=9 tree[9]=256

i=10 tree[10]=512

---------- initialize as a binary indexed tree ----------

i=1 tree[1]=1

i=2 tree[2]=3

i=3 tree[3]=4

i=4 tree[4]=15

i=5 tree[5]=16

i=6 tree[6]=48

i=7 tree[7]=64

i=8 tree[8]=255

i=9 tree[9]=256

i=10 tree[10]=768

---------- check sum as a binary indexed tree -----------

a=7 b=127 c=511

---------- updated as a binary indexed tree -------------

i=1 tree[1]=6 <--- +5

i=2 tree[2]=8 <--- +5

i=3 tree[3]=4

i=4 tree[4]=20 <--- +5

i=5 tree[5]=16

i=6 tree[6]=48

i=7 tree[7]=64

i=8 tree[8]=260 <--- +5

i=9 tree[9]=256

i=10 tree[10]=768

---------- updated as a binary indexed tree -------------

i=1 tree[1]=6

i=2 tree[2]=8

i=3 tree[3]=6 <--- +2

i=4 tree[4]=22 <--- +2

i=5 tree[5]=16

i=6 tree[6]=48

i=7 tree[7]=64

i=8 tree[8]=262 <--- +2

i=9 tree[9]=256

i=10 tree[10]=768

■参照サイト
AtCoder Beginner Contest 038
Fenwick tree.
Fenwick (Binary Indexed) Trees.
Binary Indexed Tree のはなし.

C++の練習を兼ねて, AtCoder Beginner Contest 121 の 問題D (D – XOR World) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 096 の 問題C（Grid Repainting 2) ～ 問題D (Five, Five Everywhere) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 117 の 問題C（Streamline) ～ 問題D (XXOR) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 084 の 問題C（Special Trains) ～ 問題D (2017-like Number) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 083 の 問題C（Multiple Gift) ～ 問題D (Wide Flip) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 081 の 問題C（Not so Diverse) ～ 問題D (Non-decreasing) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 002 の 問題C（C – Knot Puzzle) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 002 の 問題B（Box and Ball) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 113 の 問題C（ID) ～ 問題D (Number of Amidakuji) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 038 の 問題C（単調増加) ～ 問題D (プレゼント) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 121 の問題D (D – XOR World) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 096 の問題C（Grid Repainting 2) ～問題D (Five, Five Everywhere) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 117 の問題C（Streamline) ～問題D (XXOR) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 084 の問題C（Special Trains) ～問題D (2017-like Number) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 083 の問題C（Multiple Gift) ～問題D (Wide Flip) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 081 の問題C（Not so Diverse) ～問題D (Non-decreasing) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題C（C – Knot Puzzle) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題B（Box and Ball) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 113 の問題C（ID) ～問題D (Number of Amidakuji) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 038 の問題C（単調増加) ～問題D (プレゼント) を解いてみた.