統計検定準1級に合格したので合格するまでにやったことを書く

2019年6月16日に実施された統計検定の準1級に合格したので、合格までにやったことを書いておく。

試験の結果

統計検定はただの合格の他に評価S(極めて優秀な成績)と評価A(特に優秀な成績)がある。

今回は合格したものの、評価Aには及んでおらず、自己採点の結果では多肢選択が7割、記述・論述が3割くらいの感覚だったので、良い成績での合格ではない。今のまま再度受験して合格できるかは怪しい。

前提知識

2018年11月25日の統計検定で、2級を受験して評価Aを得ており、2級の範囲についてある程度の自信をもって解ける程度の知識はあった。2級のレベル感は簡単すぎず難しすぎずで手頃なので、統計検定を受けたことがなければまずは2級を目標にすると良いと思う。

2級は試験会場と日程にある程度融通のきくCBT方式(コンピュータを使って受験するもの)に対応しているので、好きなタイミングで受験することもできる。 

2級については過去問を数度周回し、わからない部分を軽く調べる、という程度の勉強だった。多肢選択なので問題に慣れておけばそれだけでもある程度の点数は取れる。

やったこと

期間

2級に合格した時点(2018年末)で受けてみようかと思い過去問を買ってきたりしたがあまり捗らず、紙とペンで真面目に勉強をし始めたのは5月の連休あたりからだった。

勉強方法

例の赤い本を流し読みしたりはしていたが、ある程度腰を据えて勉強を始めたのは5月の連休頃からだった。

まずは「心理統計学ワークブック」を8割くらいやった。わからないところは「心理統計学の基礎」に書いてあるので、分からなかった部分に遭遇したらノートに転記していた。8割でやめたのは特に範囲がどうこうということではなくて、単に飽きたためである。2週間くらいやった。

その後は公式問題集の過去問を解き、

  • 自信をもって解けた → 次の問題へ
  • 解けなかった
    • 解説を読んで理解できた → 次の問題へ
    • 解説を理解できなかった → 理解できるまで調べてノートにまとめ、再度挑戦

ということを試験当日まで繰り返した。

公式問題集の解説は紙面の都合もあるのか非常にあっさりしているので、ある程度内容をわかっていなければ理解することもままならない。逆に言えば、解説を読んで理解できるのであれば、過去問の練習だけで類似の問題は解けるようになると思う。

やらなかった/やれなかったこと

用語の確認

はじめ、出題範囲に記載されている用語を洗い出して分からない部分を潰していこうと考えていた。しかしこれは2日で挫折した。統計検定準1級は範囲がクソ広いので、出題範囲に含まれる用語もクソ多い。したがって用語を書き出すだけでも一苦労で、それを一つ一つ洗っていくなどということはとてもやれなかった。評価A以上を狙うのであれば、ある程度勉強した段階でやる必要があっただろうとは思う。

手法の実践

ありがちな問題として「このデータセットに○○という手法を適用したときの結果はどれか(グラフを選ぶ)」というものがある。これはほぼボーナス問題みたいなもので、その手法をRやPythonでやったことがあればかなりの割合で正解できる。たいてい、そのような問題が出る手法というだけあって、グラフには手法の特徴が明瞭に現れるから判断がしやすいのだ。

しかし、やったことがなければ解けない。理屈を知って結果を想像するのは、結果そのものを見て覚えてしまうのよりもずっと労力がかかる。

今回は主に紙とペンで勉強していたので、手法を実際にやってみるというのは不足していたと思う。今回は問8にFused Lassoの結果のグラフを選べという問題が出たが、正答できなかった。

参考書

アフィ置き場コーナー。

後のものほどあまり真面目に読んでいない。あまり馴染みのない概念を調べる場合、私は複数の情報源の説明を比べないと理解の効率が悪いので、内容的に重複しているようなものでもなるべく手元に置いて勉強するようにしていた。

試験前後の動き

※この先は何の参考にもなりません。

全体スケジュール

会場は北海道だったので、前日に移動して翌日帰るという2泊3日のスケジュールであった。ただの北海道旅行である。

前日

行きの移動はフェリーにした。昼に新潟港を出発して翌朝小樽港に付く航路であった。最初飛行機で行くつもりだったので、差額で良い部屋をとってみたが非常に快適であった。でかい風呂があったりビンゴ大会が開催されていたりエンターテイメント性が高い。

船内では主に真面目に勉強していた。

ちなみに何もしないと下船は4:30だが、そんな時間に降りてもやることがない。これは事前にカウンターで申し出ておくことで6:00まで延長できる。

当日

当日は雨だった。寒かった。薄着で行ってしまったので、完全に軽装で山に登ってしまった人の気持であった。6:00に小樽に居てもやることがないので、さっさと札幌に移動して駅のドトールで朝食をとりながら時間を潰した。

その後は事前に調べておいた札幌市中央図書館へ向かった。ここは自習室があるので自習がしやすい。また、経路上に時計台がある。

図書館で2時間程度勉強してから札幌駅に戻り、適当に昼食を済ませてから会場の北海道大学へ向かった。

北大は構内の手入れがかなり行き届いていて、どう見てもただの観光客みたいな人や犬の散歩してる人が多いのが印象的だった。

試験結果はさんざんでまさか合格はしていまい…、という感覚だったので、試験後は完全に北海道旅行モードであった。

試験後に付近を散策していたらホクレンのビルがあった。異様にでかかったのと入り口で水稲品種の展示をしていたのがホクレン感があってよかった。

ホクレンのビルの前に水稲展示してた

そしてホクレンのビルはウルトラクソデカ㌱であった…

翌日

ニッカウイスキーの工場である余市蒸溜所へ行った。

マッサンは全く見ていないが色々と見るものがあって面白かった。

稼働しているので工場内のいたるところでウイスキーの香りが立ち込めており、歩いているだけで酔いそうになる。

そしてウイスキーの試飲ができる。シングルモルト余市は最&高であった。若干高かった気がしたけど気づいたら買っていた。

これは帰宅してからもう1本買った。

見学と試飲とお買い物済ませたあたりで丁度工場内のレストランが開店したので、うまいものやうまいものを食べたり飲んだりした。

プレミアムハイボール

なんか玉ねぎ揚げたやつ(うまい)

ザンギ(うまい)

アイスにウイスキーついてるやつ!

また行きたい。何なら住みたい。

n日後

(試験駄目だったし来年も北海道だなー仕方ないなー)と思ってたら合格してたのでびっくりした。

🙌

とはいえギリ合格で準1級相当の知識・能力が本当にあるかというと微妙なので、来年も受験しようと思う。やむを得ない。

あと某所で話をした(このときは結果発表前なので完全に落ちてるテンションだった)。

ABC 125反省会

問題自体はそれほど難しくなかったが、問題が正しく読めて無くてCとDでWAを何度か出してしまった。読解力を鍛えたい。

A. Biscuit Generator

「0.5秒」のところで若干不安になったけどとりあえずこれで正解だった。

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

int main(){
  int a, b, t;
  cin >> a >> b >> t;
  cout << t / a * b << endl; 
}

B. Resale

これは危なげなくクリア。

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

int main(){
  int n;
  cin >> n;
  vector<int> v(n);
  vector<int> c(n);
  
  for (int i = 0; i < n; i++) {
    cin >> v.at(i);
  }
  for (int i = 0; i < n; i++) {
    cin >> c.at(i);
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (v.at(i) > c.at(i)) ans += v.at(i) - c.at(i);
  }
  cout << ans << endl;
}

C. GCD on Blackboard

gcd(a, b, c) = gcd(gcd(a, b), c)なので、順番に見ていってOK。

任意の数に変更できるというのは数を除外するのと同じなので「次の数を使わないパターン」がこれまでの最大ケースより大きいかどうかを順次比較しつつ結果を更新していけばよい。

最初手間取ったので、もうちょっとコードを綺麗にできそうな気もする。

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

ll gcd(ll a, ll b) {
  ll tmp = 0;
  while (b != 0) {
    if (b < a) {
      swap(a, b);
    }
    b = b % a;
  }
  return a;
}

int main(){
  ll N;
  cin >> N;
  vector<ll> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }

  if (A.size() == 2) {
    cout << max(A.at(0), A.at(1)) << endl;
  } else {
    ll a = A.at(0);
    ll b = A.at(1);
    ll c = A.at(2);
    ll gcd_max = 0;
    ll gcd_all = gcd(a, b);
    if (gcd(a, c) > gcd(b, c)) {
      gcd_max = gcd(a, c);
    } else {
      gcd_max = gcd(b, c);
    }
    for (int i = 2; i < N; i++) {
      ll c = A.at(i);
      gcd_max = gcd(gcd_max, c) > gcd_all ? gcd(gcd_max, c) : gcd_all;
      gcd_all = gcd(gcd_all, c);
    }
    cout << gcd_max << endl;
  }
}

D. Flipping Signs

Cより簡単だった気がする。実際正解者数もCよりかなり多かった様子。

最初、最後の1個だけ見るのかと思ってWAを2回ほど出してしまった。

操作はいくらでもできるので、負数が偶数個なら全部正整数にできるし、奇数個ならどれか1つが負数になる。

したがって、負数をカウントして偶数なら絶対値の和が答えになり、奇数個なら絶対値の和から絶対値が最小の値の2倍を引けば答えになる。

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

int main(){
  ll N;
  cin >> N;
  vector<ll> A(N);
  for (ll i = 0; i < N; i++) {
    cin >> A.at(i);
  }

  ll ans = 0; // 絶対値の合計
  for (ll i = 0; i < N; i++){
    ans += abs(A.at(i));
  }

  int minus_cnt = 0; // 負数の数を数える
  for (ll i = 0; i < N; i++) {
    if (A.at(i) < 0) minus_cnt++;
  }
  
  if (minus_cnt % 2 != 0) { // 負数が奇数個ならどれか一つ-が残るので、絶対値が一番小さいものを負にする
    ll min = abs(A.at(0));
    for (ll i = 1; i < N; i++) {
      if (abs(A.at(i)) < min) min = abs(A.at(i));
    }
    ans -= abs(min) * 2;
  }
  
  cout << ans << endl;
}

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;
}

ABC 124反省会

初4完。でも今回正解者多かったし少し簡単だったかも…?

A. Buttons

A==Bの場合だけ気をつける。

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

int main(){
  int A, B;
  cin >> A >> B;
  int m = max(A, B);
  cout << (A == B ? m + m : m + m - 1) << endl;
}

B. Great Ocean View

最大の山の高さを保持しつつ、比較していけば良い。

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

int main(){
  int N;
  cin >> N;
  int h;
  cin >> h;
  int hmax = h;
  int cnt = 1;
  for (int i = 1; i < N; i++) {
    cin >> h;
    if (h >= hmax){
      hmax = h;
      cnt++;
    };
  }
  cout << cnt << endl;
}

C. Coloring Colorfully

一つ前と色が違えばカウントを増やす。

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

int main(){
  string S;
  cin >> S;
  int pre = S.at(0) - '0';
  int cnt = 0;
  int cur;
  for (int i = 1; i < S.size(); i++) {
    cur = S.at(i) - '0';
    if (pre == cur) {
      cnt++;
    };
    pre = !pre;
  }
  cout << cnt << endl;
}

D. Handstand

例えば入力例2は次のように見ることができる。

  • 1が3個
  • 0が1個
  • 1が1個
  • 0が1個
  • 1が1個
  • 0が1個
  • 1が2個
  • 0が2個
  • 1が2個

このような集計をした上で、各1からk*2+1個分先までの区間の「個数」が最大になる場合を探せば良い。もし文字列Sが0から始まったら、最初に「1が0個」があるとみなせば良い。これなら計算量はO(S.size())程度なので余裕で間に合う。

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

int main(){
  int N, K;
  cin >> N >> K;
  string S;
  cin >> S;
  vector<int> arr(N, 0);
  int idx = 0;
  char pre = '1';
  if (S.at(0) == '0') { // 0スタートだった
    idx++;
    arr.at(0) = 0; // 1が0個あることにする
    pre = '0';
  }
  for (int i = 0; i < N; i++) {
    if (pre == S.at(i)) {
      arr.at(idx)++;
    } else {
      idx++;
      arr.at(idx)++;
    }
    pre = S.at(i);    
  }
  
  int max_lensum = 0;
  for (int i = 0; i < idx+1; i = i+2) {
    int lensum = accumulate(arr.begin()+i, arr.begin() + min(i+2*K+1, idx+1), 0);
    if (lensum > max_lensum) max_lensum = lensum;
    if (i+2*K+1 > idx) break;
  }
  cout << max_lensum << endl;
}

ABC 123反省会

今回はAとBはスッと解けたもののCでハマってしまった。

A. Five Antennas

条件よく読んでなくて総当たりしてしまった。

a = [int(input()) for _ in range(5)]
k = int(input())
flag = True

for i in range(5):
  for j in range(5):
    if abs(a[i] - a[j]) > k:
      flag = False
      break

if flag:
  print('Yay!')
else:
  print(':(')

C++でやり直し。これでよかったですね。

#include <bits/stdc++.h>
using namespace std;
int main(){
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  cout << (e - a <= k ? "Yay!" : ":(") << endl;
}

B. Five Dishes

Python

import math

t = [int(input()) for _ in range(5)]

min1 = map(lambda x: x % 10, t)
min1 = min([10 if i == 0 else i for i in min1])

print(sum(map(lambda x: math.ceil(x) * 10, [i/10 for i in t])) - (10 - min1))

C++

#include <bits/stdc++.h>
using namespace std;
int main(void){
  int min_1 = 10;
  int sum = 0;
  int t;
  for (int i = 0; i < 5; i++) {
    cin >> t;
    if (t % 10 != 0 && t % 10 < min_1) min_1 = t % 10;
    sum += int(ceil(t / 10.0) * 10);
  }
  cout << sum - 10 + min_1 << endl;
}

C. Five Transportations

ここで時間切れになってしまった。

1つの都市が空になるまでの時間を積み重ねていこうと思ったんだけど、これが良くなかった。最終的に解ける方法ではあったのだけれど、細かい部分にバグが入り込みやすくてWA連発してしまった。テストケースをもう少しうまく組み立てられればなんとかなったかもしれない。

N = int(input())
abcde = [int(input()) for _ in range(5)]

time = 0
n = N # 次の都市でまだ残っている人数
last = 0 # 最後の1回で移動する人数

for i in range(5):
  time += n // abcde[i]
  if n % abcde[i] > 0:
    time += 1

  last = n % abcde[i]
  if last == 0:
    last = abcde[i]

  if i < 4: 
    n = last + max((N-last) - (time-i-1) * abcde[i+1], 0)
  
print(time)

まあ実際にはこれでよかったんだけど…。

Python

import math

N = int(input())
a = [int(input()) for _ in range(5)]

print(math.ceil(N / min(a)) + 4)

C++

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

int main(){
  ll N;
  cin >> N;
  vector<ll> max_n(5);
  for (int i = 0; i < 5; i++) {
    cin >> max_n.at(i);
  }
  ll min;
  min = *min_element(max_n.begin(), max_n.end());
  cout << setprecision(16) << ceil(N / double(min)) + 4 << endl;
}

D. Cake 123

解答見て素直な方法をやってみたらギリTLEになってしまった(提出 #4867478 - AtCoder Beginner Contest 123)。

x, y, z, k = [int(i) for i in input().split()]

a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

ab = [ai + bi for ai in a for bi in b]
ab.sort(reverse=True)
ab = ab[:k]

abc = [abi + ci for abi in ab for ci in c]
abc.sort(reverse = True)

for i in range(len(abc)):
  if i < k:
    print(abc[i])
  else:
    break

ところが全く同じコードをPyPy3で提出したところACになった(提出 #4868185 - AtCoder Beginner Contest 123)。ループの少ない例ではあまり時間が短縮されないようだった(むしろ長くなる例もあった)が、ループが多いとかなりの時間短縮が見込めるようだ。ギリギリTLEになるときはとりあえずPyPy3にしてみるというのはアリかもしれない。互換性がどの程度なのかよく調べてないけど…。

ちなみにC++なら相当余裕があった。

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

#define REP(i, n) for(int i = 0; i < (int)(n); i++)

using lli = long long int;

int main(){
  int x, y, z, k;
  cin >> x >> y >> z >> k;
  vector<lli> a(x);
  vector<lli> b(y);
  vector<lli> c(z);
  
  REP(i, x) cin >> a.at(i);
  REP(j, y) cin >> b.at(j);
  REP(k, z) cin >> c.at(k);
  
  vector<lli> ab(x*y);
  int idx = 0;
  REP(i, x) {
    REP(j, y) {
      ab.at(idx) = a.at(i) + b.at(j);
      idx++;
    }
  }
  
  sort(ab.rbegin(), ab.rend());
  
  vector<lli> abc(k*z);
  idx = 0;
  REP(i, min(x*y, k)) {
    REP(j, z) {
      abc.at(idx) = ab.at(i) + c.at(j);
      idx++;
    }
  }
  
  sort(abc.rbegin(), abc.rend());
  REP(i, k) {
    cout << abc.at(i) << endl;
  }
}

Project Euler 27 - 二次式素数

久しぶりにProject Euler

Problem 27 Quadratic primes

問題の概要

オイラーは次のような驚くべき関数を発見した。

n^2 + n + 41

この関数のnに、0から順に整数を入れて行くと、素数が順番に生成されていく。ただし、n=40のとき、結果は41で割り切れてしまう。つまりこの関数は0から39の範囲で素数を生成するのだ。また、 n=41のとき、41で割り切れるというのは自明だろう。

さらに驚くべきことがある。次の式は80個の素数を連続して生成するのだ。

n^2 - 79n  + 1601

一般化して、次のような関数を考えよう。

n^2 + an + b

ここで、|a| \lt 1000かつ|b| \leq 1000とする。最も多くの素数を連続して生成するabの組み合わせは何か。abの積として答えよ。

続きを読む

エクサウィザーズ 2019反省会

エクサウィザーズ 2019 - AtCoder。AとBは解けたけどCでダメだった。

A: Regular Triangle

最初Pythonand&&と書いてしまってRE出してしまった…。少なくとも1回はテストしないとダメ。

Python

A, B, C = map(int, input().split())
 
if A == B and B == C:
  print('Yes')
else:
  print('No')

C++

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

int main(){
    int A, B, C;
    cin >> A >> B >> C;
    
    if (A == B && B == C) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
}

B: Red or Blue

C++

最初の提出。

#include <bits/stdc++.h>
using namespace std;
int main(void){
  int N;
  string s;
  cin >> N >> s;
  
  int r_cnt = 0;
  int b_cnt = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s.at(i) == 'R') {
      r_cnt++;
    } else {
      b_cnt++;
    }
  }
  if (r_cnt > b_cnt) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

これはstd::countを使えば短く書けるらしい。

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

int main(void){
  int N;
  string s;
  cin >> N >> s;
  int B = count(s.begin(), s.end(), 'B');
  cout << ((N - B) > B ? "Yes" : "No") << endl;
}

Python

N = int(input())
s = input()
B = s.count("B")

if N - B > B:
  print("Yes")
else:
  print("No")

C: Snuke the Wizard

O(NQ)の方法しか思いつかずダメだった。

Python

import sys
import numpy as np
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()

tile = {}
now = np.array([1] * (N+2))

for s in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
  tile.setdefault(s, [])

for i in range(len(S)):
  tile[S[i]].append(i+1)

for i in range(Q):
  t, d = input().split()
  old = now[tile[t]]
  if d == "L":
    now[(np.array(tile[t])-1).tolist()] += old
    now[tile[t]] -= old
  else:
    now[(np.array(tile[t])+1).tolist()] += old
    now[tile[t]] -= old

print(sum(now) - now[0] - now[-1])

解説によると、「最終的に左(右)に出たゴーレムより左(右)に居たゴーレムはすべて左(右)に出る」ことから、左(右)に出るゴーレムと出ないゴーレムの境界を探せば良いらしい。ゴーレム1対の最終的な結果はO(Q)で求められるので、境界は二分探索で探せばO(QlogN)で見つかる。左右探してもO(2QlogN)なので間に合う。

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == -1:
    left = mid
  else:
    right = mid

lb = right

# 右側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == N:
    right = mid
  else:
    left = mid

rb = left

print(rb - lb + 1)

C++

Pythonだと1500msくらいかかって結構ギリギリなのでC++でも書いてみた。

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

int sim(int i, int N, string& S, vector<int>& dest, vector<vector<char>>& td_list) {
  int idx = i;
  if (dest.at(i) != -2) return dest.at(i);
  for (vector<char> td : td_list) {
    if (idx == -1) {
      dest.at(i) = -1;
      return -1;
    }
    if (idx == N) {
      dest.at(i) = N;
      return N;
    }
    if (td.at(0) == S.at(idx)) {
      if (td.at(1) == 'L') {
        idx--;
      } else {
        idx++;
      }
    }
  }
  dest.at(i) = idx;
  return idx;
}

int main(void){
  int N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;
  vector<int> dest(N, -2);
  vector<vector<char>> td_list(Q, vector<char>(2));
  for (int i = 0; i < Q; i++) {
    cin >> td_list.at(i).at(0) >> td_list.at(i).at(1);
  }
  
  // 左側の境界を探索
  int left = -1;
  int right = N;
  while (right - left != 1) {
    int mid = (left + right) / 2;
    if (sim(mid, N, S, dest, td_list) == -1){
      left = mid;
    } else {
      right = mid;
    }
  }
  int lb = right;

  // 右側の境界を探索
  left = -1;
  right = N;
  while (right - left != 1) {
    int mid = (left + right) / 2;
    if (sim(mid, N, S, dest, td_list) == N){
      right = mid;
    } else {
      left = mid;
    }
  }
  int rb = left;

  cout << rb - lb + 1 << endl;
}

300ms程度にはなった。

f:id:Rion778:20190331025405p:plain