ABC167に参加しました - imomoの勉強記録

AtCoderのコンテストに参加した際の結果と考え方、反省点などを書いていきます。
コンテストページはこちら

解いた/挑んだ問題
結果
- コンテスト結果
- 順位、パフォーマンス変動
反省点

解いた/挑んだ問題

A問題

問題の概要

文字列S,Tが与えられる。
Tが文字列Sの末尾に一文字加えたものなら"Yes",それ以外なら"No"を出力せよ

制約

S,Tは英小文字列
$1 \leq |N| \leq 10$
$|T| = |S| + 1$

どのように考えたか

Sと、Tの末尾を除いた文字列を比較して等しければ"Yes"、それ以外なら"No"

結果

一発ACでした。
・提出ししたコード

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;

int main() {
	string s, ss;
	cin >> s >> ss;
	bool ans = false;
	if (s.substr(0, s.size()) == ss.substr(0, s.size())) ans = true;



	if (ans) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}	return 0;
}

A問題らしい問題だった
もっといい書き方はあったと思う

ACまでの時間

ACしたのはコンテスト開始から3分後です。

f:id:iiiimmmmo:20200510232805p:plain — ABC167_A

B問題

問題の概要

1が書かれたカードがA枚、0が書かれたカードがB枚、-1と書かれたカードがC枚あります。
K枚を丁度選択した時のカードに書かれた数の和が最大となるものを出力せよ

制約

入力はすべて整数である
$0 \leq A,B,C$
$1 \leq K \leq A + B +C \leq 2 × 10^9$

どのように考えたか

A+B+CがK以上なので、k からAを引いて、sumにAの値を入れる　
kをbと比較してkの方が大きい場合、kからbを引いて、sumからkを引く

結果

3回提出しましたが全部WAでした。
提出したコード

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;

int main() {
	int a, b, c, k;
	int sum = 0;
	cin >> a >> b >> c >> k;
	k -= a;
	sum += a;
	if (k > b) {
		k -= b;
		sum -= k;
	}
	else {
		//
	}
	cout << sum << endl;
	return 0;
}

なんでACにならないか分からなかった
基礎を固めて行きたいです。

ACまでの時間

今回はACできていないです。

f:id:iiiimmmmo:20200510234717p:plain — ABC167_B

C問題

問題の概要

理解したいアルゴリズムがM個あり、それらはN冊ある参考書でそれぞれ学ぶことができる。
各アルゴリズムにおいて、理解度がX以上となったら理解したこととなり、各参考書は $C_i$ 円で売られており、j番目のアルゴリズムの理解度を $A_{i,j}$ あげることができる。
M個のアルゴリズムをすべて理解できる場合は最小金額を、できない場合は-1を出力せよ。

制約

入力はすべて整数
$1 \leq N,M \leq 12$
$1 \leq X \leq 10^5$
$1 \leq C_i \leq 10^5$
$0 \leq A_{i,j} \leq 10^5$

どのように考えたか

bit全探索で最小値の変数"minmoney"に値を入れておいて、全部理解できたら"minmoney"を更新
bit全探索を抜けて"minmoney"が初期値なら-1、それ以外なら"minmoney"を出力する。

結果

時間はかかったが一発AC
・提出したコード

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;

int main() {
	int n, m,money=0;
	ll minmoney = 100100100100100;
	bool reg = true;
	ll a, b, c,x;
	ll sum = 0;
	cin >> n >> m >> x;
	vii alg(n);
	vi vsum(m + 1);
	vi vtmp;
	rep(i, n) {
		cin >>money;
		vsum[0] += money;
		alg[i].push_back(money);
		rep(j, m) {
			cin >> a;
			alg[i].push_back(a);
			vsum[j + 1] += a;
		}
	}

	for (int bit = 0; bit < (1 << n); bit++) {
		vtmp = vsum;
		reg = true;
		rep(k, n) {
			if (bit & (1 << k)) {
				vtmp[0] -= alg[k][0];
				rep(s, m) {
					vtmp[s + 1] -= alg[k][s + 1];
				}
			}
		}
		rep(s, m) {
			if (vtmp[s + 1] < x) reg = false;
		}
		if (reg) {
			if (vtmp[0] < minmoney) minmoney = vtmp[0];
		}
	}
	if (minmoney != 100100100100100) {
		cout << minmoney << endl;
	}
	else {
		cout << -1 << endl;
	}
	return 0;
}

久々にbit全探索を実装したので、知識があやふやだった
復習して自らの力にしていきたいです。

ACまでの時間

ACしたのはコンテスト開始から75分後。

f:id:iiiimmmmo:20200511000215p:plain — ABC167_C

D問題

問題の概要

N個の町があります。
それぞれの町にはテレポーターがあり、町iのテレポーターの転送先は町 $A_i$ です。
最初に町1にいて、K回テレポートしたときの到着した町を出力せよ

制約

$2 \leq N \leq 2 × 10^5$
$1 \leq A_i \leq N$
$1 \leq K \leq 10^{18}$

どのように考えたか

サイクルを検出してサイクルの数でKを割ってあまりを基に町を割り出す。

結果

TLEでした。
・提出したコード

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;

int main() {
	ll n, k, a;
	cin >> n >> k;
	vector<int>city(n);
	vi cycle;
	cycle.push_back(1);
	rep(i, n)cin >> city[i];
	int pos = 1;
	while (1) {
		pos = city[pos - 1];
		if (pos == 1)break;
		cycle.push_back(pos);
	}
	cout << cycle[(k % cycle.size())] <<  endl;
	return 0;
}