AtCoderわからん日記_4 ABC081B,087B,083B（ABSより）

はじめに

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
　年末年始でしばらくコンテストがなかったのでこちらの記事に載っているAtCoder Beginners Selectionの問題をやってみました。
　B問題かあ、とわりとなめてかかっていたんですが、どれもすごく難しかったです。そりゃあ、これだけ解けば闘えるなあと感じました。
　あと、な～んかおかしいなあと思いつつ記事を書いていたんですが、すっっごい勢いで誤字をしまくっていたので直しました。あまりにも恥ずかしいので何かは言いませんが、気づいていた方がいたら、初心者なので生暖かい目で見てください。すみません。

ABC081B - Shift only

黒板に N 個の正の整数 A₁,...,A_N が書かれています．
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．

• 黒板に書かれている整数すべてを，2 で割ったものに置き換える．

すぬけ君は最大で何回操作を行うことができるかを求めてください．

考えたこと

①全部割る操作をするしかないのだろうか……TLEにならないかな……
②とにかく計算量を少なくするために小さい順に並べよう
③リストは改変せずに2の累乗で割る方向でいこう
問題によってコンマ派か句読点派か分かれるんですね。

書いてみた

n = input()
a = list(map(int, input().split()))
a.sort()
i = 0
#とりあえずループ
while i <= a[0]:
  for j in a:
    #割れなくなったら内ループを抜ける
    if j % (2**(i+1)) != 0:
      print(i)
      break
  #リスト内全部割れたら次
  else:
    i += 1
    #↓のbreakは無視！
    continue
  #内ループの後に外ループを抜ける
  break

　たったこれだけのコードなんですが、ここまでくるのに数時間かかりました。割れない数が来た時に両方のループをbreakするという操作を実現するのにとても苦戦したためです。
　意外と実行時間は少なめでした。
　elseのインデントずらしていいなんて知らなかった……。ダメって書いてなかったから、いいんだね。
　i <= a[0]のところ、前回同様そのうちbreakするし適当にこれでいいかと思ってa[0]にしたのだけど、もっといいやり方がある気がするなあ……。

強人（つよびと）の解答

• びっくりするほど全く意味がわからない

不勉強で申し訳ない限りですが、コードが最も短めの群の解答は全くわかりませんでした。知らない関数がまだまだたくさんありますね。この日記の主旨としては、今のレベルであと一歩たどり着けなかったコードを書きたいという気持ちなので、とりあえずここは飛ばして自分と似た構造の解答を探しました。いつかちゃんと調べるかも。

• all()とfor文を組み合わせる
• リスト内包表記を使う

　そんなやり方があったんですね。なるほど……。all関数は今まであまり使ってこなかったので、全く思いつきませんでした。それに、リスト内包表記、知ってはいたんですけれどいまいち苦手な分野ですね。きちんとおさらいしようと思います。
　とてもとても学びが多い問題でした。ABSに選ばれるだけある……。元記事のかたがあげてくださっている線形探索の記事もきちんと読みます。

ABC087B - Coins

あなたは500円玉を A枚、100円玉をB枚50円玉をC枚持っています。これらの硬貨の中から何枚かを選び合計金額をちょうどX円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。2通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

考えたこと

①目的額を分解すると複雑すぎちゃう？
②じゃあ持ってる硬貨で総当たりしたほうがよさそう

書いてみた

a = int(input())
b = int(input())
c = int(input())
x = int(input())
ans = 0
#組み合わせ総当たり
for i in range(a+1):
  for j in range(b+1): 
    for k in range(c+1):
      total = (i * 500)+(j * 100)+(k * 50)
      if total == x:
        ans += 1
        break
print(ans)

　これも書くのに1時間ぐらいかかりました。こっちは見返してみると説明もいらんぐらいすごく簡単なのに……。多重ループだけど単純な構造だし。これはひとえに愚かだったからですが、これから愚かでなくなるようにがんばるので大丈夫です。

強人（つよびと）の解答

だいたい同じでした。やったー！　まあ、単純な問題だもんね。

ABC083B - Some Sums

1 以上N 以下の整数のうち、10進法での各桁の和がA 以上B以下であるものの総和を求めてください。
制約

• 1≤N≤10⁴
• 1≤A≤B≤36
• 入力はすべて整数である

考えたこと

①ほぼ四桁までならそこまで大きくないから総当たりでいけそう
②さっきと同じようにそれぞれの桁でループしたらいけるんちゃうかな
③計算量増やさないようにいらない桁でループしないようにしよう
さっきやった！　と思って調子に乗りました。あとでちょっと仇になっています。

書いてみた

n, a, b = map(int, input().split())
ans = 0
#nの値によって、十～千の位はループしないようにする
ir = 1 if n < 1000 else 10
jr = 1 if n < 100 else 10
kr = 1 if n < 10 else 10
#組み合わせ総当たり
for i in range(ir):
  for j in range(jr):
    for k in range(kr):
      for l in range(10):
        #桁の合計
        s = i + j + k + l
        if s >= a and s <= b:
          #値段の合計
          t = 1000 * i + 100 * j + 10 * k + l 
          if t <= n:
            ans += t
print(ans)

WA。二件だけだったので、例外の見落としがあるなと思ってちゃんと確認したら、n=10⁴の時のことを忘れていました。もちろん過程でほかにもうっかりミスはたくさんしており、こんな小さい間違いを載せるか迷ったんですが、これは戒めとしてきちんとおいておきます。自分で作った例外を忘れるな。

書いてみた_2

n, a, b = map(int, input().split())
ans = 0
ir = 1 if n < 1000 else 10
jr = 1 if n < 100 else 10
kr = 1 if n < 10 else 10
for i in range(ir):
  for j in range(jr):
    for k in range(kr):
      for l in range(10):
        s = i + j + k + l
        if s >= a and s <= b:
          t = 1000 * i + 100 * j + 10 * k + l 
          if t <= n:
            ans += t
#例外を拾ってあげる
if n == 10000 and a ==1:
            ans += n            
print(ans)

例外を作った時は、忘れないように例外のほうからコードをかいたほうがいいかもしれないですね。

強人（つよびと）の解答

• sum(map(int, str))

　文字列iそれぞれをintで数値にしてsumをとる。なるほど……なるほど……？！　全く思いつかなかった。map関数、今まで入力のときしか使っていなかったな……。みんな思いついていてすごい。しかし、なにがしかのスタンダードがあり、みんなもこうやって学んできたんだろうな。わたしもがんばります。
　と思って解説を読んでみたらわりとよくある問題らしい。10で割り続けたたあまりを足す方法、なるほど、なるほど、こんなのよく思いつくなあ。こうした他人の思い付きを自分のものにして、もっと難しいものも自分で思いついていかなければならないね……。早くこうした定石に慣れていきたいです。
　それと、a <= s <= bでよかったみたいです。できそうだと思っていたのになんとなく信じていなかったな。信じて。

　今まで何回か解いてたB問題より圧倒的に時間がかかってびっくりしました。¹ そのうえ、三つともすごく学びがありました。さすが選ばれた問題なのだなという感じです。
　またそのうち残りのABS問題にも挑戦します。きちんと復習したら追記したい……。

---

1. 単純に無駄な徹夜明けに解いたからでは？という説が浮上しました ↩