NOSSの雑記

主に競プロでやったことを書きます。

ICPC2021国内予選参加記

参加記 ICPC

チーム Royal Blue としてICPC2021国内予選に参加しました。
私としては5度目の参加で最後のICPC大会になります。

チームメイト

  • NOSS: 自分
  • mhrb: チームとして組むのは3度目。一番チーム歴が長い。
  • Rogi: 確かICPC初参加だけど、部内予選1位。いつのまにか幾何を解いている。

開始前

家に16:00頃に着く。
16:30開始なので部屋の整理とお菓子のチョコレートの準備をし、16:15頃からチームと通話をつなぐ。
とりあえず4完を全力で頑張ろうという感じで準備していたらいつの間にか開始時間になっていた。

大会本番

16:30と同時にコンテストページを更新するとアクセスできず「おや？」となる。（去年もこんなことがあったような...）
ちょっとすると本番の問題一覧が表示された。

初動はAをRogi、Bをmhrb、Cを自分が担当。

C問題は構文木が与えられて自由に根や子の配置を操作してよいので式を評価したときの値を最大化せよ、という問題。
とりあえず、根が固定なら葉から順に決まるのでよい。問題は根を取り替えるときで、頂点数 n が小さいなら根を全部試して O(n2)。でも、nが最大3*105くらいはありそうだしダメそう。全方位木DPをやれればできる...できるなあ。 でも、C問題で構文解析+全方位木DPは実装エグくないか...？

その間にAが通る。Bもちょっとバグってたぽいけど通る。

自分は「C考察はできたけど実装やばいので...後は任せます」とだけ報告してCの実装に張り付く。
Dを2人が通してくれることを祈る。

...

Cの実装に四苦八苦していると、いつの間にか開始1時間が経っていた。
もっと楽な実装の解法があるのではないかと疑心暗鬼になりながら順位表を眺めるとCを通しているチームが1桁程度しかいないことがわかり、「本当に実装するしかない」ことを確信する。

一方、Dは考察が難航しているらしく雲行きがよくない。

Cの実装途中で各ノードの最大値だけでなく、最小値も持たないといけないことに気づき、少し実装がやり直しになりつらくなる...

Cの実装がつらかったので気分転換にDの概要を聞く。ぱっと見では貪欲に降順ソートすればよさそうだけどSample2が反例らしい。たしかに...

...

開始2時間経過、ようやくＣのサンプルが通り、一通りの実装を終えたのでテストケースを実行させる。 しかし、実行が終わらないケースを発見する。無限実装編から無限デバッグ編へ突入...

チームメイトにCのコードを投げつつコードとにらめっこをしていると、

for(auto i : vec){
    ...
    for(auto i : vec){
        ...
    }
}

みたいなヤバい個所を発見し(？？？)、内側のループを消すとテストケースが秒で終了する。 提出すると無事AC！(開始2時間30分経過)

残り30分しかなく、全力でDが解けることに賭けることに。

Rogi君が貪欲で通らないSample2の解を全列挙してくれていて、

4 3 3 3 3 4 3 3 1 
3 4 3 3 3 4 3 3 1 
3 3 4 3 3 4 3 3 1 
4 3 3 3 3 1 4 3 3 
3 4 3 3 3 1 4 3 3 
3 3 4 3 3 1 4 3 3 
3 3 1 4 3 3 4 3 3 
3 1 3 4 3 3 4 3 3

をぐっと睨むと、周期3でなにかあるっぽい。
試しに mod3 で和をとってみると割と平均化されているっぽい...?
数列を3等分...?
3つの箱を用意しておいて値を順次加算していく。1操作ですべての箱の値を-1する。操作回数の最大値は...?
値を3つの集合に分割したときの総和の最小値の最大化！→ DP！→ 解けた！！！

この解法を思いついたのが終了15分前くらいで、思いついたときは本当に体が震えた。 急いで解法を2人に共有し、 「～で解けました。え、僕の言ったこと分かりましたか？じゃあ全員同時実装して一番早かった人が出しましょう！」 で実装を始める。

実装を終え、終了3分前くらいでサンプルが合う！！！
自分が一番早かったっぽいのでテストケースを実行する。
そしてテストケース1が...通った！！！ （このときもう感情がやばかった*1）
急いでテストケース2をダウンロードして実行する。

そして...AC！！！
提出する瞬間はマウスを握る手が震えて、心臓はバクバクして音が耳から聞こえそうだったしヤバかった。通った瞬間は歓喜のあまり叫んだ。

実際にDが通ったのは終了51秒前だった。

f:id:NOSS:20211106011232p:plain
順位表

結果

チーム Royal Blue の順位は ABCD 4完 38位 (学内1位) でした。

順当に行けば無事に国内予選突破です！

大会後

自分のDのサンプルがあった直後にRogi君も実装が終わったらしく、後にテストケースを試した感じACっぽいらしい。最悪私がWAでもなんとかなっていたのかもしれない。

同じ大学のチームの方々と感想戦をして、解法の共有だったりEの考察を話したりした。Dのブザービートを決めて興奮してたのでちょっとうるさかったかもしれない。

感想

過去最高にギリギリの4完だった。最後通ったのでめでたしだけど、試合経過2時間30分くらいまで絶望だった。大会後の感想戦の感じだと、もう少し時間の使い方を良くすればEも通せていた気がする。

反省点としては、自分がずっと2時間半もCに張り付いていたせいでDの考察を手伝えずチーム全体が停滞してしまっていた。今回オンラインで通話をつないでの参加でしたが、ちゃんと連絡を取り合わないとチームメイトが何をしているかわからないので、気を付けないといけないなと感じた。

とはいえ、最後のICPCでも国内予選を突破できたのはめっちゃくちゃ嬉しいし、終了1分前にDを通せたのはめちゃくちゃ熱かった。 連絡手段がチャット・通話のみという環境の中戦ってくれたチームメイトに感謝。皆さん横浜大会オンサイトで会いましょう。

*1:開始直後のシステム障害で1分終了時間が延長されていたのに気づいておらず、手元の時計だと残り1分を切っていた

ICPC 2020 Asia Yokohama Regional Contest 参加記

ICPC 参加記

NOSS, まほろば, まつしたの3人で横浜国立大学チームChabashiraとしてICPC2020アジア地区横浜大会に参加しました。

1日目

受付・開会式

zoomでカメラ越しに学生証を提示して本人確認をしました。
実は、ずっとオンラインのみで活動していたためチームメンバー全員の顔を見たのはこの受付のタイミングが初めてでした。

リハーサル

問題概要や考察をGoogle Documentに書きこんで共有する仕組みを導入してみたところかなり良かったので採用。

問題自体は去年のリハーサルの問題と同じだったのできっちりリベンジはしました。
Dで配列のサイズを間違えてREを出したのは本当に反省。

2日目

コンテスト

A,Bが比較的容易、C以降難易度ランダムのため Aをまつした君、Bをまほろば君に任せて、C以降をNOSSが読んでいく作戦。

C...ぱっと見やばそう。全くいい性質が見えないので飛ばす。
D...問題は非常にシンプル。ただ、点の数が多すぎるのでわからない。
E...明らかに幾何。読まずに飛ばす。
F...やや幾何。問題を読んでも特に何も方針が立たない。

ここでAのヘルプが来たので概要を聞くと、n * n * nの立方体から0の部分を削除して最後に投影図が成り立つか確認すればよさそうなのでそれを伝えて実装を任せる。

まほろば君がBを提出するとWAだったのでデバッグを手伝う。ここif elseじゃないとダメじゃないですか？等言っていたら色々自分で気づいたらしくいつの間にかACしていた。

Aの実装が破滅した報告が来たので、入力を逆順にすると配列の先頭と原点が一致するので楽そう、と伝える。まほろば君が詳細なデバッグにまわってくれた。

Jがかなり解かれているので読む。若干読解がむずいがナッツをとなりの頂点に押し出していくっぽい。木なので根からDFSすればよさそうなので実装する。やや実装に手間取ってしまい時間をとられるがAC。

この間に他の2人がG,H,Iの概要をまとめてくれた。

Hはgcdとlcmは素因数ごとのmin,max操作に置き換えられるから...？までいってそれ以上思考が進まず。

Gは連結成分がたくさんあって異なるグループ間でつなぎあう感じ。
頂点数vの連結成分は他方の連結成分をv-1減らせるのでl_iの値が小さいグループをa、他方をbとして(aの頂点数)-(aの連結成分の個数)+1>=(bの連結成分の個数)ならよさそう。
連結成分の個数はl_iが小さい順に見ていくとUF木でわかって、逆側もやれば両方のグループがわかる。
チームメイトに判定式があってそうか聞くと反例や正当性を確かめてくれたのでその間に実装だけ進める。

実装が終わるころには大丈夫そうという結論になったようでサンプルもあったので提出　-> WA...

l_iが同じ値の頂点がたくさんあったときにやばかったのでそこを直すとAC。

残り1:30:00で解けそうなのを探すとIがどう見てもDPなので頑張る。
考察するうちに数え上げPDFに載っていた問題を思い出したのでみんなで読む。

たぶん、こういう遷移だよなあ。とりあえず3乗で書くか。いやこの状態もつだけだとだめじゃね？と、みんなでうんうん唸る

最後にまほろば君に実装してもらったけどサンプルが合わずコンテスト終了。

解説・順位発表

去年と違い解説が日本語で聞けたので話は聞きやすかった。IがやっぱりDPなのが非常に悔しいのとCが左手法で解けてそれを5行で表現できると聞いたとき天才過ぎて感動した。

Yes/Noはやっぱり盛り上がった(Twitterが)

どのチームも凍結後にACを重ねられていて素晴らしかった。どこでこの差は生まれたのだろう...

僕たちのチームはABGJの4完で30位でした。
30位は企業賞としてLegalForce様からキーボートとノベルティTシャツがいただけるとのことで、初めての企業賞となりました。ありがとうございます！

その後は過半数のチームが6完していてすげーとなったり、eat_iceがどんどん上位に上っていくのが見れて楽しかった。そしてKINGのKINGっぷりがすごい。

f:id:NOSS:20210317225921j:plain

懇親会

Gather TownというレトロRPG風のサービス上で懇親会をしました。

以前の会津合宿で同じチームだったsutaさんと話をしてちょっとエモくなった。チームUHISHIROは個人的に注目していたチームの1つだったので6完を見たときは本当に驚いた。おめでとうございます。
その後もチームUHISHIROの方々やふるやんさんなどいろいろな方と話をさせていただいて楽しかったです。

感想

結果は40チーム中30位と上位には食い込めず、オンライン、並列PDならではの作戦や個人の競プロ技術をもっと磨いておけばなあと後悔はあります。
でも、競プロをチームで取り組んだり、競プロをしている方々のとの交流ができ、企業賞ももらえて、オンラインでありつつも非常に楽しいICPCでした。

参加権はあと1回ですがまた地区予選に来れるように頑張ります。

ECR102 1473F Strange Set

Codeforces フロー グラフ

問題

問題リンク：https://codeforces.com/contest/1473/problem/F

次を満たす集合 S を'strange'とする。

  • \forall i \in S, j \lt i \land a_i \% a_j = 0 \to j \in S

'strange'である集合 S に対し \sum_{i \in S} b_i の最大値を求めよ。

解法

いわゆる、「燃やす埋める問題」に落とし込めるので最小カットで解くことができる。

正負のペナルティは典型通り処理する。j \lt i \land a_i \% a_j = 0 のとき、iを選んでいるのにjを選んでいないことを禁止する辺を張る。

注意しないといけない点は、Dinic法の計算量は O(VE) だが、愚直に辺を張ると辺の数が最大 n^{2} 程度になるためDinic法が O(n^{3}) になる。
辺の数を削減するため、辺を張るときは a_j = k のうち最も大きい j に辺を張る。そうすると辺の数が n*\max(a) で抑えられる。

公式解説

Code

#include <bits/stdc++.h>
using namespace std;

template <typename T>
struct Dinic{
    // 行先、容量、逆辺の番号
    struct edge{
        int to, rev;
        T cap;
        edge() = default;
        edge(int to, T cap, int rev) : to(to), cap(cap), rev(rev) {}
    };
    std::vector<std::vector<edge> > G;
    std::vector<bool> used;
    std::vector<int> level, iter;

    Dinic() = default;
    Dinic(int n) : G(n), used(n), level(n), iter(n) {}
    
    T inf = std::numeric_limits<T>::max()/2;

    void init(int n){
        G.clear();
        G.resize(n);
        used.resize(n, false);
        level.resize(n);
        iter.resize(n);
    }

    void add_edge(int from, int to, T cap, bool directed = true){
        G[from].emplace_back(to, cap, int(G[to].size()));
        G[to].emplace_back(from, directed?0:cap, int(G[from].size())-1);
    }

    void bfs(int s){
        std::fill(level.begin(), level.end(), -1);
        std::queue<int> que;
        level[s] = 0;
        que.push(s);
        while(!que.empty()){
            int v = que.front();
            que.pop();
            for(edge &e : G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    // 増加路の探索
    T dfs(int v, int t, T f){
        if(v == t) return f;
        for(int &i = iter[v]; i<G[v].size(); i++){
            edge &e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                T d = dfs(e.to, t, std::min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    T max_flow(int s, int t, T lim){
        T flow = 0;
        while(1){
            bfs(s);
            if(level[t] < 0) break;
            std::fill(iter.begin(), iter.end(), 0);
            T f;
            while((f = dfs(s, t, lim)) > 0){
                flow += f;
                lim -= f;
            }
        }
        return flow;
    }
    T max_flow(int s, int t){return max_flow(s, t, inf);}
};

bool solve(){
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
    }
    Dinic<int> g(n+2);
    int S = n, T = n+1;  // in, out
    int ans = 0;
    for(int i=0;i<n;i++){
        int b;
        scanf("%d", &b);
        if(b < 0){
            g.add_edge(i,T,abs(b));
        }else{
            ans += b;
            g.add_edge(S,i,b);
        }
    }
    for(int i=0;i<n;i++){
        bool used[101]{};
        for(int j=i-1;j>=0;j--){
            if(a[i]%a[j]==0 && !used[a[j]]){
                g.add_edge(i,j,g.inf);
                used[a[j]] = true;
            }
        }
    }
    ans -= g.max_flow(S,T);
    printf("%d\n", ans);
    return false;
}

int main(){
    solve();
    return 0;
}

コメント

MLEしてから辺の数が多すぎることに気づいたので反省。フローの計算量をよく把握する。
辺を張るところで公式解説のコードのほうが賢い。

AOJ 2403 The Enemy of My Enemy is My Friend

AOJ グラフ

問題

問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2403

解法

頂点に重み付きの価値がついているグラフの最大独立集合を求める問題。

n \le 40 なので枝刈り探索によって解くことができる。具体的な枝刈り方法はwataさんのスライドのp.28以降を参照。

ただし、今回は頂点に重みがついているため「次数1以下は必ず使用」を「次数0は必ず使用」に変更する必要がある。また、グラフ全体が非連結であるケースがあることに注意する。

公式解説

Code

#include <bits/stdc++.h>
using namespace std;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int n;
vector<int> b;
vector<vector<int> > g;
map<string, int> id;
vector<bool> used, visited;

int rec(int v, bool must_use = false){
    int res = b[v];
    visited[v] = true;
    used[v] = true;

    // use v
    vector<int> ls;
    for(auto u : g[v]){
        if(!visited[u]){
            visited[u] = true;
            ls.push_back(u);
        }
    }
    for(int i=0;i<n;i++){
        if(!visited[i]){
            chmax(res, rec(i)+b[v]);
            break;
        }
    }
    for(auto u : ls){
        visited[u] = false;
    }
    // don't use v
    if(ls.size()>0 && !must_use){
        for(int i=0;i<n;i++){
            if(!visited[i]){
                chmax(res, rec(i));
                break;
            }
        }
    }
    visited[v] = false;
    return res;
}

bool solve(){
    cin >> n;
    if(n==0) return false;
    g.clear();
    g.resize(n);
    b.resize(n);
    id.clear();
    used.resize(n);
    visited.resize(n);
    vector<vector<string> > d(n);

    for(int i=0;i<n;i++){
        string s;
        int c;
        cin >> s >> b[i] >> c;
        id[s] = i;
        for(int j=0;j<c;j++){
            string t;
            cin >> t;
            d[i].push_back(t);
        }
    }
    for(int i=0;i<n;i++){
        for(auto s : d[i]){
            g[i].push_back(id[s]);
        }
    }
    cout << rec(0, true) << endl;
    return true;
}

int main(){
    while(solve());
    return 0;
}

コメント

一度探索した連結成分の使用済みフラグをつけるのを忘れていたことにしばらく気が付かなかったので反省

ICPC2020国内予選参加記

ICPC 参加記

チーム Chabashira (NOSS, まほろば, まつした)としてICPC国内予選に参加しました。

追記(2020/11/09)
チームメイトの参加記
- ICPC2020国内予選参加記 - まほろば精進日誌
- ICPC2020国内予選に出場しました｜MacaronBLOG

開始前

開始直前まで研究室のタスクがあって忙しく、前日はあまり眠る時間がとれなかった… 若干不安になりつつも時間のすきまにリハーサルのKを通したり、他人やチームメイトのライブラリを回収して準備。

コンテスト環境は完全オンラインでチームメイトと通話をつなぎながらやっていました。

コンテスト本番

16:30とコンテストページを更新するとアクセスできず「あれ？」となる。チームメイト全員がアクセスできずちょっと焦る。Twitterを覗きたい気持ちを抑えつつ運営との連絡方法などを確認していると徐々にサイトが復帰し始めたので待機。
16:40頃に突然問題が表示されコンテスト開始。

初動はAをまつした君、Bをまほろば君、Cを自分が担当。

Cは問題文は非常にシンプルで p=w*h*d のとき s=w+h+d の最小値を求める整数問題。0\lt p \lt 10^{15} なのでそれなりに高速なアルゴリズムが必要かもしれないと考える。(問題を読んだときはこれを思い出してよくない予感がした)
しかし、考えても何もわからず。これやばくね...？

この間にチームメイトが順調にA,Bを通す。
まだ自分がCの方針を立てられていないので模擬国内の反省1を活かし、まつした君をCのヘルプに呼んでDをまほろば君に読んでもらう。

Cでp^{1/3}の付近を探索する方針は p が素数のときに破綻するので、とりあえず愚直に約数列挙をするコードを実行してみようという話になる。
Cを解ける気持ちにならなかったので実装と実行をまつした君に丸投げお願いしてDに移る。

まほろば君からDの概要を聞くと構文解析系の問題なのでちょっと難しそう。この時点でCが詰まっていてDも通せないとなると予選突破は厳しいのでDを通すぞ！と心の中で気合を入れる。
Dを受け取り他の問題をまほろば君に任せる。

文字の種類数が n \le 16 であることからエスパーすると 2^{n} の計算量になりそう。なのでTSPのような順列を扱う系のbitDPにならないか考察する。
式から文字同士の前後関係を有向グラフに変換できないか？などの考察しても良い方法思いつかなかったので模擬国内Eを反省にして2冷静に条件を見直してみる。

式にはmin,max演算しか含まれないので実はかなり単純。2つの式の出力が一致するということだから各式の出力は知りたい。出力の通り数が少ないのでこちらを固定してみる。
するとある注目した文字が出力されるかどうかの判定は...その他の文字が注目した文字の前か後かのどちらにあるかだけわかっていればできる！！！
つまり文字を前後2つのグループに分ける方法を全探索すればよくそのときの通り数も簡単に計算できるので解ける！

念のためまほろば君に解法を確認してもらうと解けていると同意がもらえたのでさっそく実装にとりかかる。構文解析パートはこんなときのために実装の練習をしていたのでサッと実装ができた。精進していた過去の自分に感謝。
サンプルも無事に合ったので提出すると...AC！激アツ。
この時点でDを通しているチームは十数チームくらいしかいなかったのでかなり嬉しくなる。

あとはCを通せれば予選突破にかなり近づくのでCの状況をチームメイトに確認する。
約数を愚直にやっていく解法は実行が遅かったのでまほろば君が枝刈り高速化したコードを書いてくれたらしい。とりあえず実行してもらうとなぜかよくわからないが(？？？)割と速く実行が終わった

ここで伝家の宝刀「コンパイルオプション -O3 + 感謝の言葉」バイナリファイルに感謝の言葉をかけると実行速度が速くなることが知られている3のでチームみんなで通話越しにありがとう、ありがとうと唱えると無事にテストケースの実行が終了する。提出してもらうと...AC！ ありがとうC++のコンパイル最適化。

この時点で4完24位(学内1位)ぐらいでそれなりの速度で4完できたのでかなり気持ちが安らかになる。これはもしかしたら初の5完いけるのでは？という雰囲気になる。

Eはまほろば君がすでに考察を進めてくれていて点が4つのグループに分けられてそれぞれのグループはgrid状になっていることを聞く。ここまでだと30*30のサイズなので幅がもう半分の15程度だったらbitDPできるのになーとチームメイトに伝える。みんなで上手いこと幅を減らせないかと考えたけど結局ここから進まなかった。

順位表をみるとEよりFが通されているのでFをよむ。辺の切断は時刻を逆順にみると結合なのでUnionFindで管理できる。連結成分のサイズと最適地の候補の集合をうまいこと管理すればよさそうという話になる、が、怖いコーナーケースが見つかったりサイズの確認回数がO(NM)になる/ならないのような話がたくさんでてきて頭が壊れる。

正直なにもわからずE,Fを眺めていたら時間が経過...。

コンテスト終了5分前くらいにまほろばくんが永続UnionFindをつかった実装でFのサンプルがあったらしいので驚く。これで通ったらマジ天才だなと思いながら提出してもらうとWA... 出力形式や怪しい答えも出力していないと確認してもらったのでもはやここまで。コンテストが終了した。

結果

チーム Chabashira の結果は ABCD 4完 33位(学内1位) でした。

無事に国内予選突破です！

f:id:NOSS:20201107121950p:plain
横浜国立大学のチームの順位表

コンテスト後

同大学の他チームとも通話をつないで解法の共有をしたり感想を話したりした。他チームもCは約数列挙してゴリ押しだったぽい。ここで高度合成数の話を思い出したので調べてみると 10^{15} 以下では約数の個数は最大でも 2.5*10^{4} 程度らしい。この辺の話を知っておきながら、本番中に約数の個数が少ないことを指摘出来なかったのもしかして戦犯では？ EはTwitterで流れてきた解法が天才すぎて完敗。

感想

Cが解けなくても1人で固執せずにチームメイトに託してDを見れたのはとてもいいムーブだったと思う。おそらくあのままずっとCを考えてDに移っていなかったらもっと解くのが遅くなっていた。今後もやばくなったら積極的に投げていきたい。Fはもっと冷静に考えていれば解けたかもしれない。
全体としてはDの考察・実装ができたのでチームの中での役割を果たせたかなと思う。

連絡手段がチャット・通話のみという環境の中戦ってくれたチームメイトに感謝。横浜大会オンサイトで会いましょう。

  1. 模擬国内Cで実装をバグらせ延々とデバッグをしていた結果、自分がD以降の問題を見るのが遅れてしまったことがあった↩

  2. 落ち着いてvalidな条件を式で表すと2-SATであることがすぐにわかる問題だった↩

  3. 去年の国内予選でもN=1000のO(N3)をこれでゴリ押した↩

AOJ 1362 Do Geese See God?

AOJ 数え上げ 文字列 DP

問題

文字列Sを部分列に含む回文であって長さが最小であるもののうち、辞書順でk番目のものを求めよ。

問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1362

解法

まずは最小長さを求め、最小長さとなるような回文の個数を数え上げる。

最小長さは区間DPで求めることができる。 dp[l][r]=文字列Sの区間[l,r]を部分列に含む回文の最小長さ、と置く。 遷移はs[l]==s[r]ならばそのまま両端を取り除けるので dp[l][r]=dp[l+1][r-1]+2, s[l]!=s[r]ならば左端の文字を右端に補うかその逆をする必要があり dp[l][r]=min(dp[l][r-1]+2,dp[l+1][r]+2) となる。

回文の個数も同様に区間DPで求めることができる。 dp[l][r]=文字列Sの区間[l,r]を部分列に含む最小長の回文の個数、と置けばよい。 個数が非常に大きくなる可能性があるので数の上限をkより少し大きい値程度にしておく。 もし回文の個数がk未満なら解は存在しない。

辞書順でk番目を求めるときは外側の文字を区間DPと同じような遷移をしながら決めていく。 s[l]!=s[r]のとき辞書順に小さいものがk以上にならないように文字を追加していく。 最小長さとなるような操作のみに遷移を行うことに注意すること。

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long int;
constexpr int INF = 1<<30;

ll n ,k;
string s;

int dp[2005][2005];  // dp[l][r]: 文字列Sの区間[l,r]を部分列に含む回文の最小長さ
ll dp2[2005][2005];  // dp[l][r]: 文字列Sの区間[l,r]を部分列に含む最小長の回文の個数

// 回文の最小長さを求める [l,r]
int rec(int l, int r){
    if(l == r) return dp[l][r] = 1;
    if(l > r) return 0;
    if(dp[l][r] > 0) return dp[l][r];
    int res = INF;
    if(s[l] == s[r]) res = min(res, rec(l+1,r-1)+2);
    else{
        res = min(res, rec(l,r-1)+2);
        res = min(res, rec(l+1,r)+2);
    }
    return dp[l][r] = res;
}

// 回文の個数を数える [l,r]
ll rec2(int l, int r){
    if(l >= r) return dp2[l][r] = 1;
    if(dp2[l][r] >= 0) return dp2[l][r];
    ll res = 0;
    if(s[l] == s[r]){
        res += rec2(l+1,r-1);
    }else{
        if(dp[l][r] == dp[l][r-1]+2) res += rec2(l,r-1);
        if(dp[l][r] == dp[l+1][r]+2) res += rec2(l+1,r);
    }
    return dp2[l][r] = min(res, k+10);
}

// 辞書順でk番目を求める
string rec3(int l, int r, ll m){
    if(l == r) return s.substr(l,1);
    if(l > r) return "";
    string res;
    if(s[l] == s[r]){
        res = rec3(l+1,r-1, m);
        res.insert(res.begin(),s[l]);
        res.push_back(s[r]);
    }else{
        if(s[l] < s[r]){
            if(dp[l][r] != dp[l+1][r]+2 || dp2[l+1][r] <= m){
                res = rec3(l,r-1,m-(dp[l][r] != dp[l+1][r]+2 ? 0 : dp2[l+1][r]));
                res.insert(res.begin(),s[r]);
                res.push_back(s[r]);
            }else{
                res = rec3(l+1,r,m);
                res.insert(res.begin(),s[l]);
                res.push_back(s[l]);
            }
        }else{
            if(dp[l][r] != dp[l][r-1]+2 || dp2[l][r-1] <= m){
                res = rec3(l+1,r,m-(dp[l][r] != dp[l][r-1]+2 ? 0 : dp2[l][r-1]));
                res.insert(res.begin(),s[l]);
                res.push_back(s[l]);
            }else{
                res = rec3(l,r-1,m);
                res.insert(res.begin(),s[r]);
                res.push_back(s[r]);
            }
        }
    }
    return res;
}

int main(){
    cin >> s >> k;
    n = s.size();
    rec(0,n-1);
    for(int i=0;i<n;i++) fill(dp2[i], dp2[i]+n, -1);
    if(rec2(0,n-1) < k){
        cout << "NONE\n";
    }else{
        cout << rec3(0,n-1,k-1) << "\n";
    }
    return 0;
}

コメント

もう少しきれいに実装できるようにしたい。

AOJ 1302 Twenty Questions

AOJ DP

問題

m bitからなる異なる n 個のbit列が与えられる。1回の質問でbitを1つ明らかにできるとき最悪でも何回の質問でbit列を1つに特定できるか求めよ。

問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302

解法

まず前計算として、 cnt[S][T] = 質問したbitの集合がSでその結果がTであるようなbit列の個数、を求めます。TのSに含まれないbitは0としておきます。ここで S \supset T であることに注目すればS,Tの組は部分集合の列挙の方法を用いて 3^{m} で調べ上げられます。

次に dp[S][T] = 質問したbitの集合がSでその結果がTであるときの最小回数、としてDPを行います。遷移はSに含まれない i bit目を質問したとして、最悪ケースを考えるため質問結果が0,1のときのmaxをとって dp[S][T] = max(dp[S|1<<i][T], dp[S|1<<i][T|1<<i])+1 のようになります。

計算量は O\left(nm + (n+m) 3^{m}\right) になりました。

Code

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 1 << 30;

void chmin(int &a, int b){
    a = min(a, b);
}

int cnt[1<<11][1<<11], dp[1<<11][1<<11];

int solve(){
    int m, n;
    cin >> m >> n;
    if(m==0) return 1;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        for(int j=0;j<m;j++){
            a[i] |= (s[j]-'0')<<j;
        }
    }
    for(int S=0;S<1<<m;S++){
        for(int T=S;;T=(T-1)&S){
            cnt[S][T] = 0;
            dp[S][T] = INF;
            for(int i=0;i<n;i++){
                if((S&a[i])==T) cnt[S][T]++;
            }
            if(T==0) break;
        }
    }
    for(int S=(1<<m)-1;S>=0;S--){
        for(int T=S;;T=(T-1)&S){
            if(cnt[S][T]<=1){
                dp[S][T] = 0;
            }else{
                for(int i=0;i<m;i++){
                    if((S>>i)&1) continue;
                    chmin(dp[S][T], max(dp[S|1<<i][T], dp[S|1<<i][T|1<<i])+1);
                }
            }
            if(T == 0) break;
        }
    }
    cout << dp[0][0] << endl;
    return 0;
}

int main(){
    while(solve()==0);
    return 0;
}

コメント

bitの包含関係で頭を混乱させてしまったのでもっとスムーズに考察できるようにしたいです。