読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

TopCoder SRM 590 Div 1 o-- 1211->1280

競技プログラミング topcoder

367th, +0/-0 challenge
Volatility 370->362
初めてDiv 1でレートが上がったかもしれない(弱

部屋の誰も500解けてなかったんでチャレンジ成功してれば部屋で1位ぐらいの僅差だった
システムテストで250が落ちてる人が何人かいたので、チャンスはあったのになぁ

250: FoxAndChess

2つの盤面が与えられる。
1つ目から2つ目へ変形できるかどうかを答える
盤面上には左にだけ動ける駒"L"と右にだけ動ける駒"R"と空白のマス"."がある
ただし駒同士が入れ替わることはできない

  1. ".L.R.R."
  2. "L...R.R"

は変形可能

解法

まず駒の数と順番が一致しているかどうか確かめる
これは"."を抜いた文字列同士の比較をすれば一度にできて、あっていれば端から順番に駒の対応がとれていることがわかる
あとは駒の位置関係が正しいかどうかを調べれば良い

ソースコード

public class FoxAndChess {

	public String ableToMove(String begin, String target) {
		String o1 = begin.replaceAll("\\.", "");
		String o2 = target.replaceAll("\\.", "");

		if(!o1.equals(o2)) {
			return "Impossible";
		}

		int countL_begin = 0;
		int countL_target = 0;
		for(int i = begin.length() - 1; i >= 0; i--) {
			if(begin.charAt(i) == 'L') {
				countL_begin++;
			}
			if(target.charAt(i) == 'L') {
				countL_target++;
			}
			if(countL_target > countL_begin) {
				return "Impossible";
			}
		}

		int countR_begin = 0;
		int countR_target = 0;
		for(int i = 0; i < begin.length(); i++) {
			if(begin.charAt(i) == 'R') {
				countR_begin++;
			}
			if(target.charAt(i) == 'R') {
				countR_target++;
			}
			if(countR_target > countR_begin) {
				return "Impossible";
			}
		}

		return "Possible";
	}

}

500: XorCards

与えられた数字が書かれたカードのうち好きなだけを使うことができる
使ったカードのXORがある数limitよりも小さくなる組み合わせの数を答える

dp[カードの枚数][XORの種類数]しか思いつかず、XORの種類数は最悪で上限の\(10^{15}\)になることに気づいて未提出

-->