Codeforces Beta Round #34 (Div. 2)

10/11(月) 日本時間22:00~と参加しやすい時間帯だったので参加してきました。

A. Reconnaissance 2

兵士が順番に環状に並ぶ。そして、n人の兵士の身長が与えられる。隣合ったもの同士の身長の差が最小となる場合の「その差」を出力せよ。

ポイントは環状ということ。最初の人と最後の人の身長の差も考慮しなきゃいけない。

最初、兵士のペアの身長が最小になるものを出力する問題だと思ってWAもらった。

隣り合ったって太字で書いてるのに・・・。てか最小値更新にpairとか使うべきじゃないな。

Accepted 10min. 430Pt.

#include <iostream>
#include <cstdlib>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
#define INF (1<<21)
int main(){
	int n,m;
	cin >> n;
	int data[100];
	pair<int , pair<int,int> > ret = make_pair(INF,make_pair(-1,-1)); 
	rep(i,n){
		cin >> data[i];
	}
	rep(i,n-1){
		ret =	min(
			 ret,
			 make_pair(abs(data[i]-data[i+1]),make_pair(i,i+1))
			);
	}
	ret =  min(ret,
		 make_pair(abs(data[n-1]-data[0]),make_pair(0,n-1))
		);
	cout << ret.second.first+1 << " " << ret.second.second+1 << endl;
}

B. Sale

中古テレビ、普通に買うやつと引き取り料金逆にもらえるやつがある。問題の主人公はmコまで引き取ることが"できる"。利益を最大化したいんでヨロシクゥ。

複雑な前処理いらない気がするけどまあいい。それなりに早かったし。

Accepted 16min. 936Pt.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	int n,m,t;
	cin >> n >> m;
	vector<int> data;
	rep(i,n){
		cin >> t;
		data.push_back(-t);
	}
	sort(data.begin(),data.end(),greater<int>());
	int ret = 0;
	rep(i,m){
		if(data[i]>0)ret+=data[i];
	}
	cout << ret << endl;
	
}

C. Page Numbers

ページ番号を書式に沿ってくくる。AOJで全く同じ問題が出題されていたが、大昔に解いたのでソースが無く流用できず、結局自分で考えながら書くことに。

そうしたら超ごちゃごちゃになったでござる。クソひどい実装。

Accepted 32min. 1308Pt.

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
#define SS stringstream
typedef long long ll;

int main(){
	int t;
	string s;
	vector<int> data;
	
	cin >> s;
	while(~s.find(","))s[s.find(",")] = ' ';
	SS ss(s);
	while(ss >> t)data.push_back(t);
	
	sort(data.begin(),data.end());
	data.erase(unique(data.begin(),data.end()),data.end());

	SS ret;
	bool flag = false;
	int prev = -1;
	for(int i=0;i<data.size();i++){
		if(data[i] == prev+1){
			flag = true;
		}else{
			if(flag)ret << "-" << data[i-1] << "," << data[i];
			else ret << (i?",":"") << data[i];
			
			flag=false;
		}
		prev = data[i];
	}
	if(flag)ret << "-" << data[data.size()-1];

	cout << ret.str() << endl;
		
}

D. Road Map

  1. 問題文をサラっと読んで首都を移したいんだなってことは分かる。しかしテストケースを見てもよく分からない。
  2. 注意深く問題文を読んでようやく意味が分かる。要するに木が与えられるから、「木の回転」を実装しろってことだった。この時点で残り1時間10分くらい
  3. しかし、木の回転はおろか実は木自体実装したことない。まあnodeに親とか子とかやるだけだけど。
  4. 木の回転に悩む。Wikipediaを見るも二分木の回転うんぬんとかしかなくて、問題設定では二分木じゃないからダメだよなーとかいろいろ考える。
  5. 考えまくった挙句に、親だけを再帰的に巡っていくだけで良いことに気づく。子については考慮する必要がない。→実装する。

迷走しまくったので1時間以上掛かった。既知のアルゴリズムを当てはめること以外出来ないという事実が露呈してしまった・・・。

Accepted 93min. 1308Pt.

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

vector<int> data;

void start(int now,int from)
{	
	if(now != -1){
		start(data[now],now);
		data[now] = from;
	}
}

int main()
{
	int n,r1,r2,t;
	cin >> n >> r1 >> r2;
	r1--;r2--;
	
	data.resize(n);
	fill(data.begin(),data.end(),-1);
	rep(i,n){
		if(i == r1)continue;
		cin >> t;
		t--;
		data[i] = t;
	}
	
	start(data[r2],r2);
	data[r2] = -1;
	
	bool first = false;
	rep(i,n){
		if(data[i] != -1){
			if(first)cout << " ";
			cout << data[i]+1;
			first = true;
		}
	}
	cout << endl;
}

E. Collisions

問題文読んでいないけど、物理っぽかった。式とか載っていたけど、物理苦手なのと残り30分切ってるということであきらめた。

Opened.

Hack

E解くの諦めてから、他人のソースをHackしようとして眺めていたが、pretestがあるCFで、穴を突ける気がしない。初期化ミスとかも見つけられなかったし。ダメだなあ。

Result

点数:A,B,C,D - Accepted - 3930Pt.

順位:78位/515人(ルーム内:6位/36人)

レート:1325→1482

感想

以前まで全然解けなかったのによく解けるようになったなという感じです。

Div2で問題自体が簡単だったってのもあるし、英文が前より読みやすい?(てか慣れた?)ってのもあるし、しっかり集中して読む癖がついたってのもある気がする。

あと18ポイントで青コーダーだ。