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

A問題

atcoder.jp

所感

単なる順列の問題。さすがに秒殺

コード

#!/usr/bin/env python3

#### input
N = int(input())
print(N**3)

B問題

atcoder.jp

所感

配列のインデックスをひたすら参照していくだけ。

コード

#!/usr/bin/env python3

#### input
N = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
Cs = list(map(int, input().split()))

#### process
score = 0
tmp_A = -2    # +1した値がAに含まれない適当な数字
for A in As:
  score = score + Bs[A - 1]
  if A == tmp_A + 1:
    score = score + Cs[tmp_A - 1]
  tmp_A = A

print(score)

C問題

atcoder.jp

所感

\( b_1 \geq a_1 \cap b_1 \geq a_2 \)

\( b_2 \geq a_2 \cap b_2 \geq a_3 \)

︙
なので、求めるAの要素について、

\( b_1 \geq a_1 \)

\( min(b_1, b_2) \geq a_2 \)

︙

\( min(b_{n-1}, b_n) \geq a_n \)

となるので最大値をとってあげればOK

コード

#!/usr/bin/env python3

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

#### process
As = [Bs[0]]

for i in range(0, len(Bs) - 1):
  As.append(min(Bs[i], Bs[i + 1]))

As.append(Bs[-1])
print(sum(As))

D問題

atcoder.jp

所感

前回のD問題は計算量で破れたので今回はちゃんと考える

\( 0 \leq N, K \leq 10^5\)なので、おそらく求める答えの計算量は\( O(NlogK) \) か \( O(KlogN) \)

取るべき選択肢は「全通り試す」「各回で最適解が存在して、それを繰り返す」「特殊な解法が存在する」で、「全通り試す」は計算量的に無理

「各回で最適解が存在して、それを（\( K \)回）繰り返す」パターンの場合、\( O(logN) \)で最適解を見つけないといけないが、

どう頑張っても( O(N) ) 未満で最適解を見つけられる気がしない
そもそも、現在の得点を計算しようとしたら、「連続して出現するパターン」を求めることになり、

score = 0
for i in range(0, len(S) - 1):
  if(S[i] == S[i+1]): score = score + 1

で愚直に計算すればこれだけで\( O(N) \) 回かかってしまう（もっと減らせる可能性もあるけど思いつかず）

よって、特殊な解法が存在して「初期状態に対して最大の得点が\( O(KlogN) \)（または \( O(NlogK) \)）で一意に定まる」

と考えて、特殊な法則がないかを見に行くことにした
　

まず最初に、ある長さの区間を反転させても左右の関係もそのまま反転するので、
区間の両端に関係する得点以外は保持されるんだなというのは気づいた。ただこれだけでは先に進まず。
　

詰まったのでとりあえず例題の"LRLRRL"でひたすらパターンを試してみると、( (l, r) = (2, 5) )の他に( (l, r) = (2, 2) )や( (l, r) = (3, 3) )、( (l, r) = (4, 5) )でもいけることがわかった
特殊な解法が存在するなら、この4パターンがすべて等価に扱われている可能性が高く、
特に一文字しか変えない( (l, r) = (2, 2) )や( (l, r) = (3, 3) )が出現しているのがかなり気になる
一文字変える場合に、連続した文字列の途中を変えるのは効率が悪そうなのはなんとなく察しが付くので、
今回のケースを見るに「端の一文字」「単独で出てくる一文字」「連続して出てくる一文字」は区別したほうが良さそう
更に、LとRの扱いは向きを持っているので、端の文字については「左端のL」「左端のR」「右端のL」「右端のR」まで分解する可能性も念のため頭に入れとく
その上で、反転においては区間両端の文字しか関係ないので、RRやRRRはRと等価だし、RLLLRやRLRLRもRと等価説が浮上した
一旦LRLRRLの「端」「単独」「連続」の3つを変えたときにそれぞれ得点がどう変わるかを見てみると、

• 初期状態の得点：1点
• 端のLを変えた時の得点：2点（どっちの端でも）
• 単独変えた時の得点：3点（全体の2番目のRまたは3番目のL）
• 連続変えた時の得点：3点（RR）

となっていて、パターンに応じて増分が変化してそうだとわかった

この考えで他の例題含めて色々試してみると、

• 端以外の長さ1以上の連続部分を変えると2点増える
• 端を含む長さ1以上の連続部分を変えると1点増える
• （「両端が等しいものは同じ長さの連続部分として扱ってよい」も成り立ちそうだけど解き方が複雑になるので一旦保留した）

がなんとなく見えてきた
加えて、今回は手順の数も考慮しないといけなく、一回変更を加えたところに再度上記を適用させてLRL→LLL→RRRとしても最後のLLL→RRRは何も増えないので、これも扱う必要がありそう
RLRLRで考えてみた時に、
RLRLR→RLLLR→LLLLR→LLLLLだと3手順かかるのがRLRLR→RLLLR→RRRRRだと2手順で終わるので、
最大の連続部分が最優先になるように処理する（つまり、毎回処理後の最大の連続部分を計算する必要がある＋計算量が余分にかかる）のか・・・？と思ったけど、
RLRLR→RRRLR→RRRRR
という風に考えると最初にLかRかを正しく選べれば一度処理した部分は考慮しなくていい（計算量が減る！）のでは？という考えに至った。多分LかRかは全体に対する多さで決めて良さそう
他の例題でも試してみるとなんとなくいけそうだったので
　

１．「存在比を計算してLとRのどちらを対象にするか決める」（ \( O(N) \) ）

２．「初期状態の得点を計算する」（ \( O(N) \) ）

３．「長さ1以上連続する部分を抜き出す」（ \( O(N) \) ）

４．「K回以下で、各部分が端を含まないなら+2点、（回数が残っていて）端を含むなら+1を加算する」（ \( O(N)？ \) ）

（全体での計算量： \( O(N) \) ）

の処理で書いてみたところ無事AC
D問題のリベンジができたのでよかった
へとへとになったので今回もD問題で打ち止め。今後もDまで解けば良さそう

コード

#!/usr/bin/env python3

#### input
N, K = map(int, input().split())
S = input()

#### process
score = 0
for i in range(0, len(S) - 1):
  if(S[i] == S[i+1]): score = score + 1

num_R = len([s for s in S if s == "R"])

if num_R > len(S) / 2:
  S2 = S.split("R")
else:
  S2 = S.split("L")

# 端に出現するパターンのやつ
edge     = len([s for s in [S2[0],S2[-1]] if s != ""])
# 端以外に出現するパターンのやつ
non_edge = len([s for s in S2[1:-1] if s != ""])

score = score + 2 * min(K, non_edge)
K = K - min(K, non_edge)
score = score + min(K, edge)

print(score)

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）を解きに行く方がよいのでは説

説明的なやつ

淡々とAtCoderを解いていくブログ（今のところは）
書く練習とモチベ維持を兼ねてとりあえず勢いで登録した

簡単な自己紹介（ブログ開始時点）

• 学歴：情報系の大学・大学院卒
  • 情報系といいつつ計測とか回路設計中心なのでコード書くよりはんだ付けしてた
• 就職：文系職（非エンジニア）
• 競技プログラミング：未経験
  • ソートみたいなアルゴリズムの詳細とかわからん
  • 計算量・メモリの考慮もしたことなし
• プログラミング一般：学生の頃に趣味でちまちま。最近TECH::EXPERTなる塾に通ってWeb周りの基本がだいたいわかった
  • ReactとかVue.jsとかはまだ触れてないので気になる

まともにやったことのある言語（だいたい大学の授業か趣味）：

• HSP：GUIに特化した言語。昔に５年くらい？もう１０年くらい触ってないので忘れた
• C：昔に１年くらい。６年くらい触ってないので忘れた
• Arduino：昔に１年くらい。ほぼ忘れた
• Python：１年半くらい。実験の計算をさせたりした
• R : １ヶ月くらい。統計に興味でてきたので触りはじめた（最近）
• HTML / Haml：合計９年くらい。何年も触ってなかったけど最近ちょっと触った
• CSS / Sass：合計２年くらい。デザインセンスは無い
• JavaScript / jQuery：３ヶ月くらい。非同期通信のチャット作ったりした
• Ruby on Rails：８ヶ月くらい。大体の基本機能とちょっとしたメタプロ程度
• その他：gitとかDockerとかAWSとかVPSとか少し