Codeforces Round #162 (Div. 2)に参加してみた！

http://codeforces.com/contest/265

登録したもののなかなか参加出来なかったCodeforcesについに参加しました。
Codeforcesは形式がTopCoderに似ていて、得点は時間依存で、hackというTopCoderの撃墜があります。ただし、hackはコーディング中に行うという点が違います。

以下記録です。

A. Colorful Stones (Simplified Edition)

実装するだけ。でも問題文が英語なので理解に時間がかかりました。3回くらい読み直してようやく分かりました。15分くらい。

import java.util.Scanner;

public class A {

	public static void main(String[] args) {
		doIt();
	}

	static void doIt(){
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		char[] t = sc.next().toCharArray();
		int pos = 0;
		for(int i = 0; i < t.length; i++){
			if(s[pos] == t[i]) pos++;
		}
		System.out.println(pos + 1);
	}

}

B. Roadside Trees (Simplified Edition)

これも実装するだけ。でも問題文が英語なので（略
one secondが1,2のことかと思った自分はもう駄目かもしれない。
これも15分くらい。

import java.util.Scanner;

public class B {

	public static void main(String[] args) {
		doIt();
	}

	static void doIt(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] h = new int[n];
		for(int i = 0; i < n; i++) h[i] = sc.nextInt();
		int height = h[0];
		int sec = h[0] + 1;
		for(int i = 1; i < n; i++){
			if(height > h[i]){
				sec += height - h[i];
				height = h[i];
			}
			sec++;
			sec += h[i] - height;
			height = h[i];
			sec++;
		}
		System.out.println(sec);
	}

}

C. Roadside Trees (Simplified Edition)

降ってくる石を与えられたように左、右に避け続けた時の最終的な石の並び順を求める問題。

単に左右に石を配置してコードを提出したところ、コンテスト終了直前にhackされてWAでした。
やっぱりシミュレーションかと思ってコンテスト終了後にdoubleで石の位置を覚えておいて、最後にソートしてみたけどWA。どうもdoubleの精度の問題で最後の方は値が同じになってしまい、TreeMapにkeyが同じと見なされているっぽい。どうすればいいんだろう？

D. Good Sequences

与えられた数字の配列から順序を保持し、「隣り合う数字のgcdが2以上」という条件のもとで出来る部分列の最長の長さを求める問題。単純にDPで実装してみたけど、計算量がn^2になり、n <= 10^5なので全然無理。これも分からない。

Eはやってません。

次回参加することがあったらとりあえずCを解くことを目標にします。
C、Dは時間があったら解き直したいなー。

Rating : Unrated → 1435

2013/1/26 追記
C解けました。
アルゴリズムは合っていたっぽいのですが、TLEになっていました。
前はVectorで配列を作りながらシミュレートしていたのと、出力にSystem.out.printlnを使っていたために遅いみたいです。
なのでシミュレートをやめ、出力はPrintWriterでやったところAC。

import java.io.PrintWriter;
import java.util.Scanner;

public class C2 {

	public static void main(String[] args) {
		doIt();
	}

	static void doIt(){
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		char[] input = sc.next().toCharArray();
		for(int i = 0; i < input.length; i++){
			if(input[i] == 'r') out.println(i+1);
		}
		for(int i = input.length - 1; 0 <= i; i--){
			if(input[i] == 'l') out.println(i+1);
		}
		out.flush();
	}
}

次はDをなんとかしたい。