個人用メモ帳

2021年5月8日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題034 (There are few types of elements) を解いてみた.

■感想.
1. 問題034は, 実装に苦労したものの, 何とかAC版に到達出来た.
2. 尺取り法の復習ができたので非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題034 をご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int a[101010];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 連続する部分列で最大の長さを計算(尺取り法).
    map<int, int> m;
    int ans = 0, s = 0;
    rep(l, N){
        // 2-1. index を 保存.
        int idx = 0;
        
        // 2-2. r を 伸ばしていく.
        repx(r, s, N){
            // 要素をカウントアップ.
            m[a[r]]++;
            
            // index 更新.
            idx = max(l + 1, r - 1);
            
            // 要素の種類数が, K を超えたら, 処理を中断.
            if(m.size() > K){
                // 要素の種類数が, K を超えたので, mapから除去.
                m.erase(a[r]);
                
                // 次回処理における, 二重カウント防止のため, 処理.
                if(m.count(a[s])){
                    // 要素をカウントダウン.
                    m[a[s]]--;
                    
                    // 要素数が, 0 ならば, 種類数を減らす.
                    if(m[a[s]] == 0) m.erase(a[s]);
                }
                
                // Skip.
                break;
            }
            
            // 最大値更新.
            ans = max(ans, r - l + 1);
        }
        
        // 2-3. 次回 の s を 設定.
        s = idx;
        
        // 2-4. 次回 の l に向けて準備.
        if(m.count(a[l])){
            // 要素をカウントダウン.
            m[a[l]]--;
            
            // 要素数が, 0 ならば, 種類数を減らす.
            if(m[a[l]] == 0) m.erase(a[l]);
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

int a[101010];

int main(){

// 1. 入力情報.

int N, K;

scanf("%d %d", &N, &K);

rep(i, N) scanf("%d", &a[i]);

// 2. 連続する部分列で最大の長さを計算(尺取り法).

map<int, int> m;

int ans = 0, s = 0;

rep(l, N){

// 2-1. index を保存.

int idx = 0;

// 2-2. r を伸ばしていく.

repx(r, s, N){

// 要素をカウントアップ.

m[a[r]]++;

// index 更新.

idx = max(l + 1, r - 1);

// 要素の種類数が, K を超えたら, 処理を中断.

if(m.size() > K){

// 要素の種類数が, K を超えたので, mapから除去.

m.erase(a[r]);

// 次回処理における, 二重カウント防止のため, 処理.

if(m.count(a[s])){

// 要素をカウントダウン.

m[a[s]]--;

// 要素数が, 0 ならば, 種類数を減らす.

if(m[a[s]] == 0) m.erase(a[s]);

}

// Skip.

break;

}

// 最大値更新.

ans = max(ans, r - l + 1);

}

// 2-3. 次回の s を設定.

s = idx;

// 2-4. 次回の l に向けて準備.

if(m.count(a[l])){

// 要素をカウントダウン.

m[a[l]]--;

// 要素数が, 0 ならば, 種類数を減らす.

if(m[a[l]] == 0) m.erase(a[l]);

}

// 3. 出力.

printf("%d\n", ans);

return 0;

}

[入力例]
5 1
1 2 3 4 5

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

[入力例]
5 4
1 1 2 4 2

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

[入力例]
10 2
1 2 3 4 4 3 2 1 2 3

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

[入力例]
10 2
2 3 1 3 2 1 1 1 1 1

[出力例]
6

[入力例]
10 1
2 3 1 3 2 1 1 1 1 1

[出力例]
5

[入力例]
20 3
4 5 1 2 5 2 1 3 1 4 3 2 5 2 3 5 5 4 1 3

[出力例]
7

[入力例]
32 3
1 1 2 2 5 4 2 1 4 1 4 1 1 4 2 5 1 4 2 2 5 1 3 1 1 1 4 1 5 4 5 2

[出力例]
10

[入力例]
52 3
3 1 2 2 1 2 2 3 6 3 1 1 3 5 6 4 2 2 3 2 4 6 4 1 5 5 6 1 2 5 4 3 4 1 3 4 6 2 2 1 1 6 1 2 1 6 3 6 2 3 2 4

[出力例]
10

[入力例]

5 1

1 2 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 1 2 4 2

[出力例]

※AtCoderテストケースより

[入力例]

10 2

1 2 3 4 4 3 2 1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

10 2

2 3 1 3 2 1 1 1 1 1

[出力例]

[入力例]

10 1

2 3 1 3 2 1 1 1 1 1

[出力例]

[入力例]

20 3

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

[出力例]

[入力例]

32 3

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

[出力例]

[入力例]

52 3

3 1 2 2 1 2 2 3 6 3 1 1 3 5 6 4 2 2 3 2 4 6 4 1 5 5 6 1 2 5 4 3 4 1 3 4 6 2 2 1 1 6 1 2 1 6 3 6 2 3 2 4

[出力例]

■参照サイト
034 – There are few types of elements

2021年5月8日

Python（Qiskit）について（１０）

概要

Qiskit について, 学習サイトのサンプルプログラムを動かしてみた.
動作環境は, Google Colaboratory で行った
実行プログラム, 解説は, 下記の参照サイトをご覧ください

感想

本家のサイトの学習教材が非常に詳しいので, 今後も, 時間を見つけて, 確認していこうと思う.

量子ビット状態を表現する(練習問題(パターン①))

量子回路

[編集内容(量子回路)]
from qiskit import QuantumCircuit, execute, Aer
from qiskit.visualization import plot_histogram, plot_bloch_vector
from math import sqrt, pi

# 回路のシミュレーション方法を指定.
backend = Aer.get_backend('statevector_simulator')

# 初期状態を 定義
# ※ |0> を測定する確率が 1 / 3 となるようにしたい.
initial_state = [1 / sqrt(3), sqrt(2) / sqrt(3)]

# 量子回路作成(1bit).
qc1 = QuantumCircuit(1)

# 初期化操作を 0番目 の 量子ビットに適用.
qc1.initialize(initial_state, 0)

# 回路を実行.
state = execute(qc1, backend).result().get_statevector()

# 結果を表示.
print(state)

[編集内容(量子回路)]

from qiskit import QuantumCircuit, execute, Aer

from qiskit.visualization import plot_histogram, plot_bloch_vector

from math import sqrt, pi

# 回路のシミュレーション方法を指定.

backend = Aer.get_backend('statevector_simulator')

# 初期状態を定義

# ※ |0> を測定する確率が 1 / 3 となるようにしたい.

initial_state = [1 / sqrt(3), sqrt(2) / sqrt(3)]

# 量子回路作成(1bit).

qc1 = QuantumCircuit(1)

# 初期化操作を 0番目の量子ビットに適用.

qc1.initialize(initial_state, 0)

# 回路を実行.

state = execute(qc1, backend).result().get_statevector()

# 結果を表示.

print(state)

[出力結果]
[0.57735027+0.j 0.81649658+0.j]

1 2	[出力結果] [0.57735027+0.j 0.81649658+0.j]

|0>, |1> カウント

[編集内容(|0>, |1> カウント)]
# シミュレーションを行い, 結果を返す.
result = execute(qc1, backend).result().get_counts()

# グラフを表示.
plot_histogram(result)

[編集内容(|0>, |1> カウント)]

# シミュレーションを行い, 結果を返す.

result = execute(qc1, backend).result().get_counts()

# グラフを表示.

plot_histogram(result)

[出力結果]
※グラフが表示された(|0> が 33.3%, |1> が 66.7% で 表示された).

1 2	[出力結果] ※グラフが表示された(\|0> が 33.3%, \|1> が 66.7% で表示された).

量子ビット状態を表現する(練習問題(パターン②))

量子回路

[編集内容(量子回路)]
from qiskit import QuantumCircuit, execute, Aer
from qiskit.visualization import plot_histogram, plot_bloch_vector
from math import sqrt, pi

# 回路のシミュレーション方法を指定.
backend = Aer.get_backend('statevector_simulator')

# 初期状態を 定義
# ※ |0> を測定する確率が 1 / 3 となるようにしたい.
initial_state = [1 / sqrt(3), -complex(0, sqrt(2) / sqrt(3))]

# 量子回路作成(1bit).
qc2 = QuantumCircuit(1)

# 初期化操作を 0番目 の 量子ビットに適用.
qc2.initialize(initial_state, 0)

# 回路を実行.
state = execute(qc2, backend).result().get_statevector()

# 結果を表示.
print(state)

[編集内容(量子回路)]

from qiskit import QuantumCircuit, execute, Aer

from qiskit.visualization import plot_histogram, plot_bloch_vector

from math import sqrt, pi

# 回路のシミュレーション方法を指定.

backend = Aer.get_backend('statevector_simulator')

# 初期状態を定義

# ※ |0> を測定する確率が 1 / 3 となるようにしたい.

initial_state = [1 / sqrt(3), -complex(0, sqrt(2) / sqrt(3))]

# 量子回路作成(1bit).

qc2 = QuantumCircuit(1)

# 初期化操作を 0番目の量子ビットに適用.

qc2.initialize(initial_state, 0)

# 回路を実行.

state = execute(qc2, backend).result().get_statevector()

# 結果を表示.

print(state)

[出力結果]
[ 0.57735027+0.j         -0.        -0.81649658j]

1 2	[出力結果] [ 0.57735027+0.j -0. -0.81649658j]

|0>, |1> カウント

[編集内容(|0>, |1> カウント)]
# シミュレーションを行い, 結果を返す.
result = execute(qc2, backend).result().get_counts()

# グラフを表示.
plot_histogram(result)

[編集内容(|0>, |1> カウント)]

# シミュレーションを行い, 結果を返す.

result = execute(qc2, backend).result().get_counts()

# グラフを表示.

plot_histogram(result)

[出力結果]
※グラフが表示された(|0> が 33.3%, |1> が 66.7% で 表示された).

1 2	[出力結果] ※グラフが表示された(\|0> が 33.3%, \|1> が 66.7% で表示された).

量子ビット状態を表現する(練習問題(パターン③))

量子回路

[編集内容(量子回路)]
from qiskit import QuantumCircuit, execute, Aer
from qiskit.visualization import plot_histogram, plot_bloch_vector
from math import sqrt, pi

# 回路のシミュレーション方法を指定.
backend = Aer.get_backend('statevector_simulator')

# 初期状態を 定義
# ※ |0> を測定する確率が 1 / 5 となるようにしたい.
initial_state = [1 / sqrt(5), -2 / sqrt(5)]

# 量子回路作成(1bit).
qc3 = QuantumCircuit(1)

# 初期化操作を 0番目 の 量子ビットに適用.
qc3.initialize(initial_state, 0)

# 回路を実行.
state = execute(qc3, backend).result().get_statevector()

# 結果を表示.
print(state)

[編集内容(量子回路)]

from qiskit import QuantumCircuit, execute, Aer

from qiskit.visualization import plot_histogram, plot_bloch_vector

from math import sqrt, pi

# 回路のシミュレーション方法を指定.

backend = Aer.get_backend('statevector_simulator')

# 初期状態を定義

# ※ |0> を測定する確率が 1 / 5 となるようにしたい.

initial_state = [1 / sqrt(5), -2 / sqrt(5)]

# 量子回路作成(1bit).

qc3 = QuantumCircuit(1)

# 初期化操作を 0番目の量子ビットに適用.

qc3.initialize(initial_state, 0)

# 回路を実行.

state = execute(qc3, backend).result().get_statevector()

# 結果を表示.

print(state)

[出力結果]
[ 0.4472136 +0.j -0.89442719+0.j]

1 2	[出力結果] [ 0.4472136 +0.j -0.89442719+0.j]

|0>, |1> カウント

[編集内容(|0>, |1> カウント)]
# シミュレーションを行い, 結果を返す.
result = execute(qc3, backend).result().get_counts()

# グラフを表示.
plot_histogram(result)

[編集内容(|0>, |1> カウント)]

# シミュレーションを行い, 結果を返す.

result = execute(qc3, backend).result().get_counts()

# グラフを表示.

plot_histogram(result)

[出力結果]
※グラフが表示された(|0> が 20%, |1> が 80% で 表示された).

1 2	[出力結果] ※グラフが表示された(\|0> が 20%, \|1> が 80% で表示された).

量子ビット状態を表現する(練習問題(パターン④))

量子回路

[編集内容(量子回路)]
from qiskit import QuantumCircuit, execute, Aer
from qiskit.visualization import plot_histogram, plot_bloch_vector
from math import sqrt, pi

# 回路のシミュレーション方法を指定.
backend = Aer.get_backend('statevector_simulator')

# 初期状態を 定義
# ※ |0> を測定する確率が 1 / 5 となるようにしたい.
initial_state = [1 / sqrt(5), complex(2 / 5, 4 / 5)]

# 量子回路作成(1bit).
qc4 = QuantumCircuit(1)

# 初期化操作を 0番目 の 量子ビットに適用.
qc4.initialize(initial_state, 0)

# 回路を実行.
state = execute(qc4, backend).result().get_statevector()

# 結果を表示.
print(state)

[編集内容(量子回路)]

from qiskit import QuantumCircuit, execute, Aer

from qiskit.visualization import plot_histogram, plot_bloch_vector

from math import sqrt, pi

# 回路のシミュレーション方法を指定.

backend = Aer.get_backend('statevector_simulator')

# 初期状態を定義

# ※ |0> を測定する確率が 1 / 5 となるようにしたい.

initial_state = [1 / sqrt(5), complex(2 / 5, 4 / 5)]

# 量子回路作成(1bit).

qc4 = QuantumCircuit(1)

# 初期化操作を 0番目の量子ビットに適用.

qc4.initialize(initial_state, 0)

# 回路を実行.

state = execute(qc4, backend).result().get_statevector()

# 結果を表示.

print(state)

[出力結果]
[0.4472136+0.j  0.4      +0.8j]

1 2	[出力結果] [0.4472136+0.j 0.4 +0.8j]

|0>, |1> カウント

[編集内容(|0>, |1> カウント)]
# シミュレーションを行い, 結果を返す.
result = execute(qc4, backend).result().get_counts()

# グラフを表示.
plot_histogram(result)

[編集内容(|0>, |1> カウント)]

# シミュレーションを行い, 結果を返す.

result = execute(qc4, backend).result().get_counts()

# グラフを表示.

plot_histogram(result)

[出力結果]
※グラフが表示された(|0> が 20%, |1> が 80% で 表示された).

1 2	[出力結果] ※グラフが表示された(\|0> が 20%, \|1> が 80% で表示された).

量子ビット状態を表現する(練習問題(パターン⑤))

量子回路

[編集内容(量子回路)]
from qiskit import QuantumCircuit, execute, Aer
from qiskit.visualization import plot_histogram, plot_bloch_vector
from math import sqrt, pi

# 回路のシミュレーション方法を指定.
backend = Aer.get_backend('statevector_simulator')

# 初期状態を 定義
# ※ |0> を測定する確率が 3 / 11 となるようにしたい.
initial_state = [sqrt(3) / sqrt(11), complex(1 / sqrt(33), sqrt(23) / sqrt(33))]

# 量子回路作成(1bit).
qc5 = QuantumCircuit(1)

# 初期化操作を 0番目 の 量子ビットに適用.
qc5.initialize(initial_state, 0)

# 回路を実行.
state = execute(qc5, backend).result().get_statevector()

# 結果を表示.
print(state)

[編集内容(量子回路)]

from qiskit import QuantumCircuit, execute, Aer

from qiskit.visualization import plot_histogram, plot_bloch_vector

from math import sqrt, pi

# 回路のシミュレーション方法を指定.

backend = Aer.get_backend('statevector_simulator')

# 初期状態を定義

# ※ |0> を測定する確率が 3 / 11 となるようにしたい.

initial_state = [sqrt(3) / sqrt(11), complex(1 / sqrt(33), sqrt(23) / sqrt(33))]

# 量子回路作成(1bit).

qc5 = QuantumCircuit(1)

# 初期化操作を 0番目の量子ビットに適用.

qc5.initialize(initial_state, 0)

# 回路を実行.

state = execute(qc5, backend).result().get_statevector()

# 結果を表示.

print(state)

[出力結果]
[0.52223297+0.j         0.17407766+0.83484711j]

1 2	[出力結果] [0.52223297+0.j 0.17407766+0.83484711j]

|0>, |1> カウント

[編集内容(|0>, |1> カウント)]
# シミュレーションを行い, 結果を返す.
result = execute(qc5, backend).result().get_counts()

# グラフを表示.
plot_histogram(result)

[編集内容(|0>, |1> カウント)]

# シミュレーションを行い, 結果を返す.

result = execute(qc5, backend).result().get_counts()

# グラフを表示.

plot_histogram(result)

[出力結果]
※グラフが表示された(|0> が 27.3%, |1> が 72.7% で 表示された).

1 2	[出力結果] ※グラフが表示された(\|0> が 27.3%, \|1> が 72.7% で表示された).

参照サイト

量子ビット状態を表現する

2021年5月5日

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

C++の練習を兼ねて, AtCoder Regular Contest 088 の問題F (Christmas Tree) を解いてみた.

■感想.
1. 問題Fは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 実装に非常に苦労したものの, 二分探索(応用版), および, 幅優先探索を復習することが出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc088/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()

int main(){

    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. A の 値は？
    int A = 0, root = -1;
    rep(i, N){
        int size = G[i].size();
        if(size & 1) A++;
        if(size == 1 && root == -1) root = i;
    }
    A /= 2;
    
    // 3. 根 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 3-1. 空のキュー.
        queue<int> q;
        
        // 3-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 3-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 3-4. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 3-5. 訪問済であれば, 処理をスキップ.
                if(d[e])            continue;
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, root, d);
    // printf("root=%d\n", root);
    // rep(i, N) printf("%d ", d[i]);
    
    // 4. 内側の二分探索用の判定関数.
    auto f = [&](vp &x, int im, int om, int* dp) -> bool{
        int xSize = x.size();
        int dpMax = x[im].a;
        if(dpMax > om) return false;
        vi nv;
        rep(i, xSize) if(i != im) nv.pb(x[i].a);
        int nvSize = nv.size();
        rep(i, nvSize / 2){
            int s = i;
            int e = nvSize - 1 - i;
            dpMax = max(dpMax, nv[s] + nv[e]);
        }
        return (dpMax <= om);
    };
    
    // 5. 外側の二分探索用の判定関数.
    auto g = [&](int om) -> bool{
        // 5-1. 初期化.
        bool ok = true;
        priority_queue<P> pq;
        int dp[101010];
        rep(i, N){
            if(i == root) continue;
            if(G[i].size() == 1 && i != root){
                dp[i] = 1;
            }else{
                dp[i] = 101010;
                pq.push({d[i], i});
            }
        }
        
        // 5-2. dp更新.
        while(!pq.empty()){
            // 終了条件.
            if(!ok) break;
            
            // 頂点 v を一つ取り出す.
            P p = pq.top();
            pq.pop();
            
            // 頂点 v の 頂点番号は？
            int v = p.b;
            
            // 頂点 v の 子頂点 を 保存.
            vp a;
            for(auto &u : G[v]) if(d[u] > d[v]) a.pb({dp[u], u});
            
            // sort.
            sort(all(a));
            
            // サイズチェック.
            int aSize = a.size();
            
            // サイズ 0 なら次へ.
            if(aSize == 0) continue;
            
            // 内側の二分探索.
            // 奇数の場合.
            if(aSize & 1){
                int il = -1, ih = aSize, im;
                while(il + 1 < ih){
                    im = (il + ih) >> 1;
                    if(f(a, im, om, dp)) ih = im;
                    else                 il = im;
                }
                if(a[ih].a + 1 > om || !f(a, ih, om, dp)){
                    ok = false;
                    break;
                }
                
                // 残ったパス(ih番目)から親方向に伸ばす.
                dp[v] = min(dp[v], a[ih].a + 1);
            }
            
            // 偶数の場合.
            if(!(aSize & 1)){
                // パターン 1.
                int dpMax = 0;
                rep(i, aSize / 2){
                    int s = i;
                    int e = aSize - 1 - i;
                    dpMax = max(dpMax, a[s].a + a[e].a);
                }
                
                // パターン 2.
                a.pop_back(); // 端点とする頂点を除外.
                int il = -1, ih = aSize, im;
                while(il + 1 < ih){
                    im = (il + ih) >> 1;
                    if(f(a, im, om, dp)) ih = im;
                    else                 il = im;
                }
                if(dpMax > om && !f(a, ih, om, dp)){
                    ok = false;
                    break;
                }
                if(dpMax <= om){
                    dp[v] = 1;
                    continue;
                }
                if(a[ih].a + 1 > om){
                    ok = false;
                    break;
                }
                
                // 残ったパス(ih番目)から親方向に伸ばす.
                dp[v] = min(dp[v], a[ih].a + 1);
            }
        }
        
        // 5-3. 結果を返却.
        return ok;
    };
    
    // 6. B の 値は？
    // 外側の二分探索.
    int ol = 0, oh = N, om;
    while(ol + 1 < oh){
        om = (ol + oh) >> 1;
        if(g(om)) oh = om;
        else      ol = om;
        // printf("oh=%d ol=%d om=%d\n", oh, ol, om);
    }
    
    // 7. 出力.
    int B = oh;
    printf("%d %d\n", A, B);
    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

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using vp = vector;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

#define pb push_back

#define a first

#define b second

#define all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int a, b;

scanf("%d %d", &a, &b);

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. A の値は？

int A = 0, root = -1;

rep(i, N){

int size = G[i].size();

if(size & 1) A++;

if(size == 1 && root == -1) root = i;

}

A /= 2;

// 3. 根から各頂点までの距離を計算.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](vvi &G, int s, int* d){

// 3-1. 空のキュー.

queue<int> q;

// 3-2. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 3-3. キューから取り出す.

int u = q.front();

q.pop();

// 3-4. 取り出した要素を処理.

for(auto &e : G[u]){

// 3-5. 訪問済であれば, 処理をスキップ.

if(d[e]) continue;

if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);

}

return;

};

int d[N];

rep(i, N) d[i] = 0;

bfs(G, root, d);

// printf("root=%d\n", root);

// rep(i, N) printf("%d ", d[i]);

// 4. 内側の二分探索用の判定関数.

auto f = [&](vp &x, int im, int om, int* dp) -> bool{

int xSize = x.size();

int dpMax = x[im].a;

if(dpMax > om) return false;

vi nv;

rep(i, xSize) if(i != im) nv.pb(x[i].a);

int nvSize = nv.size();

rep(i, nvSize / 2){

int s = i;

int e = nvSize - 1 - i;

dpMax = max(dpMax, nv[s] + nv[e]);

}

return (dpMax <= om);

};

// 5. 外側の二分探索用の判定関数.

auto g = [&](int om) -> bool{

// 5-1. 初期化.

bool ok = true;

priority_queue pq;

int dp[101010];

rep(i, N){

if(i == root) continue;

if(G[i].size() == 1 && i != root){

dp[i] = 1;

}else{

dp[i] = 101010;

pq.push({d[i], i});

}

// 5-2. dp更新.

while(!pq.empty()){

// 終了条件.

if(!ok) break;

// 頂点 v を一つ取り出す.

P p = pq.top();

pq.pop();

// 頂点 v の頂点番号は？

int v = p.b;

// 頂点 v の子頂点を保存.

vp a;

for(auto &u : G[v]) if(d[u] > d[v]) a.pb({dp[u], u});

// sort.

sort(all(a));

// サイズチェック.

int aSize = a.size();

// サイズ 0 なら次へ.

if(aSize == 0) continue;

// 内側の二分探索.

// 奇数の場合.

if(aSize & 1){

int il = -1, ih = aSize, im;

while(il + 1 < ih){

im = (il + ih) >> 1;

if(f(a, im, om, dp)) ih = im;

else il = im;

}

if(a[ih].a + 1 > om || !f(a, ih, om, dp)){

ok = false;

break;

}

// 残ったパス(ih番目)から親方向に伸ばす.

dp[v] = min(dp[v], a[ih].a + 1);

}

// 偶数の場合.

if(!(aSize & 1)){

// パターン 1.

int dpMax = 0;

rep(i, aSize / 2){

int s = i;

int e = aSize - 1 - i;

dpMax = max(dpMax, a[s].a + a[e].a);

}

// パターン 2.

a.pop_back(); // 端点とする頂点を除外.

int il = -1, ih = aSize, im;

while(il + 1 < ih){

im = (il + ih) >> 1;

if(f(a, im, om, dp)) ih = im;

else il = im;

}

if(dpMax > om && !f(a, ih, om, dp)){

ok = false;

break;

}

if(dpMax <= om){

dp[v] = 1;

continue;

}

if(a[ih].a + 1 > om){

ok = false;

break;

}

// 残ったパス(ih番目)から親方向に伸ばす.

dp[v] = min(dp[v], a[ih].a + 1);

}

// 5-3. 結果を返却.

return ok;

};

// 6. B の値は？

// 外側の二分探索.

int ol = 0, oh = N, om;

while(ol + 1 < oh){

om = (ol + oh) >> 1;

if(g(om)) oh = om;

else ol = om;

// printf("oh=%d ol=%d om=%d\n", oh, ol, om);

}

// 7. 出力.

int B = oh;

printf("%d %d\n", A, B);

return 0;

}

[入力例]
7
1 2
2 3
2 4
4 5
4 6
6 7

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

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

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

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

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

[入力例]
20
1 2
3 2
4 2
3 6
3 5
4 8
4 7
5 10
5 11
5 9
9 12
9 13
10 18
10 19
10 20
7 14
14 15
15 16
15 17

[出力例]
8 3

[入力例]
33
1 32
3 32
2 32
6 32
1 9
1 10
6 5
8 11
5 33
33 4
33 8
33 7
16 15
4 16
7 12
7 13
7 14
9 21
10 17
10 18
10 19
10 20
20 22
20 23
20 24
31 25
14 26
26 27
26 28
26 29
26 30
26 31

[出力例]
10 6

100

101

102

103

104

105

[入力例]

1 2

2 3

2 4

4 5

4 6

6 7

[出力例]

3 2

※AtCoderテストケースより

[入力例]

1 2

2 3

3 4

4 5

5 6

5 7

5 8

[出力例]

2 5

※AtCoderテストケースより

[入力例]

1 2

2 3

3 4

2 5

6 5

6 7

7 8

5 9

10 5

[出力例]

3 4

※AtCoderテストケースより

[入力例]

1 2

3 2

4 2

3 6

3 5

4 8

4 7

5 10

5 11

5 9

9 12

9 13

10 18

10 19

10 20

7 14

14 15

15 16

15 17

[出力例]

8 3

[入力例]

1 32

3 32

2 32

6 32

1 9

1 10

6 5

8 11

5 33

33 4

33 8

33 7

16 15

4 16

7 12

7 13

7 14

9 21

10 17

10 18

10 19

10 20

20 22

20 23

20 24

31 25

14 26

26 27

26 28

26 29

26 30

26 31

[出力例]

10 6

■参照サイト
AtCoder Regular Contest 088

2021年5月5日2021年5月5日

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

C++の練習を兼ねて, AtCoder Grand Contest 036 の問題B (Do Not Duplicate) を解いてみた.

■感想.
1. 問題Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 実装に苦労したものの, ダブリングを復習することが出来たので, 非常に良かったと思う..
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc036/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pob pop_back
#define pub push_back
#define all(x) x.begin(), x.end()
int a[202020], y[202020], stock[202020];
LL g[59][202020];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    vvi v(202020);
    rep(i, N){
        scanf("%d", &a[i]);
        v[a[i]].pub(i);
    }
    
    // 2. y[a] を 計算.
    rep(i, N){
        int l = v[a[i]].size();
        if(l == 1) y[i] = i + N + 1;
        if(l != 1){
            int at = lower_bound(all(v[a[i]]), i) - v[a[i]].begin();
            if(at < l - 1) y[i] = v[a[i]][at + 1] + 1;
            else           y[i] = v[a[i]][0] + N + 1;
        }
    }
    
    // 3. Doubling.
    rep(i, N) g[0][i] = y[i];
    int u = 0;
    LL bef = 0, cur = 0, r = 0, maxG = 0;
    repx(i, 1, 59){
        rep(j, N){
            // 前回分取得.
            bef = g[i - 1][j];
            r = bef % N;
            
            // 今回分設定.
            cur = (bef - r) + g[i - 1][r];
            g[i][j] = cur;
            
            // 最大値更新.
            maxG = max(maxG, cur);
        }
        
        // 最大値が大きい場合は, 終了.
        // -> オーバーフロー防止のため.
        if(maxG > 1e18){
            u = i;
            break;
        }
    }
    
    // 4. Step 1 が 終了するタイミング の aStop は？
    LL aStop = 0, upper = N * K - 1;
    int idx = 0;
    while(upper - aStop > (LL)N){
        // 探索.
        LL t = 0;
        rep(i, u + 1){
            if(g[i][idx] - idx <= upper - aStop) t = g[i][idx];
            else                                 break;
        }
        
        // 更新.
        aStop += (t - idx);
        idx = t % N;
    }
    
    // 5. aStop, aStop + 1, ... , N * K - 1 について操作.
    int aStart = (int)(aStop % N);
    deque<int> ans;
    repx(i, aStart, N){
        if(stock[a[i]]){
            bool ok = true;
            while(ok){
                // 該当要素が見つかったら, フラグ更新.
                int t = ans.back();
                if(t == a[i]) ok = false;
                stock[t]--;
                ans.pob();
            }
        }else{
            stock[a[i]]++;
            ans.pub(a[i]);
        }
    }
    
    // 6. 出力.
    int l = ans.size();
    rep(i, l){
        printf("%d", ans[i]);
        printf("%s", (i < l - 1) ? " " : "\n");
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using LL = long long;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

#define pob pop_back

#define pub push_back

#define all(x) x.begin(), x.end()

int a[202020], y[202020], stock[202020];

LL g[59][202020];

int main(){

// 1. 入力情報.

int N;

LL K;

scanf("%d %lld", &N, &K);

vvi v(202020);

rep(i, N){

scanf("%d", &a[i]);

v[a[i]].pub(i);

}

// 2. y[a] を計算.

rep(i, N){

int l = v[a[i]].size();

if(l == 1) y[i] = i + N + 1;

if(l != 1){

int at = lower_bound(all(v[a[i]]), i) - v[a[i]].begin();

if(at < l - 1) y[i] = v[a[i]][at + 1] + 1;

else y[i] = v[a[i]][0] + N + 1;

}

// 3. Doubling.

rep(i, N) g[0][i] = y[i];

int u = 0;

LL bef = 0, cur = 0, r = 0, maxG = 0;

repx(i, 1, 59){

rep(j, N){

// 前回分取得.

bef = g[i - 1][j];

r = bef % N;

// 今回分設定.

cur = (bef - r) + g[i - 1][r];

g[i][j] = cur;

// 最大値更新.

maxG = max(maxG, cur);

}

// 最大値が大きい場合は, 終了.

// -> オーバーフロー防止のため.

if(maxG > 1e18){

u = i;

break;

}

// 4. Step 1 が終了するタイミングの aStop は？

LL aStop = 0, upper = N * K - 1;

int idx = 0;

while(upper - aStop > (LL)N){

// 探索.

LL t = 0;

rep(i, u + 1){

if(g[i][idx] - idx <= upper - aStop) t = g[i][idx];

else break;

}

// 更新.

aStop += (t - idx);

idx = t % N;

}

// 5. aStop, aStop + 1, ... , N * K - 1 について操作.

int aStart = (int)(aStop % N);

deque<int> ans;

repx(i, aStart, N){

if(stock[a[i]]){

bool ok = true;

while(ok){

// 該当要素が見つかったら, フラグ更新.

int t = ans.back();

if(t == a[i]) ok = false;

stock[t]--;

ans.pob();

}

}else{

stock[a[i]]++;

ans.pub(a[i]);

}

// 6. 出力.

int l = ans.size();

rep(i, l){

printf("%d", ans[i]);

printf("%s", (i < l - 1) ? " " : "\n");

}

return 0;

}

[入力例]
3 2
1 2 3

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

[入力例]
5 10
1 2 3 2 3

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

[入力例]
6 1000000000000
1 1 2 2 3 3

[出力例]

※AtCoderのテストケースより

[入力例]
11 97
3 1 4 1 5 9 2 6 5 3 5

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

[入力例]
7 11
7 1 2 7 3 4 5

[出力例]
5

[入力例]
15 7
15 2 1 7 1 2 1 5 3 8 2 12 10 13 5

[出力例]
7

[入力例]
50 2021
13 18 53 45 22 3 13 45 18 4 54 22 20 55 39 19 14 29 8 9 47 15 39 46 9 31 24 31 27 25 16 42 31 44 24 31 45 53 2 45 53 53 47 25 10 2 3 18 11 21

[出力例]
53 47 25 10 2 3 18 11 21

[入力例]

3 2

1 2 3

[出力例]

2 3

※AtCoderのテストケースより

[入力例]

5 10

1 2 3 2 3

[出力例]

※AtCoderのテストケースより

[入力例]

6 1000000000000

1 1 2 2 3 3

[出力例]

※AtCoderのテストケースより

[入力例]

11 97

3 1 4 1 5 9 2 6 5 3 5

[出力例]

9 2 6

※AtCoderのテストケースより

[入力例]

7 11

7 1 2 7 3 4 5

[出力例]

[入力例]

15 7

15 2 1 7 1 2 1 5 3 8 2 12 10 13 5

[出力例]

[入力例]

50 2021

13 18 53 45 22 3 13 45 18 4 54 22 20 55 39 19 14 29 8 9 47 15 39 46 9 31 24 31 27 25 16 42 31 44 24 31 45 53 2 45 53 53 47 25 10 2 3 18 11 21

[出力例]

53 47 25 10 2 3 18 11 21

■参照サイト
AtCoder Grand Contest 036

2021年5月4日

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

C++の練習を兼ねて, ZONeエナジープログラミングコンテスト “HELLO SPACE” の問題C (MAD TEAM) ～問題D (宇宙人からのメッセージ) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 問題Cは, 実装に苦労したものの, 二分探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト ZONeエナジープログラミングコンテスト解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/zone2021/editorial/1197
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int a[3030], b[3030], c[3030], d[3030], e[3030];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d %d %d %d %d", &a[i], &b[i], &c[i], &d[i], &e[i]);
    
    // 2. 判定関数.
    auto f = [&](int x) -> bool{
        // 2-1. 能力値の取り得る値を圧縮.
        int m[32];
        rep(i, 32) m[i] = 0;
        rep(i, N){
            int fa = (a[i] >= x) ? 16 : 0;
            int fb = (b[i] >= x) ?  8 : 0;
            int fc = (c[i] >= x) ?  4 : 0;
            int fd = (d[i] >= x) ?  2 : 0;
            int fe = (e[i] >= x) ?  1 : 0;
            m[fa + fb + fc + fd + fe] = 1;
        }
        
        // 2-2. 能力値の組み合わせを確認して, 値 x を取り得るかチェック.
        bool ret = true;
        int ml = 0;
        rep(i, 1 << 15){
            int p1 = i >> 10;
            int p2 = (i >> 5) - (p1 << 5);
            int p3 = i - (p1 << 10) - (p2 << 5);
            
            int ok = 0;
            if(m[p1]) ok |= p1;
            if(m[p2]) ok |= p2;
            if(m[p3]) ok |= p3;
            
            if(ok == 31){
                ret = false;
                break;
            }
        }
        
        // 2-3. 結果を返却.
        return ret;
    };
    
    // 3. 二分探索してみる.
    int l = 0, h = 1e9 + 1, m;
    while(l + 1 < h){
        m = (l + h) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    
    // 4. 出力.
    printf("%d\n", l);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/zone2021/editorial/1197

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

int a[3030], b[3030], c[3030], d[3030], e[3030];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%d %d %d %d %d", &a[i], &b[i], &c[i], &d[i], &e[i]);

// 2. 判定関数.

auto f = [&](int x) -> bool{

// 2-1. 能力値の取り得る値を圧縮.

int m[32];

rep(i, 32) m[i] = 0;

rep(i, N){

int fa = (a[i] >= x) ? 16 : 0;

int fb = (b[i] >= x) ? 8 : 0;

int fc = (c[i] >= x) ? 4 : 0;

int fd = (d[i] >= x) ? 2 : 0;

int fe = (e[i] >= x) ? 1 : 0;

m[fa + fb + fc + fd + fe] = 1;

}

// 2-2. 能力値の組み合わせを確認して, 値 x を取り得るかチェック.

bool ret = true;

int ml = 0;

rep(i, 1 << 15){

int p1 = i >> 10;

int p2 = (i >> 5) - (p1 << 5);

int p3 = i - (p1 << 10) - (p2 << 5);

int ok = 0;

if(m[p1]) ok |= p1;

if(m[p2]) ok |= p2;

if(m[p3]) ok |= p3;

if(ok == 31){

ret = false;

break;

}

// 2-3. 結果を返却.

return ret;

};

// 3. 二分探索してみる.

int l = 0, h = 1e9 + 1, m;

while(l + 1 < h){

m = (l + h) >> 1;

if(f(m)) h = m;

else l = m;

// printf("h=%d l=%d m=%d\n", h, l, m);

}

// 4. 出力.

printf("%d\n", l);

return 0;

}

[入力例]
3
3 9 6 4 6
6 9 3 1 1
8 8 9 3 7

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

[入力例]
5
6 13 6 19 11
4 4 12 11 18
20 7 19 2 5
15 5 12 20 7
8 7 6 18 5

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

[入力例]
10
6 7 5 18 2
3 8 1 6 3
7 2 8 7 7
6 3 3 4 7
12 8 9 15 9
9 8 6 1 10
12 9 7 8 2
10 3 17 4 10
3 1 3 19 3
3 14 7 13 1

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

[入力例]
15
79 22 32 32 45
24 71 100 54 103
108 33 5 28 104
62 8 51 20 36
77 25 2 101 12
28 14 54 65 41
89 12 90 119 98
92 40 112 67 20
18 5 31 85 10
16 70 31 62 111
55 67 1 84 86
84 37 9 64 96
118 1 31 92 106
83 114 43 58 35
76 107 59 96 39

[出力例]
96

※実際に, 2番目, 3番目, 15番目 の人を採用すると達成できる.
チーム全体のパワー:     max( 24, 108,  76) = 108
チーム全体のスピード:   max( 71,  33, 107) = 107
チーム全体のテクニック: max(100,   5,  59) = 100
チーム全体の知識:       max( 54,  28,  96) =  96
チーム全体の発想力:     max(103, 104,  39) = 104
-> チームの総合力は, min(108, 107, 100, 96, 104) = 96

[入力例]

3 9 6 4 6

6 9 3 1 1

8 8 9 3 7

[出力例]

※AtCoderテストケースより

[入力例]

6 13 6 19 11

4 4 12 11 18

20 7 19 2 5

15 5 12 20 7

8 7 6 18 5

[出力例]

※AtCoderテストケースより

[入力例]

6 7 5 18 2

3 8 1 6 3

7 2 8 7 7

6 3 3 4 7

12 8 9 15 9

9 8 6 1 10

12 9 7 8 2

10 3 17 4 10

3 1 3 19 3

3 14 7 13 1

[出力例]

※AtCoderテストケースより

[入力例]

79 22 32 32 45

24 71 100 54 103

108 33 5 28 104

62 8 51 20 36

77 25 2 101 12

28 14 54 65 41

89 12 90 119 98

92 40 112 67 20

18 5 31 85 10

16 70 31 62 111

55 67 1 84 86

84 37 9 64 96

118 1 31 92 106

83 114 43 58 35

76 107 59 96 39

[出力例]

※実際に, 2番目, 3番目, 15番目の人を採用すると達成できる.

チーム全体のパワー: max( 24, 108, 76) = 108

チーム全体のスピード: max( 71, 33, 107) = 107

チーム全体のテクニック: max(100, 5, 59) = 100

チーム全体の知識: max( 54, 28, 96) = 96

チーム全体の発想力: max(103, 104, 39) = 104

-> チームの総合力は, min(108, 107, 100, 96, 104) = 96

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pub push_back
#define puf push_front

int main(){
    
    // 1. 入力情報.
    char S[505050];
    scanf("%s", S);
    int l = strlen(S);
    
    // 2. 文字列を操作.
    deque<char> dq;
    bool f = false;
    rep(i, l){
        if(S[i] == 'R'){
            f = !f;
            continue;
        }
        if(f) dq.puf(S[i]);
        else  dq.pub(S[i]);
    }
    
    // 3. 連続文字の削除.
    stack<char> st;
    if(f){
        rep(i, dq.size()){
            if(!st.empty()){
                if(st.top() == dq[i]){
                    st.pop();
                    continue;
                }
            }
            st.push(dq[i]);
        }
    }else{
        repr(i, dq.size() - 1, 0){
            if(!st.empty()){
                if(st.top() == dq[i]){
                    st.pop();
                    continue;
                }
            }
            st.push(dq[i]);
        }
    }
    
    // 4. 文字列を構成.
    string ans = "";
    while(!st.empty()){
        ans.pub(st.top());
        st.pop();
    }
    
    // 5. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

#define pub push_back

#define puf push_front

int main(){

// 1. 入力情報.

char S[505050];

scanf("%s", S);

int l = strlen(S);

// 2. 文字列を操作.

deque<char> dq;

bool f = false;

rep(i, l){

if(S[i] == 'R'){

f = !f;

continue;

}

if(f) dq.puf(S[i]);

else dq.pub(S[i]);

}

// 3. 連続文字の削除.

stack<char> st;

if(f){

rep(i, dq.size()){

if(!st.empty()){

if(st.top() == dq[i]){

st.pop();

continue;

}

st.push(dq[i]);

}

}else{

repr(i, dq.size() - 1, 0){

if(!st.empty()){

if(st.top() == dq[i]){

st.pop();

continue;

}

st.push(dq[i]);

}

// 4. 文字列を構成.

string ans = "";

while(!st.empty()){

ans.pub(st.top());

st.pop();

}

// 5. 出力.

printf("%s\n", ans.c_str());

return 0;

}

[入力例]
ozRnonnoe

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

[入力例]
hellospaceRhellospace

[出力例]

※AtCoderテストケースより

[入力例]
abRacadabRa

[出力例]
badacba

[入力例]
fcccpkiRcckarpcvwwvcprkccddeeedkkqqqccffReewzzqqqooooRasssswwweotttoRqqffffqoooosvrnjjjjjaksrspzmmjjjmmmzpskaRkuRvdppppbpuuuudvvvRaammqqqohhiqReetfxxo

[出力例]
qioqukotoewaqdekakfcpkiwsvrnjaksrspzjmzpskavdbpdvtfo

[入力例]

ozRnonnoe

[出力例]

zone

※AtCoderテストケースより

[入力例]

hellospaceRhellospace

[出力例]

※AtCoderテストケースより

[入力例]

abRacadabRa

[出力例]

badacba

[入力例]

fcccpkiRcckarpcvwwvcprkccddeeedkkqqqccffReewzzqqqooooRasssswwweotttoRqqffffqoooosvrnjjjjjaksrspzmmjjjmmmzpskaRkuRvdppppbpuuuudvvvRaammqqqohhiqReetfxxo

[出力例]

qioqukotoewaqdekakfcpkiwsvrnjaksrspzjmzpskavdbpdvtfo

■参照サイト
ZONeエナジープログラミングコンテスト “HELLO SPACE”

2021年4月30日2021年4月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 117 の問題A (God Sequence) ～問題C (Tricolor Pyramid) を解いてみた.

■感想.
1. 問題B, Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Regular Contest 117 解説の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int A, B;
    scanf("%d %d", &A, &B);
    
    // 2. 数列を計算.
    vi ans;
    if(A > B){
        rep(i, A)     ans.pb(i + 1);
        rep(i, B - 1) ans.pb(-i - 1);
        ans.pb(-(1 + A) * A / 2 + (B - 1) * B / 2);
    }
    if(A <= B){
        rep(i, B)     ans.pb(-i - 1);
        rep(i, A - 1) ans.pb(i + 1);
        ans.pb((1 + B) * B / 2 - (A - 1) * A / 2);
    }
    
    // 3. 出力.
    int l = ans.size();
    rep(i, l){
        printf("%d", ans[i]);
        printf("%s", (i < l - 1) ? " " : "\n");
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

#define pb push_back

int main(){

// 1. 入力情報.

int A, B;

scanf("%d %d", &A, &B);

// 2. 数列を計算.

vi ans;

if(A > B){

rep(i, A) ans.pb(i + 1);

rep(i, B - 1) ans.pb(-i - 1);

ans.pb(-(1 + A) * A / 2 + (B - 1) * B / 2);

}

if(A <= B){

rep(i, B) ans.pb(-i - 1);

rep(i, A - 1) ans.pb(i + 1);

ans.pb((1 + B) * B / 2 - (A - 1) * A / 2);

}

// 3. 出力.

int l = ans.size();

rep(i, l){

printf("%d", ans[i]);

printf("%s", (i < l - 1) ? " " : "\n");

}

return 0;

}

[入力例]
1 1

[出力例]
1001 -1001
※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
-1 1

[入力例]
1 4

[出力例]
-8 -6 -9 120 -97
※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
-1 -2 -3 -4 10

[入力例]
7 5

[出力例]
-8 -6 -9 120 -97
※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
1 2 3 4 5 6 7 -1 -2 -3 -4 -18

[入力例]
12 10

[出力例]
1 2 3 4 5 6 7 8 9 10 11 12 -1 -2 -3 -4 -5 -6 -7 -8 -9 -33

[入力例]

1 1

[出力例]

1001 -1001

※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

-1 1

[入力例]

1 4

[出力例]

-8 -6 -9 120 -97

※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

-1 -2 -3 -4 10

[入力例]

7 5

[出力例]

-8 -6 -9 120 -97

※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

1 2 3 4 5 6 7 -1 -2 -3 -4 -18

[入力例]

12 10

[出力例]

1 2 3 4 5 6 7 8 9 10 11 12 -1 -2 -3 -4 -5 -6 -7 -8 -9 -33

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

// 解き直し.
// https://atcoder.jp/contests/arc117/editorial/1111
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
LL a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. sort.
    sort(a, a + N);
    
    // 3. ビルの景観の数は？
    LL ans = a[0] + 1;
    rep(i, N - 1){
        ans *= (a[i + 1] - a[i] + 1);
        ans %= MOD;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc117/editorial/1111

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

const LL MOD = 1e9 + 7;

LL a[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld", &a[i]);

// 2. sort.

sort(a, a + N);

// 3. ビルの景観の数は？

LL ans = a[0] + 1;

rep(i, N - 1){

ans *= (a[i + 1] - a[i] + 1);

ans %= MOD;

}

// 4. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
2
1 2

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

[入力例]
6
5 3 4 1 5 2

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

[入力例]
7
314 159 265 358 979 323 846

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

[入力例]
12
5 103 20 90 40 24 11 70 121 54 21 32

[出力例]
672866091

[入力例]

1 2

[出力例]

※AtCoderのテストケースより

[入力例]

5 3 4 1 5 2

[出力例]

※AtCoderのテストケースより

[入力例]

314 159 265 358 979 323 846

[出力例]

492018656

※AtCoderのテストケースより

[入力例]

5 103 20 90 40 24 11 70 121 54 21 32

[出力例]

672866091

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

// 解き直し.
// https://atcoder.jp/contests/arc117/editorial/1113
// C++ (GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int LIMIT = 404040;
int a[LIMIT], b[LIMIT], f[LIMIT], g[LIMIT], combination[LIMIT];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    char c[404040];
    scanf("%s", c);
    
    // 2. f, g を 計算.
    b[0] = 1, g[0] = 1;
    repx(i, 1, N){
        int idx = 0, q = i;
        while(q % 3 == 0) q /= 3, idx++;
        a[i] = idx;
        b[i] = q;
    }
    rep(i, N - 1) f[i + 1] = f[i] + a[i + 1];
    rep(i, N - 1) g[i + 1] = g[i] * b[i + 1], g[i + 1] %= 3;
    rep(i, N){
        if(f[N - 1] - f[i] - f[N - 1 - i] == 0){
            if(g[N - 1] == 1){
                if(g[i] * g[N - 1 - i] == 1) combination[i] = 1;
                if(g[i] * g[N - 1 - i] == 2) combination[i] = 2;
                if(g[i] * g[N - 1 - i] == 4) combination[i] = 1;
            }
            if(g[N - 1] == 2){
                if(g[i] * g[N - 1 - i] == 1) combination[i] = 2;
                if(g[i] * g[N - 1 - i] == 2) combination[i] = 1;
                if(g[i] * g[N - 1 - i] == 4) combination[i] = 2;
            }
        }
    }
    
    // 3. 初期化.
    map<int, char> ans;
    ans[0] = 'R';
    ans[1] = 'W';
    ans[2] = 'B';
    
    // 4. 集計.
    int t = 0;
    rep(i, N){
        if(c[i] == 'R') t += 0 * combination[i];
        if(c[i] == 'W') t += 1 * combination[i];
        if(c[i] == 'B') t += 2 * combination[i];
        t %= 3;
    }
    if(!(N & 1)) t *= -1;
    t = (t + 3) % 3;
    
    // 5. 出力.
    printf("%c\n", ans[t]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc117/editorial/1113

// C++ (GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

const int LIMIT = 404040;

int a[LIMIT], b[LIMIT], f[LIMIT], g[LIMIT], combination[LIMIT];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

char c[404040];

scanf("%s", c);

// 2. f, g を計算.

b[0] = 1, g[0] = 1;

repx(i, 1, N){

int idx = 0, q = i;

while(q % 3 == 0) q /= 3, idx++;

a[i] = idx;

b[i] = q;

}

rep(i, N - 1) f[i + 1] = f[i] + a[i + 1];

rep(i, N - 1) g[i + 1] = g[i] * b[i + 1], g[i + 1] %= 3;

rep(i, N){

if(f[N - 1] - f[i] - f[N - 1 - i] == 0){

if(g[N - 1] == 1){

if(g[i] * g[N - 1 - i] == 1) combination[i] = 1;

if(g[i] * g[N - 1 - i] == 2) combination[i] = 2;

if(g[i] * g[N - 1 - i] == 4) combination[i] = 1;

}

if(g[N - 1] == 2){

if(g[i] * g[N - 1 - i] == 1) combination[i] = 2;

if(g[i] * g[N - 1 - i] == 2) combination[i] = 1;

if(g[i] * g[N - 1 - i] == 4) combination[i] = 2;

}

// 3. 初期化.

map<int, char> ans;

ans[0] = 'R';

ans[1] = 'W';

ans[2] = 'B';

// 4. 集計.

int t = 0;

rep(i, N){

if(c[i] == 'R') t += 0 * combination[i];

if(c[i] == 'W') t += 1 * combination[i];

if(c[i] == 'B') t += 2 * combination[i];

t %= 3;

}

if(!(N & 1)) t *= -1;

t = (t + 3) % 3;

// 5. 出力.

printf("%c\n", ans[t]);

return 0;

}

[入力例]
3
BWR

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

[入力例]
4
RRBB

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

[入力例]
6
BWWRBW

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

[入力例]
8
WWBRBBWB

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

[入力例]
21
BWBRRBBRWBRBBBRRBWWWR

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

[入力例]
50
BBRBRGBBBGBRGRRBBGRRGRBRGBRRRGBGRRBBRGBGGGBRGGBRBR

[出力例]
R

[入力例]
100
RGRBGGGGRRGBBRBBRRRBRBRBGGRGGRRGRRRRRBGRRBGRRRRGGRRGBGRBGRRBBRGRGBRRBBRRRRRGBRGGGBRBRRBBGRGRGBGBBRGB

[出力例]
B

[入力例]

BWR

[出力例]

※AtCoderのテストケースより

[入力例]

RRBB

[出力例]

※AtCoderのテストケースより

[入力例]

BWWRBW

[出力例]

※AtCoderのテストケースより

[入力例]

WWBRBBWB

[出力例]

※AtCoderのテストケースより

[入力例]

BWBRRBBRWBRBBBRRBWWWR

[出力例]

※AtCoderのテストケースより

[入力例]

BBRBRGBBBGBRGRRBBGRRGRBRGBRRRGBGRRBBRGBGGGBRGGBRBR

[出力例]

[入力例]

100

RGRBGGGGRRGBBRBBRRRBRBRBGGRGGRRGRRRRRBGRRBGRRRRGGRRGBGRBGRRBBRGRGBRRBBRRRRRGBRGGGBRBRRBBGRGRGBGBBRGB

[出力例]

■参照サイト
AtCoder Regular Contest 117

2021年4月27日2021年4月27日

Python（Qiskit）について（９）

概要

Qiskit について, QAOA のサンプルプログラムを動かしてみた.
動作環境は, Google Colaboratory で行った
実行プログラム, 解説は, 下記の参照サイトをご覧ください

感想

本家のサイトが詳しいので, 今後も, どのような機能が利用できるかを, 時間を見つけて, 進めていこうと思う.

QAOA(4頂点)

グラフ

[出力結果]
[[ 0. -5. -6.  0.]
 [-5.  0. -2.  5.]
 [-6. -2.  0.  4.]
 [ 0.  5.  4.  0.]]

[出力結果]

[[ 0. -5. -6. 0.]

[-5. 0. -2. 5.]

[-6. -2. 0. 4.]

[ 0. 5. 4. 0.]]

グラフ描画

グラフの分割(Brute Force)

[出力結果]
Objective value computed by the brute-force method is 3

1 2	[出力結果] Objective value computed by the brute-force method is 3

グラフの分割(QAOA)

[出力結果]
[1. 0. 1. 0.]
Objective value computed by QAOA is 3.0

[出力結果]

[1. 0. 1. 0.]

Objective value computed by QAOA is 3.0

グラフの分割(NumPyMinimumEigensolver)

[出力結果]
[0 0 1 1]
Objective value computed by the NumPyMinimumEigensolver is 3

[出力結果]

[0 0 1 1]

Objective value computed by the NumPyMinimumEigensolver is 3

グラフの分割(VQE)

[出力結果]
[0. 1. 0. 1.]
Objective value computed by VQE is 3.0

[出力結果]

[0. 1. 0. 1.]

Objective value computed by VQE is 3.0

QAOA(6頂点)

グラフ

[出力結果]
[[ 0. -5. -6.  0. -2.  5.]
 [-5.  0.  4.  5. -9.  7.]
 [-6.  4.  0.  5. -6.  0.]
 [ 0.  5.  5.  0.  4.  0.]
 [-2. -9. -6.  4.  0.  3.]
 [ 5.  7.  0.  0.  3.  0.]]

[出力結果]

[[ 0. -5. -6. 0. -2. 5.]

[-5. 0. 4. 5. -9. 7.]

[-6. 4. 0. 5. -6. 0.]

[ 0. 5. 5. 0. 4. 0.]

[-2. -9. -6. 4. 0. 3.]

[ 5. 7. 0. 0. 3. 0.]]

グラフ描画

グラフの分割(Brute Force)

[出力結果]
Objective value computed by the brute-force method is 6

1 2	[出力結果] Objective value computed by the brute-force method is 6

グラフの分割(QAOA)

[出力結果]
[1. 0. 0. 0. 1. 1.]
Objective value computed by QAOA is 6.0

[出力結果]

[1. 0. 0. 0. 1. 1.]

Objective value computed by QAOA is 6.0

グラフの分割(NumPyMinimumEigensolver)

[出力結果]
[0 0 1 1 1 0]
Objective value computed by the NumPyMinimumEigensolver is 6

[出力結果]

[0 0 1 1 1 0]

Objective value computed by the NumPyMinimumEigensolver is 6

グラフの分割(VQE)

[出力結果]
[1. 0. 0. 0. 1. 1.]
Objective value computed by VQE is 6.0

[出力結果]

[1. 0. 0. 0. 1. 1.]

Objective value computed by VQE is 6.0

QAOA(8頂点)

グラフ

[出力結果]
[[  0.  -7.  -9.   0.  -2.   8.   6.   7.]
 [ -7.   0. -14.  10.   8. -10.   0.   6.]
 [ -9. -14.   0.   0.   4.  -2.   0.  12.]
 [  0.  10.   0.   0.   8.   9.  14. -14.]
 [ -2.   8.   4.   8.   0. -10.  -6.   0.]
 [  8. -10.  -2.   9. -10.   0.   0.  13.]
 [  6.   0.   0.  14.  -6.   0.   0.  -2.]
 [  7.   6.  12. -14.   0.  13.  -2.   0.]]

[出力結果]

[[ 0. -7. -9. 0. -2. 8. 6. 7.]

[ -7. 0. -14. 10. 8. -10. 0. 6.]

[ -9. -14. 0. 0. 4. -2. 0. 12.]

[ 0. 10. 0. 0. 8. 9. 14. -14.]

[ -2. 8. 4. 8. 0. -10. -6. 0.]

[ 8. -10. -2. 9. -10. 0. 0. 13.]

[ 6. 0. 0. 14. -6. 0. 0. -2.]

[ 7. 6. 12. -14. 0. 13. -2. 0.]]

グラフ描画

グラフの分割(Brute Force)

[出力結果]
Objective value computed by the brute-force method is 11

1 2	[出力結果] Objective value computed by the brute-force method is 11

グラフの分割(QAOA)

[出力結果]
[1. 1. 1. 0. 0. 1. 0. 1.]
Objective value computed by QAOA is 9.0

[出力結果]

[1. 1. 1. 0. 0. 1. 0. 1.]

Objective value computed by QAOA is 9.0

グラフの分割(NumPyMinimumEigensolver)

[出力結果]
[1 1 1 0 0 0 0 1]
Objective value computed by the NumPyMinimumEigensolver is 11

[出力結果]

[1 1 1 0 0 0 0 1]

Objective value computed by the NumPyMinimumEigensolver is 11

グラフの分割(VQE)

[出力結果]
[1. 0. 1. 0. 1. 1. 0. 0.]
Objective value computed by VQE is 11.0

[出力結果]

[1. 0. 1. 0. 1. 1. 0. 0.]

Objective value computed by VQE is 11.0

	Brute Force	QAOA	NumPyMinimumEigensolver	VQE
4頂点	コスト: 3	分割結果: [1. 0. 1. 0.] コスト: 3.0	分割結果: [0 0 1 1] コスト: 3	分割結果: [0. 1. 0. 1.] コスト: 3.0
6頂点	コスト: 6	分割結果: [1. 0. 0. 0. 1. 1.] コスト: 6.0	分割結果: [0 0 1 1 1 0] コスト: 6	分割結果: [1. 0. 0. 0. 1. 1.] コスト: 6.0
8頂点	コスト: 11	分割結果: [1. 1. 1. 0. 0. 1. 0. 1.] コスト: 9.0 (※分割に失敗しているように見える)	分割結果: [1 1 1 0 0 0 0 1] コスト: 11	分割結果: [1. 0. 1. 0. 1. 1. 0. 0.] コスト: 11.0

参照サイト

Quantum Approximate Optimization Algorithm

2021年4月26日

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

C++の練習を兼ねて, AtCoder Grand Contest 035 の問題C (Skolem XOR Tree) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc035/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 2の冪乗 を用意.
    vector<int> cPow2;
    set<int> stPow2;
    cPow2.pb(1);
    stPow2.insert(1);
    while(cPow2.back() < 1e5){
        // 最大値を2倍.
        int p = 2 * cPow2.back();
        
        // 保存.
        cPow2.pb(p);
        stPow2.insert(p);
    }
    
    // 3. N が 2の冪乗 である場合.
    if(stPow2.count(N)){
        puts("No");
        return 0;
    }
    
    // 4. 辺を保存(※解説通り).
    set<P> ans;
    ans.insert({1, 2});
    ans.insert({2, 3});
    ans.insert({3, N + 1});
    ans.insert({N + 1, N + 2});
    ans.insert({N + 2, N + 3});
    repx(i, 4, N + 1){
        if(i == N && !(N & 1)) break;
        if(i & 1){
            ans.insert({N + 1, i});
            ans.insert({i - 1, i});
        }else{
            ans.insert({N + 1, N + i});
            ans.insert({N + i, N + i + 1});
        }
    }
    
    // 5. N が 偶数の場合.
    if(!(N & 1)){
        int mPow2 = 1;
        for(auto &p : cPow2){
            if(p < N) mPow2 = p;
            else      break;
        }
        int t = N ^ mPow2 ^ 1;
        if(!(t & 1)) t += N;
        ans.insert({t, N});
        ans.insert({mPow2 + N, N * 2});
    }
    
    // 6. 出力.
    puts("Yes");
    for(auto &p: ans) printf("%d %d\n", p.a, p.b);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 2の冪乗を用意.

vector<int> cPow2;

set<int> stPow2;

cPow2.pb(1);

stPow2.insert(1);

while(cPow2.back() < 1e5){

// 最大値を2倍.

int p = 2 * cPow2.back();

// 保存.

cPow2.pb(p);

stPow2.insert(p);

}

// 3. N が 2の冪乗である場合.

if(stPow2.count(N)){

puts("No");

return 0;

}

// 4. 辺を保存(※解説通り).

set ans;

ans.insert({1, 2});

ans.insert({2, 3});

ans.insert({3, N + 1});

ans.insert({N + 1, N + 2});

ans.insert({N + 2, N + 3});

repx(i, 4, N + 1){

if(i == N && !(N & 1)) break;

if(i & 1){

ans.insert({N + 1, i});

ans.insert({i - 1, i});

}else{

ans.insert({N + 1, N + i});

ans.insert({N + i, N + i + 1});

}

// 5. N が偶数の場合.

if(!(N & 1)){

int mPow2 = 1;

for(auto &p : cPow2){

if(p < N) mPow2 = p;

else break;

}

int t = N ^ mPow2 ^ 1;

if(!(t & 1)) t += N;

ans.insert({t, N});

ans.insert({mPow2 + N, N * 2});

}

// 6. 出力.

puts("Yes");

for(auto &p: ans) printf("%d %d\n", p.a, p.b);

return 0;

}

[入力例]
3

[出力例]
Yes
1 2
2 3
3 4
4 5
5 6
※AtCoderテストケースより

[入力例]
1

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

[入力例]
5

[出力例]
Yes
1 2
2 3
3 6
4 5
6 5
6 7
6 9
7 8
9 10

[入力例]
6

[出力例]
Yes
1 2
2 3
3 6
3 7
4 5
7 5
7 8
7 10
8 9
10 11
10 12

[入力例]
7

[出力例]
Yes
1 2
2 3
3 8
4 5
6 7
8 5
8 7
8 9
8 11
8 13
9 10
11 12
13 14

[入力例]
8

[出力例]
No

[入力例]
10

[出力例]
Yes
1 2
2 3
3 10
3 11
4 5
6 7
8 9
11 5
11 7
11 9
11 12
11 14
11 16
11 18
12 13
14 15
16 17
18 19
18 20

[入力例]
12

[出力例]
Yes
1 2
2 3
3 13
4 5
5 12
6 7
8 9
10 11
13 5
13 7
13 9
13 11
13 14
13 16
13 18
13 20
13 22
14 15
16 17
18 19
20 21
20 24
22 23

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

[入力例]

[出力例]

Yes

1 2

2 3

3 4

4 5

5 6

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

Yes

1 2

2 3

3 6

4 5

6 5

6 7

6 9

7 8

9 10

[入力例]

[出力例]

Yes

1 2

2 3

3 6

3 7

4 5

7 5

7 8

7 10

8 9

10 11

10 12

[入力例]

[出力例]

Yes

1 2

2 3

3 8

4 5

6 7

8 5

8 7

8 9

8 11

8 13

9 10

11 12

13 14

[入力例]

[出力例]

[入力例]

[出力例]

Yes

1 2

2 3

3 10

3 11

4 5

6 7

8 9

11 5

11 7

11 9

11 12

11 14

11 16

11 18

12 13

14 15

16 17

18 19

18 20

[入力例]

[出力例]

Yes

1 2

2 3

3 13

4 5

5 12

6 7

8 9

10 11

13 5

13 7

13 9

13 11

13 14

13 16

13 18

13 20

13 22

14 15

16 17

18 19

20 21

20 24

22 23

■参照サイト
AtCoder Grand Contest 035

2021年4月25日2021年4月25日

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

C++の練習を兼ねて, AtCoder Grand Contest 035 の問題A (XOR Circle) ～問題B (Even Degrees) を解いてみた.

■感想.
1. 問題A, Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 問題B は, 実装に苦労したものの, グラフに対する理解を深めることが出来た気がするので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
// 解き直し.
// https://img.atcoder.jp/agc035/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<int, int> m;
    rep(i, N){
        int a;
        scanf("%d", &a);
        m[a]++;
    }
    
    // 2. 判定.
    // 2-1. すべての帽子に書かれた数字が, 0.
    if(m.size() == 1 && m.count(0)){
        puts("Yes");
        return 0;
    }
    
    // 2-2. x が 書かれた帽子が, 2 * N / 3 枚, 0 が 書かれた帽子が, 1 * N / 3 枚.
    if(m.size() == 2 && N % 3 == 0){
        vector<int> v;
        for(auto &p : m) v.pb(p.a);
        if(v[0] == 0 && m[v[0]] == N / 3){
            puts("Yes");
            return 0;
        }
        if(v[1] == 0 && m[v[1]] == N / 3){
            puts("Yes");
            return 0;
        }
    }
    
    // 2-3. x ^ y ^ z = 0 の 書かれた帽子が, 1 * N / 3 枚ずつ.
    if(m.size() == 3 && N % 3 == 0){
        int xyz = 0;
        vector<int> v;
        for(auto &p : m) v.pb(p.a), xyz ^= p.a;
        if(xyz == 0 && m[v[0]] == N / 3 && m[v[1]] == N / 3 && m[v[2]] == N / 3){
            puts("Yes");
            return 0;
        }
    }
    
    // 2-4. それ以外.
    puts("No");
    return 0;
    
}

// C++(GCC 9.2.1)

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<int, int> m;

rep(i, N){

int a;

scanf("%d", &a);

m[a]++;

}

// 2. 判定.

// 2-1. すべての帽子に書かれた数字が, 0.

if(m.size() == 1 && m.count(0)){

puts("Yes");

return 0;

}

// 2-2. x が書かれた帽子が, 2 * N / 3 枚, 0 が書かれた帽子が, 1 * N / 3 枚.

if(m.size() == 2 && N % 3 == 0){

vector<int> v;

for(auto &p : m) v.pb(p.a);

if(v[0] == 0 && m[v[0]] == N / 3){

puts("Yes");

return 0;

}

if(v[1] == 0 && m[v[1]] == N / 3){

puts("Yes");

return 0;

}

// 2-3. x ^ y ^ z = 0 の書かれた帽子が, 1 * N / 3 枚ずつ.

if(m.size() == 3 && N % 3 == 0){

int xyz = 0;

vector<int> v;

for(auto &p : m) v.pb(p.a), xyz ^= p.a;

if(xyz == 0 && m[v[0]] == N / 3 && m[v[1]] == N / 3 && m[v[2]] == N / 3){

puts("Yes");

return 0;

}

// 2-4. それ以外.

puts("No");

return 0;

}

[入力例]
3
1 2 3

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

[入力例]
4
1 2 4 8

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

[入力例]
2
0 0

[出力例]
Yes

[入力例]
6
2 2 0 0 2 2

[出力例]
Yes

[入力例]
9
2 5 7 2 5 7 2 5 7

[出力例]
Yes

[入力例]

1 2 3

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 2 4 8

[出力例]

※AtCoderのテストケースより

[入力例]

0 0

[出力例]

Yes

[入力例]

2 2 0 0 2 2

[出力例]

Yes

[入力例]

2 5 7 2 5 7 2 5 7

[出力例]

Yes

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

// 解き直し.
// https://img.atcoder.jp/agc035/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
int oDegree[101010], p[101010];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    set<P> gEdges;
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
        
        // 辺を保存.
        gEdges.insert({a, b});
        gEdges.insert({b, a});
    }
    
    // 2. 辺数が奇数の場合.
    if(gEdges.size() % 4 != 0){
        puts("-1");
        return 0;
    }
    
    // 3. 適当な根付き全域木.
    vvi sTree(N);
    set<P> stEdges;
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 3-1. 空のキュー.
        queue<int> q;
        
        // 3-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 3-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 3-4. 取り出した要素を処理.
            for(auto &v : G[u]){
                // 3-5. 訪問済であれば, 処理をスキップ.
                if(d[v])            continue;
                if(!d[v] && v != s){
                    d[v] = d[u] + 1;
                    q.push(v);
                    
                    // グラフに反映.
                    sTree[u].pb(v);
                    sTree[v].pb(u);
                    
                    // 辺を保存.
                    stEdges.insert({u, v});
                    stEdges.insert({v, u});
                    
                    // 親頂点を保存.
                    p[v] = u;
                }
            }
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, 0, d);
    
    // 4. 根 から 遠い順 に並び替え.
    priority_queue<P> pq;
    rep(i, N) pq.push({d[i], i});
    
    // 5. 根付き全域木に含まれない辺について向きを付ける.
    set<P> ans;
    for(auto &e : gEdges){
        if(!stEdges.count(e)){
            if(!ans.count({e.a, e.b}) && !ans.count({e.b, e.a})){
                // 辺を保存.
                ans.insert(e);
                
                // 出次数を更新.
                oDegree[e.a]++;
            }
        }
    }
    
    // 6. ボトムアップで確定させていく.
    while(!pq.empty()){
        // 6-1. キューから取り出す.
        P cur = pq.top();
        pq.pop();
        
        // 6-2. 根に到達したら終了.
        int u = cur.b;
        if(u == 0) break;
        
        // 6-3. 子 -> 親.
        if(oDegree[u] & 1){
            // 辺を保存.
            ans.insert({u, p[u]});
            
            // 出次数を更新.
            oDegree[u]++;
            
            // 次へ.
            continue;
        }
        
        // 6-4. 親 -> 子.
        if(!(oDegree[u] & 1)){
            // 辺を保存.
            ans.insert({p[u], u});
            
            // 出次数を更新.
            oDegree[p[u]]++;
            
            // 次へ.
            continue;
        }
    }
    
    // 7. チェック.
    int odd = 0;
    rep(i, N) if(oDegree[i] & 1) odd++;
    assert(odd == 0);
    
    // 8. 出力.
    for(auto &p: ans) printf("%d %d\n", p.a + 1, p.b + 1);
    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

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

#define pb push_back

#define a first

#define b second

int oDegree[101010], p[101010];

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

set gEdges;

vvi G(N);

rep(i, M){

int a, b;

scanf("%d %d", &a, &b);

a--, b--;

G[a].pb(b);

G[b].pb(a);

// 辺を保存.

gEdges.insert({a, b});

gEdges.insert({b, a});

}

// 2. 辺数が奇数の場合.

if(gEdges.size() % 4 != 0){

puts("-1");

return 0;

}

// 3. 適当な根付き全域木.

vvi sTree(N);

set stEdges;

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](vvi &G, int s, int* d){

// 3-1. 空のキュー.

queue<int> q;

// 3-2. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 3-3. キューから取り出す.

int u = q.front();

q.pop();

// 3-4. 取り出した要素を処理.

for(auto &v : G[u]){

// 3-5. 訪問済であれば, 処理をスキップ.

if(d[v]) continue;

if(!d[v] && v != s){

d[v] = d[u] + 1;

q.push(v);

// グラフに反映.

sTree[u].pb(v);

sTree[v].pb(u);

// 辺を保存.

stEdges.insert({u, v});

stEdges.insert({v, u});

// 親頂点を保存.

p[v] = u;

}

return;

};

int d[N];

rep(i, N) d[i] = 0;

bfs(G, 0, d);

// 4. 根から遠い順に並び替え.

priority_queue pq;

rep(i, N) pq.push({d[i], i});

// 5. 根付き全域木に含まれない辺について向きを付ける.

set ans;

for(auto &e : gEdges){

if(!stEdges.count(e)){

if(!ans.count({e.a, e.b}) && !ans.count({e.b, e.a})){

// 辺を保存.

ans.insert(e);

// 出次数を更新.

oDegree[e.a]++;

}

// 6. ボトムアップで確定させていく.

while(!pq.empty()){

// 6-1. キューから取り出す.

P cur = pq.top();

pq.pop();

// 6-2. 根に到達したら終了.

int u = cur.b;

if(u == 0) break;

// 6-3. 子 -> 親.

if(oDegree[u] & 1){

// 辺を保存.

ans.insert({u, p[u]});

// 出次数を更新.

oDegree[u]++;

// 次へ.

continue;

}

// 6-4. 親 -> 子.

if(!(oDegree[u] & 1)){

// 辺を保存.

ans.insert({p[u], u});

// 出次数を更新.

oDegree[p[u]]++;

// 次へ.

continue;

}

// 7. チェック.

int odd = 0;

rep(i, N) if(oDegree[i] & 1) odd++;

assert(odd == 0);

// 8. 出力.

for(auto &p: ans) printf("%d %d\n", p.a + 1, p.b + 1);

return 0;

}

[入力例]
4 4
1 2
2 3
3 4
4 1

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

[入力例]
5 5
1 2
2 3
3 4
2 5
4 5

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

[入力例]
17 20
1 2
1 6
1 9
6 7
6 5
7 5
5 4
3 5
4 13
4 14
13 14
15 4
10 9
8 9
10 11
10 12
11 12
17 12
11 16
11 17

[出力例]
1 2
1 9
4 14
4 15
5 3
5 4
5 6
5 7
6 1
6 7
9 8
9 10
11 10
11 12
11 16
11 17
12 10
12 17
13 4
13 14

[入力例]
21 26
1 2
1 7
1 9
2 4
2 3
3 5
3 6
3 14
5 6
6 20
6 21
7 8
8 14
8 15
8 16
8 9
9 11
11 16
11 10
11 12
11 13
12 13
10 17
10 18
10 19
17 18

[出力例]
1 2
1 9
2 3
2 4
3 6
3 14
5 3
5 6
6 20
6 21
7 1
7 8
8 9
8 14
8 15
8 16
10 18
10 19
11 9
11 10
11 13
11 16
12 11
12 13
17 10
17 18

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

[入力例]

4 4

1 2

2 3

3 4

4 1

[出力例]

1 2

1 4

3 2

3 4

※AtCoderテストケースより

[入力例]

5 5

1 2

2 3

3 4

2 5

4 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

17 20

1 2

1 6

1 9

6 7

6 5

7 5

5 4

3 5

4 13

4 14

13 14

15 4

10 9

8 9

10 11

10 12

11 12

17 12

11 16

11 17

[出力例]

1 2

1 9

4 14

4 15

5 3

5 4

5 6

5 7

6 1

6 7

9 8

9 10

11 10

11 12

11 16

11 17

12 10

12 17

13 4

13 14

[入力例]

21 26

1 2

1 7

1 9

2 4

2 3

3 5

3 6

3 14

5 6

6 20

6 21

7 8

8 14

8 15

8 16

8 9

9 11

11 16

11 10

11 12

11 13

12 13

10 17

10 18

10 19

17 18

[出力例]

1 2

1 9

2 3

2 4

3 6

3 14

5 3

5 6

6 20

6 21

7 1

7 8

8 9

8 14

8 15

8 16

10 18

10 19

11 9

11 10

11 13

11 16

12 11

12 13

17 10

17 18

■参照サイト
AtCoder Grand Contest 035

2021年4月24日

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

C++の練習を兼ねて, AtCoder Grand Contest 027 の問題D (Modulo Matrix) を解いてみた.

■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc027/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int LIMIT = 101010;
const int MAX = 500;
LL a[LIMIT], c1[MAX][MAX], c2[MAX][MAX], ans[MAX][MAX];
set<LL> c[MAX][MAX];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 素数を用意.
    repx(i, 2, LIMIT){
        if(a[i]) continue;
        repex(j, i * 2, LIMIT, i) a[j]++;
    }
    vl p;
    repx(i, 2, LIMIT) if(!a[i] && p.size() < MAX * 2) p.pb((LL)i);
    
    // 3. 市松模様を敷き詰める.
    rep(i, MAX){
        // 3-1. 左上 -> 右下.
        int b = 2 * i;
        rep(j, b + 1){
            int r = j;
            int c = b - j;
            if(r >= 0 && r < MAX && c >= 0 && c < MAX) c1[r][c] = p[i];
        }
        
        // 3-2. 右上 -> 左下.
        rep(j, b + 1){
            int r = j;
            int c = MAX - b + j;
            if(r >= 0 && r < MAX && c >= 0 && c < MAX) c2[r][c] = p[i + MAX];
        }
    }
    
    // 4. 素数部分を確定させる.
    rep(i, MAX){
        rep(j, MAX){
            ans[i][j] = c1[i][j] * c2[i][j];
            c[i][j].insert(c1[i][j]);
            c[i][j].insert(c2[i][j]);
        }
    }
    
    // 5. 未確定部分を敷き詰める.
    // -> 1e15 制約に注意.
    rep(i, MAX){
        rep(j, MAX){
            // 5-1. すでに確定している場合は, Skip.
            if(ans[i][j]) continue;
            
            // 5-2. 上下左右を取得.
            set<LL> st;
            if(i)           for(auto &q : c[i - 1][j]) st.insert(q);
            if(i < MAX - 1) for(auto &q : c[i + 1][j]) st.insert(q);
            if(j)           for(auto &q : c[i][j - 1]) st.insert(q);
            if(j < MAX - 1) for(auto &q : c[i][j + 1]) st.insert(q);
            
            // 5-3. 最小公倍数.
            LL lcd = 1LL;
            for(auto &q : st) lcd *= q;
            assert(lcd <= 1e15);
            
            // 5-4. 値を設定.
            ans[i][j] = ++lcd;
        }
    }
    
    // 6. すべて異なっているかチェック.
    set<LL> st;
    rep(i, MAX) rep(j, MAX) st.insert(ans[i][j]);
    assert(st.size() == MAX * MAX);
    
    // 7. 出力.
    rep(i, N){
        rep(j, N){
            printf("%lld", ans[i][j]);
            printf("%s", (j < N - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

#define pb push_back

const int LIMIT = 101010;

const int MAX = 500;

LL a[LIMIT], c1[MAX][MAX], c2[MAX][MAX], ans[MAX][MAX];

set<LL> c[MAX][MAX];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 素数を用意.

repx(i, 2, LIMIT){

if(a[i]) continue;

repex(j, i * 2, LIMIT, i) a[j]++;

}

vl p;

repx(i, 2, LIMIT) if(!a[i] && p.size() < MAX * 2) p.pb((LL)i);

// 3. 市松模様を敷き詰める.

rep(i, MAX){

// 3-1. 左上 -> 右下.

int b = 2 * i;

rep(j, b + 1){

int r = j;

int c = b - j;

if(r >= 0 && r < MAX && c >= 0 && c < MAX) c1[r][c] = p[i];

}

// 3-2. 右上 -> 左下.

rep(j, b + 1){

int r = j;

int c = MAX - b + j;

if(r >= 0 && r < MAX && c >= 0 && c < MAX) c2[r][c] = p[i + MAX];

}

// 4. 素数部分を確定させる.

rep(i, MAX){

rep(j, MAX){

ans[i][j] = c1[i][j] * c2[i][j];

c[i][j].insert(c1[i][j]);

c[i][j].insert(c2[i][j]);

}

// 5. 未確定部分を敷き詰める.

// -> 1e15 制約に注意.

rep(i, MAX){

rep(j, MAX){

// 5-1. すでに確定している場合は, Skip.

if(ans[i][j]) continue;

// 5-2. 上下左右を取得.

set<LL> st;

if(i) for(auto &q : c[i - 1][j]) st.insert(q);

if(i < MAX - 1) for(auto &q : c[i + 1][j]) st.insert(q);

if(j) for(auto &q : c[i][j - 1]) st.insert(q);

if(j < MAX - 1) for(auto &q : c[i][j + 1]) st.insert(q);

// 5-3. 最小公倍数.

LL lcd = 1LL;

for(auto &q : st) lcd *= q;

assert(lcd <= 1e15);

// 5-4. 値を設定.

ans[i][j] = ++lcd;

}

// 6. すべて異なっているかチェック.

set<LL> st;

rep(i, MAX) rep(j, MAX) st.insert(ans[i][j]);

assert(st.size() == MAX * MAX);

// 7. 出力.

rep(i, N){

rep(j, N){

printf("%lld", ans[i][j]);

printf("%s", (j < N - 1) ? " " : "\n");

}

return 0;

}

[入力例]
2

[出力例]
4 7
23 10
※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の値が出力される.
11402 194734759
195350467 17103

[入力例]
3

[出力例]
11402 194734759 17079
195350467 17103 486836896
17133 488376166 28505

[入力例]
4

[出力例]
11402 194734759 17079 485812156
195350467 17103 486836896 28465
17133 488376166 28505 1135952756
489746806 28555 1139544386 39907

[入力例]
5

[出力例]
11402 194734759 17079 485812156 28445
195350467 17103 486836896 28465 1133561696
17133 488376166 28505 1135952756 39851
489746806 28555 1139544386 39907 2499096062
28585 1142742546 39977 2506997648 62711

[入力例]

[出力例]

4 7

23 10

※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の値が出力される.

11402 194734759

195350467 17103

[入力例]

[出力例]

11402 194734759 17079

195350467 17103 486836896

17133 488376166 28505

[入力例]

[出力例]

11402 194734759 17079 485812156

195350467 17103 486836896 28465

17133 488376166 28505 1135952756

489746806 28555 1139544386 39907

[入力例]

[出力例]

11402 194734759 17079 485812156 28445

195350467 17103 486836896 28465 1133561696

17133 488376166 28505 1135952756 39851

489746806 28555 1139544386 39907 2499096062

28585 1142742546 39977 2506997648 62711

■参照サイト
AtCoder Grand Contest 027

C++の練習を兼ねて, 競プロ典型 90 問 の 問題034 (There are few types of elements) を解いてみた.

概要

感想

量子ビット状態を表現する(練習問題(パターン①))

量子ビット状態を表現する(練習問題(パターン②))

量子ビット状態を表現する(練習問題(パターン③))

量子ビット状態を表現する(練習問題(パターン④))

量子ビット状態を表現する(練習問題(パターン⑤))

参照サイト

C++の練習を兼ねて, AtCoder Regular Contest 088 の 問題F (Christmas Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 036 の 問題B (Do Not Duplicate) を解いてみた.

C++の練習を兼ねて, ZONeエナジー プログラミングコンテスト “HELLO SPACE” の 問題C (MAD TEAM) ～ 問題D (宇宙人からのメッセージ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 117 の 問題A (God Sequence) ～ 問題C (Tricolor Pyramid) を解いてみた.

概要

感想

QAOA(4頂点)

QAOA(6頂点)

QAOA(8頂点)

参照サイト

C++の練習を兼ねて, AtCoder Grand Contest 035 の 問題C (Skolem XOR Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 035 の 問題A (XOR Circle) ～ 問題B (Even Degrees) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 027 の 問題D (Modulo Matrix) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題034 (There are few types of elements) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 088 の問題F (Christmas Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 036 の問題B (Do Not Duplicate) を解いてみた.

C++の練習を兼ねて, ZONeエナジープログラミングコンテスト “HELLO SPACE” の問題C (MAD TEAM) ～問題D (宇宙人からのメッセージ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 117 の問題A (God Sequence) ～問題C (Tricolor Pyramid) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 035 の問題C (Skolem XOR Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 035 の問題A (XOR Circle) ～問題B (Even Degrees) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 027 の問題D (Modulo Matrix) を解いてみた.