読者です 読者をやめる 読者になる 読者になる

AOJで最近解いた問題

AOJ-ICPCの250~500くらいの問題を何問か復習(自分用)。
 2200 Mr.リトー郵便局
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2200
 りとうさんが郵便局を巡る。ただし、陸路と海路があり、船が一台しかないので船の場所を考える必要がある。順番は与えられる。

 一見巡回セールスマンみたいですが順番が与えられるので多項式時間に落ちます。あらかじめワーシャルフロイドかなにかで陸・海別々に最短距離を求めてから
dp[i][j] := (経路の)i番目まで回って船がjにあるときの最短距離
とすると

        REP(i, 1, R) rep(j, N){
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + (ll)land[z[i - 1]][z[i]]);
            rep(k, N)
              dp[i][k] = min(dp[i][k], dp[i - 1][k] + (ll)land[z[i - 1]][j] + (ll)sea[j][k] + (ll)land[k][z[i]]);
        }

で解けます。オーバーフローに注意。
 面白い問題でしたが、陸路だけのときは下の更新式で処理できないことに気づけずハマってしまいました。

 2011 Gather the maps!
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011
 memo[i][j] := iさんはjさんと会っている可能性がある
というのを総当りで更新していくみたいな感じで解きました。これも面白かったです。

vector<int> f[30];
bool memo[50][50];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, _t, _f;
    while(cin >> N && N){
        rep(i, 30) f[i].clear();
        memset(memo, 0, sizeof(memo));
        rep(i, N) memo[i][i] = true;
        rep(i, N){
            cin >> _t;
            rep(j, _t){
                cin >> _f;
                f[_f - 1].push_back(i);
            }
        }
        rep(i, 30){
            for(int k : f[i])
              for(int l : f[i])
                rep(j, N)
                  memo[k][j] |= memo[l][j];
            for(int k : f[i])
              if(count(memo[k], memo[k] + N, 1) == N){
                  cout << i + 1 << endl;
                  goto success;
              }
        }
        cout << -1 << endl;
        continue;
      success: continue;
    }
    return 0;
}

2254 Fastest Route
ビットDP

2301 Sleeping Time
 普通に探索を書いた後に枝刈り。二分探索は上界と下界の間の値しか出せないので枝刈りでかなり計算量が落ちます。

const double EPS = 1.0e-10;
int K;
double UB, LB, P, E, T;
double dfs(double lb, double ub, int turn){
    if(T + E + EPS < lb) return 0.0;
    if(ub < T - E - EPS) return 0.0;
    if(T - E + EPS < lb && ub < T + E - EPS) return 1.0;
    double mid = (lb + ub) / 2;
    if(turn == 0)
      return abs(T - mid) <= (EPS + E) ? 1.0 : 0.0;
    double res = 0.0;
    double p1 = 1.0 - P, p2 = P;
    if((T - EPS) <= mid) swap(p1, p2);
    res += dfs(mid, ub, turn - 1) * p1;
    res += dfs(lb, mid, turn - 1) * p2;
    return res;
}
int main(){
    scanf("%d%lf%lf%lf%lf%lf", &K, &LB, &UB, &P, &E, &T);
    printf("%.10f\n", dfs(LB, UB, K));
    return 0;
}

2176 For the Peace
 これ貪欲で解けるのか……。貪欲はどうしても苦手です。要復習。

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
int N, D;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int _t, _s;
    while(cin >> N >> D && N){
        vector<int> m[100];
        vector<int> sum(N, 0);
        rep(i, N){
            cin >> _t;
            rep(j, _t){
                cin >> _s;
                m[i].push_back(_s);
                sum[i] += _s;
            }
        }
        while(true){
            bool updated = false;
            rep(i, N)
              while(m[i].size()){
                  sum[i] -= m[i].back();
                  if(*max_element(sum.begin(), sum.end()) - sum[i] <= D){
                      m[i].pop_back();
                      updated = true;
                  }else{
                      sum[i] += m[i].back();
                      break;
                  }
              }
            if(!updated) break;
        }
        rep(i, N - 1) sum[i + 1] += sum[i];
        if(sum[N - 1] == 0)
          cout << "Yes" << endl;
        else
          cout << "No" << endl;
    }
    return 0;
}

めちゃくちゃ適当な内容になってしまいましたがこのへんで。