Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-12-01SRM489 Div1

SRM489 Div1 300 BallsConverter

| 21:51 | SRM489 Div1 300 BallsConverter - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM489 Div1 300 BallsConverter - SRM diary(Sigmar) SRM489 Div1 300 BallsConverter - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

→(サンプル0まで読む)

うーん・・・難しい・・・

→(10分くらいひとしきり悩む)

もう少しサンプル見てみるか

→(サンプル1を見る)

えーとつまり、1と1を先に適用して、その結果と0を適用する場合と、0と1を先に適用して、その結果と1を適用する場合で結果が異なるのでBadになるのか

あれ・・なんかどこかで聞いたことあるような何かだな・・

2個のボールから1個のボールを作り出す操作を'#'という演算に置き換えると、(1#1)#0=1、1#(1#0)=0となる

つまり、結合法則が成り立たない演算になるということか

これはもしかすると、任意の3つのオペランドの演算において結合法則が成り立つ場合のみGoodになるのだろうか

えーと・・可換なので・・いくらでも演算の順番を入れ替えることができるから・・結合法則が成り立てばGoodになる!

逆に1つでも結合法則がなりたたない3個の組み合わせがあれば、サンプル1と同様にBadになるのが明らかだ

あとは書くだけか

→書いた

→サンプル通った

→提出


チャレンジフェーズ

突込みどころなし。何もせず


システムテスト

Passed


ソースコード

何となく念のためでi,j,kの組に対して(i,j),k、i,(j,k)、(i,k),jの三つを計算しておいたが、最初の2つのみでも十分

class BallsConverter {
public:
	int calcid(char c) {
		if(isupper(c)) return c-'A';
		else return c-'a'+26;
	}

	string theGood(vector <string> conv) {
		int n=conv.size();

		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				for(int k=0; k<n; k++) {
					int a=calcid(conv[calcid(conv[i][j])][k]);
					int b=calcid(conv[calcid(conv[i][k])][j]);
					int c=calcid(conv[calcid(conv[j][k])][i]);
					if(a!=b || b!=c || c!=a) return "Bad";
				}
			}
		}

		return "Good";
	}
};

SRM489 Div1 500 DiceRotation

| 21:51 | SRM489 Div1 500 DiceRotation - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM489 Div1 500 DiceRotation - SRM diary(Sigmar) SRM489 Div1 500 DiceRotation - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何かややこしそう・・

と思ったけど、よく考えたらあんまりパターンがないな

  1. 最初に右に進むと、いくら上に進んでも1が右を向いた状態で、もう1つ右に進むと1が底に向く
  2. 最初に上に進むと、いくら右に進んでも1が上を向いた状態で、もう1つ上に進むと1が底に向く

つまり、1か2の操作をすることで1の目の向きを反転でき、この操作どちらかを2回実施する以外の操作が存在しない

何か適当にgoalxとgoalyで場合分けしたら解けそうなんだけど・・大分怪しげな解になりそうな気もする・・

うーん・・とりあえずちょっと試してみようかな

→むー・・難しい・・→(15分くらい考える)

何かやっぱり難しい?1の目が底を向く位置で場合分けとか・・・できないな・・

→元のやり方で続ける

→あれ・・気づいたら残り5分しかないけど全然できてない

→やばい。。時間があると思って油断しすぎた

→ああーーー分からんーーーやばあああーーー

→良くわからない状態で提出

終わったか・・・


チャレンジフェーズ

4,4の場合とか12になると思うんだけど何となくミスってる人がいそうな気がする

→一人目を開いてるうちに自分含め間違っている人が全員撃墜される

→終わったか・・・

→あれ、これ間違ってる?

→失敗

→コード見間違ってた。。もうダメすぎ・・


後で

冷静になって考えたらすごく簡単だった

そもそも操作1と2しかないので、まず1->2、2->1、1->1、2->2の4通りしか操作方法がないので、それぞれの操作方法で何通りあるか考える

  • 操作1は右に2つ進む間に0以上の任意の数だけ上に進むことができる
  • 操作2は上に2つ進む間に0以上の任意の数だけ右に進むことができる

このことから、1->2と2->1のパターンは、右に進む数と上に進む数を調整する機会はそれぞれ1回しかないので、1通りしか経路がないことが分かる

また、1->1のパターンは右に4つ固定で進み、上に進む数を調整する機会は2回あるので、底面が1になる位置を選ぶパターンがgoaly+1通りある。

同様に2->2のパターンはgoalx+1通りある。

更に、これらの4通りの操作が同じ操作を含むことは、最初もしくは1の目が底面にあるときに別方向に進むことからあり得ない

というわけで単純にこれらを足し合わせれば良い

それぞれの操作が可能かどうかは、すぐに判定できる

1->2と2->1のパターンはそれぞれ上と右に固定で2進む操作があり、さらに追加で右と上に任意の数進めるため、goalx>=2&&goaly>=2のときのみ操作が可能

1->1のパターンは右に4つ固定で進み、上には任意の数進めるため、goalx==4のときのみ操作が可能

2->2のパターンは同様にgoaly==4のときのみ操作が可能

ということで、goalx、goalyで場合分けするのではなく、操作方法で場合分けするように考え方を変えれば非常に簡単でした・・・


そもそもやはり考え方が1方向に深く掘り下げすぎている気がする。解法が難しくなりそうだと思ったら早めに見切りをつけて、別の解法を模索するように考えないといけない。中途半端に解けそうなやつが一番危ない気がする。むしろそういうときは大概解けないというのが実情かもしれない。このことは良く意識しておかないと本当によく嵌る。。。


ソースコード

以下上記の考え方をソースにしたものです。

まさかこんなに短く・・・5行で書けるとは・・・という感じですが。

class DiceRotation {
public:
	int theCount(int gx, int gy) {
		int res=0;

		if(gx>=2 && gy>=2) res+=2;
		if(gx==4) res+=gy+1;
		if(gy==4) res+=gx+1;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101201