みんなのプロコン2019-Cを解いた

competitive programming python

atcoder.jp

　難しかったけど解けた。難しいのは300点ではなく400点問題だからだろうか。
普通C問って何点なんだろうか。
点数をあまり意識したことはなかったけど、点数から自分のACできるかもしれない問題かどうかが判断つくなら良いことだ。
Dもいけるかなって思ったけど解説見ても書けないので今はまだ無理なのだろう。

 


自分なりの解き方
　 問題文にある操作はそれぞれ以下のAction 1-3のようなものになるだろう。

  • Action 1. biscket++;
  • Action 2. biscket -= A; money++;
  • Action 3. money--; biscket += B;


そして考えるなり紙に書くなりすると、いくつかわかることがある。

  1. Action 2 はAction 3 が行われない限りビスケットの枚数を増やせない
  2. ビスケットの枚数は選択したActionの数や種類で変化するが順番は入れ替えても影響がない
  3. Action 2とAction 3を行ってビスケットを増やすならAction 1を2回するよりも増えないといけない。
  4. Action 2を行うためにはAction 1.でビスケットをA枚以上にする

上記の条件から以下のように書けるだろう。

# python 3
k, a, b  = map(int, input().split() )


if b-a <= 2:# 3
    print(k+1)

else: 
    tap = a-1 # 4

    remK = k-tap # 4 

    ans = a # 4
    ans += (remK // 2) *( b-a ) + remK % 2 # 1 && 2
    print(ans)


*ソース中の# N ( 1 <= N <= 4 ) は関連する条件
B-A>2がfalseならAction 1をk回して初期値1枚を加算すればいい。
B-A>2がtrueならまずビスケットをA枚まで増やし、行動回数をその分減らす。

このときビスケットの枚数は以下のような、初項がAで行動回数を2回消費するごとに(B-A)ずつ増えていく等差数列で表せるだろう。
最後に行動回数が1残ったならばAction 1の操作で+1したほうがいい。

      X[a-1] = A
      X[i+2] = x[i] + (B-A)
      x[i+1] = x[i] + 1
  
    時間経ってしまったので忘れている/間違っているかもしれないけれど多分大丈夫なはず・・・。
    いつものC問に比べると考える条件だとかが多くて、D問に比べると数字の動きとかがシンプルで小さい印象。
    一発ACは良いが45分はどうなのかなぁと思っていたのだけど、レートは大きく上がったので問題の難しさと私の実力の割には早く回答できたという判定なのだろうか。