ferinの競プロ帳

競プロについてのメモ

ICPC 2019 Asia Yokohama Regional A Fast Forwarding

問題ページ
速度を何回も上げ下げする必要はない.したがって1,3,9,27,9,9,3,3,1のように一回上げて下げるような変化を考えればよい.時間を短くするには,貪欲にできるだけ早い速度にするべきである.

  • 速度を上げられる \iff 3s + s + \cdots + 3 秒で目標の時間を過ぎない
  • 速度を維持できる \iff s + s/3 + \cdots + 3 秒で目標の時間を過ぎない
  • これ以外 → s を3で割る

のどれかにしたがって速度を変更する.

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long int;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
  
signed main() {  
    ll t;  
    cin >> t;  
  
    if(t == 0) {  
        cout << 0 << endl;  
        return 0;  
    }  
  
    ll speed = 1, sum = 1, ans = 1;  
    while(sum<t) {  
        // speedを上げるか?  
        {  
            ll need = (speed*9-1)/2;  
            if(sum+need <= t+1) speed *= 3;  
        }  
        // speedを維持できるか?  
        {  
            ll need = (speed*3-1)/2;  
            if(sum+need > t+1) speed /= 3;  
        }  
  
        sum += speed;  
        ans++;  
    }  
  
    cout << ans << endl;  
}