AtCoder Beginner Contest 141 A~D（過去問）

記念すべき第一回。時間制限せずに愚直に解く。

A問題

atcoder.jp

所感

決まった順番でローテーションさせていく問題
剰余を使って配列を参照して終わり

コード

#!/usr/bin/env python3
S = input()
list = ["Sunny", "Cloudy", "Rainy"]
print(list[(list.index(S) + 1)%3])

B問題

atcoder.jp

所感

問題文の余事象で考えると判定が少なくて楽
入力の1番目は配列の0番目に相当する（偶奇が反転する）ことに注意

コード

#!/usr/bin/env python3
S = input()
# 奇数文字目にLがあるとだめ
# 偶数文字目にRがあるとだめ
ng = ["L", "R"]
for i in range(0, len(S)):
  if S[i] == ng[i%2]:
    print("No")
    exit()
print("Yes")

C問題

atcoder.jp

所感

一回クイズして正解者以外は点数が1点減るので、
N回クイズした時点での回答者Aの点数は、

（初期の持ち点） − １点 ✕ （Aが正解しなかった数）
　　＝　（初期の持ち点） − １点 ✕ （問題数） ＋ １点 ✕ （Aが正解した数）

各参加者の正解数を格納するリストを作ってループを回す

コード

#!/usr/bin/env python3
N, K, Q = map(int, input().split(" "))

A = []
for i in range(0, Q):
  A.append(int(input()))

wins = [0] * N
for i in A:
  wins[i - 1] = wins[i - 1] + 1

for i in range(0, N):
  score = K - Q + wins[i]
  if score > 0:
    print("Yes")
  else:
    print("No")

D問題

atcoder.jp

所感（１回目）

一回使うと買い物リストの中のどれかの品物の値段を半分（小数点以下切り捨て）にできるチケットが複数枚あり、
このチケットを使って最も経済的に買い物ができる方法を探す （※実際の記述では「複数回半分にしたあとに小数点以下を切り捨てる」となるので厳密には異なる。これが一致するかは一応検討した（後述））

チケットの使用は独立に行うことができるので、
　　１枚目のチケットを最も経済的に使う → ２枚目のチケットを最も経済的に使う → ・・・
をやっていくとすべてのチケットを最も経済的に使える

価格を半分にしたとき、絶対量として一番減るのは一番高い価格なので、
買い物リストを受け取ったときに最も高い商品を半分にしたリストを返す関数を書いて再帰（動的計画法）
リストを渡すとlru_cacheが使えないのでリストの中身を文字列化して辞書のキーにするとかいう強引な手法でメモ化

コード（１回目）

#!/usr/bin/env python3
import math
import numpy as np

#### input
N, M = map(int, input().split())
A = list(map(int, input().split()))

#### functions
discount_dic = {}

def discount(price_list, num_coupon):
  if num_coupon == 0:
    return price_list
  else:
    dic_key = ",".join(map(str, price_list))
    if dic_key in discount_dic:
      return discount_dic[dic_key]
    else:
      max_i = np.argmax(discount(price_list, num_coupon - 1))
      price_list[max_i] = math.floor(price_list[max_i] / 2)
      discount_dic[dic_key] = price_list
    return price_list

#### process
print(sum(discount(A, M)))

結果

[*] sample-1
[x] time: 0.132450 sec
[+] AC

[*] sample-2
[x] time: 0.126523 sec
[+] AC

[*] sample-3
Traceback (most recent call last):
  File "main.py", line 39, in <module>
    print(sum(discount(A, M)))
  File "main.py", line 33, in discount
    max_i = np.argmax(discount(price_list, num_coupon - 1))
  File "main.py", line 33, in discount
    max_i = np.argmax(discount(price_list, num_coupon - 1))
  File "main.py", line 33, in discount
    max_i = np.argmax(discount(price_list, num_coupon - 1))
  [Previous line repeated 993 more times]
  File "main.py", line 27, in discount
    dic_key = ",".join(map(str, price_list))
RecursionError: maximum recursion depth exceeded while getting the str of an object
[x] time: 0.127297 sec
[-] RE: return code 1
[-] WA
output:

expected:
0


[*] sample-4
[x] time: 0.126015 sec
[+] AC

[x] slowest: 0.132450 sec  (for sample-1)
[-] test failed: 3 AC / 4 cases

所感（２回目）

再帰が深すぎて怒られたっぽい
解けなかった３番の条件は下記

• 品数：1
• チケット枚数：100000
• 品物の値段：1000000000

頭で考えれば「全部のチケットを1つの品物に突っ込めばいいじゃん」となるけど、
上記の実装だと毎回再帰していたのでこれがエラーの原因だった
ただし、「品物の数が１個のときは全部のチケット使って終わり」という処理を行うと、

• 品数：2
• チケット枚数：100000
• 品物の値段：1000000000, 1

みたいなことをされたときにまたエラーが出る（提出すると上に類似の問題を解かされる気がする）
なので、「使えるだけチケットを使ってから再帰」させる実装にする必要あり

下記の簡単なケースで実験

• 品数：2
• チケット枚数：10（十分多ければ何枚でもいい）
• 品物の値段：2, 9

頭で考えると、9に4回チケット使ったら9 → 4 → 2（小数点以下切り捨て）となるので、 「9に3回チケット使えるじゃん」って判定してくれるコードにすればいい
更に、3回使ったあとの品物の値段は2が2つで次はどっちに割引チケット使っても良いので、
4枚目のチケットも元々値段９の品物に使ってよいことになる

上記を発展させて考えると、
「一番高い値段の品物に対して、その値段が二番目に高い値段を下回るまで、チケットを使い続ける」
ことができればOK

コード（２回目）

#!/usr/bin/env python3
import sys
import math
import numpy as np

#### input
N, M = map(int, input().split())
A = list(map(int, input().split()))

#### functions
def discount(price_list, num_coupon):
  if num_coupon == 0:
    return price_list
  else:
    if len(price_list) == 1:
      price_list[0] = math.floor(price_list[0]  / 2** num_coupon)
      return price_list
    else:
      sorted_list = sorted(price_list)
      max1st = sorted_list[-1]
      max2nd = sorted_list[-2]
      num_div = min(num_coupon, math.floor(math.log2(max1st / max2nd)) + 1)
      max_i = np.argmax(price_list)
      price_list[max_i] = math.floor(price_list[max_i] / 2**num_div)
      price_list = discount(price_list, num_coupon - num_div)
      return price_list

print(sum(discount(A, M)))

結果

サンプルケースは通ったが提出後は実行時間オーバー
うまいやり方がわからなかったのでここでギブアップ

解答と敗因

計算量の見積もり不足が原因
上記の「割れるだけ割る」方法は、最悪の場合毎回1回しか割り算を実行できないので、
計算量的にはほとんど改良されてない（どころか、悪化してそう）

解答では普通にやるとO(MN)になるけど10⁵オーダーのMとNに対してはせめてO(MlogN)（またはO(NlogM)）にしたいよねとの説明。
上記でやろうとしているのって、結局は

• １．最大値を見つける
• ２．最大値を半分にする
• ３．１〜２をチケット枚数分繰り返す

であって、それぞれの計算量は、

• １．N個の要素に対するmax() = O(N)
• ２．O(1)
• ３．O(M) * O(N) qiita.com

となるので、max()の部分をO(logN)にするか、チケットの枚数分繰り返す部分をO(logM)にする方向で考えるのが多分よい攻め方
優先度付きキューなるものを使えば最大値がO(logN)で取得できるらしいので、これを使えば良い、という問題だった

以下のコードを提出して無事完了

コード（最終提出、解答を参照）

#!/usr/bin/env python3
import math
import numpy as np
import heapq

#### input
N, M = map(int, input().split())
A = list(map(lambda x:int(x)*(-1), input().split()))

heapq.heapify(A)

#### functions
def discount(num_coupon):
  max = -heapq.heappop(A) / 2
  heapq.heappush(A, -max)

#### execution
for i in range(0, M):
  max = math.floor(-heapq.heappop(A) / 2)
  heapq.heappush(A, -max)

print(-sum(A))

※ 小数点以下切り捨て処理の話

上記で求めようとしたのは「2で何回割ってから小数点以下を切り捨てたら2番目に大きい値段を下回るか」であるのに対し、
実際に求めるのは「2で割って小数点以下を捨てることを何回したら2番目に大きい値段を下回るか」なことが問題
例を挙げて言うと、

• 「2で割っていくのを5回繰り返したところで小数点以下を切り捨てたらやっと2番目に大きい値段を下回ったけど、2で割って小数点以下を捨てるのを5回やった時点では下回らなかった（6回やらないといけない）」
• 「2で割っていくのを5回繰り返したところで小数点以下を切り捨てたらやっと2番目に大きい値段を下回ったけど、2で割って小数点以下を捨てるのを繰り返すと4回目で下回った」

の2パターンのいずれにもならないことを保証できるかが問題となる
ただし、切り捨てを含む方が値はより早く減少していくので、前者のケースは考えなくてよい

2で割っていくのを\( n \)回繰り返してから小数点以下を切り捨てた値を返す関数を\(f_n\) 、2で割って小数点以下を捨てるのを\(n\)回繰り返した値を返す関数を\(g_n\)としたとき、

\(g_{n-1}(A) \lt B \lt g_{n-2}(A)\) かつ \( f_n(A) \lt B \lt f_{n-1}(A) \)

が成り立たないことを示す。これは、

\( k, g(n) \in N, f(n) \in R \)かつ\(g \leq f\)のもとで、 \( g \lt k \Rightarrow f \lt k \)

を示せばよく、上記は\(k\)と\(f(n)\)が整数であることを考慮すると、

\( f_m(A) - g_m(A) \lt 1 \) 　　(1)

であればよい

ここで、

\( f_{m} = f'_m - p \)

\( f'_{m+1} = \frac{1}{2} f'_m \)

\( g_{m+1} = \frac{1}{2} g_m - q \)

\( p,q \) は四捨五入の際に切り捨てられる数値であり、\( 0 \leq p \lt 1, q = 0, 0.5) \)

となる。一般項を求めると(1)の左辺は、

\( (\frac{1}{2})^{n-1}A - p - \{(\frac{1}{2})^{n-1}(A + 2t) - 2t\} \)

\( = 2t\{1 - (\frac{1}{2})^{n-1}\} - p\)

\( := t - p\)

となり、

\( 0 \leq r \lt 1, 0 \leq p \lt 1 \)

となるので、(1)が成り立つ

解答のPDFを見たら剰余の式を作ってサクッと証明していたのでショック・・・。

あとがき

D問題で疲れたのでここで中断
E問題に進まずに別の回のA〜C（D）を解きに行く方がよいのでは説