Round 1B C-large
C-largeはソートされたリストに対してi番目の要素の検索と要素の削除が効率的に行えるデータ構造があればよい、一般的には赤黒木などの平衡二分木が必要になるんだけど今回の問題は挿入を考えなくてよいので単に子要素がどれだけあるかを保存した二分木をつかって書ける。この方針で書いたらlargeのデータセットに対して20秒ぐらいで解が求まった。
以下problem Cのコード、本当は検索と削除は同時に行えるけど分かりやすさのため別々に行った。
import java.util.*; class Tree{ Tree left; Tree right; int size; int value; Tree(int v){ size = 1; left = right = null; value = v; } static Tree merge(Tree l , Tree r){ Tree t = new Tree(-1); t.left = l; t.right = r; t.size = l.size + r.size; return t; } int get(int index){ if(value >= 0)return value; if(index < left.size){ return left.get(index); }else{ return right.get(index - left.size); } } void remove(int index){ size--; if(value >= 0)return ; if(index < left.size){ left.remove(index); }else{ right.remove(index - left.size); } } } public class C { private static Tree createTree(int K) { List<Tree> ts = new ArrayList<Tree>(); for(int i = 0 ; i < K ; i++){ ts.add(new Tree(i)); } while(ts.size() > 1){ List<Tree> next = new ArrayList<Tree>(); if(ts.size() % 2 == 1){ next.add(ts.get(0)); } for(int i = ts.size() % 2 ; i < ts.size() ; i += 2){ Tree l = ts.get(i); Tree r = ts.get(i + 1); Tree t = Tree.merge(l, r); next.add(t); } ts = next; } return ts.get(0); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int caseNum = 1 ; caseNum <= T ; caseNum++){ int K = sc.nextInt(); Tree root = createTree(K); int ps[] = new int[K]; int index = 0; for(int match = 1 ; match <= K ; match++){ int v = root.get(index); ps[v] = match; root.remove(index); //update index int s = root.size; if(s != 0){ index = (index + match)% s; } } int n = sc.nextInt(); System.out.printf("Case #%d:" , caseNum); for(int i = 0 ; i < n ; i++){ System.out.print(" " + ps[sc.nextInt() - 1]); } System.out.println(); } } }