A - Brick

$N=12$ ， $w = 5$ のときは， $2$ 個の荷物を載せることができる（ $3$ 個目を載せると $15$ キログラムとなりオーバーする）．これを素直に式に表すと $12÷5 = 2\cdots 3$ となる（ $\cdots$ は余りを表す）．

従って，この計算の商の部分が答えになる．pythonでは切り捨て処理は//で記述できる．

N, W = map(int,input().split())
print(N//W)

B - Blocks on Grid

ブロックを取り除くことしかできないので，すべてのマスの中でブロック数が一番少ないマスのブロック数に他のマスのブロック数を合わせるしかない．

おおむね次のような処理とした．

入力の1行ごとに，その行の最小値を保存するようにして，すべての入力が終わったあとで，それらの中から全体の最小値を取得
$H\times W$ 個の要素を走査し，その中で先の最小値との差を合計していく

H, W = map(int,input().split())
A = []
mins = []
for i in range(H):
  a = list(map(int,input().split()))
  A.append(a)
  mins.append(min(a))
ans = 0
m = min(mins)
for i in range(H):
  for j in range(W):
    ans += A[i][j] - m

print(ans)

C - Unlucky 7

少し難しかった．

各桁に7が出てくるかどうかのチェックが必要であり，それは整数型のままではできないので，文字列に変換して文字列の7を含むかどうかを判定する．
10進数については，ただ文字列に変換して上記の処理を行えばよい
8進数については，10進数を8進数に変換する処理が必要になる．

8進数への変換

実は，pythonには関数が用意されている(https://docs.python.org/ja/3/library/functions.html#oct)．ただ，ここでは向学のため8進数への変換も実装することとする．

進数について

カンジをつかむ

そもそも10進数とはどのような数の表し方かを確認する．例えば2345（二千三百四十五）は $2345 = 2000 + 300 + 40 + 5 = 2 \times 10^{3} + 3 \times 10^{2} + 4 \times 10^{1} + 5 \times 10^{0}$ と書き直すことができる．この各位の数 $2,3,4,5$ 以外の部分に注目して $10^{x}$ という形になっている．この部分が $10$ なので $10$ 進法と呼んでいる．

では，8進数で $3456_8$ と表されているという数は（10進数では）どのような数になるかというと，それは $345_8 = 3\times 8^{3} + 4\times 8^{2} + 5\times 8^{1} + 6 \times 8^{0}$ となる．ちなみにこれを計算すると $1880$ である（もちろんこれは10進数）．※ $3456_8$ の右下の小さい $8$ は，8進数で表していることを明示するためにつけている）

8進数を10進数に変換する

これで，８進数，10進数のカンジはつかめたのではないかと思うので，次は10進数で表された数を8進数に変換することを考える．先の $2345 _{10}$ を8進数に変換することを考える．8進数での表記は $8^{x}$ というかたまりを作れば良い．下の桁から順番に調べよう．一番下の桁は $k\times 8^{0}$ となっており， $k$ は $1～7$ のいずれかである（もし $k=8$ なら，繰り上がって， $8^{1}$ の桁の方に出てくることになる）．

したがって一番下の桁は，元の数字を8で割った余りを取ればよい． $2345÷8 = 293\cdots 1$ となり，最下位桁は1とわかる．

次に下から2番目の桁を求める．今，最下位桁は「●●▲◆」の◆の部分を８で割った余りとして求めたので，次の桁は一番下の◆を切り落とした「●●▲」に対して8 で割った余りを求めればよい．この一番下の◆を切り落とす方法を考える．

実は簡単である．10進法で考えると， $1234$ を $123$ にするには， $10$ で割って小数点以下を切り落とせばよい．ここで $10$ で割ることで一番下の桁が落ちるのは10進数だからである．

したがって今は8進法で考えているので $8$ で割って小数点以下を切り捨てれば目的のものが得られ，それを $8$ で割った余りを求めればよい．

$2345÷8=293.125$ なので $293$ とし，さらに $293÷8=36\cdots 5$ となり下から2番目の桁は5だとわかる．

あとはこれを繰り返せばよい．計算式のみ記す．

$293÷8 = 36.625$ となり $36÷8 = 4\cdots4$

$36÷8 = 4.5$ となり $4÷8 = 0\cdots4$

$4÷8 = 0$ となり $0÷8 = 0\cdots0$ となりここで終わり．

したがって， $2345_{10} = 4451_8$ であることがわかった．これを実装すると次のようになる．

def to_oct(n):
  s = ''
  while(n):
    s = str(n%8) + s
    n //= 8
  return s

ans = 0
N = int(input())
for i in range(1,N+1):
  if '7' not in str(i)  and '7' not in to_oct(i):
    ans += 1
print(ans)

masuTomo’s blog

競技プログラミングの勉強メモです．主にPythonを使用します．数学の記事も書くかもしれません．

ABC186 解説（A～C）