目次
AtCoder Beginner Contest 100
B - Ringo's Favorite Numbers
問題
- 100でちょうど $D$ 回割り切れる正整数のうち、$N$ 番目に小さい物を求めよ
- $D=0,1,2$
- $1 \le N \le 100$
解法
D=0 1,2,3,.... D=1 100,200,300,... D=2 10000,20000,30000,...
基本的に、100で（ちょうどでなくても良いので）$D$ 回割り切れる $N$ 番目の数は、$100^D\times N$ となる。
この内、100で割り切りすぎてしまう（$D$ 回以上になってしまう）のは、$N$ が100の倍数の時。制約内では $N=100$ の時のみ。
d, n = map(int, input().split())
if n == 100:
n += 1
print(n * 100 ** d)
C - *3 or /2
問題
- 長さ $N$ の数列 $a=\{a_1,a_2,...,a_N\}$
- この数列の全要素に対し、以下のいずれかの操作を行う
- 3をかける
- 2で割る（ただし小数になってはいけない）
- 2で割る操作を最低1要素に対して行わなければならない
- 最大何回、繰り返し操作を行えるか
解法
2つの数を1操作で同時に2で割るなら、1回ずつの操作に分けた方が操作回数は増える。1回の操作で最小限の1つの数のみ2で割れば、操作可能な回数は、それぞれの数が2で割れる回数の合計となる。
from math import log
n = int(input())
aaa = list(map(int, input().split()))
ans = 0
for a in aaa:
ans += log(a & -a, 2)
print(int(ans))
D - Patisserie ABC
問題
- $N$ 個のケーキ
- それぞれに「綺麗さ」「おいしさ」「人気度」が決められている（$x_i,y_i,z_i$）
- 0以下の場合もある
- $M$ 個のケーキを選んで食べる
- 同じケーキは2個以上食べない
- 食べたケーキの「綺麗さ」の合計の絶対値、「おいしさ」の合計の絶対値、「人気度」の合計の絶対値、の合計をスコアとする
- スコアが最大になるように $M$ 個を選んだ時、スコアはいくつか
解法
$M$ 個のケーキの、たとえば「おいしさ」の合計が負だったとする。
最終的に絶対値をとるので、最初から各ケーキの「おいしさ」の値だけ正負反転させていても「おいしさの合計の絶対値」は変わらない。また「綺麗さ」「人気度」にも影響は無い。
なので、最終的に「綺麗さ」「おいしさ」「人気度」の合計がそれぞれ正負どちらになるか、8通りを試せばよい。
配列の要素を転置したり-1をかけたりするのでNumpy使ったけど、何かあんまり綺麗じゃない。
import numpy as np
def calc(xyz, m):
srt = sorted(sum(cake) for cake in xyz)
return sum(srt[-m:])
def solve(xyz, m):
if m == 0:
return 0
xyzT = xyz.T
ans = calc(xyz, m)
xyzT[2] *= -1
ans = max(ans, calc(xyzT.T, m))
xyzT[2] *= -1
xyzT[1] *= -1
ans = max(ans, calc(xyzT.T, m))
xyzT[2] *= -1
ans = max(ans, calc(xyzT.T, m))
xyzT[2] *= -1
xyzT[1] *= -1
xyzT[0] *= -1
ans = max(ans, calc(xyzT.T, m))
xyzT[2] *= -1
ans = max(ans, calc(xyzT.T, m))
xyzT[2] *= -1
xyzT[1] *= -1
ans = max(ans, calc(xyzT.T, m))
xyzT[2] *= -1
ans = max(ans, calc(xyzT.T, m))
return ans
n, m = map(int, input().split())
xyz = np.array([list(map(int, input().split())) for n in range(n)])
print(solve(xyz, m))
