いろはちゃんコンテスト Day2 - A-Cまで

いろはちゃんコンテスト Day2

とりあえず、解けたところまで。。。
終了後は、解けた問題の考察があっていたかの確認
解けなかった問題をeditorialを読んで考察。。。しても理解不能。。。考察力を磨くとは（ry

もう少しレベルアップしたら残りの問題をやりに戻ってくる予定

A問題

• やっててよかったEducational DP Contest
• $LCS+1$の長さが [真・$p$字決まり]
  • LCS解説は
    • id:nitoyon さん作成のslideshare資料
    • 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
    • 北陸先端科学技術大学院大学の講義資料？
    • プログラミングコンテストチャレンジブック(P.56-P.57)

	private void solveA() {
		String s1 = next();
		String s2 = next();
		if (s1.isEmpty() || s2.isEmpty()) {
			out.println(0);
			return;
		}
		int l1 = s1.length();
		int l2 = s2.length();

		int[][] dp = new int[l1 + 1][l2 + 1];

		for (int i = 1; i <= s1.length(); i++) {
			for (int j = 1; j <= s2.length(); j++) {
				if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Integer.max(dp[i][j - 1], dp[i - 1][j]);
				}
			}
		}

		out.println(dp[l1][l2] + 1);

	}

B問題

　-　ベクトルの外積って、記憶にないわーー。ということでこの問題は解けませんでした。。。
-　各種場合分けに失敗したので解くのあきらめてCに移りました。

• 参考
  • 問題解説
  • 数学大好き　さんのサイト

	/**
	 * ベクトルの外積
	 * 外積の向き
	 */
	private void solveB() {
		int x = nextInt();
		int y = nextInt();
		int a = nextInt();
		int b = nextInt();

		int[] s = IntStream.range(0, 2).map(i -> nextInt()).toArray();
		int[] t = IntStream.range(0, 2).map(i -> nextInt()).toArray();

		boolean vect1 = s[0] * (b - a) - (s[1] - a) * x > 0;
		boolean vect2 = t[0] * (b - a) - (t[1] - a) * x > 0;

		out.println(vect1 == vect2 ? "No" : "Yes");
	}

C問題

• 座標圧縮だよねこれ

	private void solveC() {
		int numN = nextInt();
		int[] wk = new int[numN];
		Set<Integer> wkL = new TreeSet<Integer>();
		for (int i = 0; i < wk.length; i++) {
			wk[i] = nextInt();
			wkL.add(wk[i]);
		}

		List<Integer> tmp = new ArrayList<Integer>();
		tmp.addAll(wkL);
		Collections.sort(tmp);

		for (int i = 0; i < wk.length; i++) {
			int position = Collections.binarySearch(tmp, wk[i]);
			position = position >= 0 ? position : ~position;
			out.println(position + 1);
		}
	}