AtCoder Beginner Contest 187 D問題

AtCoder Python

前書き

atcoder.jp

D問題

難易度：茶色
時間：25分

問題設定にて与えられている値の条件が「1≤N≤2*10**5,1≤Ai,Bi≤2*10**9」なので二重ループは適用できません。
ということは1重ループで実行できるように発想の転換が必要です。

  1. scoreは現時点での高橋さんの票-青木さんの票です
  2. 高橋さんが演説しなかった場合を初期値にとります（score）
  3. 高橋さんが演説した場合「青木さんの票が高橋さんに移動分+青木さんの票の減少分+高橋さんの票増加分」（＝Delta）がscoreに加算されます
  4. Deltaはソートで影響票数が多い分に（O(nlog(n))）
  5. scoreが0を上回った時の演説回数を出力

これを実装します。

import numpy as np
N = int(input())
AB = np.array([list(map(int, input().split())) for i in range(N)])
# Takahashi - Aoki
score = (-1)*sum(AB[:,0])
Delta = AB[:,0]+AB[:,0]+AB[:,1]
count = 0
DeltaReverse = np.sort(Delta)[::-1]

for rd in DeltaReverse:
  count += 1
  score += rd
  if score>0: 
    break
print(count)

ACでした！

AtCoder Beginner Contest 186 C問題+D問題

AtCoder Python

前書き

今回は2問が茶色以下の難易度でしたので解きました。

C問題

難易度；灰
時間：30〜40分

atcoder.jp


アルゴリズム自体はすぐに思い浮かんだのですが、再帰関数への理解が甘く時間がかかってしまいました。
再帰関数では以下の処理をしています。

  1. a%Kの剰余が7 もしくは aがKより小さくなった場合にa%Kを返す
  2. ならない場合は関数nisin()を繰り返し実行
  3. 値を返却

以下のサイトの再帰関数sum()を実行してみると挙動がわかります。
note.com

import math
N = int(input())
count = 0
 
def nisin(a,K):
  if (a%K==7) or (a<K): return a%K
  return nisin(math.floor(a/K),K)
  
for i in range(1,N+1):
  amari10 = nisin(i,10)
  amari8 = nisin(i,8)
  if (amari10==7) or (amari8==7): 
    count+=1
print(N-count)

D問題

難易度；茶
時間：30分

atcoder.jp

問題設定は2≤N≤2*10**5でした。

a-b の形の式が最大(2*10**5)*(2*10**5 -1)/2パターン考えられます。

2重ループは間に合わないので、2重ループせずに計算する方法を模索。
するとそれぞれの値は必ず(N-1)回分、計算式に出現していることがわかります。

  1. 各数字を昇順にソート（O(nlog(n))）
  2. 最大値は全て加算され、値が小さくなるにつれて減算の回数が増加、最小値は全て減算の仕組み
  3. これによりO(n)の計算量で計算可能
N = int(input())
Lis = list(map(int, input().split()))
 
Lis.sort(reverse=True)
start,sum_ = 0,0 
N -= 1
for l in Lis:
  sum_ += (-start)*l+N*l
  start += 1
  N -= 1
print(sum_)

AtCoder Beginner Contest 189 C問題

AtCoder Python

前書き

atcoder.jp

C問題

難易度：茶色
時間：タイムオーバー

解けませんでした。何度かコードを書いてトライしましたが、いずれもTLEとなりました。

最初に書いたコード

短いように見えてやってることは3重ループ。
(10**4)*(10**4)の全探索（O(n**2)）な上、最小値min（O(N)）を挟んでいるので、3重ループ。
そりゃTLE吐くわ。

import itertools
N = int(input())
A = list(map(int, input().split()))
 
Lis = [min(A[i[0]:i[1]+1])*((i[1]+1)-i[0]) for i in list(itertools.combinations_with_replacement(range(0,N), 2))]
print(max(Lis))

2番目に書いたコード

これも3重ループ。
でも区間最小値を求めて、区間長と区間最小値の積の最大を求めようとしているので、筋は合っている。
ただアルゴリズムの問題。

import itertools
import numpy as np
 
N = int(input())
A = np.array(list(map(int, input().split())))
 
ans = 0
for i in range(0,N):
  for j in range(i,N):
    ans = max(ans, min(A[i:j+1]*(j+1-i)))
print(ans)

正解

区間最小値はまずLを固定します。
その後Rを探索しますが、この時点でmax()やmin()は二択をとるようにします（計算量を節約するために）。

しかもこれをpythonで実行するとTLE。。。
Pypyで実行するとACになります。なんやそれ・・・

unidayo.com


これからはPythonで厳しいと感じたら、Pypyで実行するようにしましょう。

import itertools
 
N = int(input())
A = list(map(int, input().split()))
 
ans = 0
for l in range(0,N):
  _min = 10**6
  for r in range(l,N):
    _min = min(_min, A[r])
    ans = max(ans, _min*(r+1-l))
print(ans)

AtCoder Beginner Contest 190 C問題

AtCoder Python

前書き

面接でライブコーディングをやったのですが、難しいですね。
人が見ている場面でコーディングをした経験がなく、緊張してしまって、頭が真っ白になってしまいました・・・。
挙げ句の果てには「コードちゃんと書いてたの！？」と言われてしまう羽目に。つら。
自分が情けないので、Atcoderの問題ちゃんと解こう。

解いた問題

難易度：茶色
時間：30分

まさか泥臭く解く問題とはおもわず、賢い解法を探すのに時間がかかってしまいました・・・。
ヒントは2≤N≤100,2≤M≤100,1≤K≤16なので2**16をしても、パターンは最大65536通り。
最大65536通りの選択した数値パターンから、最も多くの条件式に当てはまる数値パターンを探します。
M=100個の条件式に当てはめて、最大何個の条件式が成立するか。

65536*100 = 6553600通りなので、計算できる？
書いてみた。

atcoder.jp

import itertools
n, m = map(int, input().split())
AB = list(list(map(int, input().split())) for i in range(m))
k = int(input())
CD = list(list(map(int, input().split())) for i in range(k))

pattern = list(itertools.product(range(0,2), repeat=k))
lis = [[CD[j][l] for j,l in enumerate(p)] for p in pattern]
countLis = []
for l in lis:
  count = 0
  _lis = set(l)
  for ab in AB:
    if (ab[0] in _lis) and (ab[1] in _lis): 
      count+=1
  countLis.append(count)
print(max(countLis))

結果

AC。いけた。