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

            

        
      