1完(実はB問題は解けていた)だったので,ほんとにクソ.
B問題は問題の読み違い含め,9WAとかいうクソみたいなことをした.点数は解けた.そしてシステムテストでTLE.救いようがない()
A問題
問題
回答
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問題
問題
回答
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したので,深さ有線のほうがいいのかなあと思った.うーん.