2016-09-17

Dividing Snacks　(お菓子の分割)

JOI非公式難易度表7の問題。結構、険しかった。
問題は読んで、どうぞ。
Dividing Snacks | Aizu Online Judge
DPであろうとは思ったけど、どんなふうにするか検討がつかない。
でもしばらく考えるとN個の長さ1mmのお菓子をAとBの二つのグループに分けていくと考えればよさそうということに気づく。
dp[N][Aに選んだ数][AかBか]でいけそう。
しかし制約が2<=N<=10000であるためMLE（険しい）
またしばらく考えてdp[i+1][...][...]がdp[i][...][...]によって決まるためdp配列を使いまわせることに気づく(勝った)

#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define FI first
#define SE second
using namespace std;
typedef pair<int,int> pii;
static const int inf = 1ll<<60;
static const int MAX_N = 10000;
int N;
int a[MAX_N+5];
int dp[2][MAX_N/2+5][2];
 
signed main(){
    cin>>N;
    for(int i=1;i<N;++i)cin>>a[i];
    for(int i=0;i<2;++i)for(int j=0;j<N/2;++j)for(int k=0;k<2;++k)dp[i][j][k]=inf;
    dp[0][0][0]=0;
    for(int i=0;i<N;++i){
        for(int j=0;j<N/2;++j){
            dp[(i+1)%2][j+1][0]=min(dp[i%2][j][0],dp[i%2][j][1]+a[i+1]);
            dp[(i+1)%2][j][1]=min(dp[i%2][j][0]+a[i+1],dp[i%2][j][1]);
        }
        for(int j=0;j<N/2;++j)dp[i%2][j][0]=dp[i%2][j][1]=inf;
    }
    cout<<min(dp[N%2][N/2][0],dp[N%2][N/2][0])<<endl;
}

2016-09-17

ABC041 徒競走

結構まえに解いた問題が好きだったので書く。
1～Nまでの番号のついたウサギが徒競走し、x番目がy番目より早く着くという情報がM個与えられる。
その情報にあうような着順が何通りあるか求める問題。
制約をみると1<=N<=16であったのですぐにbitDPを思いついた。
しかし僕はDPができないのでメモ化再帰をする。（弱い）

#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define FI first
#define SE second
using namespace std;
typedef pair<int,int> PII;
static const int inf = 1ll<<60;
static const int MAX_N = 16;
static const int MBIT = 1<<17;
int N;
int M;
int all;
int mem[MBIT];
vector<int> V[MAX_N+1];
 
int cal(int bit){
    int res=0;
    if(mem[bit]!=-1)return mem[bit];
    if(bit==0)return 1;
    for(int i=1;i<=N;++i){
        bool is=false;
        int b=1<<i;
        for(int j=0;j<V[i].size();++j){
            int k=1<<V[i][j];
            if(!(k&bit)){
                is=true;
                break;
            }
        }
        if(is)continue;
        if(bit&b){
            res+=cal(bit-b);
        }
    }
    return mem[bit]=res;
}
signed main(){
    memset(mem,-1,sizeof(mem));
    cin>>N>>M;
    for(int i=1;i<=N;++i)all+=pow(2,i);
    for(int i=0;i<M;++i){
        int x,y;
        cin>>x>>y;
        V[x].PB(y);
    }
    int ans=0;
    ans=cal(all);
    cout<<ans<<endl;
}

2015-12-16

JOI惨敗日誌

こんにちは。つよっしーというものです。JOI予選落ちの烙印をつけられるであろう人間です。まだ結果は出ていませんが4問目のソースコードを提出できてないと思います。（まぁ、ケース１しか通ってないので最高320点です。）悲しいですね。

1問目・・・やるだけ

2問目・・・やるだけ

3問目・・・戦犯。誤読しました。実際はやるだけっだったはず。

4問目・・・悲しい。考察する時間がなくO(n*t)しか書けなかった。

5問目・・・幅っぽいと思って少し考えて4問目に帰る。ここで4問目のソースコードを提出していないのに気付いて急いでアップロードを押したらコンテスト終了の画面に飛ばされる。悲しい(悲しい(悲しい))。某プロによるとやるだけらしい()。

6問目・・・悲しい。

JOIはDPがでると聞いていたけどグラフの問題がでて悲しみが単調増加しています。(6問目はDPっぽい？）この悲しみを晴らすためにデレステに5K課金しましたが悲しみが増えました。

いよいよ明日は結果発表ですがプロたちからのハラスメントによって結果をみる気力がないです。予選を通過したであろう人々は本選に向けて精進してください。最後に僕に人権をください。(終わります)