ABC 023 D - 射撃王

D - 射撃王

考えたこと

二分探索問題だということは分かっていた。だが、どこを二分探索すればいいのか全く分からなかった。

理解後の感想

参考にさせて頂いたサイト
AtCoder Beginner Contest 023 D - 射撃王 の話

高度を探索するといった発想はなかった。
変数をある程度書き出し、その変数のどれを基準にすれば探索回数が一番小さくなるかをよく考えるべきだと思った。

ABC 84 C - Snuke Festival 二分探索

C - Snuke Festival

考えたこと

Aの要素を基準にしてBのlower_bound()を求め、またBを基準にしてCのlower_boundを求めるといった2重ループで求めようとした。当然TLE

気付いたこと

これ真ん中のBを基準にすれば、AとCは2重ループにしなくても直接アクセスできるので、一回のループで求めることができる。
この考え方は大事

ABC102 D - Equal Cut

D - Equal Cut

問題概要

長さ N の整数列 A を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を P,Q,R,S とするとき、max(P,Q,R,S)−min(P,Q,R,S) の最小値を求めよ。
4≤N≤2×10の5乗

考えたこと

切れ目をそれぞれ入れていって、だんだんと最適解に近づかせるやり方で解こうとした。ちょっとACがあったので回答方針はあっていたように思える。難しい。

WAコード

Submission #20189571 - AtCoder Beginner Contest 102

今回は理解が難しいため書かない。尺取り法を使うらしい。しらんけど

ABC102 C - Linear Approximation

C - Linear Approximation

問題概要

長さ N の整数列 A1,…,AN が与えられます。整数 b をいろいろ変えたときの

A1−(b+1)

+

A2−(b+1)

+⋯+

AN−(b+N)

の最小値を求めてください。

1≤N≤2×10の5乗

考えたこと

2次関数みたいなグラフになってると予想した。どっちかに動かせばどんどん小さくなるので、それを判定して出そうと思った。
途中で意味が分からなくなってあきらめた。

WAコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
int N;
 
int kaese(vector<int>A, int num) {
	int count = 0;
	int i = 0;
	while (1) {
		if (i == N) {
			break;
		}
		count += abs(A[i] - (num + i + 1));
		i++;
	}
	return count;
}
 
 
int main() {
 
	cin >> N;
	vector<int>A(N);
 
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
 
 
 
	//どっち向きに動かすか決める
	bool canr = false; bool canl = false;
	int base = kaese(A, 0);
	if (base == kaese(A, 1)) {
		cout << base;
	}
	if (base < kaese(A, 1)) {
		canl = true;
	}
	if (base < kaese(A, -1)) {
		canr = true;
	}
	if (canl && canr) {
		cout << base;
	}
 
	if (canl) {
		int i = -2;
		int back = kaese(A, -1);
		while (1) {
			int j = kaese(A, i);
			if (back < j) {
				cout << back;
				return 0;
			}
			back = kaese(A, i);
			i--;
		}
	}
	if (canr) {
		int i = 2;
		int back = kaese(A, 1);
		while (1) {
			int j = kaese(A, i);
			if (back < j) {
				cout << back;
				return 0;
			}
			back = kaese(A, i);
			i++;
		}
	}
}

参考

参考にさせて頂いたサイト
AtCoder ABC 102 C - Linear Approximation (ARC 100 C) (緑色, 300 点) - けんちょんの競プロ精進記録

まず、この [A-(b+1)]を変形して、分かりやすくすべき。
＝＞[x-Bi](Bi = Ai - i)
すると、|x−B1|+|x−B2|+⋯+|x−BN| となる

これはメディアンと呼ばれるもので、この形が出てきたら簡単に解けるらしい。

メディアンとは

中央値のこと。つまり、配列をsortし、その中央に出てきた値が、今回の答えだということ。

ACコード(けんちょんさん)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i], B[i] = A[i] - i;

    // メディアンを
    sort(B.begin(), B.end());
    long long x = B[N/2];

    // 答えを求める
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        res += max(x - B[i], -x + B[i]); // |A| = max(A, -A)
    }
    cout << res << endl;
}

ABC 101 D Snuke Numbers

D - Snuke Numbers

問題概要

正整数nに対して、nを10進法表記したときの各桁の和をS(n)とし、関数gをg(n)=nS(n)と定義する。

そして任意の正整数m>nに対してg(n)≤g(m)が成立するようなnを「すぬけ数」と呼ぶことにする。

このとき、すぬけ数を小さい方から順にK個出力せよ。

K≥1
K番目のすぬけ数は10の15乗以下である。

感想

19,29,39...199,299..みたいに右側が99..となる集合なのかなと思った。その通りに実装したら..なんとTLE。実力不足。
また、右側が99..となる集合でもないらしい。難しい..

WAコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;


int diget(int num) {

	string str = to_string(num);
	int num1 = str.length();
	if (num1 == 1) return true;

	for (int i = 1; i < num1; i++) {
		if (str[i] - '0' != 9) {
			return false;
		}
	}

	return true;
}

int main() {

	int K = 0; cin >> K;

	int count = 0;
	int i = 1;
	while (1) {

		bool can1 = diget(i);

		if (can1) {
			cout << i << endl;
			count++;
		}

		if (count == K) {
			break;
		}
		i++;
	}
}

解説を見る

参考にさせて頂いたサイト
ARC099(ABC101) 解説 - Mister雑記

理解した後の感想

まずこのすぬけ数、プログラムで扱えるものではないらしい。n<10の15乗という条件があって初めて求められるものとなる。
すべてアルゴリズムでゴリ押すのではなく、この時はどうだろう..と検証していくことがこの問題の肝であると考える。

んー..これは流石に実力不足が過ぎるのでこの問題はスルーするのがよさそう

ABC 100 D Snuke Numbers

D - Patisserie ABC

問題概要

整数 3 つ組 (xi, yi, zi) が N 個与えられる。
このうちの M 個選んで、

(x の選んだ M 個の総和の絶対値) + (y の選んだ M 個の総和の絶対値) + (z の選んだ M 個の総和の絶対値)

が最大になるようにせよ。

制約

1 <= N <= 1000

• 10の10乗 <= xi, yi, zi <= 10の10乗

感想

まずはnext_permutationで回し、最初のM個を取る楽なやり方ができないかと考えたが、条件からしてどう考えても無理。
次に再帰関数を使って解くことを考えたが、それもTLEで上手く行かない。分かんない；；

WAコード

using namespace std;
 
long long N;
long long M;
 
long long saiki(vector<vector <long long>> a, vector<long long> A) {
 
	if (A.size() == M) {
		long long mcount = 0;
		for (long long i = 0; i < 3; i++) {
			long long count = 0;
			for (long long j : A) {
				count += a[j - 1][i];
			}
			mcount += abs(count);
		}
		return mcount;
	}
	long long max = 0;
	long long prev_last = (A.empty() ? 1 : A.back());
 
	for (long long i = prev_last; i < M + 1; i++) {
		A.push_back(i);
		long long num = saiki(a, A);
		if (max < num) {
			max = num;
		}
		A.pop_back();
	}
 
	return max;
}
 
 
 
int main() {
 
 
	cin >> N;
	cin >> M;
 
	vector<vector <long long>> a(N, vector<long long>(M));
 
	for (long long i = 0; i < N; i++) {
		for (long long j = 0; j < M; j++) {
			cin >> a[i][j];
		}
	}
 
	vector<long long>A;
	
	cout << saiki(a, A) ;
 
}

参考にさせていただいたサイト

AtCoder ABC 100 D - Patisserie ABC (水色, 400 点) - けんちょんの競プロ精進記録

感想

とても難しい。分かる気がしない。
つまり、例えば次のような入力があったとする。

  1    -2      3
 -4     5     -6
  7    -8     -9
-10    11    -12
 13    -14    15

この時、一列目(1,14,7,-10,13)を＋と決め打ちする。
　　　　二列目(-2,5,-8.11,14)をーと決め打ちする。
　　　　三列目(3,-6,-9,-12,15)を＋と決め打ちする。

すると、一列目[i]＋二列目[i]＋三列目[i]のそれぞれの合計は、(6,-15,6,-33,42)となる。sortして、(-33,-15,6,6,42)と並び変えて、その中で大きい数M個(今回は3個)を選択=>(6,6,42)
それを合計して、答えが54..となる。

決め打ちする通りは2の3乗で8通り。bit全探索を使って解く。

ABC 100 B Ringo’s Favorite Numbers

問題リンク

B - Ringo's Favorite Numbers

間違えたコード

using namespace std;
 
int main() {
 
	int D; cin >> D;
	int N; cin >> N;
 
	if (N == 100) {
		cout << 100;
		return 0;
	}
 
	if (D == 0) {
		cout << N;
		return 0;
	}
	if (D == 1) {
		cout << N * 100;
		return 0;
	}
	if (D == 2) {
		cout << N * 10000;
		return 0;
	}
}

感想

3つWAだった。原因は分からん。

.正解コード確認

参考にさせていただいたサイト
ABC100 B Ringo's Favorite Numbers - 迷走

確認後の感想

なるほど..もし、n=100の時はD+1回割れてしまうので、[...97,98,99,101]と、100を飛ばすのか。
整数問題に対する知識が必要だな..。
こういった問題に対するアプローチとして、小賢しいやり方で解くのではなく、単に全探索をした方が正答率が高くなりそうだな。

ACコード

int d, n;
 
int main() {
    cin >> d >> n;
    if (n == 100)n++;
    if (d == 0) {
        cout << n << endl;
    }
    if (d == 1) {
        cout << 100 * n << endl;
    }
    if (d == 2) {
        cout << 10000 * n << endl;
    }
}