来世に期待

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

そのうち……