ABC129

atcoder.jp

久々にかく。ちなみに少し前から形式が変わって問題が6問になっている。
寝起きとはいえCで3ペナはだめ。
やっぱり少し準備しないとしっかり考えてから書くということがまだできないらしい。 夜遅いのでとりあえずBまで。 C-Dは気が向いたら。

A: Submission #5838156 - AtCoder Beginner Contest 129 簡単に言えば経路を2つ選んでそのコストの最小の和はいくつでしょう、になるんだろうか。

いろんな書き方があるだろうけど、とりあえず足してみてその中から最小を選ぶやり方。

a,b,c = map(int,input().split())

ans = min(a+b,b+c,c+a)
print(ans)

B: Submission #5843918 - AtCoder Beginner Contest 129
制約が緩いので愚直に2重ループでも通るはず。
でも工夫すれば1回のループ(入力受付を除く)だけで解ける。
今回のコードだとsumで1回余分に回っているけどそんなに影響はないはず。

考え方は今まで見てきた範囲の和(変数 l )とまだ見ていない範囲の和(変数 r )を使う。 ループを進めるたびに比較して差の最小値を出していく。 Wiに負数、0はないのでループが進むにつれてlは単調増加、rは単調減少するのでdisがこれ以上小さくならないとわかったらbreakしても良い(してないけど)。

こういうやり方はより難しい問題で当たり前に要求されるのでこういうところで練習を兼ねたい。 寝起きでぼんやりしていて勘で書いてしまってひどく時間がかかった。

n = int(input())
wn = list(map(int, input().split() ) )


r = sum(wn)
l = 0
dis = r
index_ = 0
for i in range(len(wn)):
    r -= wn[i]
    l += wn[i]
    t = abs(r-l)
    if t < dis:
        dis = t
        index_ = i
#        print(l,r,dis)

print(dis)

C:

Submission #5852752 - AtCoder Beginner Contest 129

300点にしては難しいけど400点もらえるかというと微妙な気もするのでやっぱり300点なのか…。

階段がN段のとき、移動方法は何通りあるのかをN=0から考えてみる。 ちょっと面倒なのでテキストベースで書く。 (1<=N<=10⁵なので0はなくてもいい) ()内の.は1段,-は2段移動を示す。 0 => 1 (ない) 1 => 1 ( . ) 2 => 2 ( .. | - ) 3 => 3 ( ... | .- | -. ) 4 => 5 ( .... | ..- | .-. | -.. | -- ) 5 => 8 ( ..... | -... | ...- | -.- | ..-. | --. | .-.. | .-- )

このあたりからフィボナッチ数列らしいことがわかるし、手で書いて生成するのが面倒になってくる。 ここでN段の結果はN-1段の結果から生成できそうと考える。フィボナッチなら当然できるだろう。 N-1の移動パターンの先頭に.を追加して、戦闘が..になった場合は..と-の2通りがある。そうでないならそのまま1通り。
つまりはN-1段のパターンで先頭に.があるなら+2、そうでないなら+1するとN段目のパターン数になる。 (2→3のとき　3=12+1; 3→4のとき 5 = 22+1; 4→5のとき 8 = 3*2+2 )

漸化式で表される数字を答えの算出に使えそうだが、何度も大きな値を計算すると計算コストが大きくなるだろう。ということでDPというかメモ化というか、フィボナッチをテーブルに記録しておく。 ここでfib[x]としたときにx番目のフィボナッチ数が返ってくるようにするとわかりやすいと思う。

これでAmを除いた範囲をfibのindexにしてやると答えは出る。 ただし、最後はn自身も含める必要があるので+1する。 多分もっとスマートに書けるはず。

「移動方法は何通りなのか？」という問題なので、通れないところの前後の移動方法は乗算する。 掛け算なのでそのたびにmodで割って構わないはず。

n, m = map(int, input().split())
an = [0]*m

for i in range(m):
#    s = input()
    an[i] = int( input() )
#an[-1] = n

#an.sort()
disjoint = False
for i in range(len(an)-1):
    if an[i] + 1 == an[i+1]:
        disjoint = True


if disjoint:
    print(0)

else:

    mod = 10**9+7
    tab = [0]*(10**5+10)
    tab[0] = 0
    tab[1] = tab[2]= 1

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]
#        if i<100:
#            print(tab[i])

    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if a == n else 0)
#        print(a,prev,index,tab[index])
        ans *= tab[index]
        ans %= mod
        prev = a+1

    #ans *= tab[n - prev]
    #ans %= 1000000007

    print(ans)