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

programming_algorithm/contest_history/atcoder/2018/0616_abc100.txt · 最終更新: 2018/07/25 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0