AtCoder Beginner Contest 100

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))