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

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

hamayanhamayan's blog

競技プログラミングにおけるシフトセグメントツリー問題まとめ

シフトセグメントツリー

  • shifted segment tree(造語)
  • 一般的なセグメントツリーに全ての要素をシフトさせる機能を付けたもの
  • ルートとなる頂点を用意してそこを基準として更新や取得を行うというだけ
  • 傾向になるかもしれないのでまとめておく
続きを読む

競技プログラミングにおける桁DP問題まとめ

桁DP

  • dp[桁数][条件][上限ギリギリか]
  • Digits DP
  • 参考サイト

http://pekempey.hatenablog.com/entry/2015/12/09/000603
http://torus711.hatenablog.com/entry/20150423/1429794075

続きを読む

yukicoder contest-161 解説 (yukicoder No.504 505 506 507)

http://yukicoder.me/contests/163
以下、解説

続きを読む

CSAcademy Round #25 問題と解説

https://csacademy.com/contest/round-25/

0-Sum Array

N個の数列Aがある。
i番目だけ-1倍して数列の総和を取ると0になるような最小のiを求めよ。
無ければ"-1"

Suspect Interval

N個の全ての要素が異なる数列Xがある。
以下の性質を満たすA,Bの中で、B-A+1の最大値を答えよ。

  • 1 ≦ A ≦ B ≦ 10^5
  • 区間[A,B]に数列Xの要素がただ1つだけ含まれる

Rectangle Path

N行M列の盤面があり、0だと空、1だとブロックがある。
この盤面に横H縦Wの長方形のブロックが置いてあり、パズルの箱入り娘のようにスライドさせて、(Sr,Sc)から(Fr,Fc)に移動させる。
最短、何回のスライドで移動できるか。無理ならば"-1"

Min Ends Subsequence

N個の順列Aがある。
この順列の部分列の中で最初と最後の要素が他の要素よりも大きい数列を取り出す。
このような数列の要素数の最大は?

Zone Capture

N行M列の盤面があり、0は白、1は黒で着色されている。
この盤面のうち1マスを白から黒に着色できる。
この時、白の連結成分のうち、盤面の端に接していないものは黒に変化する(囲碁碁石が取れる感覚)。
盤面全体で黒のマスを最大何個作れるか。

以下、解説

続きを読む

競技プログラミングにおけるMo's Algorithm問題まとめ

Mo's Algorithm

  • pekempeyさんの最強解説
  • pekempeyさんの記事に乗っていることですが「要素が更新されない」「クエリの先読みが可能」「区間 [L,R] の結果から [L-1, R], [L+1, R], [L, R-1], [L, R+1] の結果が容易に得られる」という条件が大切
  • 計算量はO( (N+Q)√N) で、追加削除はO(1)かO(logN)が求められることが多い、答えを求める部分はO(sqrt(N))でも間に合う
  • Mo's Algorithmの上位互換があり、永続データ構造と組み合わせることで解ける問題が増える
  • この上位互換では範囲を増やすのは自由だけど、減らすのは難しい(Rollbackでしか出来ない)場合は上位互換を使う

実装例

第3回 ドワンゴからの挑戦状 本選 B. ニワンゴくんの約数

http://dwacon2017-honsen.contest.atcoder.jp/submissions/1227819
あまりに遅いダメコードだけど、Mo's Algorithm的にはあってる

CodeChef April Challenge 2017 問題と解説

https://www.codechef.com/APRIL17?order=desc&sortBy=successful_submissions

Similar Dishes

T組の料理がある。
各料理は4つの材料で構成されている。
T組の料理が似ているならば"similar"、似てないならば"dissimilar"をそれぞれ答えよ。
※似ている : 材料のうち半分以上が同じ

Dish Of Life

N個の島とK種類の材料がある。
i番目の島ではP[i]種類の材料が集まる。

  • 全ての島を回っても材料が全て集まらないなら"sad"
  • 全ての島を回らないと材料が全て集まらないなら"all"
  • 全ての島を回らなくても材料が全て集まるなら"some"

を出力せよ

Bear and Row 01

1と0から成る文字列Nが与えられる。
行える操作は「ある1に対して端っこに行くか隣に1がある状態まで動かす」操作である。
この操作は移動距離+1のコストがかかる。
全ての1を左に移すために必要なコストの総和の最大値は?

Bear and Clique Distances

N頂点ある。
この頂点のうち、1~K番目の頂点は完全グラフであり、辺のコストはXである。
これとは別にM本の辺があり、A[i]とB[i]をコストC[i]で繋いでいる。
頂点Sから他の頂点への最短距離を求めよ。

Chef and Divisor Tree

Divisor Treeは以下のルールで作られた根付き木である。

  • 根はある数
  • ある親の子はノードに書かれた数の約数(書かれた数は除く)
  • 数が1となると葉
  • ノードにはコストがあり、そのコストはノードの次数と等しい

(問題文のテストケースに図があるのでそれをみると分かりやすい)
A<=n<=Bをみたす全てのnに対して、Divisor Treeを作り、根からある葉へのパスのコストの総和の最大値を計算し、その総和を答えよ。

Stable market

N個の数列Aがある。
その数列に対してQ個のクエリについて答える。
各クエリでは、[L[i],R[i]]の範囲でのK[i]連続区域は何個あるかを答える。
K連続区域とは同じ数がK個以上連続しているまとまりのこと。

Bear and Random Grid

命令文Sと、N*Nの盤面がある。
盤面は'.'なら通れて、'#'だと通れない。
全てのセルについて、そこを初期地点として、命令文で動ける最大命令数を求める。
'.'のセルで最大命令数を求めたとき、そのxor和を答えよ。
盤面に'#'が出る生成規則がある(割愛)。

Chef and Digits

A[0]~A[9]が与えられる。
ある数について、現れる文字をカウントした時に、ある数iの個数が丁度A[i]となったとき、その数は嫌いとされる。
L<=n<=Rを満たす全てのnに対して、嫌いでない数は何個あるか。

Serejs and Billiards

マラソン問題
ビリヤードをする。
(0,0)から(N,N)の盤面がある。
ボールがM個あり、4*M回まで操作ができる。
操作のルールは
1. 加速度としてdx,dyを-1,0,+1で指定し、E回分だけ動かす。
2. 端に当たると跳ね返る
3. (-1,-1),(-1,N+1),(N+1,-1),(N+1,N+1)のいずれかに入ると得点

Heavy-Light Decomposition

与えられた根付き木をHL分解する。

  • Light辺を通るときは長さLでコストL
  • Heavy辺を通るときは長さLでコスト(ceiling[log_2L] + 1)

かかる。Heavy辺を上手く選んで、根から全ての葉へのコストの最大値を最小化せよ。

以下、解説

続きを読む

HackerRank Week of Code 31 問題と解説

https://www.hackerrank.com/contests/w31/challenges

問題

Beautiful Word

  • 隣り合う文字が同じではない
  • 母音("aeiouy")が隣り合わない

ならば、その文字列は美しい。
文字列wが美しいなら"Yes", そうでないなら"No"を出力せよ

Accurate Sorting

長さNの0~N-1から成る数列Aがある。
隣り合う数の差が1なら隣り同士をスワップできる。
このルールでスワップして、昇順に並べることができるか。

Zero-One Game

長さNの0,1から成る数列がある。
この数列に対して以下のルールでゲームをするとき、先手Aliceと後手Bobのどちらが勝つか

  • 数列から1つ数を消していくが、左右が0で挟まれている数のみ消せる
  • 端の2つの数は消せない
  • 消せなくなったら負け

Spanning Tree Fraction

N頂点M辺の連結無向グラフがある。
辺についているコストA[i],B[i]について、(A[i]の総和)/(B[i]の総和)が最大となるようにこのグラフを全域木にする。
その最大値を既約分数の形で答えよ。

Colliding Circles

N個の数列Rがある。
等確率で数列内の2要素を取り出して消し、足して追加するという操作を行う。
この操作をK回繰り返したときに、最終的な数列Rの要素の二乗の総和*πの期待値を答えよ。

Nominating Group Leaders

N人の人物がいる。
iさんはv[i]さんに票を入れている。
これに対してクエリに答える。
[L,R]の票を集めた時に、丁度X票獲得した人を答えよ。
複数人いる場合は、最もIDが小さい人を答える。

Split Plane

以下のクエリを処理する。
N個の線分があり、線分で区切られた領域の連結成分の個数を答えよ。

続きを読む