2月, 2019 | 個人用メモ帳

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

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年2月

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

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

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

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

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 096 の問題C（Grid Repainting 2) ～問題D (Five, Five Everywhere) を解いてみた.

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