Bondo416さんのAtCoder Regular Contest 109での成績:1299位
— ボンド@競プロ (@bond_cmprog) November 28, 2020
パフォーマンス:1265相当
レーティング:1488→1467 (-21) :(#AtCoder #ARC109 https://t.co/uUNLQZ2eT1
A - Hands
算数でも出来そうだけど頭を壊しそうなのでダイクストラとかで最短経路を求める
提出コード
void solve(){ int a, b, x, y; cin >> a >> b >> x >> y; --a, --b; Dijkstra<int> dijk(2*111, INF); for(int i=0;i<100;i++){ if(i < 99) dijk.make_edge(i, i+1, y); if(i < 99) dijk.make_edge(i+1, i, y); if(i < 99) dijk.make_edge(i+1, i+100, x); if(i < 99) dijk.make_edge(i+100, i+1, x); if(i < 99) dijk.make_edge(i+100, i+100+1, y); if(i < 99) dijk.make_edge(i+101, i+100, y); dijk.make_edge(i, i+100, x); dijk.make_edge(i+100, i, x); } dijk.solve(a); cout << dijk.cost[100+b] << endl; }
B - log
$ n+1 $の丸太で出来るだけ多くの丸太を作ってから残りの丸太を買うのが最適になる
$ n+1 $の丸太で作れるものは$ \frac{x(x+1)}{2} \leq n+1 $を満たす最大の$ x $となる
この$ x $を求めるには二分探索とかで求めればいい(C++なら$ \sqrt n $でも通る)
よって答えは$ n - x + 1 $
提出コード
void solve(){ ll n; cin >> n; ll i = 1; for(;i*(i+1)<=2*n+2;i++){} cout << n - i + 2 << endl; }
C - Large RPS Tournament
文字列$ s $の対戦結果は周期を持つため、全ての対戦結果をシミュレートする必要がない
そのため $ t = s + s $としてシミュレートを行い、その結果を$ s = t $として$ k $回シミュレートした時の先頭の文字が答えになる
提出コード
vector<vector<char>> win = {{'R', 'R', 'P'}, {'R', 'S', 'S'}, {'P', 'S', 'P'}}; void solve(){ int n, k; string s; cin >> n >> k >> s; string t = s; map<char, int> mp; mp['R'] = 0, mp['S'] = 1, mp['P'] = 2; for(int j=k;j>0;j--){ t = ""; for(int i=0;i<4*n;i+=2){ t += win[mp[s[i%n]]][mp[s[(i+1)%n]]]; } s = t.substr(n); } cout << s[0] << endl; }