ABC過去問解き。＃15、#16よりもハードな問題セットな気がする。C問題がなかなかのくせもの。問題はこちら。追記：#14ではなく#13でした。

A: A

"A"から"E"のどれか１つのアルファベットを与えられるのでアルファベット順での順番を答える問題。

print "ABCDE".index(raw_input()) + 1

B: 錠

ある数字 a (0以上9以下) があたえられる。この数字はボタンによって1ずつ増減させることができ、9の次は0、0の前は9という風になっている。今 a をボタン操作により b にしたい。このときのボタン操作数の最小値を答える問題。a, bの大小関係により10-b+aだけでは正しい答えにならないのに注意。

a = int(raw_input())
b = int(raw_input())
print min(abs(a-b),10-b+a,10-a+b)

C: 節制

高橋君は現在の満腹度Hで、毎日つぎの3つの食生活を選び、これからN日間満腹度0以下にならないようにする。

・豪華な食事をする： A 円払って満腹度を B あげる。

・質素な食事をする： C 円払って満腹度を D あげる。(C < A かつ D < B)

・食事を抜く：満腹度が E 下がる。

満腹度に限界はない。N日間満腹度を０以下にならないように食事をとった時、高橋君の食費の最低値を求めよ、という問題。満腹度０以下にならないような食事のとり方があることは保証されている。N は5×10⁵、A, B, C, D, E は10⁶以下という制限なので単純に豪華な食事、質素な食事の日数についての全探索では満点は間に合わない。

満腹度に限界はないので、豪華な食事、質素な食事の順にとっていけばよい。落ち着いて関係式を導けばO(N)の解放まであと一歩となる。豪華な食事をする日数を I、質素な食事をする日数を J とおけば、 H + BI + DJ - (N - I - Y)E > 0　という関係式が得られる。ここから J についての式を導けば豪華な食事をする日数が I のとき、最低限必要な質素な食事の日数がわかり、答えを計算できる。ただその場合 J がマイナスの値をとる可能性もあるので注意が必要。自分はここで30分ほど詰まってしまった。

N,H = map(int,raw_input().split())
A,B,C,D,E = map(int,raw_input().split())
ans = A*N
for I in range(N+1):
    J = ((N-I)*E-H-I*B)/(D+E)+1
        # J*Cをそのまま足さない。負の可能性がある。
    ans = min(ans,I*A+max(0,J*C))
print ans

D: 阿弥陀

あみだくじの本数 N と横線の数 M 、横線のリスト A を与えられる。さらにあみだを繰り返す回数 D も与えられる。各スタート数字がD連結あみだを通って最終的にどこにいくかを答える問題。制限がきびしく、N は10⁵、 M は10⁵、 D は10⁹となっている。ナイーブな方法だと部分点しかもらえない。

あみだを一回通った時の行先は、横線リストの情報を逆順にたどりながら隣り合う配列を交換していけば得ることができる。問題は D 連結のあみだの処理である。これは最初に得た行先リストを用いればうまく計算量を落とせる。どういうことかというと、行先リストを2回繰り返せば2連結後の行先、それを2回繰り返せば4連結後の行先、さらに・・・、と２のべき乗の連結数について行先を求められる。あとはDの各 i 桁のビットを見ながら、2ⁱ連結の行先を参照するかどうか決めると、最終的な行先を求めることができる。

pythonで書いて間に合う気がしなかったのでC++で解答。２のべき乗連結の行先を求めれることに気が付いてから解法に至るまで長かった。配列の値の入ってない不定値を参照してしまったりなどバグ取りに苦労したけど、なんとか自力で回答をひねり出せたのはうれしい。

#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;
 
int main(void){
    int N,M,D;
    cin >> N >> M >> D;
    int A[M],S[N],L[N];
    REP(i,M) cin >> A[i];
    
    REP(i,N) S[i] = i, L[i] = i;
 
    int tmp = 0;
    for (int i=M-1; i > -1; i--){
        tmp = S[A[i]]; S[A[i]] = S[A[i]-1]; S[A[i]-1] = tmp;
    }
 
    int t = 0;
    while (D > (1<<t)) t += 1;
 
    int JUMP[t+1][N];
    REP(i,N) JUMP[0][i] = S[i];
    FOR(j,1,t+1){
        REP(i,N)
            JUMP[j][i] = JUMP[j-1][JUMP[j-1][i]];
    }
    
    int j = 0;
    while (D > 0){
        if (D&1)
            REP(i,N) L[i] = JUMP[j][L[i]];
        D >>= 1;
        j += 1;
    }
    REP(i,N) cout << L[i]+1 << endl;
    
    return 0;
}

roiti46's blog

主に競プロ問題の解説を載せてます

Atcoder Beginner Contest #013

A: A

B: 錠

C: 節制

D: 阿弥陀