ABC310 反省会

はじめに

私生活があまりに忙しくなりましたが、なんとか生きてます。
最近またABCに出始めたのですが、ボコボコにされているのでクイック反省会をブログでやりたいと思います

全体的な反省

• 問題文をちゃんと読もう
• Cぐらいまで速解き失敗するとゴタゴタになるのやめたい

A, B問題

• B問題で一生誤読していて辛かった。上方互換というより、価格が安いが同じ機能があるものみたいな言い回しにしてほしかったな
• ちゃんと読めてない自分が悪いが...

C問題

• 重複している棒の数の問題を解いていて、一生あわなかった

D問題

• どうみても全探索しか思いつかなったので、計算量がかなり不安だが全探索の方針を考えた。
• 実装してみるが合わない。最初の実装はこんな感じ

void dfs(int p, int t){
   // 空のチームがあったらNG
    if(p == N - 1){
        bool ok = true;
        for(auto& v : team)
            if(v.empty())
                ok = false;
        if(ok)
            ++ans;
        return;
    }
    for(int nt = 0; nt < T; ++nt){
        // 追加予定のチームを舐めて、組み合わせが悪いペアがなければ追加する
        bool ok = true;
        for(auto u : team[nt]){
            if(e.find(minmax(p + 1, u))!= e.end())
                ok = false;
        }
        if(ok){
            team[nt].push_back(p + 1);
            dfs(p + 1,nt);
            team[nt].pop_back();
        }
    }
    return;
}

どうやらチーム数の区別がうまくいってないらしい。
具体的には、とを重複して数え上げているらしい。
順序性を導入すると重複なしで数え上げることができそうだが、コンテスト中は思いつかず...

解説

一番大事な部分を引用するとこうなる

ここに番目の選手を追加するには、たかだか チームのいずれかに 番目の選手を入れるか、（チーム数がより少ないとき）新しく番目の選手しかいないチームを作るかのどちらかです。

自分がやりたいことを正しくやろうとすると上のような感じになるらしい。
具体的に考えてみよう。人に対しての操作を考える。全てのチームに対して追加可能かどうか判定するのは、重複して計算してしまうので無駄になる。

すでに人が存在するチームに追加するかどうかは、全て試す。を新しいチームに追加する場合は、できるだけ小さい数字のチームに追加するように変更してみる。（つまり、ただ一つに定まる)

ACしたコード

void dfs(int p, int t){
    if(p == N - 1){
        ans += (team.back().empty() ? 0 : 1);
        return;
    }
    for(int nt = 0; nt < T; ++nt){
        bool ok = true;
        for(auto u : team[nt]){
            if(e.find(minmax(p + 1, u))!= e.end())
                ok = false;
        }
        if(ok && not team[nt].empty()){
            team[nt].push_back(p + 1);
            dfs(p + 1,nt);
            team[nt].pop_back();
        }
    }
    // 新しくチームに追加する
    for(int nt = 0; nt < team.size(); ++nt){
        if(team[nt].empty()){
            team[nt].push_back(p + 1);
            dfs(p + 1,nt);
            team[nt].pop_back();
            // break immediately
            break;
        }
    }
    return;
}

と修正したらACした。
たったこれだけでteamを区別無くカウントできるのはすごい。思いつけなかったので完全敗北です。

E問題

なんかDより解かれているイメージ有るので、後日解きます。
解きました。