ABC115参加記録と解説

結果

3WA全完で648位でした。
推定緑パフォらしいですが, 全完できて嬉しかったので良いです。

beta.atcoder.jp

A - Christmas Eve Eve Eve

beta.atcoder.jp

概要

12月の日付Dが与えられる。
D=25なら'Christmas',
D=24なら'Christmas Eve',
D=23なら'Christmas Eve Eve',
D=22なら'Christmas Eve Eve Eve'を出力せよ。

制約

• 

解法

if文で問題文の通りに書きます。

#include <iostream>
using namespace std;

int main() {
  int D;
  cin >> D;
  
  if (D == 25) cout << "Christmas";
  else if (D == 24) cout << "Christmas Eve";
  else if (D == 23) cout << "Christmas Eve Eve";
  else cout << "Christmas Eve Eve Eve";
  cout << endl;
  return 0;
}

B - Christmas Eve Eve

beta.atcoder.jp

個目の品物が円の品物が個ある。
個の品物のうち最も高い品物を半額にできる時, 品物の合計金額はいくらか?

制約

• 
• 
• は偶数

解法

最も高い品物のみを半額にするので, 最大値のみを1/2すれば良いですね。そのため, ソートしてから最後の要素(最大値)のみを1/2して全ての要素を足せば良いです。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector< int > p(N);
  for (int i=0; i<N; ++i) cin >> p[i];
  
  sort(p.begin(), p.end());
  
  int ans = 0;
  for (int i=0; i<N; ++i) {
    if (i < N - 1) ans += p[i];
    else ans += p[i] / 2;
  }
  
  cout << ans << endl;
  return 0;
}

C - Christmas Eve

beta.atcoder.jp

本目の木の高さがメートルの木が本植えられています。
その中から本の木を選んで装飾する時, 装飾した木のうち最も高い木の高さと最も低い木の差を最小化してください。

制約

• <
• 

解法

本を選ぶときに木の高さの幅を最小化するためには, ソートしてから連続した本を見てあげるのが良いでしょう。

なぜなら, 連続した本のうち最初の木が最小, 最後の木が最大となるので, (最大の木) - (最小の木)を全て試せば木の高さの幅を最小化できるからです。

#include <iostream>
#include <algorithm>
using namespace std;

costexpr int INF 1 << 30;

int main() {
  int N, K;
  cin >> N >> K;
  vector< int > h(N);
  for (int i=0; i<N; ++i) cin >> h[i];
  
  sort(h.begin(), h.end());
  
  int ans = INF;
  for (int i=0; i<N-K+1; ++i) {
    ans = min(ans, h[i+k-1] - h[i]);
  }
  
  cout << ans << endl;
  return 0;
}

D-Christmas

beta.atcoder.jp

多次元バーガーはパティ(以下と略す)とバン(以下と略す)で出来ています。
レベルLの多次元バーガーは次のように定義される。

• レベルバーガーは, 枚である。
• レベルバーガーとは,
  • 枚,
  • レベルバーガー,
  • 枚,
  • レベルバーガー,
  • B枚,
    をこの順に下から積み上げたものである。

レベルバーガーを作って下から枚取った時, その中には何枚あるか?

解法

レベルバーガー(以下バーガーと略する)の定義を見ると, 再帰的にバーガーを呼び出しています。それなので,

バーガーの枚数

とすると, このは以下のように表せます。

そして, の数は図の赤い部分と, f(L-1)の再帰に含まれるPの数のみです。それなので,

バーガーに含まれるの枚数
とすると, このは以下のように表せます。

また, 図と式を見ると分かりますが, バーガーは以下の手順で作れます。

1. を1つ置く
2. を置く
3. を1つ置く
4. を置く
5. を1つ置く

この上で, 下から枚取ったときを考えてみます。作成手順を見ると上下対称なのが分かるので, 上から枚の中にが何枚あるかを同様の手順で考えてみます。

手順	上からの枚数	含まれるPの数
を1つ置く	1	0
を置く
を1つ置く
を置く
を1つ置く

すると, 上の図のように場合分けされます。の時は当然1つも選べないので省略しています。この図に従って再帰関数を実装し, main関数から呼び出すことで解を求められます。

#include <iostream>
using namespace std;
// オーバーフローの可能性があるため, 64bitのint_fast64_tを使用します。
using int64 = int_fast64_t;

// Lバーガーの枚数を格納します。
int64 memo[55];
// Lバーガーに含まれるPの枚数を格納します。
int64 p_memo[55];

int64 f(int64 L) {
  // すでにメモされている場合はそちらの値を利用します。
  if (memo[L] > 0) return memo[L];
  // 0バーガーの枚数はPのみで1枚です。
  if (L == 0) return memo[0] = 1;
  // LバーガーはB + f(L-1) + P + f(L-1) + Bなので, 
  // まとめると全体の枚数は2 * f(L-1) + 3枚になります。
  return memo[L] = 2 * f(L-1) + 3;
}

int64 getP(int64 L) {
  if (p_memo[L] > 0) return p_memo[L];
  if (L == 0) return p_memo[0] = 1;
  // LバーガーはB + f(L-1) + P + f(L-1) + Bなので, 
  // まとめるとPの枚数は2 * f(L-1) + 1枚になります。
  return p_memo[L] = 2 * getP(L-1) + 1;
}

int64 solve(int64 L, int64 X) {
  if (X == 0) {
    // 残りの枚数が0枚になったら0を返します。
    return 0;
  } else if (L == 0) {
    // 階層が0になってしまったらgetP(0)=1を返します。
    return getP(0);
  } else if (X <= 1 + f(L-1)) {
    return solve(L-1, X-1);
  } else if (X <= 2 + f(L-1)) {
    return getP(L-1) + 1;
  } else if (X <= 2 + 2*f(L-1)) {
    return getP(L-1) + 1 + solve(L-1, X-f(L-1)-2);
  } else {
    return getP(L-1) + 1 + solve(L-1, X-f(L-1)-2);
  }
}

int main() {
  int64 N, X;
  cin >> N >> X;
  f(N);
  getP(N);
  
  int64 ans = solve(N, X);
  cout << ans << endl;
}

感想

今回のABCは, 最近のABCとは異なる難易度だったと考えています。A-Cは最近のABCの傾向からすると拍子抜けな簡単さだったと思います。そして, D問題は難しいと言う人がいるかもしれませんが, それは「考える」難しさではなく, 「実装する」難しさだと思います。なぜなら, 今回のD問題は実際に書き出してみれば再帰関数の目星はつき, 朧げでも実装方法は思いついていたはずだからです。そのため, 落ち着いて, 時間をかければACすることは不可能ではなかったでしょう。

逆に, 厄介なのは, Small Multipleのような「考える」難しさを要求してくる問題だと考えています。あの問題を見てdijkstra法が出てきますか？私は出てきませんでした。そのような, 問題と解法を繋げるのが難しい問題が私にとっては難しいようです。

長々と語ってしまいましたが, 久々に粘ってACをもぎ取るムーブが出来て非常に楽しいコンテストになりました。このようなコンテストが続くと良いです。