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

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

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を理解しやすい

問題

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
ある区間においてある数値よりも大きい要素の数、小さい要素の数を求めるのに使用。難しめ。
分割区間のidxを持っておき、ソートしておくと、lower_boundなどで1区間に対し対数時間で個数が得られる。

競技プログラミングにおける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分解 + セグ木(区間積)

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

オイラーツアー(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


以下、解説

続きを読む

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

遅延評価セグメント木

セグ木に区間に対して値の変更を行えるデータ構造。
色んなパターンがあるので、まとめついでに。
あと、よくHL分解と一緒に使われる(難しくなる)

以下、問題

[l,r)にvを足す + [l,r)の最大値

CODE FESTIVAL 2015 決勝 D. 足ゲームⅡ

http://pekempey.hatenablog.com/entry/2015/11/15/193946

[l,r)にvを足す + [l,r)の最小値

ARC 045 B. ドキドキデート大作戦高橋君

http://arc045.contest.atcoder.jp/tasks/arc045_b

天下一プログラマーコンテスト 2016 予選B D. 天下一数列にクエリを投げます

http://tenka1-2016-qualb.contest.atcoder.jp/tasks/tenka1_2016_qualB_d
考察が難しいので入門ではない。

[l,r)にvを足す + [l,r)の総和

ABC 035 C. オセロ

http://abc035.contest.atcoder.jp/tasks/abc035_c
imos法でいけるが、verifyとしての例が紹介されていた
http://mmxsrup.hatenablog.com/entry/2017/01/02/191018

yukicoder No. 399 動的な領主

http://yukicoder.me/problems/no/399
HL分解と併用

[l,r)をvにする + [l,r)の総和

yukicoder No. 318 学学学学学

http://yukicoder.me/problems/899

yukicoder No. 230 Splarraay スプラレェーイ

https://yukicoder.me/problems/no/230

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

http://codeforces.com/contest/343/problem/D
Euler Tourと併用

[l,r)をvにする + [l,r)のOR和

Educatinonal Codeforces Round 6 E. New Year Tree

http://codeforces.com/contest/620/problem/E
EulerTourも必要

[l,r)にxor1する + [l,r)の総和

NJPC2017 H. 白黒ツリー

http://njpc2017.contest.atcoder.jp/tasks/njpc2017_h
HL分解も必要

square869120Contest #2 H. Counting 1's

http://kmjp.hatenablog.jp/entry/2016/04/23/1200

神様向けの問題

AOJ 2450. Do use segment tree

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2450
HL分解も必要。人が解く問題じゃない。

yukicoder No. 235 めぐるはめぐる(5)

http://yukicoder.me/problems/640
必要な知識は揃ってるはずなのに解けない問題