AOJ 2005: Water Pipe Construction

アルゴリズム

そすうライブラリのverifyに使われていたので解いてみた。

問題

Water Pipe Construction | Aizu Online Judge

  • 有向グラフと各辺のコストが与えられる。
  • 頂点sから頂点g1とg2を結ぶコスト最小の道を作るときのコストを求めよ

解法

全点対間の最小コストを求めておいて、全ての頂点vについて「sからvの最小コスト」+「vからg1の最小コスト」+「vからg2の最小コスト」を調べて最小となるコストを返せばよい。

ダイクストラ

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

struct edge {
    int src, dst, cost; 
    edge(int s, int t, int c): src(s), dst(t), cost(c) {}
};
const int INF = 1e8;

void dijkstra(const vector<vector<edge> > &G, vector<int> &d, const int s) {
    d.assign(d.size(), INF);
    d[s] = 0;
    typedef pair<int, int> P;
    priority_queue<P, vector<P>, greater<P> > que;
    que.push(P(0, s));

    while(!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if(d[v] < p.first) continue;
        for(auto &e : G[v]) {
            if(d[e.dst] > d[v] + e.cost) {
                d[e.dst] = d[v] + e.cost;
                que.push(P(d[e.dst], e.dst));
            }
        }
    }
}

int main(void) {
    int n, m, s, g1, g2;
    while(cin >> n >> m >> s >> g1 >> g2 && n) {
        vector<vector<edge> > G(n);
        vector<vector<int> > d(n, vector<int>(n));
        --s; --g1; --g2;
        REP(i, m) {
            int b1, b2, c;
            cin >> b1 >> b2 >> c;
            G[b1-1].push_back(edge(b1-1, b2-1, c));
        }
        REP(i, n) {
            dijkstra(G, d[i], i);
        }
        int cost = numeric_limits<int>::max();
        REP(i, n) {
            cost = min(cost, d[s][i] + d[i][g1] + d[i][g2]);
        }
        cout << cost << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098833

ベルマン・フォード

#include <bits/stdc++.h>
  
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
struct edge {
    int src, dst, cost; 
    edge(int s, int t, int c): src(s), dst(t), cost(c) {}
};
 
const int INF = 1e8;
 
void bellman_ford(const vector<edge> &edges, vector<int> &d, const int s) {
    d.assign(d.size(), INF);
    d[s] = 0;
    for(auto &i : d) {
        for(auto &e : edges) {
            d[e.dst] = min(d[e.dst], d[e.src] + e.cost);
        }
    }
}
 
int main(void) {
    int n, m, s, g1, g2;
    while(cin >> n >> m >> s >> g1 >> g2 && n) {
        vector<edge> edges;
        vector<vector<int> > d(n, vector<int>(n));
        --s; --g1; --g2;
        REP(i, m) {
            int b1, b2, c;
            cin >> b1 >> b2 >> c;
            edges.push_back(edge(b1-1, b2-1, c));
        }
        REP(i, n) {
            bellman_ford(edges, d[i], i);
        }
        int cost = numeric_limits<int>::max();
        REP(i, n) {
            cost = min(cost, d[s][i] + d[i][g1] + d[i][g2]);
        }
        cout << cost << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098843

ベルマン・フォードは次のような実装でもよい。

void bellman_ford(const vector<edge> &edges, vector<int> &d, const int s) {
    d.assign(d.size(), INF);
    d[s] = 0;
    for(int i=0; i < edges.size(); ++i) {
        edge e = edges[i];
        if (d[e.dst] > d[e.src] + e.cost) {
            d[e.dst] = d[e.src] + e.cost;
            i = -1;
        }
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098773

ワーシャル・フロイド

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

struct edge {
    int src, dst, cost; 
    edge(int s, int t, int c): src(s), dst(t), cost(c) {}
};
const int INF = 1e8;

void warshall_floyd(vector<vector<int> > &d, vector<edge> &edges) {
    for(size_t i=0; i<d.size(); ++i) {
        d[i].assign(d[i].size(), INF);
        d[i][i] = 0;
    }
    for(auto &e : edges) {
        d[e.src][e.dst] = e.cost;
    }
    const size_t n = d.size();
    for(size_t j=0; j<n; ++j) {
        for(size_t i=0; i<n; ++i) {
            for(size_t k=0; k<n; ++k) {
                d[i][k] = min(d[i][k], d[i][j] + d[j][k]);
            }
        }
    }
}

int main(void) {
    int n, m, s, g1, g2;
    while(cin >> n >> m >> s >> g1 >> g2 && n) {
        vector<edge> edges;
        vector<vector<int> > d(n, vector<int>(n, INF));
        --s; --g1; --g2;
        REP(i, m) {
            int b1, b2, c;
            cin >> b1 >> b2 >> c;
            edges.push_back(edge(b1-1, b2-1, c));
        }
        warshall_floyd(d, edges);
        int cost = numeric_limits<int>::max();
        REP(i, n) {
            cost = min(cost, d[s][i] + d[i][g1] + d[i][g2]);
        }
        cout << cost << endl;
    }
 }

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098872

追記: 添字の順番を間違えたワーシャル・フロイド

qiita.com

KIJ （正しい）

for(size_t k=0; k<n; ++k) {
    for(size_t i=0; i<n; ++i) {
        for(size_t j=0; j<n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455812

KJI （KIJと同じはず）

for(size_t k=0; k<n; ++k) {
    for(size_t j=0; j<n; ++j) {
        for(size_t i=0; i<n; ++i) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455808

IJK

for(size_t i=0; i<n; ++i) {
    for(size_t j=0; j<n; ++j) {
        for(size_t k=0; k<n; ++k) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

WA: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455813

IJK x 3

for(size_t i=0; i<n; ++i) {
    for(size_t j=0; j<n; ++j) {
        for(size_t k=0; k<n; ++k) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}
for(size_t i=0; i<n; ++i) {
    for(size_t j=0; j<n; ++j) {
        for(size_t k=0; k<n; ++k) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}
for(size_t i=0; i<n; ++i) {
    for(size_t j=0; j<n; ++j) {
        for(size_t k=0; k<n; ++k) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455814

IKJ x 3

for(size_t i=0; i<n; ++i) {
    for(size_t k=0; k<n; ++k) {
        for(size_t j=0; j<n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}
for(size_t i=0; i<n; ++i) {
    for(size_t k=0; k<n; ++k) {
        for(size_t j=0; j<n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}
for(size_t i=0; i<n; ++i) {
    for(size_t k=0; k<n; ++k) {
        for(size_t j=0; j<n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455815

JIK x 3

for(size_t j=0; j<n; ++j) {
    for(size_t i=0; i<n; ++i) {
        for(size_t k=0; k<n; ++k) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}
for(size_t j=0; j<n; ++j) {
    for(size_t i=0; i<n; ++i) {
        for(size_t k=0; k<n; ++k) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}
for(size_t j=0; j<n; ++j) {
    for(size_t i=0; i<n; ++i) {
        for(size_t k=0; k<n; ++k) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455817

JKI x 3

for(size_t j=0; j<n; ++j) {
    for(size_t k=0; k<n; ++k) {
        for(size_t i=0; i<n; ++i) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}
for(size_t j=0; j<n; ++j) {
    for(size_t k=0; k<n; ++k) {
        for(size_t i=0; i<n; ++i) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}
for(size_t j=0; j<n; ++j) {
    for(size_t k=0; k<n; ++k) {
        for(size_t i=0; i<n; ++i) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455819

AOJ 1608: Selection of Participants of an Experiment

問題

Selection of Participants of an Experiment | Aizu Online Judge

  • 数列の中で最も差の小さい2つの数の差を出力する

コード

#include <bits/stdc++.h>
  
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int n;
    vector<int> a;
    while(cin >> n && n) {
        a.resize(n);
        REP(i, n) cin >> a[i];
        int ans = numeric_limits<int>::max();
        sort(a.begin(), a.end());
        REP(i, n-1) ans = min(ans, a[i+1]-a[i]);
        cout << ans << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2094065

CODE FESTIVAL 2016 Final

A問題

A: Where's Snuke? - CODE FESTIVAL 2016 Final | AtCoder

  • snukeという文字列がある場所の列(アルファベット)と行(数字)を出力

コード

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
string s;
int H, W;
 
int main(void) {
    cin >> H >> W;
    REP(i, H) {
        REP(j, W) {
            cin >> s;
            if(s=="snuke") {
                char c = 'A'+j;
                cout << c << i+1 << endl;
            }
        }
    }
}

Submission #991415 - CODE FESTIVAL 2016 Final | AtCoder

B問題

B: Exactly N points - CODE FESTIVAL 2016 Final | AtCoder

  • 和がNになる重複のない自然数の集合で最大の数字が最も小さい集合を出力せよ

方針

  • m(m+1)/2 > Nとなる最小のmを取り、大きいものから順に除外できる数字を除外していって、ちょうどNになる集合を作る

コード

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    int m = 1;
    for(int i=1; i<=N; ++i) {
        if(i*(i+1)/2 >= N) {
            m = i;
            break;
        }
    }
    int res = m*(m+1)/2 - N;
    vector<int> contain(m+1);
    contain.assign(contain.size(), 1);
    for(int i=m; i>0; --i) {
        if(res == 0) break;
        if(res-i >= 0) {
            res -= i;
            contain[i] = 0;
        }
    }
    for(int i=1; i<=m; ++i) {
        if(contain[i]) cout << i << endl;
    }
}

Submission #992560 - CODE FESTIVAL 2016 Final | AtCoder

C問題

C: Interpretation - CODE FESTIVAL 2016 Final | AtCoder

  • N人が話すM種類の言語が与えられる。全員が意思疎通可能か答えろ

方針

  • N+M個の頂点を持つ二部グラフを作って人を表すN個の頂点が連結かどうか調べる
  • 連結判定はDFSでできる

コード

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
vector<vector<int> > edge;
vector<bool> visit;
 
void dfs(int v) {
    if(visit[v]) return;
    visit[v] = true;
    for(int i=0; i<edge[v].size(); ++i) {
        dfs(edge[v][i]);
    }
}
 
int main(void) {
    int N, M;
    int K, L;
    cin >> N >> M;
    edge.resize(N+M);
    REP(i, N) {
        cin >> K;
        edge[i].resize(K);
        REP(j, K) {
            cin >> L;
            L = N+L-1;
            edge[i][j] = L;
            edge[L].push_back(i);
        }
    }
    visit.resize(N+M);
    dfs(0);
    REP(i, N) {
        if(!visit[i]) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}

Submission #993138 - CODE FESTIVAL 2016 Final | AtCoder

D問題

通らず

E問題

部分点を狙ってt秒でできる最大クッキー数を考えたが失敗

AOJ 1600: Entrance Examination

問題

Entrance Examination | Aizu Online Judge

codefestival前の肩ならし

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    int m, nmin, nmax;
    while(cin >> m >> nmin >> nmax && m) {
        vector<int> p(m);
        REP(i, m) scanf("%d", &p[i]);
        sort(p.begin(), p.end(), greater<int>());
        int gap = 0;
        int ans = 0;
        for(int i=nmin-1; i<nmax; ++i) {
            if(p[i]-p[i+1] >= gap) {
                gap = p[i]-p[i+1];
                ans = i+1;
            }
        }
        printf("%d\n", ans);
    }
}

CODE FESTIVAL 2016 qual C

A問題

A: CF - CODE FESTIVAL 2016 qual C | AtCoder

文字列がCFを部分文字列として含むか判定せよ

方針

  • Cを見つけたらレベルへ、レベル1でFを見つけたらクリアみたいな

    コード

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    string s;
    int k=0;
    cin >> s;
    for(int i=0; i<s.size(); ++i) {
        if(k==0 && s[i]=='C') k=1;
        if(k==1 && s[i]=='F') {k=2; break;}
    }
    if(k==2) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Submission #942379 - CODE FESTIVAL 2016 qual C | AtCoder

B問題

B: K個のケーキ / K Cakes - CODE FESTIVAL 2016 qual C | AtCoder

なるべく連続したケーキを食べないようにするとき、連続したケーキを食べる回数

方針

可能なら前回食べたケーキを食べないようにして、残りが一番多いケーキを食べる

コード

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    int K, T;
    int a[101];
    cin >> K >> T;
    REP(i, T) {
        cin >> a[i];
    }
    int ans = 0;
    int max = 0, max_index=-1;
    REP(j, T) if(a[j] > max) {max = a[j]; max_index = j;}
    int before = max_index;
    a[max_index]--;
    REP(i, K-1) {
        max = 0, max_index=-1;
        REP(j, T) if(a[j] > max && j!=before) {max = a[j]; max_index = j;}
        if(max_index != -1) {
            before = max_index;
            a[max_index]--;
        }
        else {
            a[before]--; ans++;
        }
    }
    cout << ans << endl;
}

Submission #943260 - CODE FESTIVAL 2016 qual C | AtCoder

C問題

C: 二人のアルピニスト / Two Alpinists - CODE FESTIVAL 2016 qual C | AtCoder

  • 右から見てそこまでで一番高い山と左から見たそこまでで一番高い山の標高が与えられる
  • 情報に矛盾があれば0、なければありえる山の高さの場合の数を出力

    方針

  • 各山についてあり得る標高の種類を記録しておいて後で掛ける
  • i番目のデータで最高標高が更新されていたら1通りに確定
  • 確定しない場合はその時点での標高通りの組み合わせがある。右からと左からで低い方
  • 左から確定した山の高さを使って、右から見たときの最高標高が確定値よりも低かったら矛盾

    コード

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

ll T[100001], A[100001];
ll cand[100001], kaku[100001];
ll mod = 1000000007;
int main(void) {
    int N;
    bool flag = true;
    cin >> N;
    REP(i, N) cin >> T[i];
    REP(i, N) cin >> A[i];
    if(T[N-1] != A[0]) {
        cout << 0 << endl;
        return 0;
    }
    cand[0] = 1;
    FOR(i, 1, N) {
        if(T[i] > T[i-1]) {
            cand[i] = 1;
            kaku[i] = T[i];
        }
        else {
            cand[i] = T[i];
            kaku[i] = -1;
        }
    }
    cand[N-1] = 1;
    for(int i=N-2; i>=0; --i) {
        if(kaku[i] != -1 && A[i] < kaku[i]) {
            flag = false;
            break;
        }
        if(A[i] > A[i+1]) cand[i] = 1;
        else cand[i] = min(cand[i], A[i]);
    }
    if(flag == false) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 1;
    REP(i, N) {
        ans = (ans*cand[i])%mod;
    }
    cout << ans << endl;
}

Submission #944505 - CODE FESTIVAL 2016 qual C | AtCoder

D, E

解けない

CODE FESTIVAL 2016 qual A

来世に期待

A

A: CODEFESTIVAL 2016 - CODE FESTIVAL 2016 qual A | AtCoder

  • 長さ12の文字列sの前半4文字と後半8文字の間に半角スペースを1つ挿入して出力せよ
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); ++i)
 
int main(void) {
    string s;
    cin >> s;
    cout << s.substr(0, 4) << " " << s.substr(4,11) << endl;
}

Submission #890791 - CODE FESTIVAL 2016 qual A | AtCoder

std::string::substr()の関数名を正確に覚えていなかったから検索してた。

B

B: 仲良しうさぎ / Friendly Rabbits - CODE FESTIVAL 2016 qual A | AtCoder

  • N行の入力でうさぎiがうさぎjを好きという情報が与えられる。(i != j)
  • うさぎiがうさぎjを好き かつ うさぎjがうさぎiを好きというペアの数を求めよ
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); ++i)
 
int R[100001];
 
int main(void) {
    int N, a;
    cin >> N;
    rep(i, N) {
        cin >> a;
        R[i] = a-1;
    }
    int ans = 0;
    rep(i, N) {
        if(R[R[i]] == i) ans++;
    }
    cout << ans/2 << endl;
}

Submission #892907 - CODE FESTIVAL 2016 qual A | AtCoder

  • 0-indexedにするために入力から1引く処理を入れた
  • 配列サイズを間違えていて1WA

C

C: 次のアルファベット / Next Letter - CODE FESTIVAL 2016 qual A | AtCoder - 文字列から1文字選んで次の文字(zの次はa)にする操作をK回まで行える。辞書順最小の文字列を作れ

さすがに余裕だと思っていたら、ここでハマって終了。

ACするコード (ジャッジ結果)

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); ++i)
 
int main(void) {
    string s;
    int K, n;
    cin >> s >> K;
    n = s.size()-1;
    rep(i, n) {
        int p = 'z'-s[i]+1;
        if(s[i] != 'a' && K >= p) {
            K -= p;
            s[i] = 'a';
        }
    }
    s[n] = 'a' + (s[n]-'a'+K)%26;
    cout << s << endl;
}

ACしないコード (ジャッジ結果)

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); ++i)
 
int main(void) {
    string s;
    int K, n;
    cin >> s >> K;
    n = s.size()-1;
    rep(i, n) {
        int p = 'z'-s[i]+1;
        if(s[i] != 'a' && K >= p) {
            K -= p;
            s[i] = 'a';
        }
    }
    s[n] += K%26;
    if(s[n] > 'z') s[n] = 'a' + (s[n]-'z'-1);
    cout << s << endl;
}

一度zより大きい値を入れてから戻すという処理を書いたら、char型に入れられる値の範囲が-128から127（一般的な環境の話）なせいでif文が成立せず通らなくなっていたようだ。 ダメになる例

今までASCIIコードを操作する問題では数字(ASCIIコードで48〜57）しか扱ったことがなかったのでこういうハマり方をしたことがなかった。

以後気をつけよう。

D

D: マス目と整数 / Grid and Integers - CODE FESTIVAL 2016 qual A | AtCoder

  • 任意の2x2の正方形が左上+右下=右上+左下を満たすようにRxCのマス目に非負整数を書き込むことができるか

editorialにある通り実装したのに1時間かかった

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;

using namespace std;

int R, C, N;
vector<ll> w;

struct E{
    int to, cost;
    E(int t, int c): to(t), cost(c) {};
};
vector<vector<E> > edge;
ll rmin, cmin;

bool dfs(int v) {
    if(v < R) rmin = min(rmin, w[v]);
    else cmin = min(cmin, w[v]);
    REP(i, edge[v].size()) {
        E e = edge[v][i];
        if(w[e.to] != -1) {
            if(w[v]+w[e.to]!=e.cost) return false;
        } else {
            w[e.to] = e.cost - w[v];
            if(!dfs(e.to)) return false;
        }
    }
    return true;
}

int main(void) {
    int tr, tc, ta;
    cin >> R >> C >> N;

    edge.resize(R+C);
    REP(i, N) {
        cin >> tr >> tc >> ta;
        tr--; tc--;
        edge[tr].push_back(E(R+tc, ta));
        edge[R+tc].push_back(E(tr, ta));
    }

    w.resize(R+C);
    w.assign(R+C, -1);

    REP(i, R+C) {
        if(w[i] != -1 || edge[i].size() == 0) continue;
        w[i] = 0;
        rmin = numeric_limits<ll>::max();
        cmin = numeric_limits<ll>::max();
        if(!dfs(i) || rmin+cmin < 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Submission #899631 - CODE FESTIVAL 2016 qual A | AtCoder

  • 解説中の「上側にR個の頂点を並べ，下側にC個の頂点を並べ」たグラフを、前のR個が上側・後ろのC個が下側となる全体でR+C個の頂点を持つグラフとして表現し、dfsで条件判定した
  • rminとcminで非負になることを確認した
  • 重みはlong long intでないとオーバーフローしてWA（それでハマってた）。

E

そのうち……

Codeforces Round #372 (Div. 2)

2回目のCodeforces。

A問題

http://codeforces.com/contest/716/problem/A

入力の間隔がcを超えたらリセット、そうでなければインクリメントという感じで数えていく

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); ++i)

int main(void) {
    int n, c, ans, t, before;
    cin >> n >> c;
    ans = 0;
    before = 0;
    rep(i, n) {
        cin >> t;
        if(t - before > c) ans = 1;
        else ans++;
        before = t;
    }
    cout << ans << endl;
}

B問題

http://codeforces.com/contest/716/problem/B

入力文字列の長さ26の部分列がA〜Zを重複なく含むようにする。

長さ26の部分列を全て見て、2回以上出現するアルファベットがなければいい感じに埋めてつくれる。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); ++i)

int main(void) {
    string S;
    cin >> S;
    bool none = true;

    if(S.size() < 26) {
        cout << -1 << endl;
        return 0;
    }

    char list[26];
    rep(i, S.size()-25) {
        rep(j, 26) list[j] = 0;
        for(int j=i; j<i+26; ++j) {
            list[S[j]-'A']++;
        }
        bool flag = true;
        rep(j, 26) {
            if(list[j] > 1) flag = false;
        }
        if(flag) {
            int k = 0;
            for(int j=0; j<S.size(); ++j) {
                if(j >= i && j<i+26) {
                    if(S[j] == '?') {
                        for(; k<26; ++k) {
                            if(list[k] == 0) {
                                char c = 'A'+k;
                                cout << c;
                                list[k] = 1;
                                break;
                            }
                        }
                    } else {
                        cout << S[j];
                    }
                }
                else {
                    if(S[j] == '?') {
                        cout << 'A';
                    } else {
                        cout << S[j];
                    }
                }
            }
            cout << endl;
            none = false;
            break;
        }
    }
    if(none) cout << -1 << endl;
}

C問題

http://codeforces.com/contest/716/problem/C

変なルールに従ってレベルアップするために何回ボタンを押せばいいか。

今のレベルと次のレベルの公倍数の平方になるまでボタンを押せばレベルアップできるので、各レベルの回数はO(1)で求まる。 全部用意しておいて入力に従って表示するだけ。

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i, n) for(int i=0; i<(int)(n); ++i)

ll dp[100001];

int main(void) {
    dp[1] = 2;
    for(ll k=2; k<=100000; ++k) {
        dp[k] = (k+1)*(k+1)*k - (k-1);
    }
    int n;
    cin >> n;
    for(int i=1; i<=n; ++i) {
        cout << dp[i] << endl;
    }
}

D問題, E問題

Dは?を1としてdijkstraで最短路を求めてから、最短路がLになるよう増やせばいいのかなと思っていろいろ試したがそれが最短路ではなくなってしまう場合を考慮してなくて時間内に解けず。 Eは開いてすらいない。

まだsystem test通っていないのでACかは不明。