ABC - 017 - A&B&C

AtCoder ABC 017 A&B&C

AtCoder - 017

A - プロコン

	private void solveA() {
		int res = 0;
		for (int i = 0; i < 3; i++) {
			int point = nextInt();
			int ratio = nextInt();
			res += point * ratio / 10;
		}

		out.println(res);
	}

B - choku語

• 'ch''o''k''u'が入っているとchoku語にならない
  • 'ch''o''k''u'を全部空文字に置換したら入力値の長さは0になる
    • 置換ではなくて1個ずつ調べるでもいいと思うけどjavaはreplaceの方が簡単なので

	private void solveB() {
		String res = next().replaceAll("ch", "").replaceAll("o", "").replaceAll("k", "").replaceAll("u", "");

		out.println(res.length() == 0 ? "YES" : "NO");
	}

C - ハイスコア

ループ（部分点30+70/TLE)

• 問題より

  • 全種類の宝石をとってはいけない
    • 1-n種類の宝石の内、どの宝石をとらないのが一番特典が高いのか？と読み替えられる
      • どの遺跡を探検するのか？ ではなく、 どの宝石をとらないべきか？ で考える
        • ある種類の宝石をとる場合は、ほかの遺跡の同種類の宝石も全て取ったほうが良いので

• 問題を読み替えると、ある宝石をとらない場合の得点の最大値を求めるとなる

  • $宝石1をとらない場合、宝石2をとらない場合、宝石3をとらない場合・・・宝石Nをとらない場合$

• 単純にループ回すと絶対間に合わないので、累積和っぽくやってみる

• 入力例1:

4 6
1 3 30
2 3 40
3 6 25
6 6 10

• 例えば、1の宝石をとらないと決めた場合以下のようになる
  • 遺跡1には行けない
  • 遺跡2と3は行ける
  • 遺跡4は行けない
    • 1-3をとらない場合はこの点数が入らないが、4-6をとらないと決めた場合はこの点数は入る

	宝石1	宝石2	宝石3	宝石4	宝石5	宝石6
遺跡1				30	30	30
遺跡2	40			40	40	40
遺跡3	25	25
遺跡4	10	10	10	10	10
合計 (宝石をとらない場合の最大値)	75	35	10	80	80	70

• これだと、最後の1点が入らない
  • ただ、累積和の部分がいもす法で実装できそうな感じがしたので別解を試した

	private void solveC2() {
		int n = nextInt();
		int m = nextInt();

		int[] l = new int[n];
		int[] r = new int[n];
		int[] s = new int[n];
		int[][] res = new int[m + 1][1];
		for (int i = 0; i < n; i++) {
			l[i] = nextInt();
			r[i] = nextInt();
			s[i] = nextInt();
			for (int j = 1; j <= m; j++) {
				if (j < l[i] || r[i] < j) {
					res[j][0] += s[i];
				}
			}
		}

		Arrays.sort(res, (x, y) -> -Integer.compare(x[0], y[0]));
		out.println(res[0][0]);
	}

いもす法(101点解法)

• 参考サイト(いもす法および累積和)
  • いもす法
  • 競技プログラミングにおけるimos法・累積和問題まとめ
  • 累積和を何も考えずに書けるようにする！
  • ABC - 035- A&B&C

上記解法の以下の部分を修正した

			for (int j = 1; j <= m; j++) {
				if (j < l[i] || r[i] < j) {
					res[j][0] += s[i];
				}
			}

	private void solveC() {
		int n = nextInt();
		int m = nextInt();

		int[] l = new int[n];
		int[] r = new int[n];
		int[] s = new int[n];
		int[] res = new int[m];
		for (int i = 0; i < n; i++) {
			l[i] = nextInt() - 1;
			r[i] = nextInt() - 1;
			s[i] = nextInt();
			res[0] += s[i];
			res[l[i]] -= s[i];
			if (r[i] < m - 1) {
				res[r[i] + 1] += s[i];
			}
		}

		for (int i = 1; i < res.length; i++) {
			res[i] = res[i] + res[i - 1];
		}
		Arrays.sort(res);
		out.println(res[m - 1]);
	}