Google Code Jam Qualification Round 2021

A:Reversort
- 問題概要
- 解法
B:Moons and Umbrellas
- 問題概要
- 解法
C:Reversort Engineering
- 問題概要
- 解法

できたとこまで.身の丈.受験明け初コンテスト.リハビリにはよかった感がある.

A:Reversort

問題概要

　数列{ $L_n$ }を下の擬似コードで示されるアルゴリズムでソートする:

for i := 1 to length(L) - 1
　j := position with the minimum value in L between i and length(L), inclusive
　Reverse(L[i..j])

　Reverseのときにコストがj-i+1だけかかる.かかるコストの総和をT個のテストケースそれぞれについて求めよ.

解法

　上の擬似コードをお好みの言語で書き直してあげてコストを計算するとできる. $O(N^2)$ .

B:Moons and Umbrellas

問題概要

　文字列 $S$ は''C,'J','?'の3文字のみで構成されている.このうち'?'の文字すべてを独立に'C'か'J'のいずれかに置き換える.最終的に完成した文字列が'CJ'を含むとXpt,'JC'を含むとYptのコストがかかる.コストのminは?

解法

　'CC'も'JJ'もコスト0なのでHardのケースでなければ'?'が連続する区間を'C'か'J'のみで埋めることでコストがminになることが分かり,これは結局 $S$ から'?'を抜いた文字列でコストがいくらになるかを考えればよいことになる. $O(|S|)$ .Hardは多分文字列DP.この1点が無くても通過できるのでまあ良し.

C:Reversort Engineering

問題概要

　A:Reversortの問題について,コストが $C$ であるような $1,2,...,N$ を並び替えた順列を１つ出力する問題を $T$ 個のテストケースそれぞれについて解け.

解法

　Easyの方はnext_permutationで全探索すれば解けて $O(N!・N^2)$ .この時点で予選通過は確定したのでHardは出していないが $C$ が $N-1\leq C\leq {}_NC_2-1$ を満たせば構成可能でそうでなければ"IMPOSSIBLE"っぽいことがわかり,Reversortを行う際には順列を前から順にみていくことを考えると順列を構成する際には $1,2,...,N$ を後ろから見ていって構成すれば $O(N^2)$ でできそう.Hardは通してないので知らんけど.