AtCoder Beginner Contest 103

最近忙しくてブログを書くのはおよそ二か月ぶりになります。一か月ほど前のABC100にて緑になりました。Yay!

今回はABC103の参加記です。結果はA, B, C, Dの全完で青パフォでした。
使用言語: C++

A - Task Scheduling Problem

問題

タスクは3個しかないので何も考えずに全探索すればできるが、地力をつけるためにも解法を考えてみる。

のとき
を最初に選ぶと明らかに合計コストは最小値にならないのでかを最初に選ぶ。
→を最初に選ぶと合計コストは
　
　を最初に選んでも同様
　→が最小値

A問題にしては難しい。今回はC問題すら解けないかも……と思った。

コンテストの始めのころジャッジが壊れていたらしいのだが、改行も出力していたからなのか提出が遅かったからなのか分からないが特に問題なくACだった。

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b, c;
	cin>>a>>b>>c;
	int ans=max({a, b, c})-min({a, b, c});
	cout<<ans<<'\n';
	return 0;
}

B - String Rotation

問題

文字の長さは100以下なのでを一文字ずつ回転させてと一致するか調べて十分間に合う。

コンテスト後に知ったのだがrotateという関数を使えば回転できるらしい。

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(n); ++i)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s, t;
	cin>>s>>t;
	int len=s.size();
	if(s==t){
		cout<<"Yes"<<'\n';
		return 0;
	}
	char u[114];
	REP(i, s.size()){
		bool ok=true;
		REP(j, len){
			if(s[(j+i)%len]!=t[j]){
				ok=false;
				break;
			}
		}
		if(ok){
			cout<<"Yes"<<'\n';
			return 0;
		}
	}
	cout<<"No"<<'\n';
	return 0;
}

C - Modulo Summation

問題

ごとの和をとるのでぱっと見難しそう。
→なので
・・・(1)
　→中国剰余定理っぽい形だな～と思いつつを眺めるとのとき(1)の等号が成立している！
　　→サンプルを見て確かめる（ここでなぜかが最大値をとるときのを求めるものと勘違いして時間を浪費）。
　　　→ｱ、よく見たらの最大値を求める問題だった。

個人的には今回のコンテストで一番簡単だった。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i=0; i<(n); ++i)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, a;
	cin>>n;
	ll ans=0;
	REP(i, n){
		cin>>a;
		ans+=a-1;
	}
	cout<<ans<<'\n';
	return 0;
}

D - Islands War

問題

とりあえずサンプルを使って取り除く橋をどうやって選ぶか考えた。
→要望をソートすると考えやすそう。
　しばらくUnion-Findを使うのではとか考えて迷走……
　→要望を順に見て取り除く橋の候補を絞っていき、候補から外れる要望が来たら取り除く橋をもう一つ増やす方針で解けそう。
　　→サンプルを使いつつ反例を考えたが無さそうなのでこれでOK。

コンテスト中はでソートしたのだが、冷静に考えたらでソートすれば蟻本の区間スケジューリング問題だった。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define REP(i, n) for(int i=0; i<(n); ++i)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, a, b;
	pii ab[114514];
	cin>>n>>m;
	REP(i, m){
		cin>>a>>b;
		ab[i]=make_pair(a-1, b-2);
	}
	sort(ab, ab+m);
	int r=m;
	int ans=1;
	REP(i, m){
		if(r>=ab[i].first){
			r=min(r, ab[i].second);
		}
		else{
			r=ab[i].second;
			++ans;
		}
	}
	cout<<ans<<'\n';
	return 0;
}