Codeforces Beta Round #31参加記録
最近Topcoder SRMに参加していますが、Codeforcesなる存在も知ったので、参加して来ました。
http://www.codeforces.com/contest/31
なお、IDはa-hisameにて参加です。
感想
今回は「問題になれとけ」この一言に尽きました。
英文の「any」を「任意(の全て)」を出力するものと勘違いして、Problem A/BでPresentation Errorを食らいまくる。
結果非常に残念な事に...。
次からはこんなミスはしないけどね！
以下解いた問題と回答。
問題A
a1,a2,...,anの列が与えられて、ai = aj + akとなる（最初の？）i,j,kを出力する問題。
ここで(少なくとも)j,kは任意なので、sampleの出力例(3 2 1)は答えの一つ。
これは(3 1 2)でも良い*1
これさえ分かれば単純に3重ループでOK。
import java.util.Scanner; public class A { public static void main(String[] args) { new A().run(); } private void run() { Scanner s = new Scanner(System.in); int n = s.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = s.nextInt(); } boolean find = false; for(int i = 0; i < n; i++) { if(find) break; for(int j = 0; j < n; j++) { for(int k = j+1; k < n; k++) { if( i == j || j == k || k == i ) continue; if(arr[i] == arr[j] + arr[k]) { System.out.printf("%d %d %d", i+1, j+1, k+1); find = true; break; } } if(find) break; } } if(!find) System.out.println(-1); } }
問題B
メールアドレスがカンマ区切りで保存されてたけど、カンマが全部消えたので、とりあえず適当にカンマ入れて復元できるかを試す問題。
ここでのメールアドレスの形式はA@B。ただし、AとBは一文字以上のアルファベット小文字([a-z]+)で表される。
最初は「全て」を求めてたので再帰を使ってたけど、任意の１つだとものすごい簡単に出来る。
まずはNo Solutionの場合を全部書き出す
- @で始まる/終わる場合
- @が文字列に含まれない場合。
- @@が文字列に含まれる場合*2
これらを求めてから、入力行を@で分割して、最初と最後以外が2文字以上あるかをチェック。
ない場合はB/Aに分割できないのでダメ。
これらの条件を満たさなければ、少なくとも１つの分割例がある。
今回は任意の1つを求めるので、Bを1文字、Aを残りの文字として例を１つ出力。
import java.util.Scanner; public class B { public static void main(String[] args) { new B().run(); } private void run() { Scanner s = new Scanner(System.in); String line = s.nextLine(); if( line.startsWith("@") || line.endsWith("@") || line.indexOf("@") == -1 || line.indexOf("@@") != -1) { System.out.println("No solution"); return; } String[] letters = line.split("@"); for(int i = 1; i < letters.length-1; i++) { if( letters[i].length() <= 1 ) { System.out.println("No solution"); return; } } String prev = letters[0]; for(int i = 1; i < letters.length-1; i++) { String last = letters[i].substring(0, 1); System.out.printf("%s@%s,", prev, last); prev = letters[i].substring(1); } System.out.printf("%s@%s", prev, letters[letters.length-1]); } }
問題C
レッスンスケジュールがあるので、レッスンを重複無く行うために、どのレッスンをキャンセルするかを確かめる問題。キャンセル可能なレッスンの数と、そのindexを出力。
なお、開始時間と終了時間が一致する場合はレッスンは重複しない。
まずは、範囲を作って、ソートして、入力されたスケジュールを作成する。
次にそのスケジュールから１つを取り除いたものを作り、前後の要素が重複しているかを調べる。
ソートしておけば、隣通しが重複していなければ、他の全ても重複していない（ハズ）。
あとはこれを書き下ろす。ただし、indexを昇順に出力するようにしておく。
import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Scanner; public class C { public static void main(String[] args) { new C().run(); } static class Pair { int index; Range range; Pair(int index, Range range) { this.index = index; this.range = range; } } static class Range { int start, end; Range(int start, int end) { this.start = start; this.end = end; } boolean intersect(Range r) { return (start <= r.start && r.start < end) || (start < r.end && r.end <= end); } } private void run() { Scanner s = new Scanner(System.in); int n = s.nextInt(); ArrayList<Pair> list = new ArrayList<Pair>(n); for(int i = 0; i < n; i++) { list.add(new Pair(i, new Range(s.nextInt(), s.nextInt()))); } Collections.sort(list, new Comparator<Pair>() { public int compare(Pair o1, Pair o2) { if( o1.range.start != o2.range.start) return o1.range.start - o2.range.start; return o1.range.end - o2.range.end; } }); ArrayList<Integer> res = new ArrayList<Integer>(n); for(int i = 0; i < n; i++) { ArrayList<Pair> rlist = new ArrayList<Pair>(list); rlist.remove(i); boolean success = true; for(int j = 0; j < rlist.size()-1; j++) { Range r1 = rlist.get(j).range; Range r2 = rlist.get(j+1).range; if(r1.intersect(r2)) { success = false; break; } } if(success) { res.add(list.get(i).index+1); } } Collections.sort(res); System.out.println(res.size()); for(int index : res) { System.out.printf("%d ", index); } System.out.println(); } }
問題D/E
見てすらない。
総評
こ れ は ひ ど い 。
あと、Hackのやり方が分からなかったのもきつかった。
ちゃんと説明よんでから参加しよう……orz
