名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

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

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したので,深さ有線のほうがいいのかなあと思った.うーん.