AtCoder Beginner Contest 261

https://atcoder.jp/contests/abc261

結果

A - Intersection:AC(8:25)
B - Tournament Result:AC(39:53)
C - NewFolder(1):AC(59:13)
D - Flipping and Bonus:提出無し

A - Intersection

数直線に範囲が2つ与えられ、2つが重なっている範囲の長さを求める問題

自分の回答

int main() {
  int L1, R1, L2, R2;
  cin >> L1 >> R1 >> L2 >> R2;
 
  int L, R;
  L = (L1 > L2) ? L1 : L2;
  R = (R1 < R2) ? R1 : R2;
  int X = R - L;
 
  if (X > 0){
    cout << X << endl;
  }
  else{
    cout << 0 << endl;
  }
}

制約からL1<R1,L2<R2なため(Rの小さい方:R)-(Lの大きい方:L)でOK
なお解説を見るまでmaxとmin関数の存在をど忘れしていたためもっと短く書けた
答えである重なった範囲の長さ:Xは重なった部分が無い時負になるため、また制約で入力は整数のためifでX>0ならXを、そうでないなら0を出力すればOK

公式解説

大枠同じため基本省略
ただ、忘れてたmax,min関数を含め

cout << max(0, min(r1, r2) - max(l1, l2)) << endl;

https://atcoder.jp/contests/abc261/editorial/4482より

で終わるのはなるほどと思った

B - Tournament Result

総当たり戦の表に矛盾があるかをチェックする問題

自分の回答

int main() {
  int N;
  cin >> N;
 
  vector<vector<char>> result(N, vector<char>(N, '-'));
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      cin >> result.at(i).at(j);
    }
  }
  
  bool check = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(i == j){
        if(result.at(i).at(j) != '-'){
          check = 1;
        }
      }
      if(result.at(i).at(j) == 'D' && result.at(j).at(i) != 'D'){
        check = 1;
      }
      if(result.at(i).at(j) == 'W' && result.at(j).at(i) != 'L'){
        check = 1;
      }
      if(result.at(i).at(j) == 'L' && result.at(j).at(i) != 'W'){
        check = 1;
      }
      if(check){
        break;
      }
    }
    if(check){
      break;
    }
  }

  if(check){
    cout << "incorrect" << endl;
  }
  else{
    cout << "correct" << endl;
  }
}

Ai,jに対応するのはAj,iになるため2次元配列を作れば楽そう
入力が改行以外は連続しているけどcharで作れば問題はない
後はifでWなら対応先がLか、LならWか、DならDかで判定して結果を出力して終わり

ただコードにとんでもなく無駄が多い
第一にi=jの時、制約により - なことは確定してるからcontinueのみで大丈夫。問題文はちゃんと読もう
第二にループの脱出、「矛盾があったら」でifを作っているためそこに入ったらincorrectを出力してループ脱出した方が間違いなく短く、見やすくなる

公式解説

基本は同じでコードがPythonだったため省略

C - NewFolder(1)

名前被りがあった時のファイル名のやつを作る問題

自分の回答

int main() {
  int N;
  cin >> N;
  
  map<string, int> dup;
  for(int i = 0; i < N; i++){
    string S;
    cin >> S;
    if(dup.count(S)){
      printf("%s(%d)\n", S.c_str(), dup[S]);
      dup[S]++;
    }
    else{
      dup[S] = 1;
      printf("%s\n", S.c_str());
    }
  }
}

同じ名前が何回出てきたかを保持するmapを作れば楽そうだったからそこから繋げて、keyがあるならその数字を含めて出力してインクリメント、無いなら初期値1で作って名前そのまま出力
ただvalueの初期値を0にしてインクリメントを出力の前にした方が挙動として正しい気がする

公式解説

大枠同じため省略

D - Flipping and Bonus

コイントスをし、表ならカウントを増やしお金を貰う、裏ならカウントを0にする
その他カウントの値に応じてお金が貰え、最大何円貰えるかを求める問題

自分の回答

無し

さすがに与えられた回数で総当たりしてたらTLEすることはわかるが、ならどうすれば効率的に最大値を求められるかが思いつかずタイムアップ

公式解説

まず自分が思いつかなかった根本的なやり方について
i回目のコイントスでカウントがjの時貰えるコインの最大値をdp[ i ][ j ]、i回目に表が出た時貰えるお金をX[ i ]、ボーナスをBとすると、基本的な処理としてdp[ i ][ j ]はdp[ i-1 ][ j-1 ]の時に表を出したということなためdp[ i ][ j ]=dp[ i-1 ][ j-1 ]+X[ i ]+Bで求められる
また、j-1が存在しないj=0の時、これはi回目で裏を出した時のためこの時取りうる最大値dp[ i ][ 0 ]はdp[ i-1 ][ 0~j ]の中の最大値となる
そしてカウントは1づつ増えるためj≦iである
この3つによりdp[1][0]から連鎖してdp[ i ][ j ]までを簡単な演算で全て求められる
このようなアルゴリズムを動的計画法(Dynamic Programming)と言う
動的計画法については後でしっかり勉強する

そしてこれを基にこの問題の回答例として

int main(void) {
	int n, m;
	long long x[5001];
	long long c, y;
	long long b[5001], dp[5001][5001];
	long long ans;
	for (int i = 0; i <= n; i++)b[i] = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> x[i + 1];
	for (int i = 0; i < m; i++) {
		cin >> c >> y;
		b[c] = y;
	}
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) dp[i][j] = dp[i - 1][j - 1] + x[i] + b[j];
		dp[i][0] = 0;
		for (int j = 0; j < i; j++)dp[i][0] = max(dp[i][0], dp[i - 1][j]);
	}
	ans = 0;
	for (int i = 0; i <= n; i++)ans = max(ans, dp[n][i]);
	cout << ans << endl;
	return 0;
}

https://atcoder.jp/contests/abc261/editorial/4483より

二重ループが動的計画法の部分
全パターンを求められたらn回コイントスした中から最大の値を出力する
なるほど