読者です 読者をやめる 読者になる 読者になる

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

Codeforces Round #321 (Div. 2)に参加しました

CodeForces Python C++ 競技プログラミング

1完(実はB問題は解けていた)だったので,ほんとにクソ.
B問題は問題の読み違い含め,9WAとかいうクソみたいなことをした.点数は解けた.そしてシステムテストでTLE.救いようがない()

f:id:kawasumi_yume:20150923150814p:plain

A問題

問題

Problem - A - Codeforces


回答

Submission #13145959 - Codeforces

連続して増加し続けている最大区間を求めましょう〜 みたいな問題.なんか似たような問題をAtcoderでみたことがあったような気がしないでもない.
これか? ↓
B: 解像度が低い。 - AtCoder Regular Contest 017 | AtCoder

前からひたすら見ていくだけでOKです.

n = int(input())
al = list(map(int, input().split()))
res, t = 0, 0
last = -1
for i in al:
    if i >= last:
        t += 1
    else:
        res = max(t, res)
        t = 1
    last = i
print(max(t, res))

B問題

問題

Problem - B - Codeforces

回答
C++
Submission #13171082 - Codeforces
Python3
Submission #13173350 - Codeforces

なんか最初ものすごい無駄な計算をしていたためにTLEしていた.しかも最初の方は問題文を読み違えており,失敗した.
結局,回答としては,2次元配列に格納して,第一要素で降順ソート,そしてひたすら差がd以下になるように足しあわせる.d以上になったら,インデックスをずらして,配列の範囲をずらす… という回答法方針でした.
書き直した方はそこそこの速度で捌けてたけど,もう少し良い回答があるかもしれない.


C++

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(16);

  int n, d;
  cin >> n >> d;

  vector< vector<int> > A(n);
  REP(i, n) {
      std::vector<int> B(2);
      cin >> B[0] >> B[1];
      A[i] = B;
  }
  sort(A.begin(), A.end());

  ll res = A[0][1];
  int idx = 0;
  ll t = A[0][1];
  FOR(i, 1, n) {
      if(A[i][0] - A[idx][0] < d) {
          t += A[i][1];
      } else {
          while(A[i][0] - A[idx][0] >= d) {
              t -= A[idx][1];
              idx++;
          }
          t += A[i][1];
      }
      res = max(res, t);
  }

  cout << max(res, t) << endl;
  return 0;
}

Python3

n, d = map(int, input().split())
al = [list(map(int, input().split())) for _ in range(n)]
al.sort()
res = al[0][1]
t = al[0][1]
idx = 0
for i in range(1, n):
    if al[i][0] - al[idx][0] < d:
        t += al[i][1]
    else:
        while al[i][0] - al[idx][0] >= d:
              t -= al[idx][1]
              idx += 1
        t += al[i][1]
    res = max(res, t);
print(res)

あと,pypyのほうが早いよってアドバイスを頂いたのだが,なぜかこのソースコードの場合,処理速度が1.5倍かかっており,本当にpypy早いの? っていう疑問が残った.
pypyの仕組みを少し頭に入れてみたが,決定的にこの処理の場合に処理速度が遅くなる,という原因がわからなかった.
なんででしょうね? 2次元配列とか標準入出力が原因なのかな?
あと,pypyを使うと,メモリかなり食うので,入力数が多い場合は使用を避けたほうがいい.(yukicoderでいろいろ試してみたら,ある問題でMLEで落ちた)

というメモ.早くなりそうなシーンがあれば使ってみるのも手かもしれない.でも今のところはいいかなあ….


C問題ですが,幅優先で組んだら,TLEしたので,深さ有線のほうがいいのかなあと思った.うーん.