プロコン
概要 †
Topcoder 0点の場合は慎重に †
- topcoderでは負の点数になるとチャレンジできなくなる!!なので、初めのチャレンジは非常に慎重に!!
やってはいけないこと †
- 焦る
- 10分以上残っていないならチャレンジするべきではない
- 小さな配列外参照にチャレンジする
- REするかどうかは運ゲーなので、よほどでない限り(nとmを逆にしてるとか、侵害領域が10000個あるとか)はスルーする
- 特にCodeforcesでは配列外参照が意味不明な挙動を示すので、本当にチャレンジしたい場合は写経&System Invocationが必要
配列外参照 †
- 配列外参照は、ローカルでは6000個くらい侵害すると落ちる
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
int main(void) {
cin.tie(0); ios::sync_with_stdio(false);
int a[1] = {};
rep(s, 10000) {
if (s % 100== 0) cout << s << endl;
int sum = 0;
rep(i, s) {
sum += a[i];
}
}
return 0;
}
Codeforces †
- 配列外参照に関して、コンパイラがおかしい!
- 具体的には、for文内部では添字がクリップされ、直指定するとmapみたいな挙動を示す。
- for文で
- a[m(>=size)] = k;は、a[size-1] = k;となる
- int k = a[m(>=size)]は、k = a[size-1]となる
- 添字直指定で
- a[m(>=size)] = k;は、本当にa[m]にkが代入される
- int k = a[m(>=size)]は、本当にk = a[m]となる
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
int main(void) {
int a[1]; a[0] = 1; a[1] = 2;
cout << a[0] << " " << a[1] << " " << a[2] << endl;
rep(i, 3) cout << a[i] << " "; cout << endl;
cout << a[0] << " " << a[1] << " " << a[2] << endl;
return 0;
}
1 2 0
1 1 1
1 2 0
#include <iostream>
using namespace std;
int main(void) {
int a[1]; long long n=1e18;
a[n]=10;
cout<<a[n]<<endl; //10!!?
return 0;
}
基本 †
- まず自分の答えから分岐を列挙する(1, 2, 2^n, それ以外、など)
- これらに対して正しい答えを出せそうかを別個考える
- 例: Codeforces 368 D2C
- 最大ケースは問答無用で用意しておく
- 想定誤解法があるなら実装してしまう
- 例: SRM 694 D1E, 貪欲はいかにも思いつきそうだが間違いなど
- みんな提出してるけど、そんなに簡単なわけがない
- この場合、チャレンジ祭りになる
- 例: SRM 697 D1E,
- 出力がYES, NOである
- YES, NOの境界を何個か列挙しておく
- 例: SRM 697 D1E
類型化 †
問題の性質 | 想定される間違い | 備考 |
入力が1e9まで | INFを1e9にして死亡 | |
入力が1e18まで | INFを1e18にして死亡 | |
静的配列を使っている | 確保してる空間が足りない | |
全探索 | 1e9個とか無理 | |
答えが再帰 | 再帰が深すぎるとMLE | どれくらいならOK? |
__builtin_popcountを使っているが32bit以上が入力される | __builtin_popcountllじゃないとだめ | |
問題文の制約を満たしていない | 正のものを一例挙げよ、と言われているのに負も出そう | |
問題特有 †
- 変数の表を紙に書いて動作をシミュレートする
- 写経する