ABC 002

abc002.contest.atcoder.jp

A問題

#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 a, b;
    cin >> a >> b;
    cout << max(a, b) << endl;
}

Submission #1024114 - AtCoder Beginner Contest 002 | AtCoder

B問題

#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 W;
    cin >> W;
    REP(i, W.size()) {
        if(W[i] != 'a' && W[i] != 'i' && W[i] != 'u'
                       && W[i] != 'e' && W[i] != 'o') {
            cout << W[i];
        }
    }
    cout << endl;
}

Submission #1024115 - AtCoder Beginner Contest 002 | AtCoder

C問題

ヘロンの公式

#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 x[3], y[3];
    REP(i, 3) cin >> x[i] >> y[i];
    double a = sqrt(pow(x[0] - x[1], 2.0) + pow(y[0] - y[1], 2.0));
    double b = sqrt(pow(x[1] - x[2], 2.0) + pow(y[1] - y[2], 2.0));
    double c = sqrt(pow(x[2] - x[0], 2.0) + pow(y[2] - y[0], 2.0));
    double s = (a+b+c)/2.0;
 
    printf("%.3f\n", sqrt(s*(s-a)*(s-b)*(s-c)));
}

D問題

ビット全探索で最大クリークを求める。

bitsetとかいう便利ライブラリがあることを知った。

#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, M;
    cin >> N >> M;
    vector<vector<int> > e(N, vector<int>(N, 0));
    REP(i, M) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        e[x][y] = e[y][x] = 1;
    }
    int ans = 0;
    for(int bit=1; bit<(1<<N); ++bit) {
        int t = bitset<12>(bit).count();
        if(t <= ans) continue;
 
        bool flag = true;
        REP(i, N) {
            REP(j, i) {
                if((bit >> i & bit >> j & 1) && e[i][j] != 1) {
                    flag = false;
                }
            }
        }
        if(flag) ans = t;
    }
    cout << ans << endl;
}

Submission #1024133 - AtCoder Beginner Contest 002 | AtCoder

ABC 001

abc001.contest.atcoder.jp

A問題

#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 a, b;
    cin >> a >> b;
    cout << a-b << endl;
}

Submission #1024112 - AtCoder Beginner Contest 001 | AtCoder

B問題

#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;
    cin >> m;
    int VV;
    if(m < 100) VV = 0;
    else if(m <= 5000) VV = m*10/1000.0;
    else if(m >= 6000 && m <= 30000) VV = m/1000.0+50;
    else if(m >= 35000 && m <= 70000) VV = (m/1000.0-30)/5.0 + 80;
    else if(m >= 70000) VV = 89;
    printf("%02d\n", VV);
}

Submission #1024109 - AtCoder Beginner Contest 001 | AtCoder

C問題

やるだけなんだけど、バグる。

#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 Deg, Dis;
    string a;
    int b;
    cin >> Deg >> Dis;
 
    int I = (Dis/6.0 + 0.5);
    double D = double(I) / 10.0;
 
    if     (D >= 0.0 && D <= 0.2)          a = "C";
    else if(Deg >= 112.5 && Deg < 337.5)   a = "NNE";
    else if(Deg >= 337.5 && Deg < 562.5)   a = "NE";
    else if(Deg >= 562.5 && Deg < 787.5)   a = "ENE";
    else if(Deg >= 787.5 && Deg < 1012.5)  a = "E";
    else if(Deg >= 1012.5 && Deg < 1237.5) a = "ESE";
    else if(Deg >= 1237.5 && Deg < 1462.5) a = "SE";
    else if(Deg >= 1462.5 && Deg < 1687.5) a = "SSE";
    else if(Deg >= 1687.5 && Deg < 1912.5) a = "S";
    else if(Deg >= 1912.5 && Deg < 2137.5) a = "SSW";
    else if(Deg >= 2137.5 && Deg < 2362.5) a = "SW";
    else if(Deg >= 2362.5 && Deg < 2587.5) a = "WSW";
    else if(Deg >= 2587.5 && Deg < 2812.5) a = "W";
    else if(Deg >= 2812.5 && Deg < 3037.5) a = "WNW";
    else if(Deg >= 3037.5 && Deg < 3262.5) a = "NW";
    else if(Deg >= 3262.5 && Deg < 3487.5) a = "NNW";
    else                                   a = "N";
 
    if     (D >= 0.0 && D <= 0.2)   b = 0;
    else if(D >= 0.3 && D <= 1.5)   b = 1;
    else if(D >= 1.6 && D <= 3.3)   b = 2;
    else if(D >= 3.4 && D <= 5.4)   b = 3;
    else if(D >= 5.5 && D <= 7.9)   b = 4;
    else if(D >= 8.0 && D <= 10.7)  b = 5;
    else if(D >= 10.8 && D <= 13.8) b = 6;
    else if(D >= 13.9 && D <= 17.1) b = 7;
    else if(D >= 17.2 && D <= 20.7) b = 8;
    else if(D >= 20.8 && D <= 24.4) b = 9;
    else if(D >= 24.5 && D <= 28.4) b = 10;
    else if(D >= 28.5 && D <= 32.6) b = 11;
    else if(D >= 32.7)              b = 12;
    cout << a << " " << b << endl;
}

Submission #1024104 - AtCoder Beginner Contest 001 | AtCoder

D問題

いもす法

#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, S, E;
    cin >> N;
    vector<int> record(24*12+1, 0);
    REP(i, N) {
        scanf("%d-%d", &S, &E);
        record[(S/100)*12 + (S%100)/5] += 1;
        record[(E/100)*12 + (E%100)/5 + ((E%100)%5 > 0 ? 1 : 0)] -= 1;
    }
    int t = 0;
    int start_time = 0;
    REP(i, record.size()) {
        if(t == 0 && record[i] > 0) {
            printf("%02d%02d-", i/12, (i%12) * 5);
        }
        if(t > 0 && t + record[i] == 0) {
            printf("%02d%02d\n", i/12, (i%12) * 5);
        }
        t += record[i];
    }
}

Submission #1024090 - AtCoder Beginner Contest 001 | AtCoder

AOJ 2005: Water Pipe Construction

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

問題

Water Pipe Construction | Aizu Online Judge

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

解法

全点対間の最小コストを求めておいて、全ての頂点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

解けない