プロコン/チャレンジ のバックアップ(No.5)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• プロコン/チャレンジ へ行く。
  • 1 (2016-08-22 (月) 05:01:14)
  • 2 (2016-08-22 (月) 05:01:47)
  • 3 (2016-08-24 (水) 09:51:14)
  • 4 (2017-01-16 (月) 20:14:39)
  • 5 (2017-03-22 (水) 21:50:41)

プロコン

概要 †

• コード読みましょう
• チャレンジ記録

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

類型化 †

問題特有 †

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

strlen †

• O(n)です