ABC293の解法と要点、感想(AからD問題まで)

はじめに

A,B,Cの3完で39:12+1ペナでした。
コンテスト後にDも解いたので、それについてもまとめておきます。
コンテスト成績証

なお、記事内で登場するコードには独自のテンプレートやマクロが含まれている場合があります。
それらの詳細については、お手数ですがこちらの記事をご確認ください。

A問題

問題文:

Diff: 12

どことなく処理内容が複雑な感じではありますが、A問題なだけあって制約が厳しく、問題文通り実装すれば解けます。
std::swapを用いて入れ替え処理を行うと簡潔に実装できます。

int main() {
    string s;
    cin >> s;
    REP(i,1,s.size()/2){
        swap(s[(i*2)-2],s[2*i-1]);
    }
    cout << s << el;
}

提出コード: https://atcoder.jp/contests/abc293/submissions/39603285

B問題

問題文:

Diff: 65

A問題と同様、問題文通り実装すればよいです。
ただし、Nの制約が緩くなっているので、毎回「まだ人iが呼ばれていないか」をループで確認するような二重ループ構造にしているとTLEしてしまいます。配列を用いて各人が呼ばれたかを記録しましょう。(下の実装例ではstd::setを用いていますが、公式解説の通りbool型のstd::vectorで十分です。)

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,0,n) cin >> a[i];
 
    set<int> se;
    rep(i,0,n) se.insert(i+1);
    rep(i,0,n){
        if(se.count(i+1)){
            se.erase(a[i]);
        }
    }
 
    cout << se.size() << el;
    for(auto x : se) cout << x << spa;
    cout << el;
}

提出コード: https://atcoder.jp/contests/abc293/submissions/39606575

C問題

問題文:

Diff: 431

$2 \leq H,W \leq 10$ と制約がかなり厳しく、また入出力例2によって$H,W = 10$ で全ての経路を通るケースでも48620通りしか経路がないことがわかります。これは全列挙しても十分間に合いそうなので、どうすれば経路を列挙できるか考えるとよいでしょう。
bit全探索やstd::next_permutationによる順列全探索、幅優先探索などでも解けるようですが、再帰による深さ優先探索(DFS)が直感的な実装方法ではないでしょうか。ということで、実装例では再帰DFSで解いています。ただし自分は再帰DFSが苦手なので、あまりきれいな実装ではないと思います。
実装のお気持ちとしては、以下のような感じです。

• {0,0}を始点に、「右,下(,前のマスに戻る)」の優先度で進む
• 経路で整数が重複するかはset<int>を用いて判定する
• {H-1,W-1}のマスにたどり着いた時点でansを+1して前のマスに戻る

dfs関数内のse2は、直接seに要素を挿入すると一度記録した整数を永続的に保持してしまうため、別途用意した形です。しかし、よく考えればseに要素を挿入しても、dfs関数の終了時(if(y+1 != h)の後の部分)にse.erase(v[y][x])してやれば問題ありませんでした。¹
se2を用意する方法では毎回seの要素をコピーが生じているので、当然遅くなります。今回は制約が厳しかったので通りましたが、悪い実装方法なことには間違いないので、1つのstd::setで済ませる方法を強く推奨します。再帰、難しいです……

// dfs関数内のコメントはstd::set 1つで済む方法を示す
int h,w;
int ans;
vector<vector<int>> v;

void dfs(int x, int y, set<int>& se){
    if(x+1 == w && y+1 == h) ans++;
    if(x+1 != w){
        if(!se.count(v[y][x+1])){
            set<int> se2 = se;
            se2.insert(v[y][x+1]);
            //se.insert(v[y][x+1]); 上2行は不要.
            dfs(x+1,y,se2);
        }
    }
    if(y+1 != h){
        if(!se.count(v[y+1][x])){
            set<int> se2 = se;
            se2.insert(v[y+1][x]);
            //se.insert(v[y+1][x]); 上2行は不要.
            dfs(x,y+1,se2);
        }
    }
    //se.erase(v[y][x]);
}

//----------------------------------------------------------------------
int main() {
    cin >> h >> w;
  	v.resize(h);
  	rep(i,0,h) v[i].resize(w);
    rep(i,0,h) rep(j,0,w) cin >> v[i][j];

    set<int> se;
    se.insert(v[0][0]);
    dfs(0,0,se);
    cout << ans << el;
}

提出コード²: https://atcoder.jp/contests/abc293/submissions/39674406

D問題

問題文:

Diff: 830

N本のロープを頂点とし、M回のロープの端を結ぶ操作をロープAとロープCの2頂点間に無向辺を張る と置き換えると、グラフ理論の問題になります。
ここからの判定方法は色々と考えられ、例えば公式解説のように連結成分内の全ての頂点の次数が2であるかを確認するなどがあります。この方針だと、前回(ABC292)のD問題と同じような実装でよさそうです。³

今回自分がとった方針は、DSU(UnionFind)を用いた閉路判定です。閉路が検出された組は、環状になっているといえます。
A,Cのロープ同士に辺を張る操作M回分をDSUに反映させていきますが、その途中で辺を張る前からロープAとロープCが同じ組に既に属しているなら閉路を含むということになります。上の解法にもいえますが、色を表すB,Dは使用する必要がないです。

環状の組とそうでない組の個数を出力する必要がありますが、これについては上手な実装方法が思いつきませんでした。実装例では、閉路判定がtrueになったときの頂点番号A,Cをstd::set<int> seに記録し、DSU::groupsで連結成分ごとに分解したのち(g)、各連結成分についてseに含まれる頂点番号を1つでも含むか判定することで個数をカウントしました。

別解として頂点数2Nのグラフに見立て、頂点番号をRなら$2×(A_i-1)$, Bは$2×(A_i-1)+1$として管理する方法もあります。(Cの場合$C_i$, またRとBは逆転させてもよい)

int main() {
    int n,m;
    cin >> n >> m;
    dsu tree(n);
    set<int> se;
 
    rep(i,0,m){
        int a,c;
        char b,d;
        cin >> a >> b >> c >> d;
        a--, c--;
        if(tree.same(a,c)){
            se.insert(a);
            se.insert(c);
        }
        tree.merge(a,c);
    }
 
    vector<vector<int>> g = tree.groups();
    int alone = g.size();
    for(auto x : g){
        for(auto y : x){
            if(se.count(y)){
                alone--;
                break;
            }
        }
    }
 
    cout << g.size()-alone << spa << alone << el;
}

提出コード: https://atcoder.jp/contests/abc293/submissions/39666949

感想

A問題もB問題も問題文に少し面食らってしまい、実装が遅れました。どちらもやるだけだったので、もったいなかったです。まぁペナ受けてないので許容範囲ですが……
C問題は苦手な再帰DFSを実装する羽目になり苦労しましたが、一応解けたのでよかったです。ただdfs関数内の[y+1][x]を[y][x+1]と間違えたところがあり、それでペナ合わせると10分弱ロスしたのが痛かったです。添え字には要注意。

それはそうとしてD問題、2分くらいで「グラフ理論の問題に帰着できるな」と確信できたのに、そこから実装も考察も沼って解けなかったのが悔しくて仕方ないです。
グラフ理論の問題はかつて得意だったはずなのに、最近のコンテストでは全然解けていないので重点的に精進しないといけないなと反省しています。別解としてちらりと紹介した「Rは$2×(A_i-1)$に…」が思い浮かんでいたのですが、これでも上と同じような処理で解けたはずなので、甘かったとしか……
次のコンテストで成功しないと3回目の落茶を経験させられそうなので、次こそは頑張ります。

1. 現在のマスからバックするときに、現在のマスの整数を除外してやればよいだけの話…… ↩

2. コンテスト中の提出では、se2の使用に加えansとvをグローバル変数にしていなかったため、引数も多くなっています。 https://atcoder.jp/contests/abc293/submissions/39623629 ↩

3. やってないので本当にできるかはわかりません。多分同じだと思いますが… ↩