AtCoder Beginner Contest 266 備忘録

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

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

# 1. 所感と成績
|  問題 | 成績 | 回答時間 |所感 |
| ---- | ---- | ---- | ---- |
| A | 時間内AC | 1分 | いつもに増して簡単 |
| B | 時間内AC | 5分 | かんたん |
| C | 時間内AC | 54分| 普通。ベクトル的な問題に置き換え。 |
| D | 終了後AC | - | 時間内に終わらず。考え方は合ってた。 |
| E | 終了後AC | - | 時間内着手できず。Dより簡単な気がする。 |

DのDP構築に時間かかり、回答できなかったのが残念。
DPだなと気づけるまではよかったので、遷移条件を整理して実装、を練習しないとあかん。
Eのほうが簡単そうだったので、チラ見してみても良かったかもだが、ハマる可能性もあったので微妙。

# 2. ソースコード

# A問題
特に迷うところはなし。

```c++
int main(){
    string s;
    cin >> s;
    ll len=s.size();
    cout<<s[(len)/2]<<endl;
 
}
```


# B問題
迷わず。
```c++
int main(){
    ll n;
    cin>>n;
    rep(i,0,998244353+1){
        if((n-i)%998244353==0){
            cout<<i<<endl;
            return 0;
        }
    }
}
```
# C問題
三角形が凸、という表現は初めて知った。
4点から3点を選んで三角形を作り、残りの1点がその三角形の内側にあるかどうか、と読み替えた。
下記を参考にベクトル演算的な考え方で判定。

http://www.thothchildren.com/chapter/5b267a436298160664e80763

4点の取り方は4通りあるので、それぞれで判定。
全部やらんでもいい気がするけど、必要十分かすぐ判断できなかったので、
計算量もあきらかに多くないのでとりあえず4通りとも条件に入れておく。

もう少し早く回答したかった。

```c++
bool check(double p0x, double p0y, double p1x, double p1y, double p2x, double p2y, double px, double py){
    //(p0x, p0y),(p1x, p1y),(p2x, p2y)の三角形
    //(px, py)が判定したい点
    double Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);
    double s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
    double t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);
    
    if((0 < s && s < 1)){
        if((0 < t && t < 1)){
            if((0<1-s-t && 1-s-t<1)){
                return true; //Inside Triangle
            }
        }
    }
    // if((0.0 < s < 1.0) && (0.0 < t < 1.0) && (0.0 < 1-s-t < 1.0)){
    //     return true;
    // }
    else{
        return false;
    }
}
int main(){
    double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;
    cin >> Ax >> Ay >> Bx >> By >> Cx >> Cy >> Dx >> Dy;
    if(check(Ax,Ay,Bx,By,Cx,Cy,Dx,Dy) || check(Bx,By,Cx,Cy,Dx,Dy,Ax,Ay) || check(Cx,Cy,Dx,Dy,Ax,Ay,Bx,By)|| check(Dx,Dy,Ax,Ay,Bx,By,Cx,Cy)){
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;
 
}
```

# D問題
コンテスト後にAC。

位置が５個で固定、nは1E5で遷移していく条件っぽいのでDPだなとすぐに判断。
DP[i][j]を時刻tでjにいる時の最大のスコア　と定義。
jにいくのは前回と同じ位置か±1の位置からの遷移だけど、0,4の端っこの場合だけは範囲外参照にならないよう注意。
時刻tの時の各位置のうち最大値が答えになる。

余計な記述が多い。
記述増えるほど記載ミスによるバグがリスクになるので、
もう少し軽い記述を心がけたほうがいいかも。
考え方は時間内に考えてた方法であってたので、デバッグを早くするのと考えに至るのを早くする。

```c++
int main(){
    ll n;
    cin>>n;
    map<ll,ll> MP;
    vector<ll> T(n+1);
    vector<ll> X(n+1);
    vector<ll> A(n+1);
    ll t=0;
    map<ll,ll> MP2;
    rep(i,1,n+1){
        cin>>T[i]>>X[i]>>A[i];
        MP[T[i]]=A[i];
        MP2[T[i]]=X[i];
        t=max(t,T[i]);
    }
 
    vector<vector<ll>> DP(t+1,vector<ll>(5,0));
    DP[0][0]=0;
    rep(i,1,t+1){
        ll d=min(ll(5),i+1);
        rep(j,0,d){
            if(MP[i]!=0){
                if(MP2[i]==j){
                    DP[i][j]=max(DP[i][j],DP[i-1][j]+MP[i]);
                    if(j==0){
                        DP[i][j]=max(DP[i][j],DP[i-1][j+1]+MP[i]);
                    }
                    else if(j==4){
                        DP[i][j]=max(DP[i][j],DP[i-1][j-1]+MP[i]);
                    }
                    else{
                        DP[i][j]=max(DP[i][j],DP[i-1][j-1]+MP[i]);
                        DP[i][j]=max(DP[i][j],DP[i-1][j+1]+MP[i]);
                    }                    
                }
                else{
                    if(j==0){
                        DP[i][j]=max(DP[i][j],DP[i-1][j+1]);
                        DP[i][j]=max(DP[i][j],DP[i-1][j]);
                    }
                    else if(j==4){
                        DP[i][j]=max(DP[i][j],DP[i-1][j-1]);
                        DP[i][j]=max(DP[i][j],DP[i-1][j]);
                    }
                    else{
                        DP[i][j]=max(DP[i][j],DP[i-1][j+1]);
                        DP[i][j]=max(DP[i][j],DP[i-1][j-1]);
                        DP[i][j]=max(DP[i][j],DP[i-1][j]);
                    }                    
                }
            }
            else{
                if(j==0){
                    DP[i][j]=max(DP[i][j],DP[i-1][j+1]);
                    DP[i][j]=max(DP[i][j],DP[i-1][j]);
                }
                else if(j==4){
                    DP[i][j]=max(DP[i][j],DP[i-1][j-1]);
                    DP[i][j]=max(DP[i][j],DP[i-1][j]);
                }
                else{
                    DP[i][j]=max(DP[i][j],DP[i-1][j+1]);
                    DP[i][j]=max(DP[i][j],DP[i-1][j-1]);
                    DP[i][j]=max(DP[i][j],DP[i-1][j]);
                }
            }
        }
    }
    ll ans=0;
    rep(i,0,5){
        ans=max(ans,DP[t][i]);
    }
    cout<<ans<<endl;
 
}
```

# E問題
コンテスト後にAC。
題意を理解に１０分くらい考えた。
要はいつやめるのが特か？という点。
最大値は6なので、n→大で期待値も6に収束していきそうだなと直感的にわかる。
100×6くらいの計算量でやれそうと判断。

n+1回目にｻｲｺﾛを振った時の期待値をaとしている。
n=0のとき、かならず1回は振るのであきらかに期待値はa=3.5。

n=1のとき2回目にふるかふらないかの判断がはいる
・4,5,6が出た場合（a<j）はこれまでの期待値3.5に対して高い値。
　例えば4が出た時は振った場合は（4+3.5）/2=3.75となるので、振らないのが適正戦略になる。5,6も同様。
・1,2,3が出た場合（else）はこれまでの期待値3.5に対して低い値。
　例えば1が出た時は振った場合は（1+3.5）/2=2.25となるので、振るのが適正戦略。2,3も同様。
・これらの１～６のケースについて期待値を出して、aを更新。

これで100×6でのループができるのでOK


```c++
int main(){
    cout << fixed << setprecision(15);  
    ll n;
    cin>>n;
    double a=0.0;
    rep(i,0,n){
        double sum=0.0;
        rep(j,1,7){
            if(a<j){
                sum=sum+j;
            }
            else{
                sum=sum+a;
            }
        }
        a=sum/6;
    }
    cout<<a<<endl;
}

```