Google Code Jam 2017 Round 1A 問題と解説

https://code.google.com/codejam/contest/5304486/dashboard

A. Alphabet Cake

R*Cのマスがある。
各マスは?かA～Zで塗られている。
A～Zは最多"1つ"だけ書かれている。
残りの?のマスを全ての文字の領域が長方形になるようにA～Zを塗れ。

B. Ratatouille

（キレた）

C. Play the Dragon

自分の体力Hd攻撃力Ad, 敵の体力Hk攻撃力Akである。
自分が先攻で以下の行動ができる。

1. 攻撃 : 攻撃力分だけ相手の体力を減らす
2. バフ : 攻撃力を+Bする
3. 回復 : 体力をHdにする
4. デバグ : 相手の攻撃力を-Dする

最短何ターンで勝てるか。勝てないならIMPOSSIBLE

以下、解説

競技プログラミングにおける平方分割問題まとめ

平方分割

• Square Root Decomposition
• 区間に対するクエリに対して高速に処理できる
• ここが詳しい
• 区間でのクエリであるが、ソートして平方分割して、各バケットでクエリに入る要素だけ抜き出す平方分割もある
  • こういう問題
  • 1.添字と共に昇順ソート 2.バケット毎に添え字ソート 3.各クエリについて全てのバケットのans[L][R]を取得してマージ
  • 出現頻度を扱う場合は平方分割が多いイメージ
• クエリの平方分割
  • Q個のクエリを分けて解く手法 資料
• 取得クエリだけで更新クエリが無い場合はバケットの間の処理は事前計算することで、処理をより軽くすることができる場合がある この解説

問題

• 平方分割
  • AOJ Range Query - Range Sum Query (RSQ)
  • AOJ Range Query - Range Minimum Query (RMQ)
  • AOJ Range Query - Range Add Query (RAQ)
  • AOJ Range Query - Range Sum Query (RSQ)
  • Codeforces #404 Div2 E. Anton and Permutation
  • CF91 Lucky Array 解説1 解説2 解説3
  • CC Hill Jumping
  • AOJ RMQ 2 解説
  • CC Chef and Isomorphic Array （ハッシュの知識も必要）
  • CF260 Serega and Fun 解説
  • CF542 Isolation
• クエリの範囲で分けない平方分割
  • CSA Closest Numbers
• クエリの平方分割
  • CF119 Xenia and Tree 解説1 解説2
  • AOJ Graph Construction 解説1 解説2
  • AOJ Tree 解説
  • JOI 回転寿司 解説1 解説2
  • CSA55 Black White Tree
  • CC Killing Monsters （＋ゼータ変換）
• 二次元平方分割
  • AOJ School of Killifish 解説
  • CodeChef Rectangle Query ←違うかも

競技プログラミングにおけるHL分解まとめ

HL分解

• Heavy-Light Decomposition
• 木に対するクエリをO(log^2n)くらいで処理できる
• 辺にコストが載っている場合は頂点にコストを移す
• 部分木クエリもこなせる構築方法

問題

• 頂点にコストがある問題
  • yukicoder No.399 動的な領主 HL分解 + 遅延セグ木(区間加算 + 区間総和)
  • yukicoder No.235 めぐるはめぐる(5) HL分解 + 遅延セグ木(区間加算 + 区間総和)
  • yukicoder No.529 帰省ラッシュ HL分解 + 二重辺連結成分分解 + UnionFind + セグメントツリー(RMQ)の難問
• 辺にコストがある問題
  • SPOJ QTREE - Query on a tree + セグ木(区間max)
  • Codeforces #329 Div2 D. Happy Tree Party + セグ木(区間積)
  • CodeChef Pishty and tree + セグ木（区間xor）
  • yukicoder No.650 行列木クエリ 解説
• 部分木クエリも使う問題
  • HR Subtrees And Paths
  • AOJ Tree 解説
• 未整理
  • CodeChef Idols and Fans
  • CC Fibonacci Numbers on Tree

競技プログラミングにおけるオイラーツアー問題まとめ

オイラーツアー

• 木をDFSしたときの順番で頂点を記録する手法
  • pre-order : 頂点に到着したら記録
  • post-order : 頂点から離れるときに記録
• 用途
  • 根付き木のある頂点からの部分木に対するクエリを処理
  • ある頂点がある頂点の部分木に含まれるかを高速に判定する
  • 上手くオイラーツアーを作るとパスのコストの総和が取れる
• 木をBFSしたときの順番で頂点を記録するBFS Euler Tourというのもある
  • オイラーツアーのbfs-order
  • 用途としては、ある頂点から一定の距離にある頂点に対して区間操作を行える

問題

• DFS Euler Tour
  • ECR6 New Year Tree Euler Tour + 遅延セグ木(区間set,区間or)
  • TCO 2015 Round1B Hard TheTipsTheTreeAndMan 用途2
  • SRM 621 Div1 Med TreesAnalysis 用途2
  • CF200 Water Tree Euler Tour + 遅延セグ木(区間set,区間総和) + セグメント木(最大値)
  • CF232 On Changing Tree Euler Tour + BIT + imos法
  • CF225 Propagating tree Euler Tour + BIT
  • AtCoder 根付き木のみさわさん Euler Tour + LCA (考察が難しい)
  • (難）AtCoder 白黒ツリー Euler Tour + BIT + LCA
  • RUPC2015 F. Tree/木 Euler Tour + BIT
  • CF442 Danil and a Part-time Job Euler Tour+遅延セグ木(バイナリでの区間xor,区間sum)
  • RUPC2017 Day3 ブロッコリー？カリフラワー？ (Broccoli or Cauliflower) 解説
• BFS Euler Tour
  • yukicoder No.899 γatheree 解説

オイラーツアーっぽくやる問題

• 頂点に入ったら操作をして、出るときに逆操作をする系の問題
  • yukicoder No.778 クリスマスツリー 解説

Google Code Jam Qualification Round 2017 問題と解説

https://code.google.com/codejam/contest/3264486/dashboard

問題

A. Oversized Pancake Flipper

＋と-から成る文字列Sがある。
連続する丁度K個の文字をひっくり返して全て+にする。
最小何回ひっくり返すと全て+になるか。
不可能ならIMPOSSIBLE

B. Tidy Numbers

N以下で最大のtidyな数を答えよ。
tidyな数 : 各桁毎で見ると狭義単調増加列である数

C. Bathroom Stalls

x=0, x=N+1に仕切りがしてある。
以下のルールでK個の仕切りを追加する。

• 左右の仕切りへの距離Ls,Rsのmin(Ls,Rs)が最大となるx座標に置く
• 複数個候補があるならば、その中でmax(Ls,Rs)が最大となるx座標に置く
• それでも、複数個候補がある場合は最も左に置く

K個目の仕切りを置いた時の、左右の距離の最大と最小を答えよ。

D. Fashion Show

N*NのグリッドにM個の'+','x','o'が置いてある。
'+'と'x'は1ポイント、'o'は2ポイント入る。
ポイントを最大化するが、以下のルールを守る必要がある。

• 左右上下の任意の二組のうち、どちらか1つが'+'
• 対角線上の任意の二組のうち、どちらか1つが'x'

以下の操作を行ってルールを守りつつポイントを最大化せよ。

• '+'と'x'を'o'にする
• 空の所に任意の記号を追加する

以下、解説

AtCoder Beginner Contest 058 / AtCoder Regular Contest 071 解説

http://abc058.contest.atcoder.jp
http://arc071.contest.atcoder.jp
www.youtube.com

以下、解説

HourRank 19 問題と解説

https://www.hackerrank.com/contests/hourrank-19/challenges
問題から

Recover the Arrays

N個の配列が与えられる。
これを先頭から「e a[0] a[1] ... a[e-1]」のルールで改行する。
何行になるか。

What Are the Odds?

N個の石の山に対してNimをする。
ゲームの前にAliceは[b,e]の範囲の石を全て取り去り、Bobが先手でNimが始まる。
AliceがNimで勝てる[b,e]の範囲は何通り？

Maximal Tree Diameter

N頂点の木がある。
以下の操作を1回だけ行うことで木の直径を最大化する。

• 辺を1つだけ削除
• 辺を1つだけ再び木に戻るよう追加

直径の最大値は？
※ 木の直径 : 木の中の最長距離

以下、解説