【RCO】日本橋ハーフマラソン予選 A問題

AtCoder マラソン RCO 競技プログラミング

AtCoderで開催された日本橋ハーフマラソンの予選のA問題です.
A問題に時間をかけすぎてBが悲惨なことになりました.
ちなみに予選115位でした…

A: Multiple Pieces - RCO presents 日本橋ハーフマラソン 予選 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

問題概要

・50*50のマスに0~9の数字が書いてある
・9個の連結したマスを1グループとする
・グループ内の数同士の掛け算をそのグループの得点とする
・全てのグループの得点の和が最終的なスコア
・スコアを最大化するようにグループを作ってください

方針

・なるべく大きい数同士同じグループにしたい
と思ったので、実装しやすそうな9の周りから大きい数字を選んで行くという方法をとりました。

実装例

焦って書いたコードなので汚いです.
このコードだとA問題だけでは75位でした.

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int H, W, K;
vector<string> inputmass;
int mass[51][51];
bool used[51][51];
typedef pair<int, int> YX;//座標
typedef pair<int, YX> P;//値,座標

int main(){
    cin >> H >> W >> K;
    cin.ignore();
    FOR(i, 0, H){
        string s;
        getline(cin, s);
        inputmass.push_back(s);
    }
    FOR(i, 1, 51){
        FOR(j, 1, 51){
            mass[i][j] = inputmass[i-1][j-1] - '0';
        }
    }
    //連結できるならqueに入れておく
    //4方向を見る
    int vx[4] = {0, 1, 0, -1};
    int vy[4] = {-1, 0, 1, 0};
    priority_queue<P> que;
    stack<YX> output;
    int C = 0;
    //9の周りでグループ作る->8の周りで->...
    for(int num = 9; num > 0; --num){
    FOR(yi, 1, H+1){
        FOR(xi, 1, W+1){
            //すでに使われていたらもしくわnum(9->8->7->...)でなければcontinue
            if(used[yi][xi]==true || mass[yi][xi] != num) continue;
            while(!que.empty()) que.pop();
            que.push(P(mass[yi][xi],YX(yi, xi)));
            used[yi][xi] = true;
            //queの周りを調べる
            //0出なければ連結させる
            int k = 0;//グループ内の数の個数-1
            while(1){
                if(k==8){
                    C++;
                    while(!que.empty()){
                        P p = que.top();que.pop();
                        used[p.second.first][p.second.second] = false;//あまりは戻す
                    }
                    break;
                }
                //8個できるまでに連結できなかったら戻す
                if(que.empty()){
                    FOR(kesu, 0, k){
                        YX yx = output.top();output.pop();
                        used[yx.first][yx.second] = false;//グループにできてないので戻す
                    }
                    while(!que.empty()){
                        P p = que.top();que.pop();
                        used[p.second.first][p.second.second] = false;
                    }
                    break;
                }
                //使うところを保存
                P p = que.top();que.pop();
                output.push(p.second);//あとで出力する
                k++;
                //周りを調べる
                int y0 = p.second.first;
                int x0 = p.second.second;
                FOR(vi, 0, 4){
                    if(y0 + vy[vi] <= 0 || y0 + vy[vi] > H || x0 + vx[vi] <= 0 || x0 + vx[vi] > W) continue;
                    if(mass[y0+vy[vi]][x0+vx[vi]]==0 || used[y0+vy[vi]][x0+vx[vi]]==true) continue;
                    que.push(P(mass[y0+vy[vi]][x0+vx[vi]],YX(y0+vy[vi], x0+vx[vi])));
                    used[y0+vy[vi]][x0+vx[vi]] = true;
                }
            }
        }
    }
    }
    cout << C << endl;
    while(!output.empty()){
        YX yx = output.top();output.pop();
        cout << yx.first << " " << yx.second << endl;
    }
}

コメント

1個隣だけでなく何個か先も見て得点が大きくなる場合を探す方法でやってみようと思います。

【AtCoder】AGC011 B. Colorful Creatures

AtCoder 競技プログラミング

AtCoderの問題

B: Colorful Creatures - AtCoder Grand Contest 011 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ（初心者目線）

・考え方***

・実装**

・面白さ***

問題概要

・N匹の生き物がいる
・それぞれ大きさがAiで色がiである
・この生き物は自分の大きさの2倍以下の生き物を吸収できる
・例えば大きさA色aの生き物が大きさB色bの生き物を吸収したら
・大きさA+B色aの生き物になる
・N匹の生き物が1匹になるまで吸収を繰り返した時ありえる色のパターンは？

方針

・小さい生き物からその生き物の色を最後まで残せるかどうか調べた
・昇順にソートした時、「生き物jまで合体生物の大きさの2倍>=生物j+1の大きさ」なら生き物jまでの色は残せるし生き物j+1の色も残せる
・「生き物jまでの合体生物の大きさの2倍<=生き物j+1の大きさ」なら生き物j+1の色しか残せない

吸収したらソートし直したほうがいいと思ったけどしないでACになった…
いいのかな?

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int main(){
    int N;
    cin >> N;
    vector<double> A(N);
    FOR(i, 0, N) cin >> A[i];
    sort(A.begin(), A.end());
    ll ans = 1;
    FOR(i, 0, N-1){
        //どっちにもなれるなら色の可能性+1
        if(A[i+1] <= A[i] * 2){
            ans++;
        }
        //片方にしかなれないなら色の可能性は1になっちゃう
        else ans = 1;
        A[i+1] += A[i];
        //sortすべき??
    }
    cout << ans << endl;
}

【AtCoder】AGC011 A. Airport Bus

AtCoder 競技プログラミング

AtCoderの問題

A: Airport Bus - AtCoder Grand Contest 011 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ（初心者目線）

・考え方**

・実装**

・面白さ**

問題概要

・N人の人がバス停にTi時に来る
・それぞれの人はK以下の時間待てるがそれより待つことになると怒る
・バスの最大乗員人数はC人
・全員を怒らせないために必要なバスの台数の最小値は？
・バスが何時に来るかは任意に決められる(複数台同時でも良い)

方針

・あるバスに最初に乗った人が怒らないギリギリまで
・もしくは満員になるまで人を乗せる
・そしてまた新たに次のバスを用いる
・これの繰り返し

コード

焦って書いたコードなので汚いかもです!

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int main(){
    int N;
    double C, K;
    cin >> N >> C >> K;
    vector<double> T(N, 0);
    FOR(i, 0, N) cin >> T[i];

    sort(T.begin(), T.end());
    int ans = 0;
    //先頭の人
    double t = T[0];
    int people = 0;
    bool last = false;
    FOR(i, 0, N){
        //バス出発
        if(t + K < T[i]){
            ans++;
            people = 1;
            t = T[i];
        }
        //乗れた
        else{
            people++;
            //あるバスで最後の乗客だった場合
            if(people==C){
                ans++;
                people = 0;
                if(i+1==N) last = true;
                //次の先頭の人
                t = T[i+1];
            }
        }
    }
    if(!last) ans++;
    cout << ans << endl;
}

【自分用メモ】Union-Find木

メモ アルゴリズム Union-Find木

Union-Find木のコード

参考書

プログラミングコンテストチャレンジブック [第2版]

Union-Find木とは…
・グループ分けを管理するデータ構造
・根が同じ場合同じグループとする

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

#define MAX_V ノードの数

int par[MAX_V]; //ノードiの親=par[i]
int rnk[MAX_V]; //深さ

//配列の初期化
//最初は自分が根
void init(int V){
    FOR(i, 0, V){
        par[i] = i;
        rnk[i] = 0;
    }
}

//根を探す
int find(int x){
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}

//合併
void unite(int x, int y){
    x = find(x);//xの根
    y = find(y);//yの根
    if(x == y) return;
    //深い方にくっつける
    if(rnk[x]>=rnk[y]){
        par[y] = x;
        if(rnk[x]==rnk[y]) rnk[x]++;
    }
    else{
        par[x] = y;
    }
}

//同じグループかどうか
bool same(int x, int y){
    return find(x) == find(y)
}

【自分用メモ】ダイクストラ法

メモ アルゴリズム

ダイクストラ法のコード

ダイクストラ法とは…
グラフのある頂点から他の頂点への最短距離を求めるときの方法

参考書

プログラミングコンテストチャレンジブック [第2版]

ダイクストラ法 - Wikipediaのgifがわかりやすい

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

#define INF 99999999
#define MAX_E 1000
#define MAX_V 1000

//ダイクストラ法 using queue

//頂点の数
int V;
//次の頂点、次の頂点へのコスト
struct edge{ int to, cost; };

//頂点iと繋がっている頂点の情報
//G[i][頂点iと繋がっている頂点の個数]
vector<edge> G[MAX_V];

//始点からのコスト、頂点番号
//priority_queueで並び変えるためにpair
typedef pair<int, int> P;

//始点sからのコスト
int dijkstra(int s){
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+V, INF);
    d[0] = 0;
    que.push(P(0, s));

    while(!que.empty()){
        P p = que.top();que.pop();
        //頂点
        int v = p.second;
        //すでに小さくなっていたらcontinue;
        if(d[v] < p.first) continue;

        //vと繋がっている頂点についてコストが下がるかどうかを調べる
        FOR(i, 0, G[v].size()){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

【yukicoder】No.179 塗り替え

yukicoder 競技プログラミング 全探索

yukicoderさんの問題

No.179 塗り分け - yukicoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ（初心者目線）

・考え方***

・実装***

・面白さ***

問題概要

・白と黒で塗られたマスがある
・黒いマスを赤か青に塗り替えたい
・この時、赤いマスを平行移動させると青いマスにちょうど重なるようにしたい
・白いマス".“と黒いマス”#“が与えられるので、上記の条件で塗り替えられるかどうか求めよ

方針

・塗り替えられていない黒いマスについて(dx, dy)移動した先に塗り替えられていない黒マスがあればOK ・全探索

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//塗り替えられていない黒いマスについて(dx, dy)移動した先に塗り替えられていない黒マスがあればOK
//全探索

int main(){
    int H, W;
    cin >> H >> W;
    //#or.を保存
    vector<string> mass(H);
    FOR(i, 0, H) cin >> mass[i];
    //塗り替えたかどうか
    bool isPainted[H][W];
    FOR(i, 0, H) FOR(j, 0, W) isPainted[i][j] = false;
    //移動した先のマスを塗り替えられたかどうか
    bool check = false;
    FOR(dy, -H, H){
        FOR(dx, -W, W){
            //移動量が0の時は飛ばす
            if(dy==0 && dx==0) continue;

            //塗り替えたかどうかの情報初期化
            FOR(i, 0, H) FOR(j, 0, W) isPainted[i][j] = false;

            //注目するマスをFORでまわす
            FOR(z, 0, (H-1)*W+W){
                int y = z / W;
                int x = z % W;

                //塗り替えられていない#のマスについて
                if(mass[y][x]=='#' && isPainted[y][x]==false){
                    isPainted[y][x]=true;

                    //移動先が範囲外ならbreak移動量変えてやり直し
                    if(y+dy<0 || y+dy>=H || x+dx<0 || x+dx>=W){
                        check = false;
                        break;
                    }

                    //移動先が塗り替えられていない#ならOK
                    if(mass[y+dy][x+dx]=='#' && isPainted[y+dy][x+dx]==false){
                        isPainted[y+dy][x+dx]=true;
                        check = true;
                    }

                    //塗り替えられていたらbreak移動量変えてやり直し
                    else{
                        check = false;
                        break;
                    }
                }
            }

            //falseでなければ全て矛盾なかったということ
            if(check){
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl;
}

【POJ】Conscription

POJ 競技プログラミング Union-Find木 クラスカル法 面白い

POJの問題

3723 -- Conscription

参考書

プログラミングコンテストチャレンジブック [第2版]
今回の解法はこの本から得ています.

難しさ（初心者目線）

・考え方****

・実装****

・面白さ*****

問題概要

・女N人、男M人を雇いたい
・1人10000ドルで雇える ・ただし、女と男の間に親密な関係がある場合がある
・親密な関係は親密度Zで表される
・親密な場合はすでに片方が雇われていたらもう片方は(10000-Z)ドルで雇える
・雇う順番は自由である
・(N+M)人を雇うのにかかる最小のお金を求めよ

方針

・無向グラフで考える
・男と女の番号を頂点とする(男と女共に0から始まるので男は+Nしておく)
・男Aと女Bが親密な関係の場合頂点Aと頂点Bを結ぶ(costは-1*親密度にしておく)
・閉路ができないように辺を小さいコストから選んで行く->最小全域木->クラスカル法

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define pb         push_back
#define mp         make_pair
#define ll         long long
#define PI         acos(-1.0)
#define ALL(A)     ((A).begin(), (A).end())
#define vsort(v)   sort(v.begin(),v.end())
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//無向グラフで考える
//男と女の番号を頂点とする(男と女共に0から始まるので男は+Nしておく)
//男Aと女Bが親密な関係の場合頂点Aと頂点Bを結ぶ(costは-1*親密度にしておく)
//閉路ができないように辺を小さいコストから選んで行く->最小全域木->クラスカル法
//答えは人数*10000 + 最小全域木のコスト

#define MAX_V 20000 //頂点の最大数
#define MAX_E 50000 //辺の最大数

/////////////////////union-find木/////////////////////
int par[MAX_V]; //親
int rnk[MAX_V]; //木の深さ

//配列の初期化
void init(int V){
    FOR(i, 0, V){
        par[i] = i;
        rnk[i] = 0;
    }
}

//根を探す
int find(int x){
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}

//合併
void unite(int x, int y){
    int px = find(x);
    int py = find(y);
    //すでに一緒なら何もしない
    if(px == py) return;
    //深い方の木にくっつける
    if(rnk[px]>=rnk[py]){
        par[py] = px;
        if(rnk[px]==rnk[py]) rnk[py]++;
    }
    else par[px] = py;
    return;
}

//同じグループかどうか=根が同じかどうか
bool same(int x, int y){
    return find(x) == find(y);
}

/////////////////////////////kruskal////////////////////////////

struct edge { int u, v, cost; };

bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}

edge es[MAX_E]; //辺の数分
int V, R;

//最小全域木を求めるアルゴリズム=クラスカル法
int kruskal(){
    //短い順にソート
    sort(es, es+R, comp);
    int ret = 0;
    FOR(i, 0, R){
        edge e = es[i];
        if(same(e.u, e.v)) continue;
        ret += e.cost;
        unite(e.v, e.u);
    }
    return ret;
}

////////////////////////main////////////////////////

int main(){
    int n; //テストケースの数
    cin >> n;
    int N, M;
    //改行があるからgetlineいる？
    string s;
    getline(cin, s);
    FOR(i, 0, n){
        scanf("%d %d %d", &N, &M, &R);
        V = N + M;
        //union-find木の初期化
        init(V);
        //親密関係入力->esに保存
        FOR(j, 0, R){
            scanf("%d %d %d", &es[j].u, &es[j].v, &es[j].cost); //cinだとLTE
            //性別を区別する女(0~N-1) 男(N~N+M-1)
            es[j].v += N;
            //親密度分だけ安くなる
            //-1をかけて小さい方がより多くお金が安くなる->小さくなるパスを選ぶ
            //->閉路ができてはいけない->最小全域木
            es[j].cost *= -1;
        }
        getline(cin, s);
        cout << (V * 10000 + kruskal()) << endl;
    }
}

コメント

クラスカル法ではUnion-Find木を用いることで閉路ができるかどうか判定できるので、 最小全域木を求めるのが簡単にできる.
クラスカル法を知らなかったので勉強になった.
クラスカル法 - Wikipedia