TooCoder:SRM513

SRM513に参戦してきました。
最近ブログに報告はしてませんでしたがちょくちょく参加してました。かなーり調子悪いです。

あ、あと今回からこの報告もプログラミングカテゴリにしますね。

とりあえず今回の戦績。

Easy:93.65pt
Medium:Opened
Hard:Unopened

Challenge:No Challenge

Rating:1279 -> 1236

正直、Easyはもっと早く解けました。
それぞれの板の可能な配置の積が解なので、

（１）ans=1とする。
（２）platformMount[i]が、どのボールの落下点間にあるかを調べる
（３）板の可動範囲を計算する
（４）（可動範囲＋１）をansにかけて1000000009とのmodをとる。

という方針が割と早く浮かんだのですが、（２）でどの区間にplatformMount[i]があるか調べるところで
ballsをソートし忘れていて、しかもいつまでもそのバグが取れずorz
極めて残念な結果になりました。

コード自体は割とすっきりかけたと思うので晒しときます。
コメントはあとで付け加えました。

#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
using namespace std;
class YetAnotherIncredibleMachine {
public:
    int countWays(vector <int> platformMount, vector <int> platformLength, vector <int> balls) {
	int N = platformLength.size();
	int B = balls.size();
	int section;
	int leftmost,rightmost;
	unsigned long long int ans=1;

	sort(balls.begin(),balls.end());   //これを忘れてた＼(^o^)／

	for(int i=0;i<N;i++){
	    section = 0;
	    // platformMount[i]を含む落下地点間を調べる。
	    for(int j=0;j<B;j++){
		if(balls[j]<=platformMount[i]){
		    section = j+1;
		}
		if(balls[j]==platformMount[i])ans=0;
	    }

	    // 板の左端の可動領域の左端を求める
	    if(section>0)leftmost = max(balls[section-1]+1,platformMount[i]-platformLength[i]);
	    else leftmost = platformMount[i]-platformLength[i];
	    // 板の左端の可動領域の右端を求める
	    if(section<B)rightmost = min(balls[section]-platformLength[i]-1,platformMount[i]);
	    else rightmost = platformMount[i];
	    
	    //（可動領域＋１）をansにかけてmodをとる
	    // 可動領域が負の値なら、そもそもボールに当たらないような板の配置など一つもないので、答えは０とする。
	    if(leftmost<=rightmost){
		ans *= (rightmost-leftmost+1);
		ans %= (unsigned long long int)1000000009;
	    }else{
		ans = 0;
	    }
	}
	return ans;
    }

せっかく早く思いつけても動かなければアウトなわけで。
結局かなり悩んだ挙句に左端と右端の値を出力してみてようやく気づけました。

今回の教訓としては、変数の値は出力できるならとりあえず見てみて、プログラムの挙動を細かくチェックすべきだということですかね。

cout<<"value="<<value<<endl;

のようなprintデバッグは大事に。

マクロで

#define printval(X) cout<<#X " = "<<X<<endl

とでもしておけば「printval(var)」で一発なので便利かもですね。

この夏はもっとプロコンがんばろうと思います。それでは（・ω・）ﾉｼ