今日の精進(20191231)

大晦日なので少な目。来年は水色になりたいですね…。

怪文書/Dubious Document

よくわからんところで詰まったが、別に難しくなかった。

# coding: utf-8  
N = int(input())  
d = {}  
alp = "abcdefghijklmnopqrstuvwxyz"  
cnt = {}  
for s in alp:  
    cnt[s] = 0  
for i in range(N):  
    d[i] = {}  
    s = input()  
    for j in range(len(alp)):  
        d[i][alp[j]] = 0  
    for j in range(len(s)):  
        d[i][s[j]] += 1  
for s in alp:  
    l = []  
    for k in d.keys():  
        l.append(d[k][s])  
    cnt[s] = min(l)  
ans = ""  
for a in alp:  
    ans += a * cnt[a]  
print(ans)  

高橋君と文字列圧縮

前から数えていけばできる。最後の文字をfor文内に含めることができなかったので最後に付け足した。
こういうのはどうすればいいかわからん…。

# coding: utf-8  
S = input()  
ans = ""  
cnt = 1  
for i in range(1, len(S)):  
    if S[i-1] == S[i]:  
        cnt += 1  
    else:  
        ans += S[i-1] + str(cnt)  
        cnt = 1  
ans += S[-1] + str(cnt)  
print(ans)  

Multiple Array

0~i番目までが+1されてしまうので、前からやっていくのは難しい。後ろから必要な回数を加算していけば$O(N)$でできる!考察3分くらいなのでかなりうまくいった!

# coding: utf-8  
from math import ceil  
N = int(input())  
ans = 0  
A, B = [], []  
for i in range(N):  
    a, b = map(int, input().split())  
    A.append(a)  
    B.append(b)  
A, B = A[::-1], B[::-1]  
for i in range(N):  
    a, b = A[i], B[i]  
    cnt = b * ceil((a + ans) / b) - (a + ans)  
    ans += cnt  
print(ans)  

背の順

入力の順番を覚えておいて身長でソートした後入力の順番を出力。簡単。

# coding: utf-8  
N = int(input())  
A = list(map(int, input().split()))  
L = []  
for i in range(N):  
    L.append([i+1, A[i]])  
L.sort(key=lambda x: x[1], reverse=True)  
for i in range(N):  
    print(L[i][0])  

2017-like Number

これが解けたのはうれしい。40分くらい考察に使ってしまった気がするのでもう少しはやくできるようになりたい。

問題文


最初は毎回計算していっても間に合うかなと思っていたが、案の定TLE。そこで、制約の範囲までの条件を満たす素数を前もってすべて計算して、bisect_leftで$l$と$r$の位置を二分探索することで高速化を図った。結果としてPythonでもPypyでも通った。これは本当にうれしい。

# coding: utf-8  
from bisect import bisect_left, bisect_right  
def check(x):  
    # 素数判定  
    flag = True  
    for i in range(2, int(x**0.5) + 1):  
        if x % i == 0:  
            flag = False  
            break  
    return flag  

def primes(n):  
    # 1~nまでの素数の配列を作成  
    is_prime = [True] * (n + 1)    
    is_prime[0] = False    
    is_prime[1] = False    
    for i in range(2, int(n**0.5) + 1):    
        if not is_prime[i]:    
            continue    
        for j in range(i * 2, n + 1, i):    
            is_prime[j] = False    
    return [i for i in range(n + 1) if is_prime[i]]  
def primes_plus(l):  
    # 条件2を満たす素数の配列を作成  
    # l: 素数の配列  
    L = []  
    for p in l:  
        if check((p+1)//2):  
            L.append(p)  
    return L  
l_primes = primes(10**6)  
l_primes = primes_plus(l_primes)[1:]  
Q = int(input())  
for i in range(Q):  
    ans = 0  
    l, r = map(int, input().split())  
    r += 1  
    l_idx = bisect_left(l_primes, l)  
    r_idx = bisect_left(l_primes, r)  
    if l == r and l_idx == r_idx and l == l_primes[l_idx]:  
        print(1)  
    else:  
        print(r_idx - l_idx)  

感想

今日は新しいアルゴリズムとかを修得したわけではないので、なんだか消化不良だった。文字列系とか2次元配列とかの問題がとにかくできないので、今後はそれらをやっていきたい。
来年も精進を続けていきます!