Hatena::Grouptopcoder

kuuso1の日記

2014-05-05

Google Code Jam 2014 round1B

| 18:01 |  Google Code Jam 2014 round1B  - kuuso1の日記 を含むブックマーク はてなブックマーク -  Google Code Jam 2014 round1B  - kuuso1の日記

A: s:o/L:o B: s:o/L:- C: s:-/L:- (31pts/2135th)。次頑張ります。

Aの判定方法で最後自分のやった方法が、コンテスト中は「嘘解法くさい」と思っていたのですが、

終了後にtwitterのTLでsune2さんにいただいた指摘で間違ってないことが分かったので記録しておきます。

Problem A. The Repeater

  • 100文字以下の文字列がN個与えられる
  • 以下の操作を繰り返して全ての文字列を同じものに変更できるかを考える
    • 操作1:隣り合う同じ文字は1つ消すことができる (ex "abbc" -> "abc")
    • 操作2:文字のコピーを追加することができる (ex "efg" -> "eefg")
  • 上記が可能な時、最小の操作回数を求める

(制約)Small:N=2/Large:N=100

文字数/Nともに小さいので実行時間的には十分マージナルな問題なので、

  1. 文字の出てくる順序や種類が違うものは作ることができない
  2. 作ることができるものについては、各文字ごとに最小の手数を調べる

をそれぞれチェックすればよい


 ここで2番目の、最小の手数を調べる部分について例えばN=3,サンプルが"aaaaaabbccc","abbbccc","abc"としたときに最初のaをいくつにそろえるのが最小かというのを考えると、確実なのは1文字から6文字の全検索で最小値を探す方法。

 「Median(中央値)にそろえたらいんじゃね」と思って実装したのですが、「あれ?サンプル数偶数だと中央が2つあるから怪しいな」と思い、念のため見ておくかと中央とその両隣の値にそれぞれそろえた場合の最小値を出すことで回答を提出。LargeもAccept


 この最後のMedianをとる部分が、大体はイケてそうだけど実際OKなのかはちょっと怪しいなと本番中は思っていましたが、終了後のtwitterのやりとりでsune2さんに「f(x)=Σ|ai-x|を考えるとMedianでOKなのが分かる」と教えていただきました。

くどい感じもしますが絵をかくと下みたいになります。f:id:kuuso1:20140505170944p:image

 下に凸なグラフで、最初考えてた偶数だと中央が2つある点は、関数的には中央では定数になっているのでどちらを選んでも結果は変わらないので、気にせずm=N/2の値を見てやればよいという事が分かります(個人的には目からウロコでした)。

オーダー的には、要素の個数Nと値の範囲Mに対して

  • 全検索:O(NM)
  • Median:O(NlogN) (配列ソートして中点を選ぶ)

なので、今回のような小サイズケースではあまり差はないですが、値の範囲(今回だと文字列長)がもっと大きいと効いてきたかも。

C#はたまに定数倍怖いですからね~(遠い目)


以下本番のコード(一部削除)。途中謎の参照バグがでてコンパイルできなかったのでごちゃごちゃしたコードになってます。。

using System;
using System.Collections;
using System.Collections.Generic;
 
class TEST{
	static void Main(){
		int T=int.Parse(Console.ReadLine());
		for(int i=1;i<=T;i++){
			Sol mySol =new Sol(i);
			mySol.Solve();
		}
	}
}

class Sol{
	public void Solve(){
		List<char>[] Lc=new List<char>[N];
		List<int>[] Ln=new List<int>[N];
		for(int i=0;i<N;i++){
			Lc[i]=new List<char>();
			Ln[i]=new List<int>();
		}
		for(int i=0;i<N;i++){
			Lc[i].Add(S[i][0]);
			Ln[i].Add(1);
			for(int j=1;j<S[i].Length;j++){
				if(S[i][j]!=S[i][j-1]){
					Lc[i].Add(S[i][j]);
					Ln[i].Add(1);
					continue;
				}else{
					Ln[i][Ln[i].Count-1]++;
				}
			}
		}
		
		//chk;
		for(int i=1;i<N;i++){
			if(Lc[i].Count!=Lc[0].Count){
				Console.WriteLine("Fegla Won");
				return;
			}
		}
		for(int i=1;i<N;i++){
			for(int j=0;j<Lc[0].Count;j++){
				if(Lc[i][j]!=Lc[0][j]){
					Console.WriteLine("Fegla Won");
					return;
				}
			}
		}

		int ans=0;
		for(int i=0;i<Lc[0].Count;i++){
			List<int> LL=new List<int>();
			for(int j=0;j<N;j++){
				LL.Add(Ln[j][i]);
			}
			LL.Sort();
			int anss;
			int ans0=0;
			int trgt=LL.Count/2;
			for(int j=0;j<LL.Count;j++){
				ans0+=Math.Abs(LL[trgt]-LL[j]);
			}
			anss=ans0;
			
			//念のため両隣を調べる
			if(LL.Count/2+1<=LL.Count-1){
				int ans1=0;
				int trgt1=LL.Count/2+1;
				for(int j=0;j<LL.Count;j++){
					ans1+=Math.Abs(LL[trgt1]-LL[j]);
				}
				if(ans1<anss)anss=ans1;
			}
			
			if(LL.Count/2-1>=0){
				int ans2=0;
				int trgt2=LL.Count/2-1;
				for(int j=0;j<LL.Count;j++){
					ans2+=Math.Abs(LL[trgt2]-LL[j]);
				}
				if(ans2<anss)anss=ans2;
			}

			ans+=anss;
		}
		Console.WriteLine("{0}",ans);
	}

	int N;
	String[] S;
	public Sol(int T){
		Console.Write("Case #{0}: ",T);
		N=int.Parse(Console.ReadLine());
		S=new String[N];
		for(int i=0;i<N;i++){
			S[i]=Console.ReadLine();
		}
	}
}

TCOは落ちたので(Round1Cで順位見直しがあったが759th(!?)でギリギリ(<750)落ちた)

こっちはもうちょい踏ん張りたい。