コンテストがunratedになったのは残念だが、5完でした。時間の問題もあり、若干点数に対して簡単な問題が選択されているような感じがしました。

長いので続きから。

A問題

要約: 指定の文字を小文字に置換せよ

n, k = map(int, input().split())
s = input()
print(s[:k - 1] + s[k - 1].lower() + s[k:])

B問題

atcoder.jp

要約: YYMM か MMYY かのフォーマットに当てはまるか？

これ単純に分岐がめんどくさかった。綺麗に書く方法はあるかもしれないが。。。

s = input()
f, t = s[:2], s[2:]
YYMM = 0 <= int(f) <= 99 and 1 <= int(t) <= 12
MMYY = 0 <= int(t) <= 99 and 1 <= int(f) <= 12
if YYMM and MMYY:
    print('AMBIGUOUS')
elif YYMM:
    print('YYMM')
elif MMYY:
    print('MMYY')
else:
    print('NA')

C問題

atcoder.jp

要約: とあるゲームをするが、そのゲームの勝率を求めてください。

ゲームルールに沿って勝率を計算していく。最初の時点で勝つ場合もあるので、その勝率は最初に足しておく。それ以外の場合は、コインを振って勝つしかないのだが、得点の増え方は2のべき乗になるので、予め2のべき乗の配列を用意してやって、それを超えた瞬間に勝ちとして確率に足してあげるとOK。

n, k = map(int, input().split())
ans = 0
if n >= k:
    ans = (n - k + 1) / n
al = [2 ** i for i in range(1, 18)]
for i in range(1, min(n + 1, k)):
    for j in al:
        if i * j >= k:
            ans += (1 / n) * (1 / j)
            break
print(ans)

D問題

atcoder.jp

要約: 木が与えられるので、ある点Aとある点Bを結んだとき、偶数なら同じ色、奇数なら違う色で塗ってください。

木の形を考えると、複雑にループする形や複数の木が生えていない。よって、最初の1箇所を決めて、単純に深さ優先なり幅優先なりで探索していけばいいことがわかる。

色の塗り分けはよく考えると、現在の頂点と次の頂点の距離だけを考えれば良いので、単純に求まる。

本番では変に距離の計算をしてしまったり、デバッグ用の出力スペースに（そういうマクロを書いていて、手元ではオプション付きで実行をしている）答えの出力を書いてしまい、無駄なWAをはやしてしまったので反省。

vector<int> mark;
vector<bool> checked;
vector<vector<pair<int, int>>> vvp;
int current_mark = -1;
 
void dfs(int index) { 
    if(current_mark == -1) {
        mark[1] = 0;
        current_mark = 0;
    }
    for(int i = 0; i < vvp[index].size(); i++) {
        int n = vvp[index][i].first;
        int c = vvp[index][i].second;
        if(checked[n]) {
            continue;
        }
        mark[n] = c % 2 == 1 ? (mark[index] ^ 1) : mark[index];
        checked[n] = true;
        dfs(n);
    }
}
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.precision(16);
 
    int n;
    cin >> n;
 
    mark.resize(n + 1);
    checked.resize(n + 1);
    vvp.resize(n + 1);
 
    REP(i, n - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        vvp[u].push_back(make_pair(v, w));
        vvp[v].push_back(make_pair(u, w));
    }
 
    dfs(1);
 
    for(int i = 1; i <= n; i++) {
        cout << mark[i] << endl;
    }
 
    return 0;
}

E問題

atcoder.jp

要約: 裏側になっているカードのすべての値を知るために、表側にする必要がある最小限の枚数を答えてください。なお、カードの値は計算式で求めることができ、計算式には別のカードの値を使うことがわかっている。

グルーピングして同じグループならあるカードをめくったときにたどっていくことができる構造であることがわかる。なのでUnion−Findを使って、グループを集計する。

Union-FindのC++実装を持っていなかったので、ググってそれらしいのを見つけてはったが、問題なかった。

参考としてURLを貼っておきます（ありがとうございました）。そのまま貼って使えました。

qiita.com

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.precision(16);
 
    int n, m;
    cin >> n >> m;
 
    UnionFind tree(n);
    for(int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        tree.unite(x - 1, y - 1);
    }  
 
    set<int> s;
    for(int i = 0; i < n; i++) {
        s.insert(tree.root(i));
    }
    cout << s.size() << endl;
 
    return 0;
}

F問題（本番解けず）

atcoder.jp

要約: 長さ 2^(m+1) の配列がある。ある値 L に対して、 Lが現れる ai ~ aj の区間がKとなる配列の例を出力してください。

解説を読んでしまったのだが、 2^m の値が重要でKの値によっては答えが出ないパターンがあるので、それをカットすることと、Mの値を見て1以下の場合だけ特殊な処理をする。で、それ以降の場合は k をうまいこと作り出せるように配列を作るのだが、自分が思っていたよりも簡単な方法で解説は作っていたので、頭がいいなあと思いました（小並感）

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.precision(16);
 
    ll m, k;
    cin >> m >> k;
    ll p2m = pow(2, m);
 
    if(m <= 1) {
        if(k == 0) {
            cout << (m == 0 ? "0 0" : "0 0 1 1") << endl;
        } else {
            cout << -1 << endl;
        }
        return 0;
    }
 
    if(k >= pow(2, m)) {
        cout << -1 << endl;
        return 0;
    }
 
    vector<ll> b(p2m);
    vector<ll> c(p2m);
    for(ll i = 0; i < p2m; i++) {
        b[i] = i;
        c[p2m - i - 1] = i;
    }
    b.erase(b.begin() + k);
    c.erase(c.begin() + (p2m - k - 1));
    
    vector<ll> ans(p2m * 2);
    ll idx = 0;
    for(auto bi : b) { ans[idx] = bi; idx++; }
    ans[idx++] = k;
    for(auto ci : c) { ans[idx] = ci; idx++; }
    ans[idx++] = k;
 
    for(int i = 0; i < idx; i++) {
        cout << ans[i] << (i != idx - 1 ? ' ' : '\n');
    }  
 
    return 0;
}

まとめ

普段より簡単な感じがしたので（時間に対する問題の数の問題かと思っている）、次もかまけないように頑張りたいです。

名もなき未知

ABC126に参加した

A問題

B問題

C問題

D問題

E問題

F問題（本番解けず）

まとめ