tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

SRM186 Div1 Hard

昔の問題は変な意味で面白い。

プログラミングコンテストの問題の題材としてアイスホッケーが出題されることは少なくありません.しかし,活動時間の全てをオンラインジャッジにつぎ込む生活では,アイスホッケーを想像することができず,問題の理解に困ってしまうこともあるでしょう.一分一秒を争うこの世界では,致命傷となりかねません.

当然この問題の本質は問題文読解なんだけど、まず普通の人が思い浮かべるのは、「好きな方向に打てて何回でも反射できるので最短距離を求める」みたいな感じ。しかしテストケースを見てみても問題の妥当性を考えてみてもこれはおかしいので、徐々に「反射は1回以下なのでは...?」と疑うことになる。
それでもなおうまくいかないので、魔力で反射が0回のケースは考慮してはいけないことと、問題文冒頭の The left-handed Finnish hockey player から左利き選手は右にシュートしやすそうだから右のみ反射なのでは?と考えるに至る。

実は、画像の下の段落にちょろっと反射のルールが書いてあるんだけど、実はここでは「right」としか書いてない上実はこれは反射の法則ではなく、この問題でvalidとみなされる移動の仕方である。知るか。

複数経路があるときの処理も謎でゴールの右端に近いものを採用するんだけど(角度のminではない)、これも実際ゴールを入れる人は端に打ってそうだなあと思うとなんか納得できなくもない感じになる。これらのエスパーによって同点のものがたくさん現れてどれを出力しないといけないか問題も解消できて一件落着。


冒頭みたいな逸話は笑い話のように扱われていますが、この「アイスホッケー」を「物理学」や「機械・パソコンの仕組み」に置き換えてみると、未だに背景知識がないと理解できない系の問題文を書く人がいます。専門的なストーリーにしたいときはちゃんと親切に全部問題文中に記述されているかどうかを念入りに確認しましょう。物体の落下の仕方の式やファイルのURLの表し方に説明がないなんて論外です。

// I like wolves!!
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const double EPS = 1e-13;
const double INF = 1e+10;
const double PI = acos(-1);
vector<Pt>L;
vector<Pt>R;
vector<Pt>hb;
class PuckShot {
	public:
	double caromAngle(int X0, vector <int> X, vector <int> Y) {
		int n=X.size();
		double val=INF;
		double ret=-1.0;
		hb.push_back(Pt(X0,1));
		for(int i=0;i<=1;i++){
			for(int j=0;j<n;j++){
				double tx=X[j];
				double ty=Y[j];
				if(i%2==0)tx+=3000*i;
				else{
					tx=3000-tx;
					tx+=3000*i;
				}
				L.push_back(Pt(tx-25,ty));
				R.push_back(Pt(tx+25,ty));
				hb.push_back(Pt(tx-25-(1e-10),ty));
				hb.push_back(Pt(tx+25+(1e-10),ty));
			}
			if(i==0)continue;
			Pt gl,gr;
			gl=Pt(3000*i+1408.5,1733);
			gr=Pt(3000*i+1591.5,1733);
			if(i%2)swap(gl,gr);
			hb.push_back(gl);
			hb.push_back(gr);
			for(int j=0;j<hb.size();j++){
				bool ok=true;
				for(int k=0;k<L.size();k++){
					if(iLS(Pt(X0,0),hb[j],L[k],R[k])){
						ok=false;break;
					}
				}
				if(!iLS(Pt(X0,0),hb[j],gl,gr))ok=false;
				if(ok){
					Pt p=pLL(Pt(X0,0),hb[j],gl,gr);
					double dist=(p-gr).ABS();
		//			printf("%f %f %f\n",hb[j].x,hb[j].y,dist);
					if(dist<val){
						val=dist;
						ret=(hb[j]-Pt(X0,0)).arg()*180/PI;
					}
				}
			}
		}
		return ret;
	}
};