ARC-177

A

$URL\:\to$ https://atcoder.jp/contests/arc177/tasks/arc177_a

#貪欲法

int main(void) {
  #define Num 6

    ll M[Num]; rep(i,0,Num) scanf("%lld", &M[i]);
    ll Q[Num] = {1,5,10,50,100,500};
    ll N; scanf("%lld", &N);
    rep(i,0,N) {
        ll tmp; scanf("%lld", &tmp);
        sh ix = Num-1;
        while (tmp>0) {
            if (M[ix]<=0 && ix==0) {
                    printf("%s\n", "No");
                    return 0;
            }
            else {
                if (tmp>=Q[ix] && M[ix]>0) {
                    tmp -= Q[ix];
                    M[ix]--;
                }
                else ix--;
            }
        }
    }
    printf("%s\n", "Yes");

    return 0;
}

解法

おつりが出るのなら話は変ってくるのだが、今回の問題ではおつりがでないので、どの順番でお会計をしてもきっちりお会計ができないケースが発生した場合は順番を変えてもきっちりできないのは感覚的にわかると思う。したがって貪欲にお会計をしていくと題意を満たせる。

B

$URL\:\to$ https://atcoder.jp/contests/arc177/tasks/arc177_b

#視点の発想

    N = Integer().content
    S = list(map(int,list(input())))
    T = [0]*N

    ans = []
    pointer = N

    while True:
        pointer -= 1
        if pointer<0: break
        if S[pointer]==T[pointer]: continue

        for i in range(pointer+1):
            T[i] = 0 if T[i]==1 else 1

        if S[pointer]==1: ans.append("A"*(pointer+1))
        elif S[pointer]==0: ans.append("B"*(pointer+1))

    ans = "".join(ans)
    print(len(ans))
    print(ans)

解法

初期配置が $00\cdots00$ ということ
反転ボタンを押すと左から反転していくこと

以上を考慮すると、「右から配置をそろえていくと無駄が生じにくいのでは」と気付けるだろう。また、 $i(0 \to N-1)$ 番目の反転させたい電球までの電球の状態がすべて一致するときに $i$ 番目を反転させるまでに必要な反転ボタンを押す回数は $i$ 回となる。したがって、答えの配列と $00\cdots00$ の配列を持って置き、右から答えの配列にそろえていけば題意を満たすことができる。****

C

$URL\:\to$

解法

D

$URL\:\to$

解法

E

$URL\:\to$