AtCoder Beginner Contest 171

ABC171 解説

2020年6月21日

ABC171 解説

A: αlphabet

αが小文字であるということは、αが'a'以上'z'以下であるということです。従って、次のようなコードによって答えを求めることができます。

a = input()
if 'a' <= a and a <= 'z':
  print('a')
else:
  print('A')

また、多くの言語には標準で小文字かどうか判定する関数が用意されているので、それを使って解くこともできます。

a = input()
if str.islower(a):
  print('a')
else:
  print('A')

B: Mix Juice

$N$ 個の果物のうち、安い順に $K$ 個買うのが最適です。もしそうでない買い方をする場合、安い順に見て $K+1$ 番目以上の果物を買うことになりますが、その果物を買わずに安い方から $K$ 番目以内の果物を買うとより安くなるので、これが最適であることを示せます。
簡単な実装としては、 $p$ をソートし、先頭から $K$ 個の和を求めると良いでしょう。

N, K = map(int, input().split())
p = sorted(list(map(int, input().split())))
print(sum(p[0:K]))

C: One Quadrillion and One Dalmatians

$f(x)$ を、整数 $x$ が与えられた時に番号 $x$ の犬の名前を返す関数とします。すると、 $f(x)$ には次のような性質があります。

$1 \leq x \leq 26$ の時、アルファベットの $x$ 番目を返す。
$26 < x$ の時、 $x-1$ を $26$ で割った値を $a$ 、あまりを $b$ として、 $f(a) + f(b+1)$ を返す。

これを適切に実装すると答えを導出できます。計算量は ${\rm O}(\log N)$ です。

def f(x):
  if 1 <= x and x <= 26:
    return chr(ord('a') + x - 1)
  else:
    return f((x - 1) // 26) + f(x % 26)
N = int(input())
print(f(N))

数列 $D_i$ を、 $A_j=i$ となるような $j$ の個数と定義します。この時、 $A_i \leq 10^5$ なので、 $D$ の長さは $10^5+1$ もあれば十分です。また、 $S_0$ を操作が行われる前の数列 $A$ の全ての要素の和と定義します。この時、 $i$ 回目の操作は $D_{C_i}$ に $D_{B_i}$ を足し、 $D_{B_i}$ を $0$ にする操作と考えることができます。また、この時の $S_i = S_{i-1} + (C_i - B_i) * (D_{B_i})$ と書けるので、十分に高速に求めることができます。計算量は ${\rm O}(N+Q)$ です。

E: Red Scarf

任意の整数 $A$ に対して、 $A {\rm \ xor \ } A = 0$ になる性質を利用します。特に、 $A$ を奇数回 ${\rm \ xor \ }$ を取ったものは $A$ に一致します。
$b_i$ を番号 $i$ が書かれたすぬけくんのスカーフに書かれた整数とし、 $S = b_1 {\rm \ xor \ } b_2 {\rm \ xor \ } \cdots {\rm \ xor \ } b_N$ とすると、 $a_i = b_1 {\rm \ xor \ } b_2 {\rm \ xor \ } \cdots {\rm \ xor \ } b_{i-1} {\rm \ xor \ } b_{i+1} {\rm \ xor \ } \cdots b_N = b_1 {\rm \ xor \ } b_2 {\rm \ xor \ } \cdots b_{i-1} {\rm \ xor \ } b_{i+1} {\rm \ xor \ } \cdots b_N {\rm \ xor \ } (b_i {\rm \ xor \ } b_i) = S {\rm \ xor \ } b_i$ と表すことができるので、 $S$ が求まっているならば $b_i = S {\rm \ xor \ } a_i$ として高速に導出できることが分かります。
ここで、 $a_1 {\rm \ xor \ } a_2 {\rm \ xor \ } \cdots {\rm \ xor \ } a_N$ は、 $a_i$ を $b_i$ の形に展開すると各 $b_i$ を丁度奇数回ずつ含むことから、これは $b_1 {\rm \ xor \ } b_2 {\rm \ xor \ } \cdots {\rm \ xor \ } b_N$ 、すなわち $S$ に一致するので、この問題を解くことができました。計算量は ${\rm O}(N)$ です。

F: Strivore

まずは計算量 ${\rm O}(K|S|)$ のDPを考えてみましょう。DPを、次のように定義します。

$dp_{i, j}$ は、左から $i$ 番目までの文字を決定して、その文字列が $S$ の $j$ 番目までの文字列を部分文字列に含み、 $j+1$ 番目までの文字列を部分文字列に含まないようなものの個数
$dp_{0, 0}$ は $1$ 通り
$dp_{i, j} (j < |S|)$ は $S_j$ を次に使う $dp_{i-1, j-1}$ と $S_{j+1}$ を使わない $dp_{i-1, j} * 25$ の和
$dp_{i, j} (j = |S|)$ は $S_j$ を次に使う $dp_{i-1, j-1}$ と自由に文字を選べる $dp_{i-1, j} * 26$ の和
答えは $dp_{K + |S|, |S|}$

さて、このDPでは、 $S$ を部分文字列として含むか含まないかで遷移が変化し、文字によらないことが分かります。そこで、 $d_i$ を丁度 $i$ 文字目までを見た時に $S$ を部分文字列に含むような文字列の個数とすると、答えは $\sum_{i=|S|}^{|S|+K} d_i$ と表せることが分かります。また、 $d_i$ は $S$ の末尾でない場所(このような場所は全部で|S|ヶ所あります)に対して全部で $|S|-i$ 個の直後の $S$ を構成する文字に一致しない文字を挿入し、 $S$ の末尾に文字を $i-|S|$ 個挿入するような場合の数なので、これは $d_i = 25^{i-|S|} \times _{i-1}C_{i-|S|} \times 26^{K-i+|S|}$ として表せます。計算量は ${\rm O}(K+|S|)$ です。

情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます