個人用メモ帳

2021年3月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 115 の問題C (ℕ Coloring) を解いてみた.

■感想.
1. 規則性が抽出出来たので, 久しぶりに, 解答見る前に, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■C++版プログラム(問題C／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 ans[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. i の 小さい順に, 数列を更新.
    rep(i, 101010) ans[i] = 1;
    repx(i, 1, N + 1) repex(j, i * 2, N + 1, i) if(ans[i] == ans[j]) ans[j]++;
    
    // 3. 出力.
    repx(i, 1, N + 1){
        printf("%d", ans[i]);
        printf("%s", (i < N) ? " " : "\n");
    }
    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 ans[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. i の小さい順に, 数列を更新.

rep(i, 101010) ans[i] = 1;

repx(i, 1, N + 1) repex(j, i * 2, N + 1, i) if(ans[i] == ans[j]) ans[j]++;

// 3. 出力.

repx(i, 1, N + 1){

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

printf("%s", (i < N) ? " " : "\n");

}

return 0;

}

[入力例]
4

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

[入力例]
7

[出力例]
1 2 2 3 2 3 2

[入力例]
77

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

[入力例]
777

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

[入力例]

[出力例]

1 2 2 3

※AtCoderのテストケースより

[入力例]

[出力例]

1 2 2 3 2 3 2

[入力例]

[出力例]

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

[入力例]

777

[出力例]

1 2 2 3 2 3 2 4 3 3 2 4 2 3 3 5 2 4 2 4 3 3 2 5 3 3 4 4 2 4 2 6 3 3 3 5 2 3 3 5 2 4 2 4 4 3 2 6 3 4 3 4 2 5 3 5 3 3 2 5 2 3 4 7 3 4 2 4 3 4 2 6 2 3 4 4 3 4 2 6 5 3 2 5 3 3 3 5 2 5 3 4 3 3 3 7 2 4 4 5 2 4 2 5 4 3 2 6 2 4 3 6 2 4 3 4 4 3 3 6 3 3 3 4 4 5 2 8 3 4 2 5 3 3 5 5 2 4 2 5 3 3 3 7 3 3 4 4 2 5 2 5 4 4 3 5 2 3 3 7 3 6 2 4 4 3 2 6 3 4 4 4 2 4 4 6 3 3 2 6 2 4 3 5 3 4 3 4 5 4 2 8 2 3 4 5 2 5 2 6 3 3 3 5 3 3 4 6 3 5 2 4 3 3 3 7 3 3 3 5 3 4 2 7 5 3 2 5 2 4 4 5 2 5 3 4 3 4 2 7 2 4 6 4 4 4 3 5 3 5 2 6 3 3 4 9 2 4 3 5 4 3 2 6 3 4 3 4 2 6 2 6 4 3 4 5 2 3 4 6 2 4 2 4 4 4 3 8 3 4 3 4 2 5 3 5 5 3 3 6 3 3 3 6 3 5 2 5 3 4 2 6 2 3 5 4 2 4 3 8 3 4 3 7 4 3 3 5 3 5 2 4 4 3 3 7 2 4 3 5 3 5 4 5 4 3 2 5 2 5 5 7 2 4 3 4 4 3 2 7 3 3 4 5 3 4 2 6 4 4 3 5 2 4 5 5 3 6 2 5 3 3 2 9 4 3 4 4 2 5 3 6 3 3 3 6 2 3 4 7 2 4 3 4 6 4 3 6 2 4 3 4 3 5 3 7 3 4 2 6 2 3 4 5 4 4 3 4 4 4 2 8 2 4 4 4 3 4 2 6 5 4 2 5 3 3 3 8 2 6 3 4 3 3 4 6 2 3 5 5 2 5 2 6 4 3 2 6 3 4 3 5 3 4 4 5 4 3 2 8 3 3 4 5 3 7 2 5 3 5 2 5 3 4 5 6 3 4 2 6 3 3 2 7 3 4 4 4 2 5 3 10 5 3 3 5 3 4 3 6 2 5 2 4 5 3 3 7 3 4 4 5 3 4 3 5 3 3 4 7 2 3 3 7 3 5 2 4 4 5 3 6 3 3 4 4 2 5 3 7 4 3 2 5 3 3 6 5 2 5 2 5 3 4 4 9 2 4 3 5 3 4 3 5 5 3 2 6 3 4 3 6 2 6 4 4 3 4 2 7 2 4 4 4 4 4 2 7 4 4 3 6 2 3 4 6 2 4 2 5 5 3 3 7 5 3 4 4 3 6 2 5 3 3 3 5 4 4 4 9 2 4 2 5 4 4 2 8 3 5 4 4 2 4 3 6 4 4 2 6 2 3 4 5 4 5 3 4 3 4 3 8 2 3 6 5 2 4 3 6 3 4 2 6 3 5 3 6 3 5 2 4 5 3 3 6 3 3 3 6 2 6 3 8 4 3 3 5 2 4 4 5 3 5 4 4 3 3 2 8 3 4 3 4 4 5 2 6 7 4 3 5 2 3 5 7 3 5 2 5 4 4 2 6 3 3 4 5 3 6 2 6 3 4 3 7 2 3 4 6 2 4 3 4 5 3 3 10 2 5 3 4 2 5 4 5 4

■参照サイト
AtCoder Regular Contest 115

2021年3月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 115 の問題A (Two Choices) ～問題B (Plus Matrix) を解いてみた.

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

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

// 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--)

int main(){
    
    // 1. 入力情報.
    int N, M;
    LL odd = 0, even = 0;
    scanf("%d %d", &N, &M);
    rep(i, N){
        int one = 0;
        char c[22];
        scanf("%s", &c);
        rep(j, M) if(c[j] == '1') one++;
        if(one & 1) odd++;
        else        even++;
    }
    
    // 2. 出力.
    printf("%lld\n", odd * even);
    return 0;
    
}

// 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--)

int main(){

// 1. 入力情報.

int N, M;

LL odd = 0, even = 0;

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

rep(i, N){

int one = 0;

char c[22];

scanf("%s", &c);

rep(j, M) if(c[j] == '1') one++;

if(one & 1) odd++;

else even++;

}

// 2. 出力.

printf("%lld\n", odd * even);

return 0;

}

[入力例]
3 2
00
01
10

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

[入力例]
7 5
10101
00001
00110
11110
00100
11111
10000

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

[入力例]
10 6
000110
001110
100111
011000
100110
100011
011001
001001
100010
101010

[出力例]
25

[入力例]
50 10
0001100101
0011101000
1001110111
0110001011
1001100011
1000110101
0110011100
0010011111
1000100000
1010101111
0101010000
0010110100
1100011010
0000101101
1010101110
0000010010
1110011001
1111001101
0000001011
0001011010
1001100011
1110110111
0101010001
0010110011
0001100001
0110100000
1101001100
1010010100
1110001100
1110100110
0100000000
0110110000
0011101110
0001101110
0101001111
0001101100
0101100111
1110001100
1011001000
1111111001
1011111010
0101111011
1010011011
1001010110
1010110011
0101111110
0000001111
0110001111
0101100110
0011111100

[出力例]
624

[入力例]

3 2

[出力例]

※AtCoderのテストケースより

[入力例]

7 5

10101

00001

00110

11110

00100

11111

10000

[出力例]

※AtCoderのテストケースより

[入力例]

10 6

000110

001110

100111

011000

100110

100011

011001

001001

100010

101010

[出力例]

[入力例]

50 10

0001100101

0011101000

1001110111

0110001011

1001100011

1000110101

0110011100

0010011111

1000100000

1010101111

0101010000

0010110100

1100011010

0000101101

1010101110

0000010010

1110011001

1111001101

0000001011

0001011010

1001100011

1110110111

0101010001

0010110011

0001100001

0110100000

1101001100

1010010100

1110001100

1110100110

0100000000

0110110000

0011101110

0001101110

0101001111

0001101100

0101100111

1110001100

1011001000

1111111001

1011111010

0101111011

1010011011

1001010110

1010110011

0101111110

0000001111

0110001111

0101100110

0011111100

[出力例]

624

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

// 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--)
LL C[505][505], ka[505], kb[505], A[505], B[505];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) rep(j, N) scanf("%lld", &C[i][j]);
    
    // 2. 行方向.
    bool rOk = true;
    rep(i, N - 1){
        // (i + 1)行目 マイナス i行目.
        LL a = C[i + 1][0] - C[i][0];
        repx(j, 1, N) if(a != C[i + 1][j] - C[i][j]) rOk = false;
        
        // 条件を満たす場合は, 保存.
        if(rOk) ka[i] = a;
        else    break;
    }
    
    // 3. 列方向.
    bool cOk = true;
    rep(j, N - 1){
        // (j + 1)列目 マイナス j列目.
        LL b = C[0][j + 1] - C[0][j];
        repx(i, 1, N) if(b != C[i][j + 1] - C[i][j]) cOk = false;
        
        // 条件を満たす場合は, 保存.
        if(cOk) kb[j] = b;
        else    break;
    }
    
    // 4. 条件を満たさない場合は, 終了.
    if(!rOk || !cOk){
        puts("No");
        return 0;
    }
    
    // 5. 条件を満たす場合.
    // 5-1. A を 計算.
    LL minA = A[0];
    rep(i, N - 1) A[i + 1] = A[i] + ka[i], minA = min(minA, A[i + 1]);
    
    // 5-2. minA が マイナスの場合, 加算.
    if(minA < 0) rep(i, N) A[i] -= minA;
    
    // 5-3. B を 計算.
    LL minB = B[0];
    rep(i, N - 1) B[i + 1] = B[i] + kb[i], minB = min(minB, B[i + 1]);
    
    // 5-4. minB が マイナスの場合, 加算.
    if(minB < 0) rep(i, N) B[i] -= minB;
    
    // 5-5. C[0][0] と 比較し, 差分 を 加算.
    LL kc = C[0][0] - A[0] - B[0];
    if(kc > 0) rep(i, N) B[i] += kc;
    
    // 6. 出力.
    puts("Yes");
    rep(i, N){
        printf("%lld", A[i]);
        printf("%s", (i < N - 1) ? " " : "\n");
    }
    rep(i, N){
        printf("%lld", B[i]);
        printf("%s", (i < N - 1) ? " " : "\n");
    }
    return 0;
    
}

// 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--)

LL C[505][505], ka[505], kb[505], A[505], B[505];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 行方向.

bool rOk = true;

rep(i, N - 1){

// (i + 1)行目マイナス i行目.

LL a = C[i + 1][0] - C[i][0];

repx(j, 1, N) if(a != C[i + 1][j] - C[i][j]) rOk = false;

// 条件を満たす場合は, 保存.

if(rOk) ka[i] = a;

else break;

}

// 3. 列方向.

bool cOk = true;

rep(j, N - 1){

// (j + 1)列目マイナス j列目.

LL b = C[0][j + 1] - C[0][j];

repx(i, 1, N) if(b != C[i][j + 1] - C[i][j]) cOk = false;

// 条件を満たす場合は, 保存.

if(cOk) kb[j] = b;

else break;

}

// 4. 条件を満たさない場合は, 終了.

if(!rOk || !cOk){

puts("No");

return 0;

}

// 5. 条件を満たす場合.

// 5-1. A を計算.

LL minA = A[0];

rep(i, N - 1) A[i + 1] = A[i] + ka[i], minA = min(minA, A[i + 1]);

// 5-2. minA がマイナスの場合, 加算.

if(minA < 0) rep(i, N) A[i] -= minA;

// 5-3. B を計算.

LL minB = B[0];

rep(i, N - 1) B[i + 1] = B[i] + kb[i], minB = min(minB, B[i + 1]);

// 5-4. minB がマイナスの場合, 加算.

if(minB < 0) rep(i, N) B[i] -= minB;

// 5-5. C[0][0] と比較し, 差分を加算.

LL kc = C[0][0] - A[0] - B[0];

if(kc > 0) rep(i, N) B[i] += kc;

// 6. 出力.

puts("Yes");

rep(i, N){

printf("%lld", A[i]);

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

}

rep(i, N){

printf("%lld", B[i]);

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

}

return 0;

}

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

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

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

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

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

[出力例]
Yes
1 8 5 3 0
5 11 4 7 10

[入力例]

4 3 5

2 1 3

3 2 4

[出力例]

Yes

2 0 1

2 1 3

※AtCoderのテストケースより

[入力例]

4 3 5

2 2 3

3 2 4

[出力例]

※AtCoderのテストケースより

[入力例]

6 12 5 8 11

13 19 12 15 18

10 16 9 12 15

8 14 7 10 13

5 11 4 7 10

[出力例]

Yes

1 8 5 3 0

5 11 4 7 10

■参照サイト
AtCoder Regular Contest 115

2021年3月23日

Python（Cirq）について（１５）

概要

Cirq について, Optimizers, Decompositions に関するサンプルをいくつか動かしてみた.
動作環境は, Google Colaboratory で行った

感想

量子物理学に関する知識(用語, 数式の意味ほか)は, 徐々に身につけていく必要があると感じた.
時間を見つけて, 今後も, ドキュメントの残りの部分を進めていこうと思う.

Circuit optimizers

Momentの個数を削減することが出来る場合があるとのこと

Circuit optimizers を使うサンプル

[編集内容(Circuit optimizers)]
import cirq

# Moment の 個数 を 削減できるケース.
c = cirq.Circuit()
c.append(cirq.Moment([]))
c.append(cirq.Moment([cirq.X(cirq.GridQubit(1, 1))]))
c.append(cirq.Moment([]))
print(f'Before optimization, Circuit has {len(c)} moments')

cirq.DropEmptyMoments().optimize_circuit(circuit=c)
print(f'After optimization, Circuit has {len(c)} moments')

[編集内容(Circuit optimizers)]

import cirq

# Moment の個数を削減できるケース.

c = cirq.Circuit()

c.append(cirq.Moment([]))

c.append(cirq.Moment([cirq.X(cirq.GridQubit(1, 1))]))

c.append(cirq.Moment([]))

print(f'Before optimization, Circuit has {len(c)} moments')

cirq.DropEmptyMoments().optimize_circuit(circuit=c)

print(f'After optimization, Circuit has {len(c)} moments')

[出力結果]
Before optimization, Circuit has 3 moments
After optimization, Circuit has 1 moments

[出力結果]

Before optimization, Circuit has 3 moments

After optimization, Circuit has 1 moments

Circuit optimizers を使うサンプル

[編集内容(Circuit optimizers)]
import cirq

# Moment の 個数 を 削減できないケース.
c = cirq.Circuit()

q0, q1 = cirq.GridQubit(0, 0), cirq.GridQubit(0, 1)

c.append(cirq.Moment(cirq.SWAP(q0, q1)))
c.append(cirq.Moment(cirq.SWAP(q0, q1)))
c.append(cirq.Moment(cirq.SWAP(q0, q1)))
print(f'Before optimization, Circuit has {len(c)} moments')

cirq.DropEmptyMoments().optimize_circuit(circuit=c)
print(f'After optimization, Circuit has {len(c)} moments')

[編集内容(Circuit optimizers)]

import cirq

# Moment の個数を削減できないケース.

c = cirq.Circuit()

q0, q1 = cirq.GridQubit(0, 0), cirq.GridQubit(0, 1)

c.append(cirq.Moment(cirq.SWAP(q0, q1)))

print(f'Before optimization, Circuit has {len(c)} moments')

cirq.DropEmptyMoments().optimize_circuit(circuit=c)

print(f'After optimization, Circuit has {len(c)} moments')

[出力結果]
Before optimization, Circuit has 3 moments
After optimization, Circuit has 3 moments

[出力結果]

Before optimization, Circuit has 3 moments

After optimization, Circuit has 3 moments

Circuit optimizers を使うサンプル

[編集内容(Circuit optimizers)]
import cirq

# Moment の 個数 を 削減できるケース.
c = cirq.Circuit()

c.append(cirq.SWAP(q, q + 1) for q in cirq.LineQubit.range(3))
c.append([cirq.Moment()])
c.append([cirq.Moment()])
print(f'Before optimization, Circuit has {len(c)} moments')

cirq.DropEmptyMoments().optimize_circuit(circuit=c)
print(f'After optimization, Circuit has {len(c)} moments')

[編集内容(Circuit optimizers)]

import cirq

# Moment の個数を削減できるケース.

c = cirq.Circuit()

c.append(cirq.SWAP(q, q + 1) for q in cirq.LineQubit.range(3))

c.append([cirq.Moment()])

print(f'Before optimization, Circuit has {len(c)} moments')

cirq.DropEmptyMoments().optimize_circuit(circuit=c)

print(f'After optimization, Circuit has {len(c)} moments')

[出力結果]
Before optimization, Circuit has 5 moments
After optimization, Circuit has 3 moments

[出力結果]

Before optimization, Circuit has 5 moments

After optimization, Circuit has 3 moments

Decompositions

量子回路を変形することができる

Decompositions を使うサンプル

[編集内容(Decompositions)]
import cirq

c1, c2 = cirq.Circuit(), cirq.Circuit()

q0 = cirq.GridQubit(0, 0)

c1.append(cirq.H(q0))
print('Before Decompositions:\n', c1)

c2.append(cirq.H(q0))
print('After Decompositions:\n', cirq.Circuit(cirq.decompose(c2)))

[編集内容(Decompositions)]

import cirq

c1, c2 = cirq.Circuit(), cirq.Circuit()

q0 = cirq.GridQubit(0, 0)

c1.append(cirq.H(q0))

print('Before Decompositions:\n', c1)

c2.append(cirq.H(q0))

print('After Decompositions:\n', cirq.Circuit(cirq.decompose(c2)))

[出力結果]
Before Decompositions:
 (0, 0): ───H───
After Decompositions:
 (0, 0): ───Y^0.5───X───

[出力結果]

Before Decompositions:

(0, 0): ───H───

After Decompositions:

(0, 0): ───Y^0.5───X───

Decompositions を使うサンプル

[編集内容(Decompositions)]
import cirq

c1, c2 = cirq.Circuit(), cirq.Circuit()

q0, q1 = cirq.GridQubit(0, 0), cirq.GridQubit(0, 1)

c1.append(cirq.X(q0))
c1.append(cirq.CNOT(q0, q1))
print('Before Decompositions:\n', c1)

c2.append(cirq.X(q0))
c2.append(cirq.CNOT(q0, q1))
print('After Decompositions:\n', cirq.Circuit(cirq.decompose(c2)))

[編集内容(Decompositions)]

import cirq

c1, c2 = cirq.Circuit(), cirq.Circuit()

q0, q1 = cirq.GridQubit(0, 0), cirq.GridQubit(0, 1)

c1.append(cirq.X(q0))

c1.append(cirq.CNOT(q0, q1))

print('Before Decompositions:\n', c1)

c2.append(cirq.X(q0))

c2.append(cirq.CNOT(q0, q1))

print('After Decompositions:\n', cirq.Circuit(cirq.decompose(c2)))

[出力結果]
Before Decompositions:
 (0, 0): ───X───@───
               │
(0, 1): ───────X───
After Decompositions:
 (0, 0): ───X────────@───────────
                    │
(0, 1): ───Y^-0.5───@───Y^0.5───

[出力結果]

Before Decompositions:

(0, 0): ───X───@───

│

(0, 1): ───────X───

After Decompositions:

(0, 0): ───X────────@───────────

│

(0, 1): ───Y^-0.5───@───Y^0.5───

Decompositions を使うサンプル

[編集内容(Decompositions)]
import cirq

c1, c2 = cirq.Circuit(), cirq.Circuit()

q0, q1, q2 = cirq.GridQubit(0, 0), cirq.GridQubit(0, 1), cirq.GridQubit(0, 2)

c1.append(cirq.X(q0))
c1.append(cirq.X(q1))
c1.append(cirq.CCNOT(q0, q1, q2))
print('Before Decompositions:\n', c1)

c2.append(cirq.X(q0))
c2.append(cirq.X(q1))
c2.append(cirq.CCNOT(q0, q1, q2))
print('After Decompositions:\n', cirq.Circuit(cirq.decompose(c2)))

[編集内容(Decompositions)]

import cirq

c1, c2 = cirq.Circuit(), cirq.Circuit()

q0, q1, q2 = cirq.GridQubit(0, 0), cirq.GridQubit(0, 1), cirq.GridQubit(0, 2)

c1.append(cirq.X(q0))

c1.append(cirq.X(q1))

c1.append(cirq.CCNOT(q0, q1, q2))

print('Before Decompositions:\n', c1)

c2.append(cirq.X(q0))

c2.append(cirq.X(q1))

c2.append(cirq.CCNOT(q0, q1, q2))

print('After Decompositions:\n', cirq.Circuit(cirq.decompose(c2)))

[出力結果]
Before Decompositions:
 (0, 0): ───X───@───
               │
(0, 1): ───X───@───
               │
(0, 2): ───────X───
After Decompositions:
 (0, 0): ───X───────T────────────@─────────────────────────────────────@─────────────────────────────@────────────────────────────@───────────────────────────────────────
                                │                                     │                             │                            │
(0, 1): ───X───────T───Y^-0.5───@────────Y^0.5───@───T^-1────Y^-0.5───@────────Y^0.5───@───Y^-0.5───@──────Y^0.5────@───Y^-0.5───@──────Y^0.5────@───────────────────────
                                                 │                                     │                            │                            │
(0, 2): ───Y^0.5───X───T────────Y^-0.5───────────@───Y^0.5───T────────Y^-0.5───────────@───Y^0.5────T^-1───Y^-0.5───@───Y^0.5────T^-1───Y^-0.5───@───Y^0.5───Y^0.5───X───

[出力結果]

Before Decompositions:

(0, 0): ───X───@───

│

(0, 1): ───X───@───

│

(0, 2): ───────X───

After Decompositions:

(0, 0): ───X───────T────────────@─────────────────────────────────────@─────────────────────────────@────────────────────────────@───────────────────────────────────────

│ │ │ │

(0, 1): ───X───────T───Y^-0.5───@────────Y^0.5───@───T^-1────Y^-0.5───@────────Y^0.5───@───Y^-0.5───@──────Y^0.5────@───Y^-0.5───@──────Y^0.5────@───────────────────────

│ │ │ │

(0, 2): ───Y^0.5───X───T────────Y^-0.5───────────@───Y^0.5───T────────Y^-0.5───────────@───Y^0.5────T^-1───Y^-0.5───@───Y^0.5────T^-1───Y^-0.5───@───Y^0.5───Y^0.5───X───

Create your own optimizers

例えば, 測定を後から外すことも出来るとのこと

Create your own optimizers を使うサンプル

[編集内容(Create your own optimizers)]
import cirq

class RemoveMeasurements(cirq.PointOptimizer):
    def optimization_at(self, circuit: cirq.Circuit, index: int, op: cirq.Operation):
      if isinstance(op.gate, cirq.MeasurementGate):
        return cirq.PointOptimizationSummary(clear_span=1,
                                             new_operations=[],
                                             clear_qubits=op.qubits)
      else:
        return None

q0, q1, q2 = cirq.LineQubit(0), cirq.LineQubit(1), cirq.LineQubit(2)
c = cirq.Circuit()
c.append(cirq.X(q0))
c.append(cirq.X(q1))
c.append(cirq.CCNOT(q0, q1, q2))
c.append(cirq.CSWAP(q1, q2, q0))
c.append(cirq.measure(q0, key='result 0'))
c.append(cirq.measure(q1, key='result 1'))
c.append(cirq.measure(q2, key='result 2'))
print('Before optimization')
print(c)
RemoveMeasurements().optimize_circuit(c)
print('After optimization')
print(c)

[編集内容(Create your own optimizers)]

import cirq

class RemoveMeasurements(cirq.PointOptimizer):

def optimization_at(self, circuit: cirq.Circuit, index: int, op: cirq.Operation):

if isinstance(op.gate, cirq.MeasurementGate):

return cirq.PointOptimizationSummary(clear_span=1,

new_operations=[],

clear_qubits=op.qubits)

else:

return None

q0, q1, q2 = cirq.LineQubit(0), cirq.LineQubit(1), cirq.LineQubit(2)

c = cirq.Circuit()

c.append(cirq.X(q0))

c.append(cirq.X(q1))

c.append(cirq.CCNOT(q0, q1, q2))

c.append(cirq.CSWAP(q1, q2, q0))

c.append(cirq.measure(q0, key='result 0'))

c.append(cirq.measure(q1, key='result 1'))

c.append(cirq.measure(q2, key='result 2'))

print('Before optimization')

print(c)

RemoveMeasurements().optimize_circuit(c)

print('After optimization')

print(c)

[出力結果]
Before optimization
0: ───X───@───×───M('result 0')───
          │   │
1: ───X───@───@───M('result 1')───
          │   │
2: ───────X───×───M('result 2')───
After optimization
0: ───X───@───×───────
          │   │
1: ───X───@───@───────
          │   │
2: ───────X───×───────

[出力結果]

Before optimization

0: ───X───@───×───M('result 0')───

│ │

1: ───X───@───@───M('result 1')───

│ │

2: ───────X───×───M('result 2')───

After optimization

0: ───X───@───×───────

│ │

1: ───X───@───@───────

│ │

2: ───────X───×───────

参照サイト

2021年3月22日

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

C++の練習を兼ねて, AtCoder Grand Contest 040 の問題C (Neither AB nor BA) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/agc040/editorial.pdf
// 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 = 998244353;
const int LIMIT = 10101010;
LL FAC[LIMIT], INV[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return: べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t % MOD;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    FAC[0] = 1;
    repx(i, 1, N + 1) FAC[i] = i * FAC[i - 1] % MOD;
    rep(i, N + 1)     INV[i] = mPow(FAC[i], MOD - 2) % MOD;
    
    // 2. 解説通り.
    // 2-1. 3 の N乗.
    LL ans = mPow(3LL, (LL)N);
    
    // 2-2. 'A' もしくは 'B' が 過半数となる文字列の個数.
    LL aORb = 0;
    repx(r, N / 2 + 1, N + 1){
        aORb += combination((LL)N, (LL)r) * mPow(2LL, (LL)(N - r));
        aORb %= MOD;
    }
    
    // 2-3. 集計.
    ans = (ans + MOD - aORb) % MOD;
    ans = (ans + MOD - aORb) % MOD;
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// 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 = 998244353;

const int LIMIT = 10101010;

LL FAC[LIMIT], INV[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

FAC[0] = 1;

repx(i, 1, N + 1) FAC[i] = i * FAC[i - 1] % MOD;

rep(i, N + 1) INV[i] = mPow(FAC[i], MOD - 2) % MOD;

// 2. 解説通り.

// 2-1. 3 の N乗.

LL ans = mPow(3LL, (LL)N);

// 2-2. 'A' もしくは 'B' が過半数となる文字列の個数.

LL aORb = 0;

repx(r, N / 2 + 1, N + 1){

aORb += combination((LL)N, (LL)r) * mPow(2LL, (LL)(N - r));

aORb %= MOD;

}

// 2-3. 集計.

ans = (ans + MOD - aORb) % MOD;

// 3. 出力.

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

return 0;

}

[入力例]
2

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

[入力例]
10

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

[入力例]
1000000

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

[入力例]
5

[出力例]
141

[入力例]
18

[出力例]
353832631

[入力例]
3141592

[出力例]
895463844

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

50007

※AtCoderテストケースより

[入力例]

1000000

[出力例]

210055358

※AtCoderテストケースより

[入力例]

[出力例]

141

[入力例]

[出力例]

353832631

[入力例]

3141592

[出力例]

895463844

■参照サイト
AtCoder Grand Contest 040

2021年3月21日

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

C++の練習を兼ねて, AtCoder Grand Contest 040 の問題B (Two Contests) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/agc040/editorial.pdf
// 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--)
#define pb push_back
#define all(x) x.begin(), x.end()
const LL INF = 202020202020202020;
LL l[101010], r[101010], as[101010], bt[101010];

struct joy{
    int i;
    LL a, b;
    bool operator < (const joy& rhs) const{
        return (a < rhs.a) || ((a == rhs.a) && (b > rhs.b));
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL ans = 0, maxL = 0, minR = INF;
    int p = -1, q = -1;
    rep(i, N){
        scanf("%lld %lld", &l[i], &r[i]);
        if(maxL < l[i]){
            maxL = l[i];
            p = i;
        }
        if(minR > r[i]){
            minR = r[i];
            q = i;
        }
        ans = max(ans, r[i] - l[i] + 1LL); // 最も長い区間を保存.
    }
    ans += max(0LL, minR - maxL + 1LL);
    
    // 2. 解説通り.
    vector<joy> v;
    rep(i, N){
        LL a = max(r[i] - maxL + 1LL, 0LL);
        LL b = max(minR - l[i] + 1LL, 0LL);
        joy j;
        j.i = i;
        j.a = a;
        j.b = b;
        v.pb(j);
    }
    
    // 3. sort.
    sort(all(v));
    // for(auto &p : v) printf("i=%d a=%lld b=%lld\n", p.i, p.a, p.b);
    
    // 4. 事前準備.
    rep(i, N + 1)     as[i] = bt[i] = INF;
    repr(i, N - 1, 0) as[i] = min(as[i + 1], v[i].a);
    rep(i, N)         bt[i + 1] = min(bt[i], v[i].b);
    // rep(i, N + 1) printf("%lld ", as[i]);
    // puts("");  
    // rep(i, N + 1) printf("%lld ", bt[i]);
    // puts("");
    
    // 5. 最大値は？
    repx(i, 1, N) ans = max(ans, as[i] + bt[i]);
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// 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--)

#define pb push_back

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

const LL INF = 202020202020202020;

LL l[101010], r[101010], as[101010], bt[101010];

struct joy{

int i;

LL a, b;

bool operator < (const joy& rhs) const{

return (a < rhs.a) || ((a == rhs.a) && (b > rhs.b));

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL ans = 0, maxL = 0, minR = INF;

int p = -1, q = -1;

rep(i, N){

scanf("%lld %lld", &l[i], &r[i]);

if(maxL < l[i]){

maxL = l[i];

p = i;

}

if(minR > r[i]){

minR = r[i];

q = i;

}

ans = max(ans, r[i] - l[i] + 1LL); // 最も長い区間を保存.

}

ans += max(0LL, minR - maxL + 1LL);

// 2. 解説通り.

vector<joy> v;

rep(i, N){

LL a = max(r[i] - maxL + 1LL, 0LL);

LL b = max(minR - l[i] + 1LL, 0LL);

joy j;

j.i = i;

j.a = a;

j.b = b;

v.pb(j);

}

// 3. sort.

sort(all(v));

// for(auto &p : v) printf("i=%d a=%lld b=%lld\n", p.i, p.a, p.b);

// 4. 事前準備.

rep(i, N + 1) as[i] = bt[i] = INF;

repr(i, N - 1, 0) as[i] = min(as[i + 1], v[i].a);

rep(i, N) bt[i + 1] = min(bt[i], v[i].b);

// rep(i, N + 1) printf("%lld ", as[i]);

// puts("");

// rep(i, N + 1) printf("%lld ", bt[i]);

// puts("");

// 5. 最大値は？

repx(i, 1, N) ans = max(ans, as[i] + bt[i]);

// 6. 出力.

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

return 0;

}

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

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

[入力例]
4
1 20
2 19
3 18
4 17

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

[入力例]
10
457835016 996058008
456475528 529149798
455108441 512701454
455817105 523506955
457368248 814532746
455073228 459494089
456651538 774276744
457667152 974637457
457293701 800549465
456580262 636471526

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

[入力例]
25
1 6
17 23
16 31
7 22
4 5
3 13
19 27
7 13
11 22
2 3
6 21
3 19
3 13
7 7
15 20
2 11
9 23
17 25
6 15
15 19
9 19
4 5
15 19
1 2
11 21

[出力例]
17

[入力例]

4 7

1 4

5 8

2 5

[出力例]

※AtCoderテストケースより

[入力例]

1 20

2 19

3 18

4 17

[出力例]

※AtCoderテストケースより

[入力例]

457835016 996058008

456475528 529149798

455108441 512701454

455817105 523506955

457368248 814532746

455073228 459494089

456651538 774276744

457667152 974637457

457293701 800549465

456580262 636471526

[出力例]

540049931

※AtCoderテストケースより

[入力例]

1 6

17 23

16 31

7 22

4 5

3 13

19 27

7 13

11 22

2 3

6 21

3 19

3 13

7 7

15 20

2 11

9 23

17 25

6 15

15 19

9 19

4 5

15 19

1 2

11 21

[出力例]

■参照サイト
AtCoder Grand Contest 040

2021年3月21日2021年3月21日

Python（Cirq）について（１４）

概要

Cirq について, Heatmaps, Qudits に関するサンプルをいくつか動かしてみた.
動作環境は, Google Colaboratory で行った

感想

量子物理学に関する知識(用語, 数式の意味ほか)は, 徐々に身につけていく必要があると感じた.
時間を見つけて, 今後も, ドキュメントの残りの部分を進めていこうと思う.

Heatmaps for Custom Data

Heatmaps を使うサンプル

[編集内容(Heatmaps)]
import cirq

cirq.Heatmap({
    (cirq.GridQubit(0, 0),): 0.07,
    (cirq.GridQubit(0, 2),): 0.002,
    (cirq.GridQubit(0, 4),): 0.15,
    (cirq.GridQubit(1, 1),): 0.08,
    (cirq.GridQubit(1, 3),): 0.14,
    (cirq.GridQubit(2, 0),): 0.001,
    (cirq.GridQubit(2, 2),): 0.09,
    (cirq.GridQubit(2, 4),): 0.003,
    (cirq.GridQubit(3, 1),): 0.12,
    (cirq.GridQubit(3, 3),): 0.10,
    (cirq.GridQubit(4, 0),): 0.13,
    (cirq.GridQubit(4, 2),): 0.004,
    (cirq.GridQubit(4, 4),): 0.11,
}, plot_colorbar = True, colorbar_position = 'right', 
colorbar_size = '3%', 
colorbar_pad = '5%',
title = "Heatmap Sample").plot()

[編集内容(Heatmaps)]

import cirq

cirq.Heatmap({

(cirq.GridQubit(0, 0),): 0.07,

(cirq.GridQubit(0, 2),): 0.002,

(cirq.GridQubit(0, 4),): 0.15,

(cirq.GridQubit(1, 1),): 0.08,

(cirq.GridQubit(1, 3),): 0.14,

(cirq.GridQubit(2, 0),): 0.001,

(cirq.GridQubit(2, 2),): 0.09,

(cirq.GridQubit(2, 4),): 0.003,

(cirq.GridQubit(3, 1),): 0.12,

(cirq.GridQubit(3, 3),): 0.10,

(cirq.GridQubit(4, 0),): 0.13,

(cirq.GridQubit(4, 2),): 0.004,

(cirq.GridQubit(4, 4),): 0.11,

}, plot_colorbar = True, colorbar_position = 'right',

colorbar_size = '3%',

colorbar_pad = '5%',

title = "Heatmap Sample").plot()

[出力結果]
※Heatmapsが表示された.

1 2	[出力結果] ※Heatmapsが表示された.

TwoQubitInteractionHeatmap を使うサンプル

[編集内容(TwoQubitInteractionHeatmap)]
import cirq

cirq.TwoQubitInteractionHeatmap({
    (cirq.GridQubit(0, 0), cirq.GridQubit(0, 1)): 0.1,
    (cirq.GridQubit(0, 1), cirq.GridQubit(0, 2)): 0.2,
    (cirq.GridQubit(0, 1), cirq.GridQubit(1, 1)): 0.3,
    # ValueError: (1, 1)-(2, 2) is not supported because they are not nearest neighbors
    # (cirq.GridQubit(1, 1), cirq.GridQubit(2, 2)): 0.4,
    (cirq.GridQubit(2, 0), cirq.GridQubit(2, 1)): 0.5,
    (cirq.GridQubit(2, 0), cirq.GridQubit(3, 0)): 0.6,
    (cirq.GridQubit(3, 0), cirq.GridQubit(3, 1)): 0.7,
    (cirq.GridQubit(3, 1), cirq.GridQubit(2, 1)): 0.8,
    (cirq.GridQubit(2, 1), cirq.GridQubit(2, 2)): 0.9,
    (cirq.GridQubit(3, 1), cirq.GridQubit(3, 2)): 1.0,
    (cirq.GridQubit(3, 1), cirq.GridQubit(3, 2)): 1.1,
    (cirq.GridQubit(2, 2), cirq.GridQubit(3, 2)): 1.2,
    (cirq.GridQubit(5, 0), cirq.GridQubit(5, 1)): 1.3,
    (cirq.GridQubit(5, 1), cirq.GridQubit(4, 1)): 1.4,
    (cirq.GridQubit(5, 1), cirq.GridQubit(5, 2)): 1.5,
}, annotation_format="0.3f", title = 'Dummy Two Qubit Manual Plot').plot()

[編集内容(TwoQubitInteractionHeatmap)]

import cirq

cirq.TwoQubitInteractionHeatmap({

(cirq.GridQubit(0, 0), cirq.GridQubit(0, 1)): 0.1,

(cirq.GridQubit(0, 1), cirq.GridQubit(0, 2)): 0.2,

(cirq.GridQubit(0, 1), cirq.GridQubit(1, 1)): 0.3,

# ValueError: (1, 1)-(2, 2) is not supported because they are not nearest neighbors

# (cirq.GridQubit(1, 1), cirq.GridQubit(2, 2)): 0.4,

(cirq.GridQubit(2, 0), cirq.GridQubit(2, 1)): 0.5,

(cirq.GridQubit(2, 0), cirq.GridQubit(3, 0)): 0.6,

(cirq.GridQubit(3, 0), cirq.GridQubit(3, 1)): 0.7,

(cirq.GridQubit(3, 1), cirq.GridQubit(2, 1)): 0.8,

(cirq.GridQubit(2, 1), cirq.GridQubit(2, 2)): 0.9,

(cirq.GridQubit(3, 1), cirq.GridQubit(3, 2)): 1.0,

(cirq.GridQubit(3, 1), cirq.GridQubit(3, 2)): 1.1,

(cirq.GridQubit(2, 2), cirq.GridQubit(3, 2)): 1.2,

(cirq.GridQubit(5, 0), cirq.GridQubit(5, 1)): 1.3,

(cirq.GridQubit(5, 1), cirq.GridQubit(4, 1)): 1.4,

(cirq.GridQubit(5, 1), cirq.GridQubit(5, 2)): 1.5,

}, annotation_format="0.3f", title = 'Dummy Two Qubit Manual Plot').plot()

[出力結果]
※TwoQubitInteractionHeatmapが表示された.

1 2	[出力結果] ※TwoQubitInteractionHeatmapが表示された.

Qudits

Qudits を使うサンプル

[編集内容(Qudits)]
import numpy as np
import cirq

class QutritPlusGate1(cirq.SingleQubitGate):
  def _qid_shape_(self):
    return (3,)
    
  def _unitary_(self):
    return np.array([[0, 0, 1],
                    [1, 0, 0],
                    [0, 1, 0]])
                    
  def _circuit_diagram_info_(self, args):
    return '[+1]'

class QutritPlusGate2(cirq.SingleQubitGate):
  def _qid_shape_(self):
    return (3,)
    
  def _unitary_(self):
    return np.array([[0, 1, 0],
                    [0, 0, 1],
                    [1, 0, 0]])
                    
  def _circuit_diagram_info_(self, args):
    return '[+2]'

# 以下のように理解.
# [前提]
# 量子ビットの取り得る値が, 三通りあると見る.
# 列ベクトル [1, 0, 0], [0, 1, 0], [0, 0, 1] を それぞれ, 状態 0, 1, 2 を 取ると見る.
# 
# [操作]
# 1. ↑(1量子ビット, 0 と見る) を 用意.
# 2-1. QutritPlusGate1 ゲート を 操作する場合.
# -> 状態 0 から 1 に変わったとみる(ここでは, q0 の 出力が, 1 のようになるはず).
# 2-2. QutritPlusGate2 ゲート を 操作する場合.
# -> 状態 0 から 2 に変わったとみる(ここでは, q1 の 出力が, 2 のようになるはず).

Gate1, Gate2 = QutritPlusGate1(), QutritPlusGate2()

# Pick two qubits.
q0, q1 = cirq.LineQid(0, dimension=3), cirq.LineQid(1, dimension=3)

for y in range(3):
  circuit = cirq.Circuit()
  op_1, op_2 = Gate1.on(q0), Gate2.on(q1)
  circuit.append([op_1, op_2])
  circuit.append([cirq.measure(q0, key='q0'), cirq.measure(q1, key='q1')])
  print("Circuit with a custom rotation gate: ", y, "times")
  print(circuit)
  
  # Simulate 5 times.
  simulator = cirq.Simulator()
  results = simulator.run(circuit, repetitions=5)
  
  # Output result.
  print(results)
  print("")

[編集内容(Qudits)]

import numpy as np

import cirq

class QutritPlusGate1(cirq.SingleQubitGate):

def _qid_shape_(self):

return (3,)

def _unitary_(self):

return np.array([[0, 0, 1],

[1, 0, 0],

[0, 1, 0]])

def _circuit_diagram_info_(self, args):

return '[+1]'

class QutritPlusGate2(cirq.SingleQubitGate):

def _qid_shape_(self):

return (3,)

def _unitary_(self):

return np.array([[0, 1, 0],

[0, 0, 1],

[1, 0, 0]])

def _circuit_diagram_info_(self, args):

return '[+2]'

# 以下のように理解.

# [前提]

# 量子ビットの取り得る値が, 三通りあると見る.

# 列ベクトル [1, 0, 0], [0, 1, 0], [0, 0, 1] をそれぞれ, 状態 0, 1, 2 を取ると見る.

# [操作]

# 1. ↑(1量子ビット, 0 と見る) を用意.

# 2-1. QutritPlusGate1 ゲートを操作する場合.

# -> 状態 0 から 1 に変わったとみる(ここでは, q0 の出力が, 1 のようになるはず).

# 2-2. QutritPlusGate2 ゲートを操作する場合.

# -> 状態 0 から 2 に変わったとみる(ここでは, q1 の出力が, 2 のようになるはず).

Gate1, Gate2 = QutritPlusGate1(), QutritPlusGate2()

# Pick two qubits.

q0, q1 = cirq.LineQid(0, dimension=3), cirq.LineQid(1, dimension=3)

for y in range(3):

circuit = cirq.Circuit()

op_1, op_2 = Gate1.on(q0), Gate2.on(q1)

circuit.append([op_1, op_2])

circuit.append([cirq.measure(q0, key='q0'), cirq.measure(q1, key='q1')])

print("Circuit with a custom rotation gate: ", y, "times")

print(circuit)

# Simulate 5 times.

simulator = cirq.Simulator()

results = simulator.run(circuit, repetitions=5)

# Output result.

print(results)

print("")

[出力結果]
Circuit with a custom rotation gate:  0 times
0 (d=3): ───[+1]───M('q0')───

1 (d=3): ───[+2]───M('q1')───
q0=11111
q1=22222

Circuit with a custom rotation gate:  1 times
0 (d=3): ───[+1]───M('q0')───

1 (d=3): ───[+2]───M('q1')───
q0=11111
q1=22222

Circuit with a custom rotation gate:  2 times
0 (d=3): ───[+1]───M('q0')───

1 (d=3): ───[+2]───M('q1')───
q0=11111
q1=22222

[出力結果]

Circuit with a custom rotation gate: 0 times

0 (d=3): ───[+1]───M('q0')───

1 (d=3): ───[+2]───M('q1')───

q0=11111

q1=22222

Circuit with a custom rotation gate: 1 times

0 (d=3): ───[+1]───M('q0')───

1 (d=3): ───[+2]───M('q1')───

q0=11111

q1=22222

Circuit with a custom rotation gate: 2 times

0 (d=3): ───[+1]───M('q0')───

1 (d=3): ───[+2]───M('q1')───

q0=11111

q1=22222

Qudits を使うサンプル

[編集内容(Qudits)]
import numpy as np
import cirq

class QutritPlusGate(cirq.SingleQubitGate):
  r = -1
  def __init__(self):
    self.r = int(np.random.rand() * 3)
    
  def _qid_shape_(self):
    return (3,)
    
  def _unitary_(self):
    if self.r < 1:
      return np.array([[1, 0, 0],
                      [0, 1, 0],
                      [0, 0, 1]])
    elif self.r < 2:
      return np.array([[0, 0, 1],
                      [1, 0, 0],
                      [0, 1, 0]])
    else:
      return np.array([[0, 1, 0],
                      [0, 0, 1],
                      [1, 0, 0]])
                      
  def _circuit_diagram_info_(self, args):
    if self.r < 1:
      return '[+0]'
    elif self.r < 2:
      return '[+1]'
    else:
      return '[+2]'

# 以下のように理解.
# [前提]
# 量子ビットの取り得る値が, 三通りあると見る.
# 列ベクトル [1, 0, 0], [0, 1, 0], [0, 0, 1] を それぞれ, 状態 0, 1, 2 を 取ると見る.
# 
# [操作]
# 1. ↑(1量子ビット, 0 と見る) を 用意.
# 2. QutritPlusGate ゲート を 操作する場合.
# -> r の 値(0, 1, 2) に応じて, q0 の 出力が, 以下のように変化するはず.
#    r = 0: q0 の 出力 は, 0.
#    r = 1: q0 の 出力 は, 1.
#    r = 2: q0 の 出力 は, 2.

for y in range(5):
  q0 = cirq.LineQid(0, dimension=3)
  Gate = QutritPlusGate()
  circuit = cirq.Circuit(
    Gate.on(q0)
  )
  circuit.append([cirq.measure(q0, key='q0')])
  print("Circuit with a custom rotation gate: ", y, "times")
  print(circuit)
  
  # Simulate 5 times.
  simulator = cirq.Simulator()
  results = simulator.run(circuit, repetitions=5)
  
  # Output result.
  print("r = " + str(Gate.r))
  print(results)
  print("")

[編集内容(Qudits)]

import numpy as np

import cirq

class QutritPlusGate(cirq.SingleQubitGate):

r = -1

def __init__(self):

self.r = int(np.random.rand() * 3)

def _qid_shape_(self):

return (3,)

def _unitary_(self):

if self.r < 1:

return np.array([[1, 0, 0],

[0, 1, 0],

[0, 0, 1]])

elif self.r < 2:

return np.array([[0, 0, 1],

[1, 0, 0],

[0, 1, 0]])

else:

return np.array([[0, 1, 0],

[0, 0, 1],

[1, 0, 0]])

def _circuit_diagram_info_(self, args):

if self.r < 1:

return '[+0]'

elif self.r < 2:

return '[+1]'

else:

return '[+2]'

# 以下のように理解.

# [前提]

# 量子ビットの取り得る値が, 三通りあると見る.

# 列ベクトル [1, 0, 0], [0, 1, 0], [0, 0, 1] をそれぞれ, 状態 0, 1, 2 を取ると見る.

# [操作]

# 1. ↑(1量子ビット, 0 と見る) を用意.

# 2. QutritPlusGate ゲートを操作する場合.

# -> r の値(0, 1, 2) に応じて, q0 の出力が, 以下のように変化するはず.

# r = 0: q0 の出力は, 0.

# r = 1: q0 の出力は, 1.

# r = 2: q0 の出力は, 2.

for y in range(5):

q0 = cirq.LineQid(0, dimension=3)

Gate = QutritPlusGate()

circuit = cirq.Circuit(

Gate.on(q0)

)

circuit.append([cirq.measure(q0, key='q0')])

print("Circuit with a custom rotation gate: ", y, "times")

print(circuit)

# Simulate 5 times.

simulator = cirq.Simulator()

results = simulator.run(circuit, repetitions=5)

# Output result.

print("r = " + str(Gate.r))

print(results)

print("")

[出力結果]
測定を繰り返すと, 出力結果 も 変化.
Circuit with a custom rotation gate:  0 times
0 (d=3): ───[+1]───M('q0')───
r = 1
q0=11111

Circuit with a custom rotation gate:  1 times
0 (d=3): ───[+2]───M('q0')───
r = 2
q0=22222

Circuit with a custom rotation gate:  2 times
0 (d=3): ───[+0]───M('q0')───
r = 0
q0=00000

Circuit with a custom rotation gate:  3 times
0 (d=3): ───[+2]───M('q0')───
r = 2
q0=22222

Circuit with a custom rotation gate:  4 times
0 (d=3): ───[+0]───M('q0')───
r = 0
q0=00000

[出力結果]

測定を繰り返すと, 出力結果も変化.

Circuit with a custom rotation gate: 0 times

0 (d=3): ───[+1]───M('q0')───

r = 1

q0=11111

Circuit with a custom rotation gate: 1 times

0 (d=3): ───[+2]───M('q0')───

r = 2

q0=22222

Circuit with a custom rotation gate: 2 times

0 (d=3): ───[+0]───M('q0')───

r = 0

q0=00000

Circuit with a custom rotation gate: 3 times

0 (d=3): ───[+2]───M('q0')───

r = 2

q0=22222

Circuit with a custom rotation gate: 4 times

0 (d=3): ───[+0]───M('q0')───

r = 0

q0=00000

Qudits を使うサンプル

[編集内容(Qudits)]
import numpy as np
import cirq

class QutritPlusGate(cirq.SingleQubitGate):
  r = -1
  def __init__(self):
    self.r = int(np.random.rand() * 5)
    
  def _qid_shape_(self):
    return (5,)
    
  def _unitary_(self):
    if self.r < 1:
      return np.array([[1, 0, 0, 0, 0],
                      [0, 1, 0, 0, 0],
                      [0, 0, 1, 0, 0],
                      [0, 0, 0, 1, 0],
                      [0, 0, 0, 0, 1]])
    elif self.r < 2:
      return np.array([[0, 0, 0, 0, 1],
                      [1, 0, 0, 0, 0],
                      [0, 1, 0, 0, 0],
                      [0, 0, 1, 0, 0],
                      [0, 0, 0, 1, 0]])
    elif self.r < 3:
      return np.array([[0, 0, 0, 1, 0],
                      [0, 0, 0, 0, 1],
                      [1, 0, 0, 0, 0],
                      [0, 1, 0, 0, 0],
                      [0, 0, 1, 0, 0]])
    elif self.r < 4:
      return np.array([[0, 0, 1, 0, 0],
                      [0, 0, 0, 1, 0],
                      [0, 0, 0, 0, 1],
                      [1, 0, 0, 0, 0],
                      [0, 1, 0, 0, 0]])
    else:
      return np.array([[0, 1, 0, 0, 0],
                      [0, 0, 1, 0, 0],
                      [0, 0, 0, 1, 0],
                      [0, 0, 0, 0, 1],
                      [1, 0, 0, 0, 0]])
                      
  def _circuit_diagram_info_(self, args):
    if self.r < 1:
      return '[+0]'
    elif self.r < 2:
      return '[+1]'
    elif self.r < 3:
      return '[+2]'
    elif self.r < 4:
      return '[+3]'
    else:
      return '[+4]'

# 以下のように理解.
# [前提]
# 量子ビットの取り得る値が, 五通りあると見る.
# 列ベクトル [1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1] 
# を それぞれ, 状態 0, 1, 2, 3, 4 を 取ると見る.
# 
# [操作]
# 1. ↑(1量子ビット, 0 と見る) を 用意.
# 2. QutritPlusGate ゲート を 操作する場合.
# -> r の 値(0, 1, 2, 3, 4) に応じて, q0 の 出力が, 以下のように変化するはず.
#    r = 0: q0 の 出力 は, 0.
#    r = 1: q0 の 出力 は, 1.
#    r = 2: q0 の 出力 は, 2.
#    r = 3: q0 の 出力 は, 3.
#    r = 4: q0 の 出力 は, 4.

for y in range(7):
  q0 = cirq.LineQid(0, dimension=5)
  Gate = QutritPlusGate()
  circuit = cirq.Circuit(
    Gate.on(q0)
  )
  circuit.append([cirq.measure(q0, key='q0')])
  print("Circuit with a custom rotation gate: ", y, "times")
  print(circuit)
  
  # Simulate 5 times.
  simulator = cirq.Simulator()
  results = simulator.run(circuit, repetitions=5)
  
  # Output result.
  print("r = " + str(Gate.r))
  print(results)
  print("")

[編集内容(Qudits)]

import numpy as np

import cirq

class QutritPlusGate(cirq.SingleQubitGate):

r = -1

def __init__(self):

self.r = int(np.random.rand() * 5)

def _qid_shape_(self):

return (5,)

def _unitary_(self):

if self.r < 1:

return np.array([[1, 0, 0, 0, 0],

[0, 1, 0, 0, 0],

[0, 0, 1, 0, 0],

[0, 0, 0, 1, 0],

[0, 0, 0, 0, 1]])

elif self.r < 2:

return np.array([[0, 0, 0, 0, 1],

[1, 0, 0, 0, 0],

[0, 1, 0, 0, 0],

[0, 0, 1, 0, 0],

[0, 0, 0, 1, 0]])

elif self.r < 3:

return np.array([[0, 0, 0, 1, 0],

[0, 0, 0, 0, 1],

[1, 0, 0, 0, 0],

[0, 1, 0, 0, 0],

[0, 0, 1, 0, 0]])

elif self.r < 4:

return np.array([[0, 0, 1, 0, 0],

[0, 0, 0, 1, 0],

[0, 0, 0, 0, 1],

[1, 0, 0, 0, 0],

[0, 1, 0, 0, 0]])

else:

return np.array([[0, 1, 0, 0, 0],

[0, 0, 1, 0, 0],

[0, 0, 0, 1, 0],

[0, 0, 0, 0, 1],

[1, 0, 0, 0, 0]])

def _circuit_diagram_info_(self, args):

if self.r < 1:

return '[+0]'

elif self.r < 2:

return '[+1]'

elif self.r < 3:

return '[+2]'

elif self.r < 4:

return '[+3]'

else:

return '[+4]'

# 以下のように理解.

# [前提]

# 量子ビットの取り得る値が, 五通りあると見る.

# 列ベクトル [1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]

# をそれぞれ, 状態 0, 1, 2, 3, 4 を取ると見る.

# [操作]

# 1. ↑(1量子ビット, 0 と見る) を用意.

# 2. QutritPlusGate ゲートを操作する場合.

# -> r の値(0, 1, 2, 3, 4) に応じて, q0 の出力が, 以下のように変化するはず.

# r = 0: q0 の出力は, 0.

# r = 1: q0 の出力は, 1.

# r = 2: q0 の出力は, 2.

# r = 3: q0 の出力は, 3.

# r = 4: q0 の出力は, 4.

for y in range(7):

q0 = cirq.LineQid(0, dimension=5)

Gate = QutritPlusGate()

circuit = cirq.Circuit(

Gate.on(q0)

)

circuit.append([cirq.measure(q0, key='q0')])

print("Circuit with a custom rotation gate: ", y, "times")

print(circuit)

# Simulate 5 times.

simulator = cirq.Simulator()

results = simulator.run(circuit, repetitions=5)

# Output result.

print("r = " + str(Gate.r))

print(results)

print("")

[出力結果]
測定を繰り返すと, 出力結果 も 変化.
Circuit with a custom rotation gate:  0 times
0 (d=5): ───[+1]───M('q0')───
r = 1
q0=11111

Circuit with a custom rotation gate:  1 times
0 (d=5): ───[+3]───M('q0')───
r = 3
q0=33333

Circuit with a custom rotation gate:  2 times
0 (d=5): ───[+1]───M('q0')───
r = 1
q0=11111

Circuit with a custom rotation gate:  3 times
0 (d=5): ───[+4]───M('q0')───
r = 4
q0=44444

Circuit with a custom rotation gate:  4 times
0 (d=5): ───[+3]───M('q0')───
r = 3
q0=33333

Circuit with a custom rotation gate:  5 times
0 (d=5): ───[+2]───M('q0')───
r = 2
q0=22222

Circuit with a custom rotation gate:  6 times
0 (d=5): ───[+0]───M('q0')───
r = 0
q0=00000

[出力結果]

測定を繰り返すと, 出力結果も変化.

Circuit with a custom rotation gate: 0 times

0 (d=5): ───[+1]───M('q0')───

r = 1

q0=11111

Circuit with a custom rotation gate: 1 times

0 (d=5): ───[+3]───M('q0')───

r = 3

q0=33333

Circuit with a custom rotation gate: 2 times

0 (d=5): ───[+1]───M('q0')───

r = 1

q0=11111

Circuit with a custom rotation gate: 3 times

0 (d=5): ───[+4]───M('q0')───

r = 4

q0=44444

Circuit with a custom rotation gate: 4 times

0 (d=5): ───[+3]───M('q0')───

r = 3

q0=33333

Circuit with a custom rotation gate: 5 times

0 (d=5): ───[+2]───M('q0')───

r = 2

q0=22222

Circuit with a custom rotation gate: 6 times

0 (d=5): ───[+0]───M('q0')───

r = 0

q0=00000

参照サイト

2021年3月19日2021年3月19日

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

C++の練習を兼ねて, AtCoder Regular Contest 099 の問題D (Snuke Numbers) を解いてみた.

■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, 条件を整数の抽出方法が, 非常に面白く感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc099/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 LL INF = 202020202020202020;

int main(){
    
    // 1. 入力情報.
    int K;
    scanf("%d", &K);
    
    // 2. 10の冪乗を用意.
    vl cPow;
    cPow.pb(1);
    while(cPow.back() < 1e18){
        // 最大値を10倍.
        LL p = 10 * cPow.back();
        
        // 保存.
        cPow.pb(p);
    }
    // for(auto &p : cPow) printf("%lld\n", p);
    
    // 3. x を保存.
    // -> N = 792 で, 丁度桁あふれするので, N / S(N) と x / S(x) を比較する部分を修正.
    int count = 0;
    LL N = 1;
    vl v;
    while(count < K){
        // 3-1. N に 対する N / S(N) の 準備.
        string nStr = to_string(N);
        LL sn = 0;
        rep(j, nStr.size()) sn += (nStr[j] - '0');
        
        // 3-2. x に 対する x / S(x) の 準備.
        int d = (int)log10(N) + 1;
        LL S = 0, X = 0, minS = INF, minX = INF;
        rep(j, d + 1){
            X = cPow[j + 1] * (N / cPow[j + 1] + 1) - 1;
            string xStr = to_string(X);
            S = 0;
            rep(k, xStr.size()) S += (xStr[k] - '0');
            
            // 初回確認時.
            if(minS == INF){
                minS = S;
                minX = X;
            }
            
            // 2回目以降.
            if(minS < INF){
                if(X * minS < minX * S){
                    minS = S;
                    minX = X;
                }
            }
        }
        // printf("count=%d S=%lld X=%lld N=%lld\n", count, S, X, N);
        
        // 3-3. N に 対する N / S(N) と x に 対する x / S(x) を 比較.
        // 前者が小さい場合は, 追加.
        // if(N * minS <= minX * sn){ // N = 792 で 桁あふれ.
        if((double)N / (double)sn <= (double)minX / (double)minS){
            // Snuke数 を 追加.
            v.pb(N);
            
            // インクリメント.
            N++;
            count++;
            
            // 次へ.
            continue;
        }
        
        // 3-4. 前者が大きい場合は, 追加しない.
        // if(N * minS > minX * sn) N = minX; // N = 792 で 桁あふれ.
        if((double)minS / (double)sn > (double)minX / (double)N) N = minX;
    }
    
    // 4. 出力.
    for(auto &p : v) printf("%lld\n", p);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/arc099/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 LL INF = 202020202020202020;

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

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

vl cPow;

cPow.pb(1);

while(cPow.back() < 1e18){

// 最大値を10倍.

LL p = 10 * cPow.back();

// 保存.

cPow.pb(p);

}

// for(auto &p : cPow) printf("%lld\n", p);

// 3. x を保存.

// -> N = 792 で, 丁度桁あふれするので, N / S(N) と x / S(x) を比較する部分を修正.

int count = 0;

LL N = 1;

vl v;

while(count < K){

// 3-1. N に対する N / S(N) の準備.

string nStr = to_string(N);

LL sn = 0;

rep(j, nStr.size()) sn += (nStr[j] - '0');

// 3-2. x に対する x / S(x) の準備.

int d = (int)log10(N) + 1;

LL S = 0, X = 0, minS = INF, minX = INF;

rep(j, d + 1){

X = cPow[j + 1] * (N / cPow[j + 1] + 1) - 1;

string xStr = to_string(X);

S = 0;

rep(k, xStr.size()) S += (xStr[k] - '0');

// 初回確認時.

if(minS == INF){

minS = S;

minX = X;

}

// 2回目以降.

if(minS < INF){

if(X * minS < minX * S){

minS = S;

minX = X;

}

// printf("count=%d S=%lld X=%lld N=%lld\n", count, S, X, N);

// 3-3. N に対する N / S(N) と x に対する x / S(x) を比較.

// 前者が小さい場合は, 追加.

// if(N * minS <= minX * sn){ // N = 792 で桁あふれ.

if((double)N / (double)sn <= (double)minX / (double)minS){

// Snuke数を追加.

v.pb(N);

// インクリメント.

N++;

count++;

// 次へ.

continue;

}

// 3-4. 前者が大きい場合は, 追加しない.

// if(N * minS > minX * sn) N = minX; // N = 792 で桁あふれ.

if((double)minS / (double)sn > (double)minX / (double)N) N = minX;

}

// 4. 出力.

for(auto &p : v) printf("%lld\n", p);

return 0;

}

[入力例]
10

[出力例]
1
2
3
4
5
6
7
8
9
19
※AtCoderのテストケースより

[入力例]
77

[出力例]
1
2
3
4
5
6
7
8
9
19
29
39
49
59
69
79
89
99
199
299
399
499
599
699
799
899
999
1099
1199
1299
1399
1499
1599
1699
1799
1899
1999
2999
3999
4999
5999
6999
7999
8999
9999
10999
11999
12999
13999
14999
15999
16999
17999
18999
19999
20999
21999
22999
23999
24999
25999
26999
27999
28999
29999
39999
49999
59999
69999
79999
89999
99999
109999
119999
129999
139999
149999

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

199

299

399

499

599

699

799

899

999

1099

1199

1299

1399

1499

1599

1699

1799

1899

1999

2999

3999

4999

5999

6999

7999

8999

9999

10999

11999

12999

13999

14999

15999

16999

17999

18999

19999

20999

21999

22999

23999

24999

25999

26999

27999

28999

29999

39999

49999

59999

69999

79999

89999

99999

109999

119999

129999

139999

149999

■参照サイト
AtCoder Regular Contest 099

2021年3月17日2021年3月17日

Python（Cirq）について（１３）

概要

Cirq について, Custom Gates に関するサンプルをいくつか動かしてみた.
動作環境は, Google Colaboratory で行った

感想

量子物理学に関する知識(用語, 数式の意味ほか)は, 徐々に身につけていく必要があると感じた.
時間を見つけて, 今後も, ドキュメントの残りの部分を進めていこうと思う.

With parameters

RotationGate を使うサンプル

[編集内容(RotationGate)]
import numpy as np
import cirq

"""Define a custom gate with a parameter."""
class RotationGate(cirq.Gate):
  def __init__(self, theta):
    super(RotationGate, self)
    self.theta = theta

  def _num_qubits_(self):
    return 1

  def _unitary_(self):
    return np.array([
      [np.cos(self.theta), np.sin(self.theta)],
      [np.sin(self.theta), -np.cos(self.theta)]
      ]) / np.sqrt(2)

  def _circuit_diagram_info_(self, args):
    return f"R({self.theta})"

# Pick two qubits.
q0, q1 = cirq.GridQubit(0, 1), cirq.GridQubit(2, 3)

# 以下のように理解.
# 1. ↑↑(2量子ビット, 00 と見る) を 用意.
# 2. 1量子ビット目に, X ゲート を 操作.
# ※ 1量子ビット目が, ↑ もしくは ↓ に 変わるはず.
# 3. 2量子ビット目に, X ゲート を 操作.
# ※ 2量子ビット目が, ↑ もしくは ↓ に 変わるはず.
# -> 1量子ビット目, 2量子ビット目の操作結果によって, 
# ↑↑(00, つまり, q0 = 0, q1 = 0), ↑↓(01, つまり, q0 = 0, q1 = 1), 
# ↓↑(10, つまり, q0 = 1, q1 = 0), ↓↓(11, つまり, q0 = 1, q1 = 1) の 4種類 の 出力結果があり得る.
"""Use the custom gate in a circuit."""
for y in range(5):
  circuit = cirq.Circuit()
  op_1 = RotationGate(theta = np.around(0.1 * (y + 1), 3)).on(q0)
  op_2 = RotationGate(theta = np.around(0.2 * (y + 1), 3)).on(q1)
  circuit.append([op_1, op_2])
  circuit.append([cirq.measure(q0, key='q0'), cirq.measure(q1, key='q1')])
  print("Circuit with a custom rotation gate: ", y, "times")
  print(circuit)
  
  # Simulate 10 times.
  simulator = cirq.Simulator()
  results = simulator.run(circuit, repetitions=10)
  
  # Output result.
  print(results)
  print("")

[編集内容(RotationGate)]

import numpy as np

import cirq

"""Define a custom gate with a parameter."""

class RotationGate(cirq.Gate):

def __init__(self, theta):

super(RotationGate, self)

self.theta = theta

def _num_qubits_(self):

return 1

def _unitary_(self):

return np.array([

[np.cos(self.theta), np.sin(self.theta)],

[np.sin(self.theta), -np.cos(self.theta)]

]) / np.sqrt(2)

def _circuit_diagram_info_(self, args):

return f"R({self.theta})"

# Pick two qubits.

q0, q1 = cirq.GridQubit(0, 1), cirq.GridQubit(2, 3)

# 以下のように理解.

# 1. ↑↑(2量子ビット, 00 と見る) を用意.

# 2. 1量子ビット目に, X ゲートを操作.

# ※ 1量子ビット目が, ↑ もしくは ↓ に変わるはず.

# 3. 2量子ビット目に, X ゲートを操作.

# ※ 2量子ビット目が, ↑ もしくは ↓ に変わるはず.

# -> 1量子ビット目, 2量子ビット目の操作結果によって,

# ↑↑(00, つまり, q0 = 0, q1 = 0), ↑↓(01, つまり, q0 = 0, q1 = 1),

# ↓↑(10, つまり, q0 = 1, q1 = 0), ↓↓(11, つまり, q0 = 1, q1 = 1) の 4種類の出力結果があり得る.

"""Use the custom gate in a circuit."""

for y in range(5):

circuit = cirq.Circuit()

op_1 = RotationGate(theta = np.around(0.1 * (y + 1), 3)).on(q0)

op_2 = RotationGate(theta = np.around(0.2 * (y + 1), 3)).on(q1)

circuit.append([op_1, op_2])

circuit.append([cirq.measure(q0, key='q0'), cirq.measure(q1, key='q1')])

print("Circuit with a custom rotation gate: ", y, "times")

print(circuit)

# Simulate 10 times.

simulator = cirq.Simulator()

results = simulator.run(circuit, repetitions=10)

# Output result.

print(results)

print("")

[出力結果]
Circuit with a custom rotation gate:  0 times
(0, 1): ───R(0.1)───M('q0')───

(2, 3): ───R(0.2)───M('q1')───
q0=0000000000
q1=0010000000

Circuit with a custom rotation gate:  1 times
(0, 1): ───R(0.2)───M('q0')───

(2, 3): ───R(0.4)───M('q1')───
q0=0000000000
q1=0000100010

Circuit with a custom rotation gate:  2 times
(0, 1): ───R(0.3)───M('q0')───

(2, 3): ───R(0.6)───M('q1')───
q0=0100000000
q1=0000000100

Circuit with a custom rotation gate:  3 times
(0, 1): ───R(0.4)───M('q0')───

(2, 3): ───R(0.8)───M('q1')───
q0=0000000000
q1=1000110101

Circuit with a custom rotation gate:  4 times
(0, 1): ───R(0.5)───M('q0')───

(2, 3): ───R(1.0)───M('q1')───
q0=0100010000
q1=1011111111
-> シュミレート結果 は, プログラム実行ごとに違った値が出力される.

[出力結果]

Circuit with a custom rotation gate: 0 times

(0, 1): ───R(0.1)───M('q0')───

(2, 3): ───R(0.2)───M('q1')───

q0=0000000000

q1=0010000000

Circuit with a custom rotation gate: 1 times

(0, 1): ───R(0.2)───M('q0')───

(2, 3): ───R(0.4)───M('q1')───

q0=0000000000

q1=0000100010

Circuit with a custom rotation gate: 2 times

(0, 1): ───R(0.3)───M('q0')───

(2, 3): ───R(0.6)───M('q1')───

q0=0100000000

q1=0000000100

Circuit with a custom rotation gate: 3 times

(0, 1): ───R(0.4)───M('q0')───

(2, 3): ───R(0.8)───M('q1')───

q0=0000000000

q1=1000110101

Circuit with a custom rotation gate: 4 times

(0, 1): ───R(0.5)───M('q0')───

(2, 3): ───R(1.0)───M('q1')───

q0=0100010000

q1=1011111111

-> シュミレート結果は, プログラム実行ごとに違った値が出力される.

From a known decomposition

decomposition を使うサンプル

[編集内容(decomposition)]
import numpy as np
import cirq

class MySwap(cirq.TwoQubitGate):
  def __init__(self):
    super(MySwap, self)

  def _decompose_(self, qubits):
    a, b = qubits
    yield cirq.CNOT(a, b)
    yield cirq.CNOT(b, a)
    yield cirq.CNOT(a, b)

  def _circuit_diagram_info_(self, args):
    return ["CustomSWAP"] * self.num_qubits()

my_swap = MySwap()

# Pick two qubits.
q = [cirq.GridQubit(0, 1), cirq.GridQubit(2, 3)]

"""Use the custom gate in a circuit."""
for y in range(3):
  circuit = cirq.Circuit()
  op_1 = cirq.X(q[0]) ** 0.52
  # TypeError: on() argument after * must be an iterable, not GridQubit
  op_2 = my_swap.on(*q)
  circuit.append([op_1, op_2])
  circuit.append([cirq.measure(q[0], key='q0'), cirq.measure(q[1], key='q1')])
  print("Circuit: ", y, "times")
  print(circuit)
  
  # Simulate 10 times.
  simulator = cirq.Simulator()
  results = simulator.run(circuit, repetitions=10)
  
  # Output result.
  print(results)
  print("")

[編集内容(decomposition)]

import numpy as np

import cirq

class MySwap(cirq.TwoQubitGate):

def __init__(self):

super(MySwap, self)

def _decompose_(self, qubits):

a, b = qubits

yield cirq.CNOT(a, b)

yield cirq.CNOT(b, a)

yield cirq.CNOT(a, b)

def _circuit_diagram_info_(self, args):

return ["CustomSWAP"] * self.num_qubits()

my_swap = MySwap()

# Pick two qubits.

q = [cirq.GridQubit(0, 1), cirq.GridQubit(2, 3)]

"""Use the custom gate in a circuit."""

for y in range(3):

circuit = cirq.Circuit()

op_1 = cirq.X(q[0]) ** 0.52

# TypeError: on() argument after * must be an iterable, not GridQubit

op_2 = my_swap.on(*q)

circuit.append([op_1, op_2])

circuit.append([cirq.measure(q[0], key='q0'), cirq.measure(q[1], key='q1')])

print("Circuit: ", y, "times")

print(circuit)

# Simulate 10 times.

simulator = cirq.Simulator()

results = simulator.run(circuit, repetitions=10)

# Output result.

print(results)

print("")

[出力結果]
Circuit:  0 times
(0, 1): ───X^0.52───CustomSWAP───M('q0')───
                    │
(2, 3): ────────────CustomSWAP───M('q1')───
q0=0000000000
q1=0001111011

Circuit:  1 times
(0, 1): ───X^0.52───CustomSWAP───M('q0')───
                    │
(2, 3): ────────────CustomSWAP───M('q1')───
q0=0000000000
q1=0000100101

Circuit:  2 times
(0, 1): ───X^0.52───CustomSWAP───M('q0')───
                    │
(2, 3): ────────────CustomSWAP───M('q1')───
q0=0000000000
q1=0111001011
-> シュミレート結果 は, プログラム実行ごとに違った値が出力される.

[出力結果]

Circuit: 0 times

(0, 1): ───X^0.52───CustomSWAP───M('q0')───

│

(2, 3): ────────────CustomSWAP───M('q1')───

q0=0000000000

q1=0001111011

Circuit: 1 times

(0, 1): ───X^0.52───CustomSWAP───M('q0')───

│

(2, 3): ────────────CustomSWAP───M('q1')───

q0=0000000000

q1=0000100101

Circuit: 2 times

(0, 1): ───X^0.52───CustomSWAP───M('q0')───

│

(2, 3): ────────────CustomSWAP───M('q1')───

q0=0000000000

q1=0111001011

-> シュミレート結果は, プログラム実行ごとに違った値が出力される.

decomposition を使うサンプル

[編集内容(decomposition)]
import numpy as np
import cirq

class MyCCNOT(cirq.ThreeQubitGate):
  def __init__(self):
    super(MyCCNOT, self)

  def _decompose_(self, qubits):
    a, b, c = qubits
    yield cirq.CCNOT(a, b, c)
    yield cirq.CCNOT(c, b, a)

  def _circuit_diagram_info_(self, args):
    return ["Custom CCNOT"] * self.num_qubits()

my_ccnot = MyCCNOT()

# Pick three qubits.
q = [cirq.GridQubit(0, 1), cirq.GridQubit(1, 2), cirq.GridQubit(2, 3)]

"""Use the custom gate in a circuit."""
for y in range(3):
  circuit = cirq.Circuit()
  op_1, op_2 = cirq.X(q[0]) ** 0.5, cirq.X(q[1]) ** 0.6
  # TypeError: on() argument after * must be an iterable, not GridQubit
  op_3 = my_ccnot.on(*q)
  circuit.append([op_1, op_2, op_3])
  circuit.append([cirq.measure(q[0], key='q0'), cirq.measure(q[1], key='q1'), cirq.measure(q[2], key='q2')])
  print("Circuit: ", y, "times")
  print(circuit)
  
  # Simulate 10 times.
  simulator = cirq.Simulator()
  results = simulator.run(circuit, repetitions=10)
  
  # Output result.
  print(results)
  print("")

[編集内容(decomposition)]

import numpy as np

import cirq

class MyCCNOT(cirq.ThreeQubitGate):

def __init__(self):

super(MyCCNOT, self)

def _decompose_(self, qubits):

a, b, c = qubits

yield cirq.CCNOT(a, b, c)

yield cirq.CCNOT(c, b, a)

def _circuit_diagram_info_(self, args):

return ["Custom CCNOT"] * self.num_qubits()

my_ccnot = MyCCNOT()

# Pick three qubits.

q = [cirq.GridQubit(0, 1), cirq.GridQubit(1, 2), cirq.GridQubit(2, 3)]

"""Use the custom gate in a circuit."""

for y in range(3):

circuit = cirq.Circuit()

op_1, op_2 = cirq.X(q[0]) ** 0.5, cirq.X(q[1]) ** 0.6

# TypeError: on() argument after * must be an iterable, not GridQubit

op_3 = my_ccnot.on(*q)

circuit.append([op_1, op_2, op_3])

circuit.append([cirq.measure(q[0], key='q0'), cirq.measure(q[1], key='q1'), cirq.measure(q[2], key='q2')])

print("Circuit: ", y, "times")

print(circuit)

# Simulate 10 times.

simulator = cirq.Simulator()

results = simulator.run(circuit, repetitions=10)

# Output result.

print(results)

print("")

[出力結果]
Circuit:  0 times
(0, 1): ───X^0.5───Custom CCNOT───M('q0')───
                   │
(1, 2): ───X^0.6───Custom CCNOT───M('q1')───
                   │
(2, 3): ───────────Custom CCNOT───M('q2')───
q0=0000000000
q1=1111111011
q2=1110110000

Circuit:  1 times
(0, 1): ───X^0.5───Custom CCNOT───M('q0')───
                   │
(1, 2): ───X^0.6───Custom CCNOT───M('q1')───
                   │
(2, 3): ───────────Custom CCNOT───M('q2')───
q0=0000000000
q1=1110101111
q2=1110101010

Circuit:  2 times
(0, 1): ───X^0.5───Custom CCNOT───M('q0')───
                   │
(1, 2): ───X^0.6───Custom CCNOT───M('q1')───
                   │
(2, 3): ───────────Custom CCNOT───M('q2')───
q0=0000100001
q1=1110011110
q2=1000001010
-> シュミレート結果 は, プログラム実行ごとに違った値が出力される.

[出力結果]

Circuit: 0 times

(0, 1): ───X^0.5───Custom CCNOT───M('q0')───

│

(1, 2): ───X^0.6───Custom CCNOT───M('q1')───

│

(2, 3): ───────────Custom CCNOT───M('q2')───

q0=0000000000

q1=1111111011

q2=1110110000

Circuit: 1 times

(0, 1): ───X^0.5───Custom CCNOT───M('q0')───

│

(1, 2): ───X^0.6───Custom CCNOT───M('q1')───

│

(2, 3): ───────────Custom CCNOT───M('q2')───

q0=0000000000

q1=1110101111

q2=1110101010

Circuit: 2 times

(0, 1): ───X^0.5───Custom CCNOT───M('q0')───

│

(1, 2): ───X^0.6───Custom CCNOT───M('q1')───

│

(2, 3): ───────────Custom CCNOT───M('q2')───

q0=0000100001

q1=1110011110

q2=1000001010

-> シュミレート結果は, プログラム実行ごとに違った値が出力される.

参照サイト

Custom gates

2021年3月17日

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

C++の練習を兼ねて, AtCoder Regular Contest 093 の問題D (Grid Components) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/arc093/editorial.pdf
// 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 board[101][101];

int main(){
    
    // 1. 入力情報.
    int A, B;
    scanf("%d %d", &A, &B);
    
    // 2. 上から K行 を 黒色.
    int K = (int)sqrt(max(2 * A, 2 * B)) + 2; // +1 だと, 02.txt などで, WA となる.
    rep(i, K) rep(j, K * 2) board[i][j] = 1;
    
    // 3. 上から (K - 1)行までで, (A - 1)個 を 白色 に 変更.
    int wRes = A - 1;
    rep(i, K - 1){
        repex(j, 0, K * 2, 2){
            // 残数ゼロならば終了.
            if(!wRes) break;
            
            // 白色に変更するマスを選択.
            if((i + j) & 1){
                // 残数をデクリメント.
                wRes--;
                
                // 白色に変更.
                board[i][j] = 0;
            }
        }
        // 残数ゼロならば終了.
        if(!wRes) break;
    }
    
    // 4. 下から (K - 1)行までで, (B - 1)個 を 黒色 に 変更.
    int bRes = B - 1;
    repx(i, K + 1, K * 2){
        repex(j, 0, K * 2, 2){
            // 残数ゼロならば終了.
            if(!bRes) break;
            
            // 黒色に変更するマスを選択.
            if((i + j) & 1){
                // 残数をデクリメント.
                bRes--;
                
                // 黒色に変更.
                board[i][j] = 1;
            }
        }
        // 残数ゼロならば終了.
        if(!bRes) break;
    }
    
    // 5. 出力.
    printf("%d %d\n", K * 2, K * 2);
    rep(i, K * 2){
        rep(j, K * 2) printf("%s", (board[i][j]) ? "#" : ".");
        puts("");
    }
    return 0;
    
}

// 解き直し.

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

// 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 board[101][101];

int main(){

// 1. 入力情報.

int A, B;

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

// 2. 上から K行を黒色.

int K = (int)sqrt(max(2 * A, 2 * B)) + 2; // +1 だと, 02.txt などで, WA となる.

rep(i, K) rep(j, K * 2) board[i][j] = 1;

// 3. 上から (K - 1)行までで, (A - 1)個を白色に変更.

int wRes = A - 1;

rep(i, K - 1){

repex(j, 0, K * 2, 2){

// 残数ゼロならば終了.

if(!wRes) break;

// 白色に変更するマスを選択.

if((i + j) & 1){

// 残数をデクリメント.

wRes--;

// 白色に変更.

board[i][j] = 0;

}

// 残数ゼロならば終了.

if(!wRes) break;

}

// 4. 下から (K - 1)行までで, (B - 1)個を黒色に変更.

int bRes = B - 1;

repx(i, K + 1, K * 2){

repex(j, 0, K * 2, 2){

// 残数ゼロならば終了.

if(!bRes) break;

// 黒色に変更するマスを選択.

if((i + j) & 1){

// 残数をデクリメント.

bRes--;

// 黒色に変更.

board[i][j] = 1;

}

// 残数ゼロならば終了.

if(!bRes) break;

}

// 5. 出力.

printf("%d %d\n", K * 2, K * 2);

rep(i, K * 2){

rep(j, K * 2) printf("%s", (board[i][j]) ? "#" : ".");

puts("");

}

return 0;

}

[入力例]
2 3

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

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

[入力例]
7 8

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

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

[入力例]
1 1

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

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

[入力例]
3 14

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

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

[入力例]
20 21

[出力例]
16 16
################
.#.#.#.#.#.#.#.#
################
.#.#.#.#.#.#.#.#
################
.#.#.###########
################
################
................
#.#.#.#.#.#.#.#.
................
#.#.#.#.#.#.#.#.
................
#.#.#.#.........
................
................

[入力例]
314 159

[出力例]
54 54
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#######################
######################################################
######################################################
######################################################
......................................................
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.........
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................

[入力例]
500 500

[出力例]
66 66
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.###########################################################
##################################################################
..................................................................
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#...........................................................

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

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

[入力例]

2 3

[出力例]

3 3

##.

..#

#.#

※AtCoderテストケースより

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

8 8

########

.#######

########

........

#.#.....

........

[入力例]

7 8

[出力例]

3 5

#.#.#

.#.#.

#.#.#

※AtCoderテストケースより

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

12 12

############

.#.#.#.#.#.#

############

............

#.#.#.#.#.#.

............

#...........

............

[入力例]

1 1

[出力例]

4 2

※AtCoderテストケースより

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

6 6

######

......

[入力例]

3 14

[出力例]

8 18

..................

....##.......####.

....#.#.....#.....

...#...#....#.....

..#.###.#...#.....

.#.......#..#.....

#.........#..####.

※AtCoderテストケースより

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

14 14

##############

.#.###########

##############

..............

#.#.#.#.#.#.#.

..............

#.#.#.#.#.#...

..............

[入力例]

20 21

[出力例]

16 16

################

.#.#.#.#.#.#.#.#

################

.#.#.#.#.#.#.#.#

################

.#.#.###########

################

................

#.#.#.#.#.#.#.#.

................

#.#.#.#.#.#.#.#.

................

#.#.#.#.........

................

[入力例]

314 159

[出力例]

54 54

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#######################

######################################################

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.........

......................................................

[入力例]

500 500

[出力例]

66 66

##################################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#