AtCoder Beginner Contest 269 備忘録

考え方を記録しておくため、atcoderのABC問題解いた時のメモを記録、公開。
茶色コーダー、趣味勢です。

#目次
- [1. 所感と成績](#1-所感と成績)
- [2. ソースコード](#3-ソースコード)
    - [A問題](#a問題)
    - [B問題](#b問題)
    - [C問題](#c問題)
    - [D問題](#d問題)
    - [E問題](#e問題)

# 1. 所感と成績
|  問題 | 成績 | 回答時間 | 所感 |
| ---- | ---- | ---- | ---- |
| A | AC | 1分 | かんたん |
| B | AC | 6分 | かんたん |
| C | AC | 90分 | bit探索を使用。でかい数字の扱いでミス |
| D | 終了後AC | x分 | BFSでやる |
| E | 終了後AC | x分 | 2分探索を手動で実装 |

あとから見ても、概ね与し易い問題が多かった気がするが、Cで桁の大きい数字の扱いをミスしたのが致命的だった。
普段使用するbit探索関数もll対応に修正をしておく。
あとpow関数のように容易に数が大きくなる場合は、キャストすることを忘れないようにする。


# 2. ソースコード

# A問題
特に迷うところは無し。
```c++
int main(){
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    cout<<(a+b)*(c-d)<<endl;
    cout<<"Takahashi"<<endl;
}
```

# B問題
・「#」は必ず四角になる
・探索していって最初に#の位置を出す
・そこからいくつ#が縦、横に連なっているかを数える

```c++
int main(){
    vector<string> S;
    rep(i,0,10){
        string s;
        cin >> s;
        S.push_back(s);
    }
    ll a,b,c,d;
    bool flg=false;
    rep(i,0,10){
        if(flg==true){
            break;
        }
        rep(j,0,10){
            if(S[i][j]=='#'){
                a=i+1;
                c=j+1;
                rep(s,i,10){
                    if(S[s][j]=='.'){
                        b=s;
                        break;
                    }
                    if(s==9){
                        b=10;
                    }
                }
                rep(t,j,10){
                    if(S[i][t]=='.'){
                        d=t;
                        break;
                    }
                    if(t==9){
                        d=10;
                    }
                }
                flg=true;
                break;                
            }
        }
    }
    cout<<a<<" "<<b<<endl;
    cout<<c<<" "<<d<<endl;
 
}

```
# C問題
かなり大きい桁の計算になり、扱いでミスしてドはまりした。
アルゴ自体は15分くらいで考えたものであってたので、とてももったいない。

・2進数にした時、0じゃない桁を選んだ時の全組み合わせを列挙する問題と把握。
・1の数は15までに注目し、2^15のbit探索が計算時間に間に合うと判断。
・与えられたNを2進数にした時、各桁を検索してどの位置に1があるかを探索してvevtor Aに格納。
　探索する桁はlog2(N)なので高々60まで。
・bit全探索で1の位置の組み合わせを全列挙して、10進数に復号し出力。
　前述の通り、最大でも2^15通りまでなので時間内の計算に間に合う。
・0は必ず条件を満たすのに注意。

【ハマりポイント】
・最初のNの2進数桁を検索する際、if(n&(1<<i))だとiが50以上どか大きくなった時に桁オーバーでNG。
　if(n&(1LL<<i))とlong longで18桁まで受けられるようにしないとあかん。
・pow(2,A[i])も同じで、long longで受けないとだめ。
　ll(pow(2,A[i]))とキャストするなどして受けれればおｋ。


```c++
int main(){
    ll n;
    cin>>n;
    vector<ll>A;
    ll len=log2(n);
 
    for(ll i=0;i<len+1;i++){
        if(n & (1LL<<i)){
            A.push_back(i);
        }
    }
    ll m=A.size();
    cout<<"0"<<endl;
    //
    for(ll bit=0;bit<=(1<<m);bit++){
        ll x=0;
        for(ll i=0;i<m;i++){
            if(bit & (1<<i)){
             //llでキャストしないと計算ずれる。
                x=x+ll(pow(2,A[i]));
                
            }
        }
        if(x==0){
            continue;
        }
        cout<<x<<endl;
    }    
}
```
# D問題
(9/20追記)
BFSの典型問題という感想。
n<1000なので、ﾗﾌに探索しても大丈夫そう。
ｽﾀｰﾄ地点を全探索し、BFSして訪問済みの点をPvisにset。
Pvis.countで訪問済み時かどうかを判定して、未訪問時は次の点から再度BFSを繰り返す。
スタートをする時にcntをｲﾝｸﾘﾒﾝﾄしていけばｽﾀｰﾄ点数＝島の数になる。

```c++
int main(){
    ll n;
    cin>>n;
    set<pair<ll,ll>>Ps;
    set<pair<ll,ll>>Pvis;
    rep(i,0,n){
        ll x,y;
        cin>>x>>y;
        pair<ll,ll>p={x,y};
        Ps.insert(p);
    }
    ll cnt=0;
    for(auto p:Ps){
        queue<pair<ll,ll>>Q;
        if(Pvis.count(p)==1){
            continue;
        }
        cnt++;
        Q.push(p);
        while(Q.empty()==0){
            pair<ll,ll>p1=Q.front();
            Q.pop();
            if(Pvis.count(p1)==0){
                Pvis.insert(p1);
                rep(r,-1,2){
                    rep(s,-1,2){
                        if(r+s==0){
                            continue;
                        }
                        
                        pair<ll,ll>p2={p1.first+r,p1.second+s};
                        if(Pvis.count(p2)==0 && Ps.count(p2)==1){
                            Q.push(p2);
                        }
                    }
                }
            }
        }
    }       
    cout<<cnt<<endl;
}
```
# E問題
インタラクティブ問題でした。
やることがX方向とY方向の二分探索だと気づけば割と簡単。
収束条件さえ間違えなければおｋ

```c++
int main(){
    ll n;
    cin>>n;
    ll Xma=n;
    ll Xmi=1;
    ll Yma=n;
    ll Ymi=1;
    ll x,y;
    rep(i,0,20){
        cout<<"?"<<" "<<Xmi<<" "<<(Xmi+Xma)/2<<" "<<1<<" "<<n<<endl;
        ll ans;
        ll a=(Xma+Xmi)/2-Xmi+1;
 
        cin>>ans;
        if(ans!=a){
            Xma=(Xma+Xmi)/2;
        }
        else{
            Xmi=(Xmi+Xma)/2+1;
        }
        if(Xmi==Xma){
            x=Xmi;
            break;
        }
    }
    rep(i,0,20){
        cout<<"?"<<" "<<1<<" "<<n<<" "<<Ymi<<" "<<(Ymi+Yma)/2<<endl;
        ll ans;
        ll a=(Yma+Ymi)/2-Ymi+1;
 
        cin>>ans;
        if(ans!=a){
            Yma=(Yma+Ymi)/2;
        }
        else{
            Ymi=(Ymi+Yma)/2+1;
        }
        if(Ymi==Yma){
            y=Ymi;
            break;
        }
    }    
    cout<<"!"<<" "<<x<<" "<<y<<endl;
}
```