JOI2016/2017予選参加しました

JOI予選参加しました

心にとてつもないダメージを負ったため、一日遅れての投稿です。
おそらく380点取れてると思われます。
提出ミスしている可能性は考えていません。
してたら即死ですし、してなくてもおそらく死んでます。
私的な感想としては、JOI予選過去問の問題4まで解ければあとは部分点でいけると思っていて、
JOI非公式難易度表で難易度5を1,2週間前から埋め始めたんですがあれは何だったんだと、
どう考えても難易度5の問題が一つもなかったぞと

とりあえず一問ずつ適当にどうやったかです。

1問目

やるだけ

って言いたかったんですが、b<0のパターンを考えてしまったり、
0℃のときは凍ってる場合と凍ってない場合がある、の意味も悩んでしまったり
1問目の出力まで終わって提出するだけになったときに予選用につくったディレクトリをrmしてしまったり
そんなこんなで10分ぐらいかかってました
2問目より難しかったです

2問目

やるだけ

ソートしてうぇいでうぇい

3問目

ほぼやるだけ

縦に設置する場合と横に設置する場合を考えて、始点を(0, 0)〜(H-1, W-1)で数え上げただけ
だけどここまでで30分ぐらいかかってました
他のプロたちが10分とか15分とかで終わらせてる中でこれは辛かった

4問目

ここでキレかけた
てかキレました
完全にDPという決めつけで問題文読んだので、普通に最初は意味がわかりませんでした
そして焦ってDP以外を考えて、でも無理だってなって
つらい

それから一応bitDPでありそうだなって気づき
dp[M][1 << M]としてがんばったけどテストケース5は間に合いませんでした。

累積和をDPに活用するという発想があれば変わったかもしれないけど、
遅い原因がそこの数える部分とは思ってなかったのでダメだと思います
普通にコードも汚い

int main(void){
    int N, M;
    vector<int> shelf;
    int num[20];
    fill(num, num+20, 0);
    cin >> N >> M;
    vector< vector<int> > dp(M, vector<int>(1 << M, INF));
    REP(i, N){
        int a;
        cin >> a;
        num[a-1]++;
        shelf.push_back(a);
    }
    REP(i, M){
        dp[0][1 << i] = diff(shelf, 0, num[i], i+1);
    }
    FOR(i, 1, M){
        REP(j, 1 << M){
            bool used[20];
            int use_num = 0;
            int sum = 0;
            fill(used, used+20, false);
            REP(k, M){
                if(((1 << k) & j) == (1 << k)){
                    used[k] = true;
                    use_num++;
                    sum += num[k];
                }
            }
            if(use_num != i+1) continue;

            REP(k, M){
                if(!used[k]) continue;

                dp[i][j] = min(dp[i][j], dp[i-1][j ^ (1 << k)] + diff(shelf, sum-num[k], num[k], k+1));
            }
        }
    }
    cout << dp[M-1][(1 << M) - 1] << endl;
    return 0;
}

5問目

全マスからBFSでmapに入れてsize()が2以上ってやったらテストケース1が間に合ったにも関わらずWAった
死にそう
小さい方から数えて工夫してれば行けたらしくて辛い

6問目

すでに時間が30分ぐらいしか残ってない
とりあえず観るだけと思ってみて、誤読して唯のダイクストラ書いて無理で終了
必要な情報をどうにか持てばいけそうだとは思ったけどどう持つべきかわからなかった

来年があるので滅入らずにやっていきたいと思います