hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

AOJ DPL_1_G: Knapsack Problem with Limitations

個数制限付きナップザック問題です。

問題概要

原文 → Knapsack Problem with Limitations | Aizu Online Judge

価値  v_i で重さ  w_i であるような  N 種類の品物と、容量が  W のナップザックがある。

 i 番目の品物は  m_i 個まで使用できる。

ナップザックの容量を超えないように品物を入れた時の価値の最大値を求めよ。

解説

各品物について、品物を  1 個入れたとき、 2 個入れたとき・・・と愚直に  1 ずつ増やして考えていくと計算量的に間に合いません。

そこで、繰り返し二乗法のように(厳密には少し違うけど)、取る数を  2 倍ずつ増やしていくことで考えていきましょう。

例えば品物が  13 個ある場合は、この場合ですと

  • 品物を  1 個入れたとき
  • 品物を  2 個入れたとき
  • 品物を  4 個入れたとき
  • 品物を  6 個入れたとき

をそれぞれ計算するというわけですね。これで計算量が  O(NW \log m) となり間に合います。

ソースコード

for 文の向きに気をつけましょう。

signed main() {
    int N, W; cin >> N >> W;
    int v[110], w[110], m[110];
    rep(i,0,N) cin >> v[i] >> w[i] >> m[i];

    int dp[10010] = {};
    rep(i,0,N) {
        // take key good(s) each
        for(int k=0; m[i]>0; k++) {
            int key = min(m[i], (int)(1<<k));
            m[i] -= key;
            for(int j=W; j>=key*w[i]; j--) {
                // do not take or take
                dp[j] = max(dp[j], dp[j-key*w[i]] + key*v[i]);
            }
        }
    }
    int ans = 0;
    repq(i,0,W) ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}

AOJ 1335: Equal Sum Sets

たとえ簡単な DP でも一発で通ると嬉しいよね。

問題概要

原文 → Equal Sum Sets | Aizu Online Judge

 n 以下の相異なる自然数  k 個の合計が  s となる組み合わせの総数を求めよ。

  •  1 \leqq n \leqq 20
  •  1 \leqq k \leqq 10
  •  1 \leqq s \leqq 155

解説

 n 以下の各数字  i について、 i を使うときと使わないときを考えてみます。

  •  i を使うときは、合計が  i 増え、使う数字の数は  1 増える
  •  i を使わないときは、合計は変わらず、使う数字の数も変わらない

これを用いて DP を書きます。計算量  O(nks) です。

ソースコード

signed main() {
    int N, K, S;
    while(cin >> N >> K >> S, N || K || S) {
        // dp[i][j][k] := i 以下の数字を j 個使って k を作る組み合わせ
        int dp[25][25][255] = {};
        dp[0][0][0] = 1;
        repq(i,1,N) {
            repq(j,0,K) {
                repq(k,0,S) {
                    // i を使うと 合計は i 増える
                    if(k - i >= 0 && j != 0) dp[i][j][k] += dp[i-1][j-1][k-i];

                    // i を使わないと 合計は変わらない
                    dp[i][j][k] += dp[i-1][j][k];
                }
            }
        }
        cout << dp[N][K][S] << endl;
    }
    return 0;
}

にしてもAOJ-ICPCでこれ150点なのかー。・・・と思ってたけどよく考えたら  n が20までしかないからビットで全列挙できるか。

TopCoder SRM 705 Div2 Med (Div1 Easy): AlphabetOrder

(追記: Div1 Easy と Div2 Med が完全に同じ問題なのでタイトルを変更しました)

今回のSRMは大勝利したので嬉しい。Medが個人的に良問だと思ったので記事を書きます。

問題概要

原文 → TopCoder Statistics - Problem Statement

英小文字のみで構成された文字列がいくつか与えられる。各文字列について、先頭から順に見た時にアルファベットが昇順に並んでいるような文字列は「良い文字列」と呼ばれる。アルファベットの順番を適切に定義したとき、全ての文字列を「良い文字列」にできるならば Possible を、できないならば Impossible を出力せよ。

解説

愚直解法 (アルファベットの順番を全て試す) は、 26! 通りもあるため当然試せません。

そこで、グラフに落として考えてみましょう。文字列の  i 文字目から  j 文字目  (i < j) に向かって、有向辺を張ります。これを全ての  (i, j) の組み合わせについて行います。

例えば、文字列 abcd の場合は、以下のようになります。

f:id:tsutaj:20170112153832p:plain

常に左側のノードから右側のノードに向かって辺を張っているため、グラフが DAG になっていることがわかりますね。

さて、このグラフに意地悪をしてみましょう。文字列 ba を考えます。この文字列と abcd の1文字目・2文字目を考慮すると、明らかに全ての文字列を「良い文字列」にすることができませんね。実際に辺を張るとどうなるでしょうか?

f:id:tsutaj:20170112153835p:plain

このように、閉路ができてしまいます。閉路があるということは、アルファベットの順番を指し示していたはずの矢印がぐるぐる回っていることになりますので、Impossible であることと同義ですね。

以上より、この方針で解いていけばよいです。

  • 各文字列に対して、  0 \leqq i < j < 文字数 を満たす全ての  (i, j) の組み合わせを考え、(  i 文字目のアルファベット)  \rightarrow (  j 文字目のアルファベット) の方向に有向辺を張る
  • できたグラフが DAG であれば Possible で、DAG でなければ Impossible

あとは DAG の判定をどうするかですが、これについては過去に @Darsein 先生から教えを受けていたのでした。

トポロジカルソートは入次数0のノードと、そのノードから出ている辺をどんどん消していくことで得られます。閉路があると入次数0 のノードがいずれ出来なくなるので、閉路判定は トポロジカルソートの結果のサイズがグラフの頂点数と等しいかどうか でできるというわけです。今回の問題の場合、連結でないグラフができる場合がありますが、閉路さえなければトポロジカルソートのサイズは頂点数と等しくなるので問題ないです。

ちなみに、ワーシャルフロイドでも閉路判定できるのですが、連結でないグラフの場合少し面倒なことに加え、頂点数が多くなると TLE するのでイマイチです。(この問題の場合は TLE しませんが)

ソースコード

トポロジカルソートのソースコードは省略します。

class AlphabetOrderDiv2 {
    public:
    string isOrdered(vector<string> words) {
        Graph(int) G(26);
        set<int> s;
        rep(i,0,words.size()) {
            rep(j,0,words[i].length()) {
                int d = words[i][j] - 'a';
                s.insert(d);
                rep(k,j+1,words[i].length()) {
                    int d2 = words[i][k] - 'a';
                    if(d != d2) {
                        G[d].pb(Edge<int>(d2, 1));
                    }
                }
            }
        }

        vector<int> v = tpsort_Kahn(G);
        if(v.size() != 26) return "Impossible";
        else return "Possible";
    }
};

次で青になれたらいいなあ・・・

東京工業大学プログラミングコンテスト2015 D: 文字列と素数

競プロに逃げすぎてレポートが進みません。

問題概要

原文 → D: 文字列と素数 - 東京工業大学プログラミングコンテスト2015 | AtCoder

文字列  S が与えられる。各文字を、同じ文字は同じ数字・違う文字は違う数字になるように '1', '3', '5', '7', '9' のいずれかに変換する。文字列を素数に変換できるならばその素数を出力し、できないならば -1 を出力せよ。

解説

map と permutation を使って全探索するだけです。next_permutation とかそんなに使わないので備忘録的に書きました。

文字列を反転させておくことで計算が楽になります。文字列から数字にしたりとか、桁数がやたら多かったりとかするときはこれで幸せになることが多い気がします。

ソースコード

bool isprime(int n) {
    if(n == 1) return false;
    for(int i=2; i*i<=n; i++) {
        if(!(n%i)) return false;
    }
    return true;
}

signed main() {
    string s; cin >> s;
    map<char, int> m;
    int cnt = 0;
    reverse(s.begin(), s.end());
    rep(i,0,s.length()) {
        if(!m.count(s[i])) {
            m[s[i]] = cnt++;
        }
    }

    if(cnt > 5) {
        cout << -1 << endl;
        return 0;
    }
    int a[] = {1, 3, 5, 7, 9};
    do {
        int d = 1;
        int num = 0;
        rep(i,0,s.length()) {
            num += d * a[ m[s[i]] ];
            d *= 10;
        }
        if(isprime(num)) {
            cout << num << endl;
            return 0;
        }
    }while(next_permutation(a, a+5));
    cout << -1 << endl;
    return 0;
}

AOJ 0037: Path on a Grid

バグが取れなくて相当苦労した。

問題概要

原文 → 格子状の経路 | Aizu Online Judge

格子の各辺が壁であるかどうかの情報が与えられる。壁に右手をついたまま1周するときの経路を出力せよ。

解説

前回の記事 と同様の方法で解いてみました。

今見ている方向を  k とおくと、

  • 右手に壁がない場合、 (k+1) \% 4 の方向に向き直す
  • 進行方向に壁がある場合、 ( (k - 1 + 4) \% 4 の方向に向き直す

というように動けばよいです。終了条件にも気をつけましょう。

ソースコード

#define S 6
// right, down, left, up
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int main() {
    bool board[S][S][4] = {};
    rep(i,0,9) {
        int l, n;
        if(i % 2 == 0) l = 4;
        else l = 5;
        rep(j,0,l) {
            scanf("%1d", &n);
            if(n == 1) {
                if(i % 2 == 0) {
                    board[i/2][j+1][1] = true;
                    board[i/2+1][j+1][3] = true;
                }
                else {
                    board[i/2+1][j][0] = true;
                    board[i/2+1][j+1][2] = true;
                }
            }
        }
    }

    string d = "RDLU";
    string ret;
    int dir = 0;
    int nx = 0, ny = 1;
    for(int i=0; i<150; i++) {
        if(nx == 1 && ny == 0 && dir == 2) break;
        if(nx == 0 && ny == 0 && dir == 3) break;
        int x, y;
        x = nx + dx[dir], y = ny + dy[dir];
        if(board[nx][ny][(dir + 1) % 4] == 0) {
            dir = (dir + 1) % 4;
            nx = nx + dx[dir], ny = ny + dy[dir];
        }
        else if(board[nx][ny][dir] == 1) {
            ret += d[dir];
            dir = (dir - 1 + 4) % 4;
        }
        else {
            ret += d[dir];
            nx = x, ny = y;
        }
    }
    cout << ret << endl;
    return 0;
}

自分の実装の方法が悪いのか、バグ直しに相当時間がかかってしまった・・・。他の実装方法も考えたい。まずは enum 使って書きなおしたほうがいいよなあ。

ICPC 国内予選 2010 B: 迷図と命ず

あけましておめでとうございます。私はひたすら AOJ-ICPC を埋めています。

実装が面倒だなあこれ・・・と思ったのでほぼ自分用記事を書きます。

問題概要

原文 → Amazing Mazes | Aizu Online Judge

 H、横  W の迷路が与えられる。迷路の壁の情報が与えられるので、スタートからゴールまでの最短距離を求めよ。ゴールに辿りつけない迷路の場合は  0 を出力せよ。

解説

解法としてはもちろん幅優先探索なんですが、今回は迷路の「壁」が与えられるため少し面倒です。いつもの方針と少し違う配列を持つ必要があります。

board[i][j][k] := 座標(i, j) において方向 k に動けるか という bool 配列を用意します。これさえ用意できればあとは普通に探索するだけです。が、バグが怖いですね。

ソースコード

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

signed main() {
    int h, w;
    while(cin >> w >> h, h || w) {
        bool board[40][40][4];
        rep(i,0,h) rep(j,0,w) rep(k,0,4) board[i][j][k] = true;

        rep(i,0,h) board[i][0][3]   = false; // left
        rep(i,0,h) board[i][w-1][2] = false; // right
        rep(i,0,w) board[0][i][1]   = false; // up
        rep(i,0,w) board[h-1][i][0] = false; // down

        int inp;
        rep(i,0,2*h-1) {
            int l;
            if(i % 2 == 0) l = w-1;
            else l = w;
            rep(j,0,l) {
                cin >> inp;
                if(inp == 1) {
                    if(i % 2 == 0) {
                        board[i/2][j][2] = false;
                        board[i/2][j+1][3] = false;
                    }
                    else {
                        board[i/2][j][0] = false;
                        board[i/2+1][j][1] = false;
                    }
                }
            }
        }

        int dist[40][40];
        rep(i,0,h) rep(j,0,w) dist[i][j] = INF;
        dist[0][0] = 1;
        queue<pii> q;
        q.push(pii(0, 0));

        while(!q.empty()) {
            pii t = q.front(); q.pop();
            rep(i,0,4) {
                if(!board[t.fr][t.sc][i]) continue;
                int x = t.fr + dx[i];
                int y = t.sc + dy[i];
                if(dist[x][y] <= dist[t.fr][t.sc] + 1) continue;
                dist[x][y] = dist[t.fr][t.sc] + 1;
                q.push(pii(x, y));
            }
        }

        if(dist[h-1][w-1] == INF) cout << 0 << endl;
        else cout << dist[h-1][w-1] << endl;
    }
    return 0;
}

なんか壁与えられる問題他にもあった気がする。

ICPC アジア地区予選 2014 F: There is No Alternative

今年ももう終わりですね。

問題概要

原文 → http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2014/F.pdf

重み付き無向グラフ  G(V, E) が与えられる。 G最小全域木に必ず含まれる辺はいくつあるか? 重みの総和と共に出力せよ。

  •  3 \leqq V \leqq 500
  •  V-1 \leqq E \leqq min(50000, \frac{V(V-1)}{2})

解説

まず、普通に最小全域木を求めてしまいます。説明のため、ここで使われる辺の集合を  H最小全域木のコストを  c とします。

 H に含まれない辺は、最小全域木を構成する時に必要なかった辺ですので、「最小全域木に必ず含まれる辺」になりえないことは明らかです。以下、 H の各要素  e について考えます。

最小全域木に必ず含まれる辺  e というのは、言い換えれば「その辺  e がないと最小全域木が作れない」ということです。したがって、以下を試せばよいです。

  •  e 以外の辺で最小全域木をつくろうとしてみる
  • 最小全域木ができなければ (連結でなければ) 、その辺は「必ず含まれる辺」である
  • 最小全域木はできるが、そのコストが  c より大きければ、その辺は「必ず含まれる辺」である

 H の要素数は高々  |V| - 1 しかありませんので、各辺を無視した最小全域木計算のループは  |V| - 1 回です。

クラスカル法を用いれば、辺のソート  O(|E| \log |V|)、各辺を無視した最小全域木計算  O(|V| |E|) より、実行時間内に解くことができます。

ソースコード

プリム法、Union-Find木のソースコードは省略します。

signed main() {
    int n, m; cin >> n >> m;
    Graph(int) G(n);
    vector< Edge<int> > es;
    int s, d, c;
    rep(i,0,m) {
        cin >> s >> d >> c; s--; d--;
        G[s].pb(Edge<int>(s, d, c));
        G[d].pb(Edge<int>(d, s, c));
        es.pb(Edge<int>(d, s, c));
        es.pb(Edge<int>(s, d, c));
    }
    pii ans = pii(0, 0);
    pair< int, vector< Edge<int> > > v = prim(G);
    sort(es.begin(), es.end());
    int E = es.size();
    rep(i,0,v.sc.size()) {
        UnionFind uf(n);
        int res = 0;
        for(int j=0; j<E; j++) {
            Edge<int> e = es[j];
            if(e.to == v.sc[i].from && e.from == v.sc[i].to) continue;
            if(e.to == v.sc[i].to && e.from == v.sc[i].from) continue;
            if(!uf.same(e.from, e.to)) {
                uf.unite(e.from, e.to);
                res += e.cost;
            }
        }

        int par = -1;
        for(int j=0; j<n; j++) {
            if(par == -1) par = uf.find(j);
            else if(par != uf.find(j)) res = INT_MAX;
        }

        if(res > v.fr) {
            ans.fr++;
            ans.sc += v.sc[i].cost;
        }
    }
    printf("%lld %lld\n", ans.fr, ans.sc);
    return 0;
}

ただのライブラリ貼るだけ問題じゃないので、好きな問題です。この手の問題たくさん解けるようになりたいですね。

おそらくこれが今年最後の投稿になるでしょう。良いお年を。