プロコン

概要

Topcoder 0点の場合は慎重に

  • topcoderでは負の点数になるとチャレンジできなくなる!!なので、初めのチャレンジは非常に慎重に!!

やってはいけないこと

  • 焦る
    • 10分以上残っていないならチャレンジするべきではない
  • 小さな配列外参照にチャレンジする
    • REするかどうかは運ゲーなので、よほどでない限り(nとmを逆にしてるとか、侵害領域が10000個あるとか)はスルーする
    • 特にCodeforcesでは配列外参照が意味不明な挙動を示すので、本当にチャレンジしたい場合は写経&System Invocationが必要

配列外参照

  • 配列外参照は、ローカルでは6000個くらい侵害すると落ちる
    • long longだと3000個
#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じゃないとだめ
問題文の制約を満たしていない正のものを一例挙げよ、と言われているのに負も出そう

問題特有

  • 変数の表を紙に書いて動作をシミュレートする
  • 写経する
    • OCRが使えると本当はいいのだけど

トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS