初回 -> はじめに

ABC116を解きました。
3完です！

問題	時間	アルゴリズム	実行時間
A	1min	-	7ms
B	4min	-	7ms
C	13min	-	8ms

まとめ

先にまとめを載せます。これ自体は最後に書いてます。

要素が重複しているかの判定で、std::setを使うとメモリ使用量を抑えられます。
配列を使った場合は速度が速いです。

D問題は難しかった。またの機会に解きます。。。

A - Right Triangle

  int a, b, c;
  cin >> a >> b >> c;
  cout << a * b / 2;

直角三角形の面積を求める問題ですね。
直角を挟む2辺の長さがわかれば答えがわかります。
入力の位置が決まっているので、そのまま答えが出せます。

B - Collatz Problem

  int s;
  cin >> s;

  set<int> st;
  st.insert(s);
  int ind = 1;
  while(true)
  {
    ind++;
    s = ((s & 1) ? 3 * s + 1 : s / 2);
    if (st.find(s) != st.end())
    {
      cout << ind;
      return;
    }
    st.insert(s);
  }

数列を生成しながら出た数値を保存して、同じものが出た時点で終了しました。
setはbool型の配列などでも大丈夫です。
setだとメモリ使用量を抑えられます。配列を使った場合は速度が速いです。

コラッツの問題(コラッツ予想)という問題がベースとなっているそうです。面白いですね。

C - Grand Garden

  int n, h;
  cin >> n;
  int old_h = 0;
  int ans = 0;
  for(int i = 0; i < n; ++i)
  {
    cin >> h;
    ans += max(0, h - old_h);
    old_h = h;
  }
  cout << ans;

いもす法の逆演算みたいな問題ですね。

イメージとしては、入力列をヒストグラムのように見て山ごとに分けて考えました。
ただ、使うのはヒストグラムではありません。順番が大事です。
山とは、数値が単調増加して単調減少している集まりです。
単調減少ののちに数値が増えると次の山になります。

例えば、入力例2の3 1 2 3 1の場合は、(0 3 1), (1 2 3 1) の二つの山ができます。
(※はじめの高さである0を入れています)
(※山の境界にある1は重複しています)
こうしてみた時、ひとつの山はその「高さ」の回数だけ水やりをすれば作れますね。

つまり、山の高さの和が答えになります。
注意が必要なのは、「高さ」は山の開始時からの高さになります。
(1 2 3 1) の山は高さが3 - 1 = 2になります。

最初の山の高さが3
つぎの山の高さが2
なので、答えは3 + 2 = 5になります。

もう少し考察を進めると、ひとつ前の入力から大きくなった時にその差を足せば答えになります。
これを実装したものが上のコードになります。

以上です。ありがとうございました。