読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

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
  • 区間に対するクエリに対して高速に処理できる
  • ここが詳しい
  • 平方分割を理解しておくと、Mo's algorithmを理解しやすい
続きを読む

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

HL分解

  • Heavy-Light Decomposition
  • 木に対するクエリをO(log^2n)くらいで処理できる
  • 頂点にコストが載っているときと辺にコストが載っているときで処理が違ってくる
  • 辺にコストが載っている場合は以下のようにして頂点にコストを移す

http://pekempey.hatenablog.com/entry/2015/11/05/210543

以下、問題




頂点にコストがある問題

yukicoder No.399 動的な領主
HL分解 + 遅延セグ木(区間加算 + 区間総和)
yukicoder No.235 めぐるはめぐる(5)
HL分解 + 遅延セグ木(区間加算 + 区間総和)

辺にコストがある問題

[http://www.spoj.com/problems/QTREE/:title=
SPOJ QTREE - Query on a tree]
HL分解 + セグ木(区間max)
Codeforces #329 Div2 D. Happy Tree Party
HL分解 + セグ木(区間積)

【発展的話題】【工事中】HL分解の頂点の列は適切に配置すればオイラーツアーのそれと同じになる

つまり、二点間のパスに対して以外にも同じデータ構造で部分木に対してもクエリ操作が行えるということ。
こういう問題とか
こういう問題とか 解説
逆にオイラ―ツアーだけでHL分解の代用もできる?
「HL分解でやるものは逆演算が定義できそうな感じのものはだいたいEulerTour+segtreeでできる」という話もある。

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

オイラーツアー(Euler Tour)

使う目的

  • 根付き木のある頂点からの部分木に対するクエリを処理するのに長ける
  • ある頂点がある頂点の部分木に含まれるかを高速に判定する
  • 上手くオイラーツアーを作るとパスのコストの総和が取れる

以下、問題

Educational Codeforces Round 6 E. New Year Tree

http://codeforces.com/contest/620/problem/E
Euler Tour + 遅延セグ木(区間set,区間or)

TCO 2015 Round1B Hard TheTipsTheTreeAndMan

https://community.topcoder.com/stat?c=problem_statement&pm=13717
Euler Tourを「ある頂点がある頂点の部分木に含まれるかを高速に判定する」用途で使用

SRM 621 Div1 Med TreesAnalysis

http://community.topcoder.com/stat?c=problem_statement&pm=13086
Euler Tourを「ある頂点がある頂点の部分木に含まれるかを高速に判定する」用途で使用

Codeforces Round #200 (Div. 1) D. Water Tree

http://codeforces.com/contest/343/problem/D
Euler Tour + 遅延セグ木(区間set,区間総和) + セグメント木(最大値)

Codeforces Round #232 (Div. 1) C. On Changing Tree

http://codeforces.com/contest/396/problem/C
Euler Tour + BIT + imos法

Codeforces Round #225 (Div. 1) C. Propagating tree

http://codeforces.com/contest/383/problem/C
Euler Tour + BIT

天下一プログラマーコンテスト2015本戦 F. 根付き木のみさわさん

http://tenka1-2015-final-open.contest.atcoder.jp/tasks/tenka1_2015_final_f
Euler Tour + LCA
考察が難しい。

(難)NJPC 2017 H. 白黒ツリー

http://njpc2017.contest.atcoder.jp/tasks/njpc2017_h
Euler Tour + BIT + LCA

RUPC2015 F. Tree/木
Euler Tour + BIT

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


以下、解説

続きを読む

競技プログラミングにおける遅延評価セグメント木問題まとめ

遅延評価セグメント木

問題

[l,r)をvにする +α

[l,r)にvを足す +α

その他

高難易度の遅延セグメント木