Chokudai SpeedRun 001 - Luzhiled's memo

10完 oooooooooo-- 68位
(↑これだけ見るとすごいね)

f:id:Luzhiled:20170803172940p:plain

友人の家に泊まっていたので最後の2問は見れてなかった
(コンテスト中のコードは汚かったので一から書いています)

A - 最大値

問題

数列 $a$ の最大値を出力してください

解法

探索をすればもちろん $O(N)$ で済むのですが、めんどくさいし余裕もあるのでsortして出力した

コード

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

int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  sort(a.begin(), a.end());

  cout << a.back() << endl;
}

B - 総和

問題

タイトル通りなんですが、数列 $a$ の総和を求める問題です

解法

本番中は焦って関数名が思いつきませんでしたが、std::accumulate() があるのでこれを使うのが楽そう(多分numericに入ってる)

コード

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

int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  cout << accumulate(a.begin(), a.end(), 0) << endl;
}

↑短い(すごい)

C - カンマ区切り

問題

数列 $a$ をカンマ区切りにして一行で出力してください。

解法

僕のテンプレートに

template<typename T> inline void print(const vector<T> &v, string s = " "){ if (!v.size()) puts(""); rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : s); }

ってのがあったんですよ、不思議なこともあるんですね

print(a, ",");

でおわり！w　とかやってもよかったんですが、まあちゃんと書き直しました

コード

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

int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  for (int i = 0; i < n; ++i) {
    cout << a[i] << (i + 1 == n ? "\n" : ",");
  }
}

D - ソート

問題

ソートします。(さっきもやりましたね)
空白区切りで出力します。(さっきもやりましたね)

解法

さっきもやりましたね

コード

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

int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  sort(a.begin(), a.end());
  for (int i = 0; i < n; ++i) {
    cout << a[i] << (i + 1 == n ? "\n" : " ");
  }
}

E - 1は何番目?

問題

数列 $a$ に含まれる整数のうち、何番目の整数が $1$ であるかを出力。

解法

共通制約の $a_i \neq a_j (i \neq j)$ より、 $1$ は1つしかないことがわかる(ので楽)

コード

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

int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  for (int i = 0; i < n; ++i) {
    if (a[i] == 1) cout << i + 1 << endl;
  }
}

F - 見える数

問題

数列 $a$ に含まれる整数のうち、 $1 \leq j < i \leq N$ を満たす任意の $j$ において、 $a_j < a_i$ を満たすような $i$ がいくつあるか出力しなさい。

解法

全然わからなくてびっくりした。まず問題の言っている意味がわからなくて、転倒数を求めれば良いのかな？　みたいになってコード書いたら違うし、あ〜人生こわれるみたいな気持ちになっていたら

質問 : この問題はどういう意味ですか？？
回答 : 高さA_iのビルが横一列に並んでるとして、左から見えるビルの個数を答える問題みたいな感じです！

とあったのではいとなって終了(はい。)

解法 : 質問を見る(は？)

コード

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

int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  int max_a = 0;
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (max_a < a[i]) {
      max_a = a[i];
      ans++;
    }
  }

  cout << ans << endl;
}

G - あまり

問題

数列 $a$ を連結させた整数を、 $1,000,000,007$ で割ったあまりを求めてください。

解法

まあ素直にmodとりながら連結させていけば良いなあと言った気持ちになる

f:id:Luzhiled:20170803194631p:plain

コード

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

using lint = long long;

lint digit(int n) {
  lint res = 1;
  while (n) {
    n /= 10;
    res *= 10;
  }
  return res;
}

int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  lint ans = 0;
  lint mod = 1e9 + 7;
  for (int i = 0; i < n; ++i) {
    ans = digit(a[i]) * ans + a[i];
    ans %= mod;
  }

  cout << ans << endl;
}

H - LIS

問題

数列 $a$ から好きな数だけ整数を取り除いて単調増加な数列を作るとき、その数列の長さの最大値を求めなさい。

解法

典型問題(というか問題名がそのまま解法になっているので最悪調べれば解ける気がする)

先頭から $i$ 番目の数字を見ている時に、それ以前の数字だけで作れる最長の単調増加な数列を持っておいて、 $i$ 番目の数字をその数列の適切な位置に挿入して単調増加な数列を作る、ということを繰り返すと解ける。

適切な位置を探すのは二分探索ができるので、これは $O(NlogN)$ で解ける。

と思ったらなんか意味不明なミスして落ちた(なぜか $a$ を二分探索している)

Submission #1479947 - Chokudai SpeedRun 001

コード

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

const int inf = 1001001001;

int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  vector<int> dp(n, inf);
  for (int i = 0; i < n; ++i) {
    *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
  }

  cout << lower_bound(dp.begin(), dp.end(), inf) - dp.begin() << endl;
}

I - 和がNの区間

問題

数列 $a$ に含まれる連続した区間のうち、和が $N$ になるものがいくつ存在するか。

解法

連続した区間なのでしゃくとりしながら解けそうだなあとなる。

今見ている区間 $[l, r)$ とした時、区間の和が $N$ 未満なら $a_r$ を区間の和に足して $r$ を進める、 $N$ 以上なら区間の和から $a_l$ を引いて $l$ を進める、みたいにして考えると解ける。

これを $[0, 0)$ から始めたい気持ちになって終了。

コード

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

int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  a.push_back(0);

  int sum = 0, ans = 0;
  for (int l = 0, r = 0; r < a.size(); ++r) {
    while (sum > n) {
      sum -= a[l];
      l++;
    }
    if (sum == n) ans++;

    sum += a[r];
  }

  cout << ans << endl;
}

本番で変な実装をしてREを出してしまった

こういう問題は最初か最後がめんどくさくなりがちなので、番兵をおいて例外をなくすと楽だなあみたいな気持ちに最近なりました(ほんまですかね)

J - 転倒数

問題

数列 $a$ をバブルソートした時、スワップが何回発生するか求めなさい。

解法

1分もかからなかった(理由:さっき書いていたので)

バブルソートの実行手順とかはおいといて*1、その性質だけを考えます。

数列 $a = {3, 1, 5, 4, 2}$ はバブルソートを実行すると、
数列 $b = {1, 2, 3, 4, 5}$ になる。

一番小さな数字である $1$ に着目すると、バブルソートの実行において、 $1$ は1回swapしていることがわかる。これは、 $1$ よりも大きいかつ $1$ よりも左側にある整数の個数とみなせる。(i回目のループにおいて、数字iを左に寄せていくソートだと考えるとわかりやすい(??))

同様に、 $2$ よりも大きいかつ $2$ よりも左側にある整数の個数、 $3$ よりも大きいかつ $3$ よりも左側にある整数の個数、.....

と考えていくと、転倒数が求められることがわかる。

このままだと計算量が悪化しているだけに見えるが、BIT(fenwic tree)やセグ木を使えば、 $i$ よりも大きいかつ $i$ よりも左側にある個数が $O(logN)$ で求めることができる。( $a_i$ を見たときにBITの $a_i$ に $+1$ をしておけば、 $a_j(i < j)$ を見ている時に $a_j$ 以下の整数の個数がBITの操作でわかるので、j - ( $a_j$ 以下の整数の個数) をすると $a_j$ より左側にある $a_j$ より大きな整数の個数がわかる。)

全体として $O(NlogN)$ 。

普通の数列の場合は座標圧縮する必要もあるけど、制約上今回は必要ない。

転倒数は最大で $\frac {N \times (N - 1)} {2}$ になるのでint型の整数だとオーバーフローします。気をつけましょう。(WAのコードは4行目のlong longをintに変えただけです)*2
f:id:Luzhiled:20170803192709p:plain

コード

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

using lint = long long;

struct BIT {
  vector<int> v;
  int n;

  BIT() { init(); }
  BIT(int size) :n(size){ init(); }

  void init() {
    v.clear();
    v.resize(n + 1);
  }

  int sum(int i, int idx = 1) {
    idx--; idx *= -1; i += idx;
    int ret = 0;
    while (i) {
      ret += v[i];
      i -= i & -i;
    }
    return ret;
  }

  void add(int i, int x, int idx = 1) {
    idx--; idx *= -1; i += idx;
    while (i <= n) {
      v[i] += x;
      i += i & -i;
    }
  }
};

int main() {
  int n;
  cin >> n;

  BIT bit(n);
  lint ans = 0;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;

    ans += i - bit.sum(a);
    bit.add(a, 1);
  }

  cout << ans << endl;
}

*1:最初"おいておいて"って書いていましたがなんか変じゃないですか

*2:実は自分で計算するのが面倒だったのでオーバーフローするかどうか実験的に投げただけ