Tenka1 Programmer Beginner Contest 2019反省会 - もうカツ丼はいいよな

Cまで届かなかった。前日飲みすぎてダルかったので今後は酒を控えたい所存。

A. On the Way

Pythonでやった。

A, B, C = [int(i) for i in input().split()]

min_n = min(A, B)
max_n = max(A, B)

if min_n < C and max_n > C:
  print("Yes")
else:
  print("No")

B. `*e ****e* *e****e* **e`

文字列走査するならC++かなと思ってC++でやった。

#include <bits/stdc++.h>
using namespace std;
int main(void){
  int N, K;
  string S;
  cin >> N >> S >> K;
  char target;
  target = S.at(K-1);
  for (int i = 0; i < S.size(); i++) {
    if (S.at(i) == target) {
      cout << target;
    } else {
      cout << '*';
    }
  }
  cout << endl;
}

C. Stones

（分割してカウントするんだよな…）と思ってこういうの書いてしまっていた。

N = int(input())
S = input().strip()

def stone_cnt(idx):
  return S[:idx].count("#") + S[idx:].count(".")

left = 0
right = len(S)

ans = min([stone_cnt(i) for i in range(N+1)])
  
print(ans)

O(N²)なのでもちろんTLEだ。「境界を動かしたらカウントがどうなるか」に注目すればO(N)で解けるというのは冷静に考えれば分かりそうだったのに、冷静ではなかった。酒を飲んではいけない。

C++版の回答。

#include <bits/stdc++.h>
using namespace std;
int main(void){
  int N;
  string S;
  cin >> N >> S;
  int lb = 0;
  int rw = count(S.begin(), S.end(), '.');
  int ans = lb + rw;
  for (int i = 0; i < N; i++) {
    if (S.at(i) == '.') {
      rw--;
    } else {
      lb++;
    }
    ans = min(ans, lb + rw);
  }
  cout << ans << endl;
}

Python版の回答。

# coding: utf-8

N = int(input())
S = input().rstrip('#')

lb = 0
rw = S.count('.')
ans = lb + rw

for i in range(len(S)):
  if S[i] == '.':
    rw -= 1
  else:
    lb += 1
  ans = min(ans, rw + lb)

print(ans)

D. Three Colors

解説だけ読んでもよく分からなくて、他の人の回答を見てやっと理解できた。

Python版。TLEになる。他の人の回答を見ると少し最適化すれば通るっぽい。

ちなみにAtCoderのPyPyにはNumPyが無いっぽいので、そのままPyPy3に切り替えるという手は使えない。NumPy外してPyPy使ってみたりもしたけど私の能力ではやっぱりTLEだった。

import numpy as np
import math

MOD = 998244353

N = int(input())
a = np.array([int(input()) for _ in range(N)])

S = sum(a)

dp1 = np.zeros((N + 1, S + 1))
dp1[0, 0] = 1
dp2 = np.zeros((N + 1, S + 1))
dp2[0, 0] = 1

for i, x in enumerate(a):
  ## 長さを計算する色をcとして、cの長さに対する組み合わせを数える
  dp1[i+1, :]  += dp1[i, :] * 2 % MOD  # c以外に塗り分ける場合（各2通り追加）
  dp1[i+1, x:] += dp1[i, :-x]   % MOD  # cに塗る場合（xずらしたところに1通り追加）
  ## 2色だけを使う組み合わせを数える
  dp2[i+1, :]  += dp2[i, :]     % MOD  # cではないいずれか1色に塗る場合（各1通り）
  dp2[i+1, x:] += dp2[i, :-x]   % MOD  # cに塗る場合
  
# 全塗り分けパターン
pat = 3 ** N % MOD
# 最大の色の値が S/2 以上のパターン（三角形ができない）
s1  = 3 * sum(dp1[N, math.ceil(S / 2):]) % MOD
# 最大の色の値が S/2 に等しいパターン（重複している）
s2  = 3 * dp2[N, S // 2] % MOD if S % 2 == 0 else 0

print(int(pat - s1 + s2) % MOD)

C++版。これは通る。通るが、結構ハマりどころがあったので（%が負数を返すパターンへの対処とか多次元配列の合計のとり方とか）もう少し練習しないと本番の時間内では実装できない感じがある。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 998244353;

ll mod(ll n, ll m) {
  ll res = n % m;
  if (res < 0) res += m;
  return res;
}

ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}


int main(void){
  ll N;
  cin >> N;
  vector<ll> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
  }
  ll S = accumulate(a.begin(), a.end(), 0);
  
  vector<vector<ll>> dp1(N+1, vector<ll>(S+1, 0));
  vector<vector<ll>> dp2(N+1, vector<ll>(S+1, 0));
  dp1.at(0).at(0) = 1;
  dp2.at(0).at(0) = 1;
  
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < S; j++) {
      dp1.at(i+1).at(j) += dp1.at(i).at(j) * 2 % MOD;
      dp2.at(i+1).at(j) += dp2.at(i).at(j) % MOD;
    }
    for (int j = a.at(i); j < S+1; j++) {
      dp1.at(i+1).at(j) += dp1.at(i).at(j-a.at(i)) % MOD;
      dp2.at(i+1).at(j) += dp2.at(i).at(j-a.at(i)) % MOD;
    }
  }
  
  ll pat;
  pat = modpow(3, N, MOD);
  ll s1 = 0;
  ll s2 = 0;

  if (S % 2 == 0) {
    for (int i = S/2; i < S+1; i++) {
      s1 += 3 * dp1.at(N).at(i);
      s1 %= MOD;
    }
    s2 = 3 * dp2.at(N).at(S / 2);
  } else {
    for (int i = S/2+1; i < S+1; i++) {
      s1 += 3 * dp1.at(N).at(i);
      s1 %= MOD;
    }
  }
  cout << mod(pat - s1 + s2, MOD) << endl;
}

A. On the Way

B. *e**** ********e* *e****e* ****e**

C. Stones

D. Three Colors

B. `*e ****e* *e****e* **e`