8/6 夏休み基礎力強化プロジェクト3日目

[idekazuki]

A - 名前

name = input()
ans = 'YES'
search = len(name) // 2
for i in range(search):
  if name[i] == name[len(name) - 1 - i]:
    ans = 'YES'
  else:
    ans = 'NO'
    break
print(ans)

しかしこれだと計算時間も長いし、きれいじゃない。 文字列を単純に反転させたものを比較すれば良い。

name = input()
ans = 'YES' if name == name[::-1] else 'NO'
print(ans)

気づいたこと。 print('YES' if name == name[::-1] else 'NO') よりも

ans = 'YES' if name == name[::-1] else 'NO'
print(ans)

のほうが1ms早い。

[idekazuki]

A - ホリドッグ

最初はnumpy でsqrt(n)求めてそこまで探索を行っていたけど。numpyをimportする時間が発生して実行時間が遅くなった。（100ms以上。）そこで検索範囲をn/2にして計算した。(19ms) 2で割り切れるものを先に非素数判定して、残りの奇数を判定するアルゴリズムを採用している。しかしなんと最初のif文を増やしたことでそんなアルゴリズムを使用しない全探索より遅くなってしまった。

def is_prime(n):
  if n == 1:
    return 'BOWWOW'
  if n == 2:
    return 'WANWAN'
  if (n % 2) == 0:
    return 'BOWWOW'
  for i in range(3, int(n/2), 2):
    if (n % i) == 0:
      return 'BOWWOW'
  return 'WANWAN'

if __name__ == "__main__":
  n = int(input())
  sum_n = int((1 + n) * n / 2)
  ans = is_prime(sum_n)
  print(ans)

実際の実行時間はif 文を減らしたほうが早くなった（pythonの最速17ms）。 アルゴリズム上は早いはずなのに実際はif文やimport などを削ることを考えたほうが早くなる事に気づいた。（pythonだけ？ちょっとショック）

def is_prime(n):
  if n == 1:
    return 'BOWWOW'
  if n == 2:
    return 'WANWAN'

  for i in range(2, int(n/2)):
    if not(n % i):
      return 'BOWWOW'
  return 'WANWAN'

if __name__ == "__main__":
  n = int(input())
  sum_n = int((1 + n) * n / 2)
  ans = is_prime(sum_n)
  print(ans)

[idekazuki]

部分文字列の個数による exp n = 6 文字長1が含まれる個数6 文字長2が含まれる個数5 文字長3が含まれる個数4 ....... 文字長6が含まれる個数1 よって文字長kが含まれる個数は n - (k - 1) これをn回ループして加算すれば良い

N = int(input())
ans = 0
for i in range(N):
  ans += N - i
print(ans)

またはΣ計算してN * 2 - ((N + 1)N / 2) + N

N = int(input())
ans = int(N ** 2 - ((N + 1)*N / 2) + N)
print(ans)

よく見たら普通に1+2+....+Nで良かった。

N = int(input())
answer = N*(N+1)//2
print(answer)

[idekazuki]

N = int(input())
student = list(list(map(int, input().split()))for _ in range(N))
max_p = 0
for i in student:
  max_p = max(sum(i) - i[4] * 79 / 90, max_p)
print(max_p)

[idekazuki]

A - 高橋くんと回文

下のようにコードを書いたらWAになった。原因が全然わからなかったが、先程処理速度を早めるために記述することにしたテンプレ文が原因だった。最初の3行を取り除いたら普通にACになった。15分位時間溶けてしまった。

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

S = input()
Sr = S[::-1]
flg = True
length = int(len(S)/2+1)
for a, b in zip(S[:length], Sr[:length]):
  if a == '*' or b == '*':
    continue
  if a != b:
    flg = False
    break
ans = 'YES' if flg else 'NO'   
print(ans)

[idekazuki]

A - ぐっすり

pop を使って実装した。appendは遅い？

N, K = map(int, input().split())
sleep_sum = []
sleep_sum.append(int(input()))
sleep_sum.append(int(input()))
ans = -1
for i in range(3, N+1):
  sleep_sum.append(int(input()))
  if sum(sleep_sum) < K:
    ans = i
    break
  sleep_sum.pop(0)
print(ans)

この人の回答見たら独自の関数をいっぱい作ってた。 https://atcoder.jp/contests/arc036/submissions/1261709

[idekazuki]

A - 全優

input()
M = list(map(int, input().split()))
ans = 0
for m in M:
  tmp = 80 - m
  ans += tmp if tmp > 0 else 0
print(ans)

numpy ver

import numpy as np
N = int(input())
M = np.array(input().split(), dtype=np.int32)

answer = np.maximum(80 - M, 0).sum()
print(answer)

もちろん最初の実装のほうが早いが、GPUとかを使って大量計算するときは配列に直したほうが良い実装かも。

[idekazuki]

A - カードと兄妹

ソートしてから、配列の終端から1個飛ばしで加算する。

input()
A = list(map(int, input().split()))
A.sort()
print(sum(A[::-2]))

numpy ver

import numpy as np
input()
A = np.array(input().split(), dtype=np.int32)
A.sort()
print(A[::-2].sum())

[idekazuki]

A - A - B problem

全通り確認することにした（6通り） 注意するところはa = aa.copy()のところ。もしもa = aaとするとaを変更したときにaaも変更されてしまいコピーした意味がなくなる。

A, B = input().split()
aa = list(map(int, [i for i in A]))
bb = list(map(int, [i for i in B]))
A = int(A)
B = int(B)
ans = -10000
for i in range(3):
  a = aa.copy()
  a[i] = 9
  ans = max(sum([a[j]*10**(2-j) for j in range(3)]) - B, ans)
  b = bb.copy()
  if i == 0:
    b[i] = 1
  else:
    b[i] = 0
  ans = max(A - sum([b[j]*10**(2-j) for j in range(3)]), ans)
print(ans)

[idekazuki]

A - 床塗り 指定した文字数をカウントして計算

N = int(input())
R = 0
B = 0
for _ in range(N):
  s = input()
  R += s.count('R')
  B += s.count('B')
ans = ('TAKAHASHI' if B < R else 'AOKI') if R != B else 'DRAW'
print(ans)

if 文を1行で書いてみたが、どっちが見やすいのかあまりわからない。

if B == R:
  ans = 'DRAW'
elif B < R:
  ans = 'TAKAHASHI'
else:
  ans = 'AOKI'

[idekazuki]

A-コインの反転

x, y = list(map(int, input().split()))
k = int(input())

if k <= y:
  ans = k + x
else:
  ans = 2 * y + x - k 
print(ans)

if 文を使用しない実装。（これのほうが1ms早い）

x, y = list(map(int, input().split()))
k = int(input())

t = min(k, y)
k -= t
x += t
ans = x - k
print(ans)

[idekazuki]

進捗