Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

競技プログラミング練習記 No.21【ABC137練習】

初回 -> はじめに

ABC137を解きました。
4完です。
E問題は解説を見て解きました。

問題 時間 アルゴリズム 実行時間
A 1min - 7ms
B 3min - 6ms
C 12min ヒストグラム 53ms
D 27min 動的計画法 41ms
E - ベルマンフォード法 88ms

A - +-x

    int a, b;
    cin >> a >> b;
    cout << max( { a + b, a - b, a * b } );

そのままですね。
3つの計算結果のmaxをとると答えになります。
max関数の引数にタプルをもってこれるのは初めて知りましたw

B - One Clue

    int k, x;
    cin >> k >> x;
    for(int i = x - k + 1; i < x + k; ++i)
    {
        cout << i << " ";
    }

座標Xに黒い石が置かれていて、その左右隣が白い石になる場合を考えるといいですね。
つまり境界値を考えます。
[ x - k + 1, x + k - 1 ] の範囲が答えになります。

C - Green Bin

    int n;
    cin >> n;
    unordered_map< string, ll > ana_list;

    string s;
    for(int i = 0; i < n; ++i)
    {
        cin >> s;
        sort(s.begin(), s.end());
        ana_list[s]++;
    }

    ll ans = 0;
    for(const auto& ana : ana_list)
    {
        ans += ana.second * (ana.second - 1LL) / 2LL;
    }
    cout << ans;

ヒストグラムが使えますね。
ヒストグラムはbin sortで使う考え方ですが、問題名の「Green Bin」より想起されました。

受け取った文字列をソートすると、アナグラムの関係にある文字列は同じ一意の結果になります。
つまり、ソート後の文字列が何回現れたかを記憶しておけば答えは出せます。

ハッシュマップより、ソート後の文字列をkeyとして発生回数を記憶しています。
最後に組み合わせ nC2の計算式をつかって答えを出しました。

D - Summer Vacation

    int n, m;
    cin >> n >> m;
    vector<P> job(n);

    for(int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        job[i] = P(a, b);
    }

    sort(job.begin(), job.end());
    priority_queue<int> job_score;

    ll ans = 0;
    int job_index = 0;
    for(int i = 1; i <= m; ++i)
    {
        while(job_index < n && job[job_index].first <= i)
        {
            job_score.push(job[job_index].second);
            job_index++;
        }
        if (!job_score.empty())
        {
            ans += job_score.top();
            job_score.pop();
        }
    }
    cout << ans;

残りi日の時にできる最も報酬の多い仕事をするのが基本方針です。
ですが、それだけでは入力例 2のような場合に解くのが難しくなります。

問題文をそのまま受け取ると、残り日数をM日から1日まで減らしていくように読み取れます。
残り日数を減らしていくと選べる仕事が減っていき、考えるべき変数が残り日数, 仕事の期間, 報酬の3つになります。

逆に、残り日数を1日からM日まで増やしてみます。
すると、残り日数を増やしていくと選べる仕事が増えていき、残り日数仕事の期間は考える必要がなくなります。
つまり、報酬のみを考えればいいです。

逆に考えると変数が1つになって考えやすくなりましたね。この方針なら解けそうです。
そしてこれが正しい考え方です。

今回は報酬の合計を最大化するので、選べる仕事のうち最も報酬が大きいものを選べば答えになります。
最大値だけわかればいいのでpriority_queue(heap)の出番ですね。
選べる仕事を抽出し、その報酬をpriority_queueに入れて計算すれば答えになります。

E - Coins Respawn

vector<int> to[2505];
vector<int> reverse_to[2505];
bool ok[2505];
bool reachableFrom1[2505];
bool reachableFromN[2505];

void dfs(int v) {
    if (reachableFrom1[v]) return;
    reachableFrom1[v] = true;
    for(const auto& u : to[v]) dfs(u);
}

void dfs_reverse(int v) {
    if (reachableFromN[v]) return;
    reachableFromN[v] = true;
    for(const auto& u : reverse_to[v]) dfs_reverse(u);
}

void solve() {
    fill(ok, ok + 2505, false);
    fill(reachableFrom1, reachableFrom1 + 2505, false);
    fill(reachableFromN, reachableFromN + 2505, false);

    int n, m, p;
    cin >> n >> m >> p;

    vector<Edge> edges;
    vector<int> dist(n, INF);
    dist[0] = 0;

    for(int i = 0; i < m; ++i) {
        Edge edge;
        cin >> edge.from >> edge.to >> edge.cost;
        edge.from--;
        edge.to--;
        edge.cost -= p;
        edge.cost *= -1; // コストを反転させて最短経路問題を解けば、最長経路になる

        edges.emplace_back(edge);
        to[edge.from].emplace_back(edge.to);
        reverse_to[edge.to].emplace_back(edge.from);
    }

    dfs(0);
    dfs_reverse(n - 1);
    for(int i = 0; i < n; ++i) ok[i] = reachableFrom1[i] & reachableFromN[i];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            Edge e = edges[j];
            if(!ok[e.to]) continue;
            if(!ok[e.from]) continue;

            if (dist[e.to] > dist[e.from] + e.cost) {
                dist[e.to] = dist[e.from] + e.cost;
                if (i == n - 1) {
                    cout << -1;
                    return;
                }
            }
        }
    }
    cout << max(dist[n - 1] * -1, 0);
}

長いです。。。行数をおさえるためにすこし整形しました。
青difficultyの問題です。
あまり多く解いたことはありませんが、青difficultyの問題は長いものが多い印象です。慣れなきゃ。

この問題について・・・
・始点が決まっています。

・グラフ上を移動するたびに報酬がもらえて、最後に移動した回数だけpが引かれます。
 ただ、最後にpを引く処理は移動中にしても結果は同じです。
 つまり、各枝の報酬から先にpを引いても大丈夫です。この時に負の値が出てきます。

・閉路が存在して報酬が無限に大きくなります。

・報酬を最大化する問題ですが、報酬の正負を反転すれば報酬を最小化する問題になります。
 つまり最短経路問題です。

長くなりましたが、この問題は「負閉路あり負数重み付き有向グラフの単一始点最短経路問題」に帰着できます。
つまりベルマンフォード法ですね。使ったのは今回が初めてです。

ただ、ここで終わらないのが青difficultyというか、それだけでは解けません。
始点と終点の間に負閉路があった場合には-1を出力するのですが、その検出はベルマンフォード法ではできません。
(始点と終点に関係なく負閉路があるかは検出できます。)

その検出を先にDFSでやります。
dfs(0);
dfs_reverse(n - 1);
の部分ですね。
始点と終点の両方から到達できない点について、ベルマンフォード法の処理をさせないようにします。

ここまでやってACです。長かった。

できるひとは「おっ、ベルマンフォードか」「でも閉路がちょっと良くないな」「始点と終点からdfsするか」
と一瞬でなるのでしょうか。その高みにいきたいです。これはその高みに続く一歩ですね。

以上です。ありがとうございました。

gummie
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away