Atcoder Regular Contest 109 (ARC109)振り返り

Atcoder Regular Contest109に参加しました。 AtCoder Regular Contest 109 - AtCoder

A問題

A - Hands 　上の図のように建物Aと建物Bは非対称につながっている。aからbに移動するときには上への移動と下への移動で場合分けすればよい。
　・下方向への移動(a>b)の場合
　建物間の移動には最低1回は廊下を通る必要があるがこの時斜めに移動するのが最短ルート。さらに下の階に移動するにはy分かけて階段で降りるか2x分かけて廊下を使うかのどちらかであり、min(y, 2x)を残りの階数(b-a-1)だけ足せばよい。
　・上方向への移動
　建物AからBへの移動は水平移動のため(b-a)階分の上への移動が必要。こちらもmin(y, 2x)だけ時間がかかるからこの通りに場合分けして出力する。なおa=bのときは上への移動に含まれる(b-a=0となるので)。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b, x, y;
  cin >> a >> b >> x >> y;
  if(a>b)cout << x+min(x*2, y)*(a-b-1) << endl;
  else cout << x+min(x*2, y)*(b-a) << endl;
}

B問題

B - log

　長さn+1の丸太をどのように切るかのみを考えればよい。さらに言えば、長い丸太を1本作るよりも短い丸太を多く作るほうがお金の節約になるため、長さ1,2,...の丸太を作るのが最善となる。(n+1の丸太を1とnに切断してもとの長さがnの丸太を切るとき、長さn丸太を切るのとn+1の丸太から切り出した長さn丸太を切るのは変わらない)
　ここで長さ1, 2, 3, ..., kの丸太の長さの和がn+1を超えない最大のkが分かればn+1-kが求める答えとなる(n+1本の丸太のうち短いk本はいらなくなるので)。丸太を切り出せるだけ切り出し続けると以下のようになる。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int64_t n, maruta, k;
  cin >>n;
  maruta=n+1; //長さn+1の丸太
  k=0;  //切り出す丸太の長さ
  while(true){
    if(maruta>=k+1){
      k++;
      maruta-=k;
    }
// 丸太から次の長さを切り出せるなら切り出す
    else break;
  }
// 切り出せなくなったら終わり
  cout << n+1-k << endl;
}

このコードでACできるが実行時間が650 msほどかかる。 最悪のケースでは1414213560回の計算を繰り返すのでc++でもぎりぎりだったと思われる。そこでkの値をより速く収束させたい。公式解説では二分探索により高速化を図っているがここではkとn+1の関係から大雑把に値を求めてみる。1からkまでの和とn+1の関係から

両辺に2をかけてルートをとれば

であるから、誤差による不都合を避けるために くらいから計算を行えば高速化できそうである。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int64_t n, maruta, k;
  cin >>n;
  maruta=n+1; //長さn+1の丸太
  //切り出す丸太の長さ
  k =sqrt(n*2)-1; //kにあたりをつけておく
  maruta -=k*(k+1)/2;//kまでの和を引く、以下同じ
  
  while(true){
    if(maruta>=k+1){
      k++;
      maruta-=k;
    }
    else break;
  }
  cout << n+1-k << endl;
}

実行時間は8 msになった。

C問題

C - Large RPS Tournament 　参加者が出す得意な手は周期性を持っていることが明らかである。例えばn=3, k=4, s=RPSのときには参加者1,2,...,16の出す手はR, P, S, R, P, S, R, P, S, ..., Rとなるが、これは参加者分だけs=RPSを繰り返していることが分かる。
　1回戦が終わった後を考えると参加者は半分になり、その得意な手はP, R, S, P, R, S, P, Rである。これはPRSの繰り返しである。このように長さnの文字列が変化しながら繰り返している。一方で参加者は半分に減り続けてk回後に優勝者ただ1人になるため、k回後の文字列の先頭の文字が優勝者の得意な手となるためこれを求めればよい。
　与えられた文字列を2倍にして、次の文字列を求めることを繰り返せばよい。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, k;
  string s, s1;
  cin >> n >> k >> s;
  
  for(int i=0; i<k; i++){
    s+=s;
/*勝負により文字列が半分になる。
周期性を維持するために長さを2倍にしておく。*/
    for(int j=0; j<n*2; j+=2){
      if(s[j]=='R'&&s[j+1]=='S')s1.push_back('R');
      else if(s[j]=='P'&&s[j+1]=='R')s1.push_back('P');
      else if(s[j]=='S'&&s[j+1]=='P')s1.push_back('S');
      else s1.push_back(s[j+1]);
    }
/*奇数番目が勝ったらその手を、そうでなければ偶数番目の手を
空文字列に追加する。*/
    s=s1;
    s1="";
/*文字列sを更新しs1を空にする*/
  } 
  cout << s[0] << endl; 
}

感想

　緑コーダーになったのでARCにも参加してみました。今回は規則性に気づければ解ける問題だったようでC問題まで解けました。嬉しい。D以降はわかりません。