ABC 145 C - Average Length 順列全探索

C - Average Length

問題概要

平面上でN個の座標が与えられる。全ての点を１回ずつ通るような動き方はN!通りあるが、これらの総移動距離の平均を求めよ。

制約

2 ≤ N ≤ 8
−1000≤xi≤1000
−1000≤yi≤1000
( xi , yi ) ≠ ( xj , yj )

考えたこと

順列全探索の問題だということは分かっていた。next_permutationを使うことを視野に入れると、1~Nまでの順の配列を作って回すのが一番楽だと考えた。
今回の問題は特に苦労しなかった。

こーど

int N;

int main() {
	cin >> N;

	vector<int>DataN(N);
	for (int i = 0; i < N; i++) DataN[i] = i;

	vector<vector<int>> Machi(N, vector<int>(2));
	for (int i = 0; i < N; i++) {
		cin >> Machi[i][0];
		cin >> Machi[i][1];
	}

	double count = 0;
	double j = 0;
	do {
		for (int i = 0; i < N - 1; i++) {

			int numx = Machi[DataN[i]][0] - Machi[DataN[i + 1]][0];
			int numy = Machi[DataN[i]][1] - Machi[DataN[i + 1]][1];

			count += sqrt(pow(numx, 2) + pow(numy, 2));
		}
		j++;
	} while (next_permutation(DataN.begin(), DataN.end()));

	cout << fixed << setprecision(10) << count / j;
}

パナソニックプログラミングコンテスト2020 D - String Equivalence

D - String Equivalence

問題概要

abcacなどの標準形を探す問題

制約

1<=N<=10
入力はすべて整数

考えたこと

再帰関数問題だということは分かっていた。まず文字コードで書く場合を考えたが、それよりも楽で簡単な方法があることに気が付いた。
それが//cout << ("b" - "a"); => 4である。これは、(c - a, d - a, e - a)とすると{4,8,12...}と続いていくため、４で割ってあげてindexにすればよい。
だが、途中でエラーが起きた。原因はchar型によるミス。char 型だと{1,2,3..}と続くらしい（//cout << ('b' - 'a'); => 1）めんどくさい。そこを直した。

また、

//文字列は必ずaから始まる
//文字列のz向きのつながりは2つ以上飛ばしにはならない。(ac..)はあり得ない。
//(a,b,c,d..)と来た時、5つ目にはa,b,c,d,eのいずれかが入れる。for使おう。
//(a,b,a,c)も成立する。forで(a,b,a)の中からbを抜き出し、cを入れる

等の条件を絞り出していった。
３つ目までは簡単にできていたが4つ目は少し苦戦した。これは気付かない。

こーど

int N;
vector<string>ABC = { "a","b","c","d","e","f","g","h","i","j" };
vector<string>Data;

void dfs(string W) {

	if (W.size() == N) {
		Data.push_back(W);
		return;
	}

	//<a,b,c,d..>と来た時、5つ目にはa,b,c,d,eのいずれかが入れる。
	//<a,b,a,c>も成立する。forで<a,b,a>の中からbを抜き出し、cを入れる
	int i_end = 0;
	for (char str : W) {
		if (str - 'a' > i_end) {
			i_end = str - 'a';
		}
	}

	for (int i = 0; i < i_end + 2; i++) {
		W += ABC[i];
		dfs(W);
		W.pop_back();
	}

}

int main() {

	cin >> N;//1<<N<<10
	string W = "a";
	dfs(W);

	for (string str : Data) {
		cout << str << endl;
	}
}

//文字列は必ずaから始まる
//文字列のz向きのつながりは2つ以上飛ばしにはならない。<ac..>はあり得ない。
//<a,b,c,d..>と来た時、5つ目にはa,b,c,d,eのいずれかが入れる。for使おう。
//<a,b,a,c>も成立する。forで<a,b,a>の中からbを抜き出し、cを入れる

//str = "" に += a,b..をしていく。
//97	0x61	a
//98	0x62	b
//99	0x63	c
//100	0x64	d
//101	0x65	e
//102	0x66	f
//103	0x67	g
//104	0x68	h
//105	0x69	i
//106	0x6a	j
//107	0x6b	k

//cout << ("d" - "a") / 4;//これでindexが得られる。

//cout << ("b" - "a"); => 4
//cout << ('b' - 'a'); => 1

楽しかった。ほかの人のコードを見る必要がないと判断したため載せない。

CPSCO2019 Session1 C - Coins

未解決

https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_c

問題概要

1, 10, 100, ..., 109, 5, 50, 500, ..., 5 * 109円硬貨がある
スーパーでN種類の果物が1つずつ、それぞれA0,A1, ..., An-1円で売られている

N種類の果物のうち、K個買う時の合計金額をちょうど支払うために必要な硬貨の枚数の最小値を求めよ
ただし、硬貨の数は限りなく多いとする

制約

1 ≤ N ≤ 32
1 ≤ K ≤ min(N,6)
1 ≤ Ai ≤10^8
入力はすべて整数

考えたこと

再帰関数問題だということはあらかじめわかっていた状態でのスタート。再帰関数に渡したデータは４つで、果物の値段の情報、合計金額の情報、もう一度同じものを選ばないようにするための処理、何回選んだかのカウント。正直あってると思っていた。超ごり押しだけど。結果は2WA,14TLE。処理が重すぎたのだろうか？分からない。

こーど

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

int N;
int K;
vector<int> mendoi;

int kaunnto(int sum) {
	string str10 = "1000000000";
	string str50 = "5000000000";

	int count = 0;
	bool can50 = true;

	while (1) {


		if (can50) {
			unsigned long long num = stoull(str50);
			if (sum / num != 0) {
				count++;
				sum %= num;
			}
			str50.pop_back();


			can50 = false;
		}
		else {
			unsigned long long num = stoull(str10);
			if (sum / num != 0) {
				count += sum / num;
				sum %= num;
			}
			if (str10 == "1") {
				return count;
			}
			str10.pop_back();

			can50 = true;
		}

	}
}

void coin(vector<int> A, int sum, int kaisuu, vector<int> erabu) {

	if (kaisuu == K) {
		int count = 0;

		count = kaunnto(sum);

		mendoi.push_back(count);
		return;
	}

	for (int i : erabu) {
		sum += A[i];
		auto it = find(erabu.begin(), erabu.end(), i);
		erabu.erase(it);
		kaisuu++;
		coin(A, sum, kaisuu, erabu);
		kaisuu--;
		erabu.push_back(i);
		sum -= A[i];
	}
}

int main() {

	cin >> N;
	cin >> K;

	vector<int> erabu;
	vector<int> A(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> A[i];//変更可能性なし参照データ
		erabu.push_back(i);
	}


	int sum = 0;
	int kaisuu = 0;
	coin(A, sum, kaisuu, erabu);

	sort(mendoi.begin(), mendoi.end());
	cout << mendoi[0];

}

ほかの人のこーどをみてみた。

参考にしたサイト>なかった..
終わり。

AtCoder ABC 161 D - Lunlun Number 再帰関数 正解問題 long long

問題概要

1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。

K 番目に小さいルンルン数を求めよ。

制約

1≤K≤10^5

考えたこと

これはよくある再帰関数問題か..整数操作じゃなくて配列に整数を入れて後から文字列変換でどうにかなりそうだな。
0の時、9の時だけ注意してそれぞれ呼び出してあげれば完璧になりそうだな。
あれ？最後のほうの問題だけWAだ。あ、seisuu()の関数の戻り値がint型になってる！。これは怖いなー。注意ししないといけない。unsigned long long型に直して..　よし！ＡＣ！

こーど

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

long long X;
vector<long long> AllData;

unsigned long long seisuu(vector<long long> Data) {
	string Data_str = "";

	for (int num : Data) {
		Data_str += to_string(num);
	}
	unsigned long long Data_num = stoull(Data_str);
	return Data_num;
}

void lunlun(vector<long long> &Data) {//初期条件(1~9)

	//配列を整数に変換して、それが10~5以下のものなのかを判定する
	//整数をDataに入れる

	unsigned long long Data_num = seisuu(Data);
	if (Data_num < 5000000000) {
		AllData.push_back(Data_num);
	}
	else {
		return;
	}


	int Data_last = Data.back();//配列の最後の要素を取り出す
	//それぞれありうるルンルン数を配列に入れて呼び出す
	if (Data_last != 0) {
		Data.push_back(Data_last - 1);
		lunlun(Data);
		Data.pop_back();
	}

		Data.push_back(Data_last);
		lunlun(Data);
		Data.pop_back();

	if (Data_last != 9) {
		Data.push_back(Data_last + 1);
		lunlun(Data);
		Data.pop_back();
	}
}

int main() {
	cin >> X;
    vector<long long> Data;
	for (int i = 1; i < 10;i++) {
		Data.push_back(i);
		lunlun(Data);//1~9
		Data.pop_back();
	}

	//Data並び替え
	sort(AllData.begin(), AllData.end());

	cout << AllData[X - 1]<<endl;
}

ほかの人のコードを見てみた

参考にしたサイト
AtCoder ABC 161 D - Lunlun Number (緑色, 400 点) - けんちょんの競プロ精進記録

けんちょんさんのコード

#include <bits/stdc++.h>
using namespace std;

void rec(int d, long long val, vector<long long> &all) {
    // 格納
    all.push_back(val);

    // 10 桁だったらそれ以上やらずに打ち切り
    if (d == 10) return;

    // 次の桁へ進む処理
    for (int j = -1; j <= 1; ++j) {
        int add = (val % 10) + j;
        if (add >= 0 && add<= 9) rec(d+1, val*10+add, all);
    }
}

int main() {
    int K;
    cin >> K;
    vector<long long> all;
    for (int v = 1; v < 10; ++v) rec(1, v, all);

    // 小さい順に並び替える
    sort(all.begin(), all.end());

    // K 番目
    cout << all[K-1] << endl;
}

考えたこと

桁数を渡すやり方すげぇ。しかもこれ整数操作で解けるんだ。なるほどなぁ

AtCoder ABC 114 C - 755 再帰関数 整数操作

不正解問題

問題概要

10 進法表記で各桁の値が 7 と 5 と 3 のみで、かつ 7, 5, 3 がすべて一度以上は登場するような数を「753 数」と呼ぶことにする。
整数 N が与えられて、N 以下の 753 数が何個あるかを求めよ。

制約

1≤N≤10^9

考えたこと(WA)

合計値のreturnを最下層でやってればなんとかなるんじゃね..あれ？できない..
やっぱり値は関数に渡しとかないといけないのかな？
３，５，７を整数で操作するのはむりだから、配列つかってあとで整数に変換しよ..
うーん、意味わからんくなった

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

int N;

int loop(int N, vector<int>A, int bit) {
	if (N < pow(10, (A.size() - 1))) {
		string str;
		for (int i = 0; i < A.size(); i++) {
			str += to_string(A[i]);
		}
		long long num = stoi(str);
		if (N <= num) {
			return 0;
		}
	}
	int sum = 0;

	if (bit == 7) {
		sum++;
	}

	A.push_back(3);
	bit |= (0 << 1);
	sum += loop(N, A, bit);
	A.pop_back();
	A.push_back(5);
	bit |= (1 << 1);
	sum += loop(N, A, bit);
	A.pop_back();
	A.push_back(7);
	bit |= (2 << 1);
	sum += loop(N, A, bit);
	A.pop_back();

	return sum;
}

int main() {
	cin >> N;
	vector<int>A;
	int bit = 0;
	int num = loop(N, A, bit);
	cout << num;
}

参考にしたサイト：

AtCoder ABC 114 C - 755 (緑色, 300 点) - けんちょんの競プロ精進記録

サイトのコードを見て考えたこと、理解したこと

• 整数で操作するのは無理だと思っていたが、全然そんなことなかった。num * 10 + nでどうとでもなる。すごい。

• main関数の方でカウント変数を初期化しておいて、関数funcに渡して増やさせていた。この発想は大事だと思った。

• 2進数は0b000..みたいに直接書くことができるらしい。知らんかったｗ

#include <iostream>
using namespace std;

// 入力
long long N;

// cur: 現在の値、use: 7, 5, 3 のうちどれを使ったか, counter: 答え
void func(long long cur, int use, long long &counter){
    if (cur > N) return; // ベースケース
    if (use == 0b111) ++counter; // 答えを増やす

    // 7 を付け加える
    func(cur * 10 + 7, use | 0b001, counter);

    // 5 を付け加える
    func(cur * 10 + 5, use | 0b010, counter);

    // 3 を付け加える
    func(cur * 10 + 3, use | 0b100, counter);
}

int main() {
    cin >> N;
    long long res = 0;
    func(0, 0, res);
    cout << res << endl;
}

一回目です。

sample問題は全問正解してるのに..なんでそんなにWAが多いの？？

原因１　long long型を使っていない
原因２　for文のループ回数を書き間違えていて足りていない　
原因３　関数の戻り値を間違えている
例：
int dfs()..×
unsigned long long dfs()..〇
..exe

ABC 112 C - Pyramid 全探索 未解決

未解決。判定ifにどう落とし込むかが大事。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int INF = 1e9;

int main() {
	int N; cin >> N;
	vector<long long>vx(N), vy(N), vh(N);
	int si = -1;
	for (int i = 0; i < N; i++) {
		cin >> vx[i] >> vy[i] >> vh[i];
		if (vh[i] > 0) si = i;//ここでh[]==0でないデータを取っておいて
	}

	long long resx = -1, resy = -1, resh = -1;
	for (long long x = 0; x <= 100; x++) {
		for (long long y = 0; y <= 100; y++) {
			long long h = vh[si] + abs(x - vx[si]) + abs(y - vy[si]);//vh[i]が0でないデータを使っている
			bool ok = true;
			for (int i = 0; i < N; i++) {
				if (vh[i] > 0 && h - vh[i] != abs(x - vx[i]) + abs(y - vy[i]))//どのように考察を落とし込むかが重要
					ok = false;
				if (vh[i] == 0 && h > abs(x - vx[i]) + abs(y - vy[i]))
					ok = false;
			}
			if (ok) resx = x, resy = y, resh = h;//後から処理するためのこれ。return 0は実力がつかない
		}
	}
	cout << resx << " " << resy << " " << resh << endl;
}