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

ABC 122 反省会

今回出遅れもあってBまでしか解けなかった。今回からC++でやっていきたいという気持ちがある。

A: Double Helix

最初の回答。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
 char b;
 cin >> b;
 char p;
 if (b == 'A') {
   p = 'T';
 } else if (b == 'T') {
   p = 'A';
 } else if (b == 'C') {
   p = 'G';
 } else {
   p = 'C';
 }
 cout << p << endl;
}

辞書とかきっとあるよなと思って調べたらstd::mapがあったので次からスッと使えるようにしておきたい。

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

int main() {
  map<char, char> mp{
    {'A', 'T'},
    {'T', 'A'},
    {'C', 'G'},
    {'G', 'C'}
  };

  char b;
  cin >> b;
  cout << mp[b] << endl;
}

B: AT Coder

最初の回答。

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

int main() {
  string acgt = "ACGT";
  string s;
  cin >> s;
  int longest = 0;
  for (int i = 0; i < s.size(); i++) {
    for (int j = i; j < s.size(); j++) {
      int start = i;
      int end = j;
      bool is_acgt = true;
      for (int k = start; k <= end; k++) {
        bool in_acgt = false;
        for (int l = 0; l < acgt.size(); l++) {
          if (s.at(k) == acgt.at(l)) in_acgt = true;
        }
        if (!in_acgt) is_acgt = false;
      }
      if (is_acgt && longest < (end - start + 1)) {
        longest = end - start + 1;
      }
    }
  }
  cout << longest << endl;
}

多少整理した。文字列の検索を覚えておきたい。

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

int main() {
  string acgt = "ACGT";
  string s;
  cin >> s;
  int longest = 0;
  for (int i = 0; i < s.size(); i++) {
    for (int j = i; j < s.size(); j++) {
      bool is_acgt = true;
      for (int k = i; k <= j; k++) {
        if (acgt.find(s.at(k)) == string::npos) {
          // 見つからないとstring::nposが返る
          is_acgt = false;
        }
      }
      if (is_acgt) {
        longest = max(longest, j - i + 1);
      }
    }
  }
  cout << longest << endl;
}

C: GeT AC

TLE連発の上ここで時間切れになった。そのまま考え続けて30分後くらいに解けた。出遅れが無かったらあるいは…

まだC++で試行錯誤しながら書くのに慣れていないのでこれはPythonで書いた。

# coding: utf-8
import sys
input = sys.stdin.readline

N, Q = [int(i) for i in input().split()]
S = input()
is_AC = [False] * N
AC_csum = [0] * N
for i in range(N):
  is_AC[i] = S[i:i+2] == "AC"
  AC_csum[i] = AC_csum[i-1] + is_AC[i]

for i in range(Q):
  l, r = [int(i) for i in input().split()]
  ans = AC_csum[r-1] - AC_csum[l-1] + is_AC[l-1] - is_AC[r-1]
  print(ans)

で、その後解説を見ながらC++で書いてみた。考え方は合っていたけど冗長なことをしていたっぽい。

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

int main() {
  int N, Q;
  string S;
  cin >> N >> Q >> S;
  
  vector<int> at_cnt(N + 1, 0);
  
  for (int i = 0; i < N; i++) {
    at_cnt.at(i + 1) = at_cnt.at(i) + (S.substr(i, 2) == "AC");
  }

  for (int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    cout << at_cnt.at(r - 1) - at_cnt.at(l - 1) << endl;
  }

D: We Like AGC

今回Dまでたどり着けてないのでこれはまた後で。

解説を見ながらC++で書いてみた。

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

const int MOD = 1e9 + 7;
vector<vector<int>> memo(200, vector<int>(200));
map<string, int> mp;
int mpidx = 0;

bool ok(string last4) {
  for (int i = 0; i < 4; i++) {
    string t = last4;
    if (i >= 1) {
      swap(t.at(i-1), t.at(i));
    }
    if (t.find("AGC") != string::npos) {
      return false;
    }
  }
  return true;
}

int dfs(int cur, string last3, int N) {
  if (mp.count(last3) == 0) {
    mp[last3] = mpidx;
    mpidx++;
  }
  if (memo.at(cur).at(mp[last3]) != 0) {
    return memo.at(cur).at(mp[last3]);
  }
  if (cur == N) {
    return 1;
  }
  int cnt = 0;
  for (int i = 0; i < 4; i++) {
    string acgt = "ACGT";
    char c = acgt.at(i);
    if (ok(last3 + c)) {
      cnt += dfs(cur + 1, last3.substr(1,2) + c, N);
      cnt %= MOD;
    }
  }
  memo.at(cur).at(mp[last3]) = cnt;
  return cnt;
}

int main() {
  int N;
  cin >> N;
  cout << dfs(0, "___", N) << endl;;
}

RでFizzBuzz

PythonFizzBuzz

PythonFizzBuzzワンライナーってどんなだったかなと思ってちょっと調べた。

for i in range(100):print(i%3//2*"Fizz"+i%5//4*"Buzz"or-~i)

最後の-~って何だと思ったら~はビット反転だった。2の補数、はるか昔に基本情報でやった記憶がうっすらと…

(参考: FizzBuzzを1byteで実装する - Qiita

RでFizzBuzz

Pythonの方法を真似ればRでもFizzBuzz短く書けるのでは…?と思ってやってみた。

cat(ifelse(""==(.=paste0(ifelse((i=0:99)%%3%/%2,"Fizz",""),ifelse(i%%5%/%4,"Buzz",""))),i+1,.),sep="\n")

少し考えて気付いたが、判定にifelse使ってるし別にTRUEのときに文字列を吐く事にこだわる必要は無い。

cat(ifelse(""==(.=paste0(ifelse((i=1:100)%%3,"","Fizz"),ifelse(i%%5,"","Buzz"))),i,.),sep="\n")

もう少し考えて気付いたが、そういえば関数も代入可能だった。代入と同時に使っても良かろう、で、こうなった。

cat((f=ifelse)(""==(.=paste0(f((i=1:100)%%3,"","Fizz"),f(i%%5,"","Buzz"))),i,.),sep="\n")

もっと短くならないかな…


普通に分けて書いたほうが短かった…

i=j=1:100;i[j%%3==0]="Fizz";i[j%%5==0]="Buzz";i[j%%15==0]="FizzBuzz";cat(i,sep="\n")

まだいけるぞ。もう無理か?

i=j=1:100;i[!j%%3]="Fizz";i[!j%%5]="Buzz";i[!j%%15]="FizzBuzz";cat(i,sep="\n")

過去の自分の記事見たり@Atsushi776さんの案見たりしながら考えたらもっと短く出来た。

for(i in 1:100)cat(i,"\r","Fizz"[!i%%3],"Buzz"[!i%%5],"\n",sep="")

AtCoder ABC 121の反省

AtCoder Beginner Contest 121 - AtCoderやったのでまたメモっておく。

A - White Cells

特に悩むことはない。白色のマス目を長方形に並べてカウントすれば良い。

# coding: utf-8

H, W = [int(i) for i in input().split()]
h, w = [int(i) for i in input().split()]

print((H - h) * (W - w))

B - Can you solve this?

特に考える部分は無かった。まずは最初の回答。

# coding: utf-8

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

correct = 0

for i in range(N):
    A = [int(i) for i in input().split()]
    if sum(i * j for i, j in zip(A, B)) + C > 0:
        collect += 1

print(correct)

ちょっと整理して内包表記で書き直してみたけど別に早くならず可読性だけ落ちてうーん…という感じ。

# coding: utf-8

def read_ints():
    return [int(i) for i in input().split()]

N, M, C = read_ints()
B = read_ints()

correct = sum(
    sum(i * j for i, j in zip(read_ints(), B)) + C > 0 
    for k in range(N)
    )

print(correct)

C - Energy Drink Collector

最初小細工しようとして時間超過してしまったので結局bruteforceっぽい感じで解いてしまった、ソートの速度次第では…と思ってたけど解説読んでも同じこと書いてあったのでこれで良しとする。

件数が多かったのでデータの読み込み方を少し調べた。sys.stdin.readlineを使うと早くなるらしい(cf. Pythonの知っておくと良い細かい処理速度の違い8個 - kumilog.net)。

# coding: utf-8
import sys
input = sys.stdin.readline
 
N, M = [int(i) for i in input().split()]
 
plices = [[int(i) for i in input().split()] for _ in range(N)]
 
plices.sort(key = lambda x:x[0])
 
m = 0
cost = 0
 
for i in range(N):
    if m >= M:
        break
    buy = min(M - m, plices[i][1])
    cost += plices[i][0] * buy
    m += buy
 
print(cost)

D - XOR World

締切に間に合わなかったが、筋は悪くないと思って考え続けた結果終了40分後に解けた。

0〜その数字までを対象に、ある桁に1が何回出現するのか、という点を考えて解いた。スピードは足りてたけど正直汚い。

# coding: utf-8

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

def count_1(bi, idx):
    bi = bi[::-1]
    cnt = 0
    if idx > 0:
        for i in range(0, idx):
            cnt += int(bi[idx]) * int(bi[i]) * int(2**i)
    if idx < (len(bi) - 1):
        for i in range(idx + 1, len(bi)):
            cnt += int(bi[i]) * int(2**i) / 2
    cnt += int(bi[idx])        
    return(int(cnt))

a = str(bin(max(A-1, 0)))[2:]
b = str(bin(B))[2:]
a = (len(b) - len(a)) * "0" + a # 長さ調整

def count_1s(bi):
    return([count_1(bi, i) for i in range(len(bi))[::-1]])

a_cnt = count_1s(a)
b_cnt = count_1s(b)


print(int("".join([str((i - j) % 2) for i, j in zip(b_cnt, a_cnt)]), 2))

で、解説を見て書き直した。

# coding: utf-8

def F_0n(n): # F(0, n)を求める
    if n % 2 == 0:
        return (n // 2 % 2) ^ n
    else:
        return (n + 1) // 2 % 2

def F(a, b):
    return F_0n(a - 1) ^ F_0n(b)

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

print(F(A, B))

きちんと排他的論理和の性質から攻めていくべきだった。半端に書き下して半端に法則を見つけてしまい、それをそのままコードにしようとしてしまったのが敗因な気がする。

AtCoder ABC 120の反省

AtCoder Beginner Contest 120 - AtCoder

やったので回答とメモを残しておく。

A - Faborite Sound

特に注意すべき点はない。

# coding: utf-8
 
a, b, c = [int(i) for i in input().split()]
 
print(min(b // a, c))

B - K-th Common Divisor

$B$の範囲がそれほど広くなかったので、bruteforceで解いてしまった。最初「大きい方から」というのを忘れていて一回ミスってしまった。

提出時は内包表記使ってなかった。慣れておきたい。

# coding: utf-8
 
a, b, k = [int(i) for i in input().split()]
 
divs = [i for i in range(1, a+1) if a % i ==0 and b % i == 0]
 
print(divs[-k])

C - Unification

列の中に異なる色がある限り必ず消滅するので、最後には0の数と1の数の差だけブロックが残る、という点に気づけば簡単。

# coding: utf-8
 
S = list(input())
 
n1 = sum(s == "1" for s in S)
n0 = sum(s == "0" for s in S)
 
print(len(S) - abs(n1 - n0))

D - Decayed Bridges

(ひっくり返せば行けそう…)とまでは気付いたものの時間内には手も足も出なかった。

Union-Find木というものを使う基本的な問題らしく、アリ本(プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?)ではp81に説明がある(もう少しちゃんと読んでおけばよかった)。

Union-Findの実装はPython:Union-Find木について - あっとのTECH LOGを参考に、グループ数をメモるように少し手を加えた。

# coding: utf-8
 
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1) # 木の高さ
        self.n = [1] * (n+1)    # グループメンバー数
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def find_n(self, x):
        return self.n[self.find(x)]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.n[y] = self.n[x] + self.n[y]
        else:
            self.par[y] = x
            self.n[x] = self.n[x] + self.n[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
# -------------------------------------------------------------------

N, M = [int(i) for i in input().split()]

bridges = [tuple(int(i) for i in input().split()) for j in range(M)]

bridges = bridges[::-1]

result = []

now = int(N * (N-1) / 2) #最終不便さ

uf = UnionFind(N)

for i in range(M):
    result.append(now)
    a = bridges[i][0]
    b = bridges[i][1]
    if uf.is_same(a, b): # 既に同じグループ
        pass
    else:
        now -= uf.find_n(a) * uf.find_n(b)
        uf.union(uf.find(a), uf.find(b))

result = result[::-1]

for i in result:
    print(i)

以下Union-Find木に関するメモ。

Union-Find木はグループを管理できるデータ構造で、その名が示すように併合(Union)と検索(Find)の2つのステップが重要となる。

初期化

まず、初期状態(それぞれのノードが1つのメンバーだけを含むグループである状態)を作る。このとき、インデックスとノード番号を一致させておく。

f:id:Rion778:20190304074301p:plain

Union

併合時には、片方のグループの根からもう片方のグループの根へ辺を張る。検索時の計算量を節約するためには、木の高さを低く抑える必要がある。そこで、それぞれの木について高さを保持しておき、併合時には高さを比較して低いものから高いものへ辺を張るようにする(もし高さが同じなら、併合後に高さを+1する)。

f:id:Rion778:20190304074648p:plain

Find

あるノードがどのグループに属するかは、ノードの番号のindexを辿るようにして根を確認すれば良い。ノード番号とindexが同じになったとき、その番号がグループ番号となる。

f:id:Rion778:20190304074756p:plain

また、あるノードのグループが分かったら、ノードが直接根につながるように辺を張り直すと良い。こうすると木の高さを低く保てる。

f:id:Rion778:20190304074905p:plain

統計検定2級の過去問

間違ったやつと自信をもって解けなかったやつ。

2016年11月 問8[1]

問題(要約)

互いに無相関な標準化された確率変数X_1, X_2, X_3およびそれらの平均Y=(X_1+X_2+X_3)/3を考える。

X_1Y相関係数を求めよ。

回答

相関係数r_{X_1Y}は次の式で求められる。

 \displaystyle{
r_{X_1Y} = \frac{Cov [X_1, Y] }{\sqrt{V [X_1] V [Y] }}
}

ここで未知なのは共分散Cov[X_1, Y]とV[Y]なので、この2つを求める。

共分散Cov[X_1, Y]を求める

共分散は次の式で求められる。

 \displaystyle{
Cov [ X_1, Y ] = E [ X_1Y ] - E [ X_1 ] E [ Y ]
}

X_1は標準化されているため、E[X_1 = 0]であり、つまりE[X_1Y]を求めれば良い。Yを展開して整理すると、次のようになる。

 \displaystyle{
E [ X_1Y ] = \frac{1}{3}(E [ X_1^2 ] + E [ X_1X_2 ] + E [ X_1X_3 ])
}

ここで、次の関係を利用する。各Xは標準化されているという点に再度注意する。


\begin{aligned}
V[X_1] &= E[X_1^2] - E[X_1]^2 \\
           &= E[X_1^2]
\end{aligned}


\begin{aligned}
Cov[X_1, X_2] &= E[X_1X_2] - E[X_1]E[X_2] \\
              &= E[X_1X_2] \\
              &= 0
\end{aligned}

無相関な2変数の共分散は0である点にも注意。上記の関係を利用すると、


\begin{align}
E[X_1Y] &= \frac{1}{3}(E[X_1^2] + E[X_1X_2] + E[X_1X_3]) \\
        &= \frac{1}{3}(V[X_1]) \\
        &= \frac{1}{3}
\end{align}

すなわち、共分散は

 \displaystyle{
Cov[X_1, Y] = \frac{1}{3}
}

V[Y]を求める

3つの変数は無相関なので、和の分散は分散の和になる。


\begin{align}
V[Y] &= V[\frac{X_1 + X_2 + X_3}{3}] \\
     &= \frac{1}{9}(V[X_1] + V[X_2] + V[X_3]) \\
     &= \frac{1}{3}
\end{align}


\begin{align}
r_{X_1Y} &= \frac{Cov[X_1, Y]}{\sqrt{V[X_1]V[Y]}} \\
         &= \frac{1/3}{\sqrt{1/3}} \\
         &\approx 0.5773503
\end{align}

odbcパッケージ経由だとvarcharが255文字に切り詰められる問題

ハマるの2回目なのでメモっておく。

PostgreSQLで“test”という名前のデータベースが存在していて、そこに接続している状態を想定する。

con <- odbc::dbConnect(odbc::odbc(), "test")

PostgreSQLのcharacter varying(varchar)は、長さ指定なしで使うと文字列の長さの制限がなくなる(cf. 8.3. 文字型)。

しかし、これをodbcパッケージ経由で取得すると255文字に切り詰められる(https://github.com/r-dbi/odbc/issues/202 で報告されているのと同じ現象?)。

library(dplyr)
query <- "SELECT (repeat('a', 1000))::varchar as str;"
odbc::dbGetQuery(con, glue::glue("CREATE TABLE x AS {query}"))
odbc::dbGetQuery(con, "SELECT str FROM x;") %>% nchar()
## str 
## 255

これは、TEXT型にキャストするととりあえず回避できる。

odbc::dbGetQuery(con, "SELECT CAST(str AS TEXT) FROM x;") %>% nchar()
##  str 
## 1000

dplyrの場合は、as.character()を使う。

tbl(con, "x") %>% mutate(str = as.character(str)) %>% pull() %>% nchar()
## [1] 1000

as.character()はTEXT型へのキャストをするSQLを生成するので、やっていることは同じ。

dbplyr::translate_sql(as.character(x))
## <SQL> CAST("x" AS TEXT)