CodeForces School Team Contest #1

先輩と同学年の子と参加した。開始して早々同学年の子は逃げ出してdxlibのお勉強をしていたので実質二人で解くことに(別に構わなかったけど)。

問題の傾向としては実装ハード杉問題が多くてライブラリ無いとやってられなかったのもあるし、そういう問題はAcceptできていない。

5時間あるけど正直5時間フルに有効に使えって言われると休憩など挟んだりしていて、まあその間も問題については考えていたけど解けないものは解けない。

とりあえずtouristはソロ参加で全完ってどういう脳構造してるんだ。ソロ参加でも時間は十分だった・・・かもしれないけど、

最初の4問くらいの平均SubmitTime2分30秒ってどういうことよ。バケモノだよ・・・。そりゃベラルーシだけど・・・ロシア語で問題文読めるけど・・・。

5/11 Accepted53位/99チーム でした。微妙・・・。

A. C*++ Calculations

前置インクリメントと後置インクリメントが置かれたキモイ式が与えられる。

インクリメントらの評価順序は先頭からでなくバラバラの可能性がある(実際のCでは未定義ですからそれに沿ってるんだと思う)

計算結果が最大になるようなインクリメントの評価順序をとった時、その計算結果を返せ。 みたいな問題・・・。合ってるのかな?

問題文理解するのにメチャクチャ時間掛かる→どこぞから電卓ライブラリ拾ってきて色々弄ってTLE覚悟で順列使って実装する→Test3とかのしょっぱなWA→理由分からない→放置

B. Company Income Growth

先輩が英文読むのに苦戦していたのでバトンタッチ。僕も苦労したが、やってみたらクソ単純だった。

売上が1 2 3 4 5と1ずつ増加していってるように見せかけたいからそうなるように都合の良い年だけ出力しろ。

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
	int n,a;
	cin >> n;
	vector<int> data(n);
	vector<int> ret;
	for(int i=0;i<n;i++)	cin >> data[i];
	
	int next = 1;
	rep(i,n){
		if(data[i]==next){
			ret.push_back(2001+i);
			next++;
		}
	}
	cout << ret.size() << endl;
	rep(i,ret.size()){
		cout << (i?" ":"") << ret[i];
	}
	if(ret.size())cout << endl;
}

C. Moon Craters

一次元の空間(正しくは位置が一次元)があって、各々の円の位置と半径が与えられる(もうどちらかというと半径というよりは幅)。で、各々がオーバーラップしないように邪魔な円を取り除いた時、最大でどれだけ被らない円があるかみたいな。説明下手だけど。

先輩が解いていて、SystemTest13が通らないと終了まで嘆いていた問題。実際先輩のソース見てもちゃんと動いてそうで、どこに穴があるのか分からなかった。結局WA。

D. Cubical Planet

問題文を読むと複雑そうに見えるけど、サンプルから想定すると簡単。先輩がしょっぱな解いていた。早かった。

(自分があとで書いたソース)

#include <iostream>
using namespace std;

int main(){
    bool a[3],b;
    bool f = false;
    for(int i=0;i<3;i++)cin >> a[i];
    for(int i=0;i<3;i++){cin >> b;if(!(a[i]^b))f = true;}
    cout << (f?"YES":"NO") << endl;
}

E. What Has Dirichlet Got to Do with That?

分かりそうで分からない問題。こういう「最善の手を取った時に~」って問題苦手。

まず英文で死ぬ。鳩の巣原理のことを言っているんだろうけど、何がしたいのかよく分からない。冒頭の

>You all know the Dirichlet principle, the point of which is that if n boxes have no less than n + 1 items, that leads to the existence of a box in which there are at least two items.

などが特に凶悪な英語だった。結構他のチームが正答してたのにも関わらず解けなかった。未提出。

F. Pacifist frogs

これも先輩が解いた問題。自分は問題把握していないので後日この記事のこの部分は更新しよう。

G. Inverse Function

再帰関数のソースを標準入力で読み込みコンパイルしたのに加え色々シュミレート、計算量的にメモ化もしなきゃいけなさそうでマジキチ。

恐ろしくて手が出せなかった。未提出。

H. Multiplication Table

これもこれも先輩が解いた問題。nが唯一が与えられるので、1からn-1までの数を使った九九の表を作れという問題。ただの九九じゃなくてオマケにn進数で出力する。

(自分があとで書いたソース)

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

string db(int a,int r){
    string ret;
    while(a){
        ret += '0'+a%r;
        a/=r;
    }
    reverse(ret.begin(),ret.end());
    return ret;
}

int main(){
    int n;
    cin >> n;
    for(int i=1;i<n;i++){
    for(int j=1;j<n;j++)
        cout << (j-1?" ":"") << db(i*j,n);
    cout << endl;
    }
}

I. Tram

英語で複雑なシュミレーション問題とかマジ勘弁wwwwみたいな感じでした。翻訳機に通してもなお日本語がめっちゃ長かったので読んですらない。未提出。

J. Spelling Check

「文字列a」と、「aより1文字だけ文字数が少ない文字列のb」が与えられる。

自分が解いた問題。一文字だけ消せるんで、消してbと一致するならそのインデックス(1を起点)を返せみたいな問題。

2文字以上編集しなきゃいけないかどうかをO(n)で判定して、その後に消すべき文字を選択するみたいな解法を選択した。

正直複数解があるのって、消すべきインデックスと同じ文字で連続してるものだけだから、それを上手く利用して計算量を減らす。

最初TLEした。後から解法変える感じでソース弄ったのでごちゃごちゃ。もっとキレイに書けるはず。

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

int main(){
	string a,b;
	cin >> a;
	cin >> b;
	
	
	int badCount = 0;
	for(int i=0;i<b.length();i++){
		if(a[i+badCount] == b[i])continue;
		if(badCount==1){
			cout << "0" << endl;
			return 0;
		}
		badCount++;
	}

	vector<int> ret;
	for(int i=0;i<a.length();i++){
		if(i != b.length() && a[i] == b[i])continue;
		string s = a;
		char del = a[i];
		s.erase(i,1);
		
		if(s==b){
			for(int j=i;j>=0;j--){
				if(a[j] == del){ 
					ret.push_back(j);
				}else{
					break;
				}
			}
			break;
		}
	}
	
	printf("%d\n",ret.size());
	for(int i=ret.size()-1;i>=0;i--){
		printf("%d",ret[i]+1);
		if(i>=0)putchar(' ');
	}
	if(ret.size())puts("");
}

G. Testing

なんか提出人数が恐かったので無いものとして避けていた。一応読む時間あったわけだし読んでもよかったかも。どうせ解けないだろうけど。未提出。