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

C++の練習を兼ねて, AtCoder Beginner Contest 269 の問題E (Last Rook) を解いてみた.

■感想.
1. 問題Eは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題Eで, 二分探索(応用版, 評価関数のインタラクティブ対応) の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題E／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 main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 評価関数.
    auto f = [&](int a, int b, int c, int d, int e) -> bool {
        // 2-1. 質問.
        printf("? %d %d %d %d\n", a, b, c, d);
        fflush(stdout);
        
        // 2-2. 応答.
        int T;
        scanf("%d", &T);
        
        // 2-3. 判定結果.
        return e ? (T == d - c + 1) : (T == b - a + 1);
    };
    
    // 3. 二分探索で確認してみる(行).
    int l = 1, h = N, X = -1;
    while(l + 1 <= h){
        int m = (h + l) >> 1;
        if(f(l, m, 1, N, 0)){
            l = m + 1;
            X = h;
        }else{
            h = m;
            X = l;
        }
    }
    
    // 4. 二分探索で確認してみる(列).
    l = 1, h = N;
    int Y = -1;
    while(l + 1 <= h){
        int m = (h + l) >> 1;
        if(f(1, N, l, m, 1)){
            l = m + 1;
            Y = h;
        }else{
            h = m;
            Y = l;
        }
    }
    
    // 5. 出力.
    assert(X != -1 && Y != -1);
    printf("! %d %d\n", X, Y);
    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 main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 評価関数.

auto f = [&](int a, int b, int c, int d, int e) -> bool {

// 2-1. 質問.

printf("? %d %d %d %d\n", a, b, c, d);

fflush(stdout);

// 2-2. 応答.

int T;

scanf("%d", &T);

// 2-3. 判定結果.

return e ? (T == d - c + 1) : (T == b - a + 1);

};

// 3. 二分探索で確認してみる(行).

int l = 1, h = N, X = -1;

while(l + 1 <= h){

int m = (h + l) >> 1;

if(f(l, m, 1, N, 0)){

l = m + 1;

X = h;

}else{

h = m;

X = l;

}

// 4. 二分探索で確認してみる(列).

l = 1, h = N;

int Y = -1;

while(l + 1 <= h){

int m = (h + l) >> 1;

if(f(1, N, l, m, 1)){

l = m + 1;

Y = h;

}else{

h = m;

Y = l;

}

// 5. 出力.

assert(X != -1 && Y != -1);

printf("! %d %d\n", X, Y);

return 0;

}

※インタラクティブな問題のため, 入出力は, デバッグ時に使用したものを記載している.

[入力例]
2
1
1

[出力例]
? 1 1 1 2
? 1 2 1 1
! 2 2

[入力例]
2
0
1

[出力例]
? 1 1 1 2
? 1 2 1 1
! 1 2

[入力例]
2
1
0

[出力例]
? 1 1 1 2
? 1 2 1 1
! 2 1

[入力例]
2
0
0

[出力例]
? 1 1 1 2
? 1 2 1 1
! 1 1

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

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

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

[出力例]
? 1 5 1 10
? 1 3 1 10
? 4 4 1 10
? 1 10 1 5
? 1 10 1 3
? 1 10 4 4
! 5 5

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

[出力例]
? 1 6 1 12
? 7 9 1 12
? 7 8 1 12
? 7 7 1 12
? 1 12 1 6
? 1 12 7 9
? 1 12 10 11
? 1 12 10 10
! 8 11

※インタラクティブな問題のため, 入出力は, デバッグ時に使用したものを記載している.

[入力例]

[出力例]

? 1 1 1 2

? 1 2 1 1

! 2 2

[入力例]

[出力例]

? 1 1 1 2

? 1 2 1 1

! 1 2

[入力例]

[出力例]

? 1 1 1 2

? 1 2 1 1

! 2 1

[入力例]

[出力例]

? 1 1 1 2

? 1 2 1 1

! 1 1

[入力例]

[出力例]

? 1 4 1 7

? 1 2 1 7

? 3 3 1 7

? 1 7 1 4

? 1 7 5 6

? 1 7 5 5

! 4 6

[入力例]

[出力例]

? 1 5 1 10

? 1 3 1 10

? 4 4 1 10

? 1 10 1 5

? 1 10 1 3

? 1 10 4 4

! 5 5

[入力例]

[出力例]

? 1 6 1 12

? 7 9 1 12

? 7 8 1 12

? 7 7 1 12

? 1 12 1 6

? 1 12 7 9

? 1 12 10 11

? 1 12 10 10

! 8 11

■参照サイト
UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)

C++の練習を兼ねて, AtCoder Beginner Contest 269 の 問題E (Last Rook) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 269 の問題E (Last Rook) を解いてみた.

コメントを残すコメントをキャンセル