Study

AtCorderはじめます!

AtCoderはじめました。

まだコンテストには参加していないのですが、今週末から参加してみる予定です。

leetCodeでなくAtCoderを選んだ理由

アルゴリズムの勉強をleetCodeでやっていこうと思ったのですが、その前にAtCorderで勉強することにしました。

leetCodeよりAtCorderを選んだ理由は以下になります。

  • leetCodeは課金サービスなので、やるなら一気に
  • アルゴリズムの基礎力がまったくないので、まずは日本語で地道に学んでいく
  • AtCorderは解説や情報が豊富にある

AtCoder事始め

QittaでLGTM数6500越え(2022年4月現在)の以下のお化け記事にある、まず最初にやる10問をやってみました。

https://qiita.com/drken/items/fd4e5e3630d0f5859067#5-%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-10-%E5%95%8F

一応、全部できはしたのですが、問題が古いせいか公式ではもう提出できなくなっているようです。サンプルは通ったのですが、本当に全問通るかどうかはわからないままです。

9問目と10問目は、解説とは随分違うコードになってしまいました。自分のコードは、長ったらしいのですが、考えかたは解説と似たような感じはしますので、特に深くは突き詰めていません。

9問目(049c-daydream)の自分の回答

def main(s: str):
# dream
# dreamer
# erase
# eraser

# print(s[-5:])
# print(s[:-5])

while len(s) >= 5:
if s[-5:] in ('dream', 'erase'):
s = s[:-5]
elif s[-6:] in ('eraser'):
s = s[:-6]
elif s[-7:] in ('dreamer'):
s = s[:-7]
else:
print('no')
return

if len(s) == 0:
print('yes')
return
print('no')

if __name__ == '__main__':
main('erasedream') # yes
main('dreameraser') # yes
main('dreamerer') # no

10問目(086c-traveling)の自分の回答

def main(n: int, t):
cur_x = 0
cur_y = 0

for ti in t:
# 目的地xへの移動量
move_x: int = abs(ti - cur_x)
# 目的地yへの移動量
move_y: int = abs(ti - cur_y)

# 残り時間
remind_sec = ti[0] - move_x - move_y
if remind_sec < 0: return 'no' # 遠すぎて到達不可 # 残り時間が偶数なら戻ってこれる、奇数なら戻って来れない if remind_sec % 2 != 0: return 'no' return 'yes' if __name__ == '__main__': print(main(2, [[3, 1, 2], [6, 1, 1]])) # yes print(main(1, [2, 100, 100])) # no print(main(2, [[5, 1, 1], [100, 1, 1]])) # no ``` ## 246を試しにやってみる AtCorderを246を試しにやってみました。 A, Bはできて、Cは最初はできなくて、翌日改めてやり直したら何とかできたという感じです。Dは、まったく太刀打ちできませんでした。 なので、実際にできたのはBまでということになります。 Cの自分の回答は以下です。 ```python n, k, x = map(int, input().split()) a_list: list = [int(x) for x in input().split()] # case 3 ans: 112 # n, k, x = 20, 815, 60 # a_list = [int(x) for x in # '2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202'.split()] # case1 ans: 12 # n, k, x = 5, 4, 7 # a_list = [8, 3, 10, 5, 13] # case2 ans: 0 # n, k, x = 5, 100, 7 # a_list = [8, 3, 10, 5, 13] total = sum(a_list) minus_total = 0 used_k_total = 0 # 割引率100%でクーポン消費 a_list.sort(reverse=True) for i in range(k): if i &gt; len(a_list) - 1: # クーポン使い切れない or 割引率100%で使いきったケース
break

used_k = a_list[i] // x
if used_k &gt; 0:
used_k_total += used_k
a_list[i] = a_list[i] - used_k * x # 割引後の価格をセット
minus_total += used_k * x
if used_k_total &gt; k: # クーポン使いきった
minus_total = k * x
break
else: # 割引率100%でない商品がある可能性がある
break

# 残りクーポンを割引率100%でない商品の大きい順に割り当てていく
# print(a_list)
# print(used_k_total)
# print(minus_total)
# print('-----')

a_list.sort(reverse=True)
for i in range(k - used_k_total):
if i &gt; len(a_list) - 1: # クーポン使い切れない
break

if a_list[i] == 0: # 割引商品がない。Ans:0 のケース
break

minus_total += a_list[i]

# print(a_list)
# print(used_k_total)
# print(minus_total)
#
# print('----ans=======')
print(total - minus_total)

ずらずらと長いコードになってしまったのですが、以下のように短いコードで行けるみたいですね・・・ この差を知ってしまったときは、落ち込みました😨

https://qiita.com/u2dayo/items/4896cea07b59c707df3a#c%E5%95%8F%E9%A1%8Ccoupon

現在値と目標

Bまでしか解けなかったという事実、C問題の模範解答は違いすぎるコード量、これらを思い知らされたときは本当にへこみました。

(昔はもう少しできた気がするんですが・・・💧)

今の自分は、ランクで言えばおそらく茶色でしょう。茶色は学生レベルらしいです。

目標は水色なんですが、AtCorderをやっている人のブログをざっと見たところ、年単位の時間がかかるようですね。気長にやっていくことにします。