AtCoder Beginner Contest 167 解説

https://atcoder.jp/contests/abc167/tasks

36位。AからDはpythonで提出。EFはC++。

A問題

startswithという接頭辞になっているかどうか判定する関数があるのでそれを使った。

def ZZ(): return list(map(int, input().split()))
def Z(): return int(input())

S = input()
T = input()
if T.startswith(S):
    print('Yes')
else:
    print('No')

B問題

制約を見てなくてS = [1] * A + [0] * B + [-1] * C; print(sum(S[:K]))を提出してしまった。

def ZZ(): return list(map(int, input().split()))
def Z(): return int(input())

A, B, C, K = ZZ()
ans = 1 * min(A, K)
K -= min(A, K)
ans += 0 * min(B, K)
K -= min(B, K)
ans += -1 * min(C, K)
print(ans)

C問題

全探索。a,*b=[1,2,3]とするとa=1,b=[2,3]になるらしい。

def ZZ(): return list(map(int, input().split()))
def Z(): return int(input())

N, M, X = ZZ()
C = []
A = []
for _ in range(N):
    tmp = ZZ()
    C.append(tmp[0])
    A.append(tmp[1:])

ans = 10 ** 100
for i in range(1 << N):
    rikai = [0] * M
    cost = 0
    for j in range(N):
        if i >> j & 1:
            cost += C[j]
            for k in range(M):
                rikai[k] += A[j][k]
    if min(rikai) >= X:
        ans = min(ans, cost)

if ans == 10 ** 100: ans = -1
print(ans)

冪集合列挙。more_itertoolsにあるけどAtCoderでは使えない。

from itertools import combinations, chain
def powerset(a):
    return chain(*(combinations(a, i) for i in range(len(a) + 1)))

冪集合列挙と組合せ列挙はビット演算で簡単にできるのでありがたみが薄い。

D問題

対称群の累乗。

def ZZ(): return list(map(int, input().split()))
def Z(): return int(input())

N, K = ZZ()
A = ZZ()
for i in range(N):
    A[i] -= 1

def mul(a, b):
    return [a[b[i]] for i in range(len(a))]

def beki(a, b):
    res = list(range(len(a)))
    while b > 0:
        if b & 1:
            res = mul(res, a)
        a = mul(a, a)
        b >>= 1
    return res

A = beki(A, K)
print(A[0] + 1)

E問題

左から順に色を決めていく。

• 先頭がM通り
• i と i+1 が異なる色の場合は、i+1はM-1通り。
• i と i+1 が同じ色の場合は、i+1は1通り。

たとえばO|OO|OOという区切り方をした場合、M*(M-1)*1*(M-1)*1。結局、区切りの個数だけわかれば計算できる。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

constexpr int MOD = 998244353;

class mint {
  int n;
public:
  mint(int n_ = 0) : n(n_) {}
  explicit operator int() { return n; }
  friend mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
  friend mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; }
  friend mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; }
  friend mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
  friend mint &operator+=(mint &a, mint b) { return a = a + b; }
  friend mint &operator-=(mint &a, mint b) { return a = a - b; }
  friend mint &operator*=(mint &a, mint b) { return a = a * b; }
  friend bool operator==(mint a, mint b) { return a.n == b.n; }
  friend bool operator!=(mint a, mint b) { return a.n != b.n; }
  friend istream &operator>>(istream &i, mint &a) { return i >> a.n; }
  friend ostream &operator<<(ostream &o, mint a) { return o << a.n; }
};

vector<mint> F_{1, 1}, R_{1, 1}, I_{0, 1};

void check_fact(int n) {
  for (int i = I_.size(); i <= n; i++) {
    I_.push_back(I_[MOD % i] * (MOD - MOD / i));
    F_.push_back(F_[i - 1] * i);
    R_.push_back(R_[i - 1] * I_[i]);
  }
}

mint I(int n) { check_fact(n); return n < 0 ? 0 : I_[n]; }
mint F(int n) { check_fact(n); return n < 0 ? 0 : F_[n]; }
mint R(int n) { check_fact(n); return n < 0 ? 0 : R_[n]; }
mint C(int n, int r) { return F(n) * R(n - r) * R(r); }
mint P(int n, int r) { return F(n) * R(n - r); }
mint H(int n, int r) { return n == 0 ? (r == 0) : C(n + r - 1, r); }

mint modpow(mint a, long long b) {
  mint res = 1;
  while (b > 0) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}   

int main() {
    int N, M, K; cin >> N >> M >> K;
    mint ans = 0;
    for (int i = 0; i <= K; i++) {
        ans += C(N - 1, i) * modpow(M - 1, N - 1 - i) * M;
    }
    cout << ans << endl;
}

F問題

正当性は示してない。変な比較関数を使う。SとTのどっちを前にするか考えると、最下点をできるだけ高い方を持ってくる方がいいので、そうなるように組んだつもり。順序になっているか不明。本質が同じ問題が過去に出てて、そのときはこれで通したはず。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

pair<int, int> f(string s) {
    int x = 0;
    int res = 0;
    for (char c : s) {
        if (c == '(') x++;
        if (c == ')') x--;
        res = min(res, x);
    }
    return make_pair(res, x);
}

int main() {
    int N; cin >> N;
    vector<string> S(N); rep(i, N) cin >> S[i];
    vector<int> F(N), G(N);
    rep(i, N) {
        auto tmp = f(S[i]);
        F[i] = tmp.first;
        G[i] = tmp.second;
    }
    vector<int> ord(N); rep(i, N) ord[i] = i;
    sort(range(ord), [&](int i, int j) {
        int ij = min(F[i], G[i] + F[j]);
        int ji = min(F[j], G[j] + F[i]);
        if (ij != ji) return ij > ji;
        return G[i] > G[j];
    });
    string ans;
    for (int i : ord) ans += S[i];
    auto tmp = f(ans);    
    cout << (tmp.first == 0 and tmp.second == 0 ? "Yes" : "No") << endl;
}