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かは不明。

AOJ 1181: Biased Dice

問題

Biased Dice | Aizu Online Judge

  • サイコロがある場所に積まれていき、転がり落ちることができる場合は6, 5, 4という優先順位でその目の方向に転がる
  • ルールに従ってサイコロを転がしていった時に見えるサイコロについて、1〜6の目がいくつずつ上を向いているか調べよ
  • 入力として、積まれるサイコロの上面の目(t)と前面の目(f)の組がn個与えられる

方針

  • 頑張ってシミュレーションする
  • 6, 5, 4の目について[t][f]を与えたときにどちらの方向にあるかを求める配列を用意する
  • 優先順位に従って転がしていき、各場所の高さとサイコロのt, fを更新していく

コード

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

#define NO 0
#define UP 1
#define RIGHT 2
#define LEFT 3
#define DOWN 4

int h[201][201], face[201][201];
const int six[7][7] = {
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, UP, NO, LEFT, RIGHT, NO, DOWN},
    {NO, UP, RIGHT, NO, NO, LEFT, DOWN},
    {NO, UP, LEFT, NO, NO, RIGHT, DOWN},
    {NO, UP, NO, RIGHT, LEFT, NO, DOWN},
    {NO, NO, NO, NO, NO, NO, NO}
};
const int five[7][7] = {
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, NO, UP, RIGHT, LEFT, DOWN, NO},
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, LEFT, UP, NO, NO, DOWN, RIGHT},
    {NO, RIGHT, UP, NO, NO, DOWN, LEFT},
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, NO, UP, LEFT, RIGHT, DOWN, NO}
};
const int four[7][7] = {
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, NO, LEFT, UP, DOWN, RIGHT, NO},
    {NO, RIGHT, NO, UP, DOWN, NO, LEFT},
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, LEFT, NO, UP, DOWN, NO, RIGHT},
    {NO, NO, RIGHT, UP, DOWN, LEFT, NO}
};
int main(void){
    int n;
    while(cin >> n && n) {
        int t, f;
        rep(i, 201) rep(j, 201) {h[i][j] = 0; face[i][j] = -1;}
        rep(i, n) {
            cin >> t >> f;
            t; f;
            int x = 100, y = 100;
            int nx, ny;
            h[y][x]++;
            bool fall = true;
            while(fall) {
                nx = x;
                ny = y;
                fall = false;
                if(six[t][f] == UP && h[y+1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y+1;
                    f = 7-t; t = 1; 
                } else if(six[t][f] == RIGHT && h[y][x+1] < h[y][x]-1) {
                    fall = true;
                    nx = x+1;
                    t = 1;
                } else if(six[t][f] == LEFT && h[y][x-1] < h[y][x]-1) {
                    fall = true;
                    nx = x-1;
                    t = 1;
                } else if(six[t][f] == DOWN && h[y-1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y-1;
                    f = t; t = 1; 
                } else if(five[t][f] == UP && h[y+1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y+1;
                    f = 7-t; t = 2;
                } else if(five[t][f] == RIGHT && h[y][x+1] < h[y][x]-1) {
                    fall = true;
                    nx = x+1;
                    t = 2;
                } else if(five[t][f] == LEFT && h[y][x-1] < h[y][x]-1) {
                    fall = true;
                    nx = x-1;
                    t = 2;
                } else if(five[t][f] == DOWN && h[y-1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y-1;
                    f = t; t = 2;
                } else if(four[t][f] == UP && h[y+1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y+1;
                    f = 7-t; t = 3;
                } else if(four[t][f] == RIGHT && h[y][x+1] < h[y][x]-1) {
                    fall = true;
                    nx = x+1;
                    t = 3;
                } else if(four[t][f] == LEFT && h[y][x-1] < h[y][x]-1) {
                    fall = true;
                    nx = x-1;
                    t = 3;
                } else if(four[t][f] == DOWN && h[y-1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y-1;
                    f = t; t = 3;
                }
                if(fall) {
                    h[y][x]--;
                    h[ny][nx]++;
                    x = nx; y = ny;
                }
                else {
                }
            }
            face[y][x] = t;
        }
        int ans[6] = {};
        rep(i, 201) rep(j, 201) {if(face[i][j] != -1) ans[face[i][j]-1]++;}
        cout << ans[0];
        rep(i, 5) cout << " " << ans[i+1];
        cout << endl;
    }
}

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

反省

  • コードが汚い

AOJ 1174: Identically Colored Panels Connection

問題

Identically Colored Panels Connection | Aizu Online Judge

  • 電気を流すと隣接した同じ色のパネルを含めて色が変わるパネルがある
  • 隣接した同じ色のパネルは結合する
  • 左上のパネルに5回電気を流したとき、指定された色で左上と結合している最大のパネル数を求めよ

方針

  • dfsであらゆる変色パターンを試す (6の5乗なので間に合いそう）
  • パネルの変色とパネル数カウントはbfsでやる

コード

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

typedef pair<int, int> P;

int p[10][10], visited[10][10];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int h, w, c;

int dfs(int count) {
    if(count == 5) {
        int ret = 0;
        if(p[0][0] != c) return 0;
        rep(i, 10) rep(j, 10) visited[i][j] = 0;
        queue<P> que;
        que.push(P(0, 0));
        while(!que.empty()) {
            P point = que.front(); que.pop();
            if(visited[point.first][point.second] == 0) {
               visited[point.first][point.second] = 1;
               ret++;
                rep(i, 4) {
                    int ny = point.first + dy[i];
                    int nx = point.second + dx[i];
                    if(nx >= 0 && nx < w && ny >= 0 && ny < h &&
                       visited[ny][nx] == 0 && p[ny][nx] == c) {
                        que.push(P(ny, nx));
                    }
                }
            }
        }
        return ret;
    }
    int org[10][10];
    int ret = 0;
    rep(i, h) rep(j, w) org[i][j] = p[i][j];
    rep(color, 6) {
        int org_c = p[0][0];
        rep(i, 10) rep(j, 10) visited[i][j] = 0;
        queue<P> que;
        que.push(P(0, 0));
        while(!que.empty()) {
            P point = que.front(); que.pop();
            p[point.first][point.second] = color+1;
            visited[point.first][point.second] = 1;
            rep(i, 4) {
                int ny = point.first + dy[i];
                int nx = point.second + dx[i];
                if(nx >= 0 && nx < w && ny >= 0 && ny < h &&
                   visited[ny][nx] == 0 && p[ny][nx] == org_c) {
                    que.push(P(ny, nx));
                }
            }
        }
        ret = max(ret, dfs(count+1));
        rep(i, 10) rep(j, 10) p[i][j] = org[i][j];
    }
    return ret;
}

int main(void){
    while(cin >> h >> w >> c && h) {
        rep(i, h) rep(j, w) cin >> p[i][j];
        cout << dfs(0) << endl;
    }
}

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

反省

  • visitedの処理がうまく書けなくて重複カウントしていてハマった
  • 遅い(1.7s)のは仕方ないのかなと思ったら、同じような解法でもvisitedの更新をしないで済むよう実装すれば0.02sで解けていた（これとか）

AOJ 1155: How can I satisfy thee? Let me count the ways...

問題

How can I satisfy thee? Let me count the ways... | Aizu Online Judge

"true", "false", "unknown"の3種類があるロジックで、与えられた式を満たすP, Q, Rの組み合わせが何種類あるか数えよ

方針

  • P, Q, Rがそれぞれ3通りの値を取るため27通りしかないから全てを評価して満たす場合を数えればよい
  • 再帰下降構文解析をすればよい

コード

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

int formula(string &s, int P, int Q, int R, int &i) {
    if(s[i] == '-') {
        i++;
        return 2-formula(s, P, Q, R, i);
    } else if(s[i] == '(') {
        int X, Y;
        i++;
        X = formula(s, P, Q, R, i);
        if(s[i] == '*') {
            i++;
            Y = formula(s, P, Q, R, i);
            i++;
            if(X == 0) return 0;
            if(X == 1) {
                if(Y == 0) return 0;
                else return 1;
            } else {
                return Y;
            }
        } else {
            i++;
            Y = formula(s, P, Q, R, i);
            i++;
            if(X == 0) return Y;
            if(X == 1) {
                if(Y == 0) return 1;
                else return Y;
            } else {
                return 2;
            }
        }
    } else {
        int ret;
        if(s[i] >= '0' && s[i] <= '2') ret = s[i]-'0';
        else if(s[i] == 'P') ret = P;
        else if(s[i] == 'Q') ret = Q;
        else if(s[i] == 'R') ret = R;
        i++;
        return ret;
    }
}

int main(void){
    string s;
    while(cin >> s && s != ".") {
        int cnt = 0;
        rep(i, 3) rep(j, 3) {
            rep(k, 3) {
                int index = 0;
                if(formula(s, i, j, k, index) == 2) cnt++;
            }
        }
        cout << cnt << endl;
    }
}

反省

  • LL(1)文法のパーサーは初めてだったので手間取った

AOJ 1602: ICPC Calculator

問題

ICPC Calculator | Aizu Online Judge

国際反括弧会議が考えた変な記法に従って計算するプログラムを作れ

  • 各行は入れ子レベルを表す'.'・加算を表す'+'・乗算を表す'*'・整数からなる
  • 式の最初の行は入れ子レベルの数だけの'.'からなる
  • レベルnの演算子はそれ以降の行にあるレベルn+1の式に対して適用される

Lispの記法をイメージすると多分分かりやすくて

+
.2
.3

は

(+ 2 3)
*
.+
..2
..3
..4
.5

は

(* (+ 2 3 4) 5)

に対応する

方針

  • 整数のみの式ならその整数を返す
  • レベルnで演算子が来たら、レベルn+1の式全部に対して演算子を適用する
  • 再帰実行すれば何段でも対応できる

コード

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

typedef pair<int, char> P;

int getLevel(string &expr) {
    int ret = 0;
    while(expr[ret] == '.') ret++;
    return ret;
}

bool isdigit(char c) {
    return c >= '0' && c <= '9';
}

int process(vector<string> &expr, int* line) {
    int ret;
    int level = getLevel(expr[*line]);
    if(level == 0 && isdigit(expr[*line][level])) 
        return expr[*line][level]-'0';
    else if(expr[*line][level] == '+') {
        (*line)++;
        ret = 0;
        while((*line) < expr.size()) {
            int new_level = getLevel(expr[*line]);
            if(new_level == level+1) {
                if(isdigit(expr[*line][new_level]))
                    ret += expr[*line][new_level]-'0';
                else 
                    ret += process(expr, line);
                (*line)++;
            } else {
                (*line)--;
                break;
            }
        }
        return ret;
    } else if(expr[*line][level] == '*') {
        (*line)++;
        ret = 1;
        while((*line) < expr.size()) {
            int new_level = getLevel(expr[*line]);
            if(new_level == level+1) {
                if(isdigit(expr[*line][new_level]))
                    ret *= expr[*line][new_level]-'0';
                else 
                    ret *= process(expr, line);
                (*line)++;
            } else {
                (*line)--;
                break;
            }
        }
        return ret;
    }
}

int main(void){
    int n;
    string s;
    vector<string> expr;
    while(cin >> n && n) {
        cin.ignore();
        expr.clear();
        rep(i, n) {
            getline(cin, s);
            expr.push_back(s);
        }
        int line = 0;
        cout << process(expr, &line) << endl;
    }
}

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

反省

AOJ 1194: Vampire

問題

Vampire | Aizu Online Judge

  • 与えられたビルの位置から、あと何秒間太陽が隠れているか求めよ

方針

  • ビルの位置が整数値なのでビルがある場所についてグリッドを埋めていく
  • 太陽が通りうる位置についてグリッドが埋まっていなかったら太陽が通過する瞬間の時間を求める
  • 全ての埋まっていないグリッドの中で時間の最小値を求める

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
  
int s[21][41];
int main(void){
    int r, n, xl, xr, h;
    while(cin >> r >> n && r) {
        rep(i, 21) rep(j, 41) s[i][j] = 0;
        rep(i, n) {
            cin >> xl >> xr >> h;
            for(int y=0; y<h; ++y) {
                for(int x=xl+20; x<xr+20; ++x) {
                    s[y][x] = 1;
                }
            }
        }
        double mint = numeric_limits<double>::max();
        rep(y, 21) {
            for(int x=-r+20; x<r+20; ++x) {
                if(s[y][x] == 0) {
                    double t;
                    if(x<20) t = (double) y+r-sqrt(pow((double)r,2.0)-pow(x-19.0, 2.0));
                    else t = (double) y+r-sqrt(pow((double)r,2.0)-pow(x-20.0, 2.0));
                    mint = min(mint, t);
                }
            }
        }
        printf("%.4lf\n", mint);
    }
}

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

反省

  • 検索すると2分探索で決めるという解法があり、そのほうが一般的に使える解法だと思った
  • たまたま間違えて配列外アクセスしたら、coutとprintfで挙動が違うという現象に遭遇した