Google Code Jam 2019 Qualification Round
せっかくなので記録付けてみようと思います。
Foregone Solution
10進表記で'4'を一つ以上含む数N(<=10100)が与えられるので、N=A+Bなる'4'を含まない数A、Bに分解せよ、という問題。
Nのうち'4'の桁を'3'にしたものをA、'4'の桁を'1'、それ以外の桁を'0'にしたものをBにすればいい。簡単すぎて英語がちゃんと読めたのか不安になる問題。入力が100桁ぐらい来るそうなので、intに直さず文字列のままやらないと多倍長が扱いにくい言語では難しい。
fn main() { input! { n: usize, ns: [chars; n], } for (i, n) in ns.into_iter().enumerate() { let mut a = vec![]; let mut b = vec![]; for c in n { if c == '4' { a.push('3'); b.push('1'); } else { a.push(c); if b.len() > 0 { b.push('0'); } } } println!( "Case #{}: {} {}", i + 1, a.iter().collect::<String>(), b.iter().collect::<String>() ); } }
You Can Go Your Own Way
N×N(<=50000)の格子を左上から右下まで、右と下の移動のみで移動するパスが与えられるので、そのパスと被らないような同じく左上から右下に右と下の移動のみで移動するパスを求めよという問題。
元のパスで対角線と交差するような点までの移動について、最初の移動方向を逆にすれば簡単に重複しないパスが求められるのでそういう実装にしたけど、よく考えたら、というか全然よく考えなくても、これ元のパスの右と下入れ替えるだけで同じところ通らないパスができますね…。
fn main() { input! { n: usize, qs: [(usize, chars); n], } for (i, (n, cs)) in qs.into_iter().enumerate() { let mut ans = vec![]; let mut head = ' '; let mut r = 0; let mut d = 0; for c in cs { if r == 0 && d == 0 { head = c; } if c == 'E' { r += 1; } else { d += 1; } if r == d { for _ in 0..r { ans.push(if head == 'E' { 'S' } else { 'E' }); } for _ in 0..r { ans.push(head); } r = 0; d = 0; } } println!("Case #{}: {}", i + 1, ans.iter().collect::<String>()); } }
Cryptopangrams
相異なる26個の素数(<=10100)を選び、小さい順にA...Zの文字を割り当てる。アルファベット大文字だけからなるL+1文字の平文テキストに対して、隣り合う文字にそれぞれ割り当てられた素数の積L(<=100)個が計算される。この計算されたL個の積が与えられるので、元のテキストを求めよ、という問題。元のテキストは必ずすべてのアルファベットを1回以上含む。ちなみに選ばれた素数はNを超えませんよという数が与えられるけど、これ制約以外に何に使うんだろう。
素数は最大で10100まであるという大きな制約なので、単に素因数分解するのは不可能。しかし隣り合った数は必ず同じ素数を素因数に持つので、gcdをとれば簡単に素因数分解できる。が、元のテキストが例えば"ABA"などとなっていた場合、P[A]×P[B] = P{B]×P[A] なので、gcdでは素因数分解できない。それでも、入力はすべての文字を1回以上含むという制約があるので、どこかしら24か所ぐらいは必ず素因数分解できるところがある。どこか一か所素因数分解できるところが見つかれば、そこから左右にばらしていけば結局全部素因数分解できる。すべての数が素因数分解できれば、あとは素因数を集めて、小さい順にA..Zの文字を割り当て、それに基づいてテキストに戻せばよい。
実装が案外面倒なので、WA積んでしまった。多倍長扱うために久しぶりに競プロでHaskellを使った。競プロはもっと多倍長使わせてもいいと思う。入力が264にフィットするようにしかならないのはやっぱなんか不自然な気がする。
{-# Language ScopedTypeVariables #-} import Control.Monad import Data.List import Data.Maybe import Text.Printf import Control.Exception main :: IO () main = do cases <- readLn forM_ [1..cases] $ \(caseno :: Int) -> do [n, l] :: [Int] <- map read . words <$> getLine ls :: [Integer] <- map read . words <$> getLine let g a b = let t = gcd a b in if t == a || t == b then Nothing else Just t let p1 = head $ catMaybes $ zipWith g ls $ tail ls let go1 (x:y:xs) p | x /= y && x`mod`p == 0 && y`mod`p == 0 = go3 xs (y `div` p) | otherwise = go1 (y:xs) p go3 [] p = p go3 (x: xs) p = assert (x`mod`p == 0) $ go3 xs (x `div` p) let initp = go1 (reverse ls) p1 let go2 [] p = [p] go2 (x:xs) p = p: go2 xs (x `div` p) let ps = go2 ls initp let dict = zip (sort $ nub ps) ['A'..] let ans = map (\p -> fromJust $ lookup p dict) ps printf "Case #%d: %s\n" caseno ans
（久しぶりにHaskell書いたからかコードが汚すぎる）
Dat Bae
N(<=1024)個のコンピューターがあって、各コンピューターは1ビットだけデータを保存できる。マスターは各コンピューターに保存させるNビットのデータを与えることができて、各コンピューターはその保存した値を返す。ところが、B個(<=15)のコンピューターは壊れており、壊れているコンピューターは値を返さない。つまり、与えたNビットのうちどこかBビットが欠損したものが返ってくる。このクエリをF(=10 or 5)回まで行えるとき、どのコンピューターが壊れているかを特定しろというインタラクティブ問題。
Test set 1ではクエリは10回まで行える。210=1024なのでとても都合の良い制約が見える。それで考えてみると、例えば、各マシンが保存できる数が0,1の2値ではなく、任意の数にできる場合ならどうなるか。この場合はとても簡単で、マシン0には0を、マシン1には1を、マシンiにはiをそれぞれ保存するように指示すると、まさに壊れているマシンのIDが欠損したリストが返ってくるはずである。では1ビットしか保存できない場合はどうすればいいのか考えると、2進の桁を1桁ずつ送ってその結果をまとめれば結局10ビットの値を扱えたのと同じことになる。0~1023の値のどこが欠損したかがわかるので、10回クエリができるなら、簡単にどのマシンが壊れているのか特定できることになる。
Test set 2ではクエリは5回までしか行えない。同じように考えると、符号化できるのは0~31までになる。ところが、壊れている台数は15台以下なので、同じようにして壊れているマシンが特定できてしまう。各マシンに与えるデータを0,1...31,0,1...31,...とIDの下位5ビットとすると、そのうち高々15か所が抜けて返ってくる。抜ける箇所が31か所までであるならば、つまり、周期1個分まるまる抜けるというようなことがなければ、周期的に考えてどこが抜けているかは簡単に求められる。というわけで、クエリが5回でも割と簡単に特定できる。問題の制約はF=5だけど、実際には4回でも解ける気がする。
// Leftover食えるようにマクロをいい加減に改造している // もうちょっとまともにきれいにしてマージしたい #[allow(unused_macros)] macro_rules! input { (next = $e:expr, $($r:tt)*) => { input_inner!{$e, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes .by_ref() .map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } #[allow(unused_macros)] macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => { let mut $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } #[allow(unused_macros)] macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::<Vec<char>>() }; ($next:expr, bytes) => { read_value!($next, String).into_bytes() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; } use std::io::Write; // 本文ここから fn main() { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String { bytes .by_ref() .map(|r| r.unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect() }; input! { next = next, cases: usize, } for _ in 0..cases { input! { next = next, n: usize, b: usize, _f: usize, } let mut acc = vec![0; n - b]; for i in 0..5 { let mut test_case = vec![0; n]; for j in 0..n { test_case[j] = ((j % 32) >> i) & 1; } for j in 0..n { print!("{}", test_case[j]); } println!(); std::io::stdout().flush().unwrap(); input! { next = next, res: chars, } assert_eq!(res.len(), n - b); for j in 0..n - b { if res[j] == '1' { acc[j] |= 1 << i; } } } let mut ans = vec![]; let mut cur = 0; for i in 0..n - b { while cur % 32 != acc[i] { ans.push(cur); cur += 1; } cur += 1; } while cur < n { ans.push(cur); cur += 1; } for i in 0..ans.len() { if i != 0 { print!(" "); } print!("{}", ans[i]); } println!(); std::io::stdout().flush().unwrap(); input! { next = next, verdict: i32, } assert_eq!(verdict, 1); } }
