JOI2017/2018予選

いよいよ待ちに待った予選ということで皆さんどうだったでしょうか
僕は2:00からモンハンワールドをやり、3:30就寝、9:00起きという規則的な生活を行いコンディションを整えました
多分発売されたらMHW買うと思います

予選開始直前にはコンビニへ赴き(5回(1回誤解に変換されて悲しい)ぐらい趣に変換されて悲しい)カフェラテとチョコを買いました
美味しかったです(飲食してる暇ありませんでしたが)

1問目

微誤読を行い場合分け必要そうな微難を感じたため読み直すと必要ないとわかる

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    cout << min((N+A-1)/A*B, (N+C-1)/C*D) << endl;
}

2問目

なんかいつものだなぁという気分になるので数えて+1する

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    int m[110] = {};
    int sum[110] = {};
    cin >> N;
    REP(i, N)
        cin >> m[i];
    int res= 0;
    REP(i, N){
        if(m[i])
            sum[i+1] = sum[i]+m[i];
        else
            sum[i+1] = 0;
        res = max(res, sum[i+1]);
    }
    cout << res+1 << endl;
}

3問目

何も考えず全探索
何も考えないので2問目より簡単そう

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int H, W;
    int A[30][30];
    cin >> H >> W;
    REP(i, H){
        REP(j, W){
            cin >> A[i][j];
        }
    }
    ll res = INF_LL;
    REP(i, H){
        REP(j, W){
            ll sum = 0;
            REP(s, H){
                REP(t, W){
                    sum += min(abs(s-i)*A[s][t], abs(t-j)*A[s][t]);
                }
            }
            res = min(res, sum);
        }
    }
    cout << res << endl;
}

4問目

DPの添字どう取るか迷いはじめて迷う
dp[i][j][k] := i個目まで見ているときにi-j個目からi個目までが繋がってて最小値kのときの差
みたいなのをやりたくなるけどなんかkが大きくなりそうみたいな気持ちになり不可能ではみたいな気持ちになる
そこで最大値の最小化であることに気づく
二分探索だね！*1
適当に差の限界を決めると、左端を固定したらその範囲に収められるかを典型DPで出来ることに気づく
ここで左端はsum(Li)/2+1ぐらいまでで良さそうなのでそうする

int N;
int L[1010], sL[1010] = {};;

bool isok(int len){
    FOR(mini, 1, sL[N]/2+1){
        bool dp[52][52] = {};
        dp[0][0] = 1;
        REP(i, N){
            REP(j, i+1){
                dp[i+1][j+1] = dp[i+1][j+1] | dp[i][j];

                int l = sL[i+1]-sL[i-j];
                if(i == N-1 && j == N-1) continue;
                dp[i+1][0] = dp[i+1][0] | (dp[i][j] && mini <= l && l <= mini+len); 
            }
        }
        if(dp[N][0])
            return 1;
    }
    return 0;
}

int main(void){
    cin >> N;
    REP(i, N)
        cin >> L[i];
    REP(i, N)
        sL[i+1] = L[i]+sL[i];

    ll l = 0, r = 1000, m;
    while(r-l > 1){
        m = (l+r)/2;
        if(isok(m))
            r = m;
        else
            l = m;
    }
    
    cout << (isok(l) ? l : r) << endl;
}

5問目

あーダイクストラね、はいはい、いつもの五問目*2、となる
ある地点までの距離dとそこに行けるようになるまでの時間tを持てば移動にかかる時間がわかりできそうとなるができない
なんか切りたいやつまでの距離によってtとdどっちが小さいほうが嬉しいか変わることに気づく
その地点までの距離dによって最短時間tが求まるねとなるので拡張ダイクストラっぽくやりたくなるのでやる
実質ヘビのJOIくん

int H, W;
int A[31][31] = {};
ll dp[31][31][911] = {};

int dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0};

PLLL mkpll(ll a, ll b, ll c, ll d){
    PLLL p = {a, {b, {c, d}}};
    return p;
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> W;
    REP(i, H){
        REP(j, W){
            fill(dp[i][j], dp[i][j]+911, INF_LL);
            cin >> A[i][j];
        }
    }
    priority_queue<PLLL, vector<PLLL>, greater<PLLL> > pq;
    pq.push({0, {0, {0, 0}}});
    dp[0][0][0] = 0;
    while(pq.size()){
        ll t = pq.top().fs, d = pq.top().sc.fs, y = pq.top().sc.sc.fs, x = pq.top().sc.sc.sc; pq.pop();
        REP(i, 4){
            if(y+dy[i] < 0 || x+dx[i] < 0 || y+dy[i] >= H || x+dx[i] >= W) continue;
            int yy = y+dy[i], xx = x+dx[i], tt = (d*2+1)*A[yy][xx]+t;
            if(dp[yy][xx][d+1] > tt && d+1 < H*W){
                dp[yy][xx][d+1] = tt;
                pq.push(mkpll(tt, d+1, yy, xx));
            }
        }
    }
    ll res = INF_LL;
    REP(i, 911){
        res = min(res, dp[H-1][W-1][i]);
    }
    cout << res << endl;
}

タプル使いたいなぁとなった

6問目

最初最小値だと思って簡単かも！となるがK番目だと気づく
調べたらなんかBITとかでできそうとなるためそれで39点取れる(ここで相当手間取った)
冷静に考えると想定解O(N log N)だろうしにぶたんが何処かで関わってくるだろという気持ちになる
適当に値Xを決めると、X以下の数がK番目の数になる区間の数はO(N)ぐらいで求められそうなことに気づく
この時点で残り15分ぐらい
焦って書くけど間に合わないね
終わった後考えたけど判定関数がうまくいってなさそうなのにどこがダメかわからない
誰か助けてください

int N, K, L;
ll cnt[214514] = {};
vector<ll> a(N);

bool isok(ll x){
    int r = 0;
    ll cnt = 0;
    ll sum = 0;
    REP(l, N){
        while(r < N && cnt < K){
            if(a[r] <= x)
                cnt++;
            r++;
        }
        if(cnt < K){
            return sum >= L;
        }
        sum += N-r+1;
        if(a[l] <= x)
            cnt--;
    }
    return sum >= L;
}


int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K >> L;
    a.resize(N);
    REP(i, N)
        cin >> a[i];
    ll sum = 0;
    int l = 0, r = N+1, m;
    while(r-l > 1){
        m = (l+r)/2;
        if(isok(m)){
            r = m;
        }else{
            l = m;
        }
    }
    while(!isok(l))
        l++;
    cout << l << endl;

}

360点だった去年とは違いドキドキしなくて済みそうなので気が楽
自明な部分点は6問目の6点だけな気がするので(部分点だけで考えてないからわかんないけど) ボーダーは306+αかなという気持ち

*1:想定解は普通のDPっぽい

*2:去年は6問目でしたね