備忘録

まとめておきたいことのメモ 主にプロコンのこと

AGC 006 B

さっきこの問題を解きました。

agc006.contest.atcoder.jp

n段のピラミッドの最も下の段のブロックに1~2 * n - 1の数字が一回ずつ書かれています。そこから上の段のブロックについては、自分のブロックの真下、左下、右下の中央値が書かれます。今、頂点の値xが与えられています。頂点の値はxかつ条件を満たすような最も下の段のブロックの記入方法があるか答えなさい。存在する場合は、その一例を
答えなさい。という問題です。

ある2つの連続したブロックについて、書かれている数字が同じであればそれらの上の2つのブロックもまた同じ数字が書かれる、ということを利用します。これにより、下から二番目の段についてその段の中央とその隣にxが書かれていれば頂点の値はxになります。したがって下から二番目の段がこうなるような記入方法を考えればいいです。
ここで、xは2以上2 * n - 2以下でないといけません。なぜならば、1と2 * n - 1は一番下の段から下から二番目の段に上がるときにどうあがいても消えてしまうからです。よってこのばあいは"No"を出力して終了します。

回答はこんな感じ。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring>
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int main()
    {
        int n, x;
        cin >> n >> x;
        if(n == 2){
            if(x == 2) cout << "Yes" << endl << 1 << endl << 2 << endl << 3 << endl;
            else cout << "No" << endl;
            return 0;
        }
        if(x == 1 || x == 2 * n - 1){
            cout << "No" << endl;
            return 0;
        }
        cout << "Yes" << endl;
        int ans[200001];
        for(int i = 0; i < 2 * n; i++){
            ans[i] = i;
        }
        swap(ans[n], ans[x]);
        if(x > n){
            if(ans[n - 1] > x - 1) swap(ans[n - 1], ans[x - 1]);
            if(ans[n + 1] != x + 1) swap(ans[n + 1], ans[x + 1]);
            if(ans[n + 2] > x - 2) swap(ans[n + 2], ans[x - 2]);
        } else if(x < n) {
            if(ans[n - 1] < x + 1) swap(ans[n - 1], ans[x + 1]);
            if(ans[n + 1] != x - 1) swap(ans[n + 1], ans[x - 1]);
            if(ans[n + 2] < x + 2) swap(ans[n + 2], ans[x + 2]);
        }
        for(int i = 1; i < 2 * n; i++){
            cout << ans[i] << endl;
        }
        return 0;
    }

まずxを中央に来るようにswapします。
次に隣に来る数を考えないといけません。このとき、自分より大きい値の数の方が、小さい値の数より多い場合とその逆の場合に分けて考えます。なぜならば、たとえばx = 2 * n - 2かつ隣に2 * n - 3が来るとしたとき、その二つのブロックの両脇には2 * n - 1が来なければxが選ばれません。しかし、これでは2 * n - 1が二回出現することになり条件を満たしません。一方隣に2 * n - 1が来るとしたとき、その二つのブロックの両脇には2 * n - 3以下の値であればどれでもいいわけです。このような場合に備えて場合分けした、というわけです。あとは、両隣に来る値を適当に書き換えればオッケーです。大体こんな感じ。

  • 隣に来るブロックがx + 1であれば、その二つのブロックの左側にはx - 1以下の、右側にはx - 2以下のブロックが来るようにする
  • 隣に来るブロックがx - 1であれば、その二つのブロックの左側にはx + 1以上の、右側にはx + 2以上のブロックが来るようにする


正直にいうとここはテストケースから判断して適当に書きました。
一発で通ったのでとても気持ちいい。

ARC 064に参加しました

arc064.contest.atcoder.jp

2,3分遅れてスタート→C問題で3回WA、その後AC→D考えてるうちに寝落ち→Eを提出するもWA
って感じでした。これはひどい

C問題: 左側から順に求めていくのと右側から順に求めていくの2通りやりましたがその必要はなかったっぽい。非負整数分だけ減らせるのを見落としていました。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring>
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int main()
    {
        long long int n, x;
        cin >> n >> x;
        long long int a[100001], b[100001];
        for(int i = 0; i < n; i++){
            cin >> a[i];
            b[i] = a[i];
        }
        long long int ans1 = 0, ans2 = 0;
        for(int i = 1; i < n; i++){
            if(a[i - 1] + a[i] > x){
                long long int tmp = a[i - 1] + a[i] - x;
                ans1 += tmp;
                if(a[i] < tmp){
                    a[i - 1] -= tmp - a[i];
                    a[i] = 0;
                } else {
                    a[i] -= tmp;
                }
            }
        }
        for(int i = n - 1; i > 0; i--){
            if(b[i] + b[i - 1] > x){
                long long int tmp = b[i - 1] + b[i] - x;
                ans2 += tmp;
                if(b[i - 1] < tmp){
                    b[i] -= tmp - b[i - 1];
                    b[i - 1] = 0;
                } else {
                    b[i - 1] -= tmp;
                }
            }
        }
        cout << min(ans1, ans2) << endl;
        return 0;
    }

E問題: ダイクストラやんけ!と思いつけたのはいいもののスタート地点からゴール地点まで直接行く道のことを考えていませんでした。解説読んで気づきました。かなしい。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring>
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    double kyori(double x1, double y1, double x2, double y2)
    {
        return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
    }
     
    int main()
    {
        double xs, ys, xt, yt;
        int n;
        cin >> xs >> ys >> xt >> yt >> n;
        double x[1001], y[1001], r[1001];
        for(int i = 0; i < n; i++){
            cin >> x[i] >> y[i] >> r[i];
        }
        double minkyori[1001];
        for(int i = 0; i < n; i++){
            minkyori[i] = -1.0;
        }
        priority_queue<pair<double, int> > qu;
        for(int i = 0; i < n; i++){
            qu.push(make_pair(-(max(0.0, kyori(xs, ys, x[i], y[i]) - r[i])), i));
        }
        while(!qu.empty()){
            int nowbaria = (qu.top()).second;
            double nowkyori = -(qu.top()).first;
            qu.pop();
            if(minkyori[nowbaria] != -1.0 && minkyori[nowbaria] < nowkyori) continue;
            minkyori[nowbaria] = nowkyori;
            for(int i = 0; i < n; i++){
                double tmp = max(0.0, kyori(x[nowbaria], y[nowbaria], x[i], y[i]) - (r[nowbaria] + r[i]));
                if(minkyori[i] == -1.0 || minkyori[i] > nowkyori + tmp){
                    minkyori[i] = nowkyori + tmp;
                    qu.push(make_pair(-nowkyori - tmp, i));
                }
            }
        }
        double ans = kyori(xs, ys, xt, yt);
        for(int i = 0; i < n; i++){
            ans = min(ans, minkyori[i] + max(0.0, kyori(xt, yt, x[i], y[i]) - r[i]));
        }
        printf("%.10f\n", ans);
        return 0;
    }

ARC 037 B

今回はこの問題です。

arc037.contest.atcoder.jp

n個の頂点とm本の辺からなる無向グラフがあります。このグラフの連結部分のうち、木になっているものはいくつあるか答えなさい、という問題です。

union findを利用しました。解答はこんな感じ。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int parent[101];
     
    int getparent(int n)
    {
        if(parent[n] < 0) return n;
        else return parent[n] = getparent(parent[n]);
    }
     
    int main()
    {
        int n, m;
        cin >> n >> m;
        for(int i = 1; i <= n; i++){
            parent[i] = -1;
        }
        for(int i = 0; i < m; i++){
            int u, v;
            cin >> u >> v;
            u = getparent(u);
            v = getparent(v);
            if(u > v) swap(u, v);
            if(u == v){
                parent[u] = -2;
            } else {
                if(parent[u] == -2 || parent[v] == -2){
                    parent[u] = -2;
                    parent[v] = -2;
                } else {
                    parent[v] = u;
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){
            if(parent[i] == -1) ans++;
        }
        cout << ans << endl;
        return 0;
    }

parent[i]の値は、頂点iが含まれる部分が木であるときはその木の根のノード番号(ただし頂点iが根であれば-1)が、木でなければ-2になります。これを枝が追加されるごとに更新していきます。
ノードuが含まれる連結部分とノードvが含まれる連結部分をつなぎます。まずそれぞれその部分の根にしておきます。ここで、両方の根が同じになる場合または片方の部分がすでに木ではない場合、uとvのノードを含む部分は木ではなくなってしまいます。したがって、parentの値を-2に更新しておきます。そうでないときはparent[v]の値を更新します。
これを繰り返すことで、最終的にparentの値が-1になっている数だけ木があることになります。

ARC 024 B

今回はこの問題です。

arc024.contest.atcoder.jp

赤または黒色の木が円周上にn本生えています。この木は1日ごとに、隣の2本の木と自分の色が同じであるとき、異なる色に変化します。隣の木が次にどうなるかは関係なく、その日の状態のみをみて変化します。何日目に木の色が変化しなくなるかを求めなさい、という問題です。

回答はこちら。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int main()
    {
        int n;
        cin >> n;
        int c[100001];
        for(int i = 0; i < n; i++){
            cin >> c[i];
        }
        vector<int> renzokunum;
        int nowcolor = c[0];
        int cnt = 1;
        for(int i = 1; i < n; i++){
            if(c[i] == nowcolor){
                cnt++;
            } else {
                renzokunum.push_back(cnt);
                cnt = 1;
                nowcolor = c[i];
            }
        }
        if(c[n - 1] == c[0]){
            if(renzokunum.size() == 0) renzokunum.push_back(cnt);
            else renzokunum[0] += cnt;
        } else {
            renzokunum.push_back(cnt);
        }
        if(renzokunum.size() == 1){
            cout << -1 << endl;
            return 0;
        }
        int maxrenzoku = 0;
        for(int i = 0; i < renzokunum.size(); i++){
            // cout << renzokunum[i] << endl;
            maxrenzoku = max(maxrenzoku, renzokunum[i]);
        }
        cout << maxrenzoku / 2 + maxrenzoku % 2 << endl;
        return 0;
    }

まず同じ色の木がいくつ連続して並んでいるかを数えます。このとき、n - 1番目の木と0番目の木が隣り合って並んでいることに注意します。そのうち最大値を求めます。この木の列が色の変化がなくなるまでかかる日数が答えになります。日数は最大値 / 2 + 最大値 % 2で求められます。

ARC 038 B

今回はこの問題。

arc038.contest.atcoder.jp

h * wのマスがあります。このマス上には障害物があることがあり、「#」で表されます。
(1, 1)のマスに駒をおきます。駒が(i, j)にあるとき、プレイヤーは交互にこのマスを(i + 1, j), (i, j + 1), (i + 1, j + 1)のいずれかに動かすことができます。障害物のあるマスには動かせません。また、範囲外には動かせません。自分のターンの際に駒を動かせない時、その人の負けになります。
h, wの値と、マスの状態が与えられます。プレイヤーが二人とも最善を尽くした場合、どちらが勝つか判断しなさい、という問題です。

回答はこちら。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int h, w;
    char s[101][101];
    int result[101][101][2] = {};
     
    int solve(int x, int y, int player)
    {
        if(result[x][y][player] != 0) return result[x][y][player];
        int dx[3] = {0, 1, 1};
        int dy[3] = {1, 0, 1};
        int ans;
        if(player == 0) ans = -1;
        else ans = 1;
        for(int i = 0; i < 3; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx > h || ny > w || s[nx][ny] == '#') continue;
            if(player == 0) ans = max(ans, solve(nx, ny, 1));
            else ans = min(ans, solve(nx, ny, 0));
        }
        result[x][y][player] = ans;
        return ans;
    }
     
    int main()
    {
        
        cin >> h >> w;
        for(int i = 1; i <= h; i++){
            for(int j = 1; j <= w; j++){
                cin >> s[i][j];
            }
        }
        if(solve(1, 1, 0) == 1) cout << "First" << endl;
        else cout << "Second" << endl;
     
        return 0;
    }

ゲーム木とよばれる手法(?)を使ってときます。現状から遷移できうる状態を全探索して、最善手をとる、という感じの方法です。
同じところを何度も探索するのは無駄なので、記録していくことにしました。result[i][j][k]には、(i, j)のマスに駒があり、k = 0のときはプレイヤー1、k = 1のときはプレイヤー2のターンである際に、この後最善手を取るとどちらが勝つか、を記録しています。この値が1ならばプレイヤー1が、-1ならばプレイヤー2が勝ちます。
solve関数のansについて、player = 0のときは初期値を-1にしていますが、まず最悪の場合である相手が勝つ、という予測?設定?をしておいて、maxを用いて書き換えると楽な気がします。これ以上進めない、つまりプレイヤー1が負けるときは、ansの値が変更されないということになるので、そのまま-1を返すことができて都合がいいです。プレイヤー2の場合はこれを逆にしただけです。

ARC 028 B

今回はこの問題。

arc028.contest.atcoder.jp

プログラミングコンテストにn人が参加しました。順位はすでにわかっています。「上位i人のうちk番目に若い人」をそれぞれのi(k <= i <= n)に対して求めなさい、という問題です。

回答はこんな感じ。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int main()
    {
        int n, k;
        cin >> n >> k;
        int x[100001];
        for(int i = 0; i < n; i++){
            cin >> x[i];
        }
        priority_queue<pair<int, int> > qu;
        for(int i = 0; i < k; i++){
            qu.push(make_pair(x[i], i + 1));
        }
        priority_queue<pair<int, int> > qu2;
        qu2.push(make_pair(-(qu.top()).first, (qu.top()).second));
        qu.pop();
        for(int i = 0; i < n - k + 1; i++){
            cout << (qu2.top()).second << endl;
            int next = x[i + k];
            // cout << next << endl;
            qu.push(make_pair(next, i + k + 1));
            qu2.push(make_pair(-(qu.top()).first, (qu.top()).second));
            qu.pop();
        }
        return 0;
    }

上位k - 1人について、先頭に最も年をとっている人とその番号が来るようにした優先度つきキューquと、のこりの人について、先頭に最も若い人とその番号がくるようにした優先度つきキューqu2を用意します。最初、quに上位k人についての情報をプッシュしてから、先頭に出てくる情報、つまり上位k人のうちk番目に若い人をqu2にプッシュし、quからポップします。
あとは順番に一人ずつ加えていきます。i + k番目の人をくわえることを考えます。まず、quに次に追加する人の情報をプッシュします。quに含まれている人のうち最も年をとっている人の情報が先頭に来るので、これをqu2に詰め直し、quからポップします。そうすると、qu2の先頭には上位i + k人のうちk番目に若い人がくる、というわけです。優先度つきキューでは最も値の大きいものが出てくるので、qu2ではマイナスをつけることで最も値が小さいものを取り出せるようにしています。

ARC 031 B

今回はこの問題です。

arc031.contest.atcoder.jp

10*10マスがあります。それぞれのマスにはoかxになっています。このうちxのマスをひとつだけoに変更することによって、すべてのoマスが連結するようにできるかどうかを判断しなさい、という問題です。ただし連結とは上下左右いずれかでつながっていることです。

回答はこちら。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    char a[10][10];
    int result[10][10] = {};
    int sum = 0;
     
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
     
    bool count(int x, int y, int cnt)
    {
        if(result[x][y] != 0) return false;
        bool ischecked[10][10];
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
                ischecked[i][j] = false;
            }
        }
        ischecked[x][y] = true;
        int ans = 1;
        queue<int> xqu, yqu;
        xqu.push(x);
        yqu.push(y);
        while(!xqu.empty()){
            int nowx = xqu.front();
            int nowy = yqu.front();
            xqu.pop();
            yqu.pop();
            if(result[nowx][nowy] != 0){
                result[x][y] = result[nowx][nowy];
                return false;
            }
            for(int i = 0; i < 4; i++){
                int nx = nowx + dx[i], ny = nowy + dy[i];
                if(nx < 0 || ny < 0 || nx > 9 || ny > 9 || a[nx][ny] == 'x' || ischecked[nx][ny]) continue;
                xqu.push(nx);
                yqu.push(ny);
                ischecked[nx][ny] = true;
                ans++;
            }
        }
        result[x][y] = cnt;
        return true;
    }
     
     
    int main()
    {
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
                cin >> a[i][j];
            }
        }
        int cnt = 1;
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
                if(a[i][j] != 'x' && count(i, j, cnt)) cnt++;
                // cout << result[i][j] << " ";
            }
            // cout << endl;
        }
        if(cnt > 5){
            cout << "NO" << endl;
            return 0;
        }
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
                if(a[i][j] == 'o') continue;
                set<int> nowans;
                nowans.insert(0);
                for(int k = 0; k < 4; k++){
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx < 0 || ny < 0 || nx > 9 || ny > 9) continue;
                    nowans.insert(result[nx][ny]);
                }
                if(nowans.size() == cnt){
                    cout << "YES" << endl;
                    return 0;
                }
            }
        }
        cout << "NO" << endl;
        return 0;
        // cout << sum << endl;
    }

cntが領域の数を表します。領域に番号をつけていきます。ひとつひとつのマスについて、幅優先探索で領域を調べていきます。探索中にすでに番号が割り振られたマスにたどり着いた場合は、このマスと同じ番号を割り当てておきます。そうでないときは、新たな番号を割り当てます。
領域が5つ以上ある際は、どうやっても全てを連結させることはできないのでNOを出力して終了します。
そうでない場合はすべてのxのマスに対して、oにかえたときすべての領域を連結させられるかをしらべます。nowansは隣接している領域の番号の集合になります。集合のサイズで比較するので、最初に0を加えておきます。集合の大きさとcntの値を比較して、一致すればYESを出力して終了します。
全てのxマスに対して調べ終わったら、全て連結させることはできないということになるのでNOを出力します。

同じ領域に含まれるマスを判断するのがちょっと大変でした。