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

hamayanhamayan's blog

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

競技プログラミング

XOR

  • 排他的論理和
  • 性質1「交換則、結合則が成り立つ」2「a xor a = 0」3「ある数xのb番目のビットが1である <=> x mod 2^(b+1) ≧ 2^b」性質4「0≦aのとき、4a, 4a+1, 4a+2, 4a+3のxor和は0」
  • 方針1「xor計算は各ビットで独立なので別々に計算」2「trieを使ったxorの最大最小探索がある解説」
  • 数列の各数をビット毎に分解して行列と考えて、ガウスの消去法を行うことで正規化する問題がある
    • 問題
    • 任意要素の入れ替えができる、隣り合う要素でなくてもXORできる→行基本変形ができる
    • この場合に行標準形に変形して、正規化できるみたい。これはガウスの消去法などで求まる
    • ガウスの消去法の結果として、行列のランクRも求めることができる
      • すると解の個数は2^(自由度) = 2^(N-R)となるが、これはsubsetでxorすることで作ることのできる数の個数に対応している。
      • けんちょんさんの記事が最強
  • 無向グラフを任意回移動してxorを取って回る -> サイクル基底を使うかも
  • 2ビットのXOR+ShiftはGCDに帰着できるかも 解説 類題
  • パスの辺全てにXORを取るのは、頂点について繋がっている辺のコストのXORを取ったA[i]を用意した時に、端点A[s]とA[t]のみにXORを取るのと同じ これ
  • 01の場合、a xor b = a(1-b) + b(1-a)となる 問題

問題

競技プログラミングにおける畳み込み問題まとめ（FFT,アダマール変換,メビウス変換,ゼータ変換）

競技プログラミング

2種類の畳み込み

  • subset convolution
    • 資料1 資料2 資料3
    • ゼータ変換とメビウス変換は逆変換の関係にある
    • ゼータ変換（状態xを含む状態yを全列挙）
      • 高速ゼータ変換でO(n2^n)
      • g[x] = sum{y⊆x}f(y)　→　rep(i, 0, N) rep(msk, 0, 1 << N) if (msk & (1 << i)) sm[msk] += sm[msk ^ (1 << i)];
      • g[x] = sum{x⊆y}f(y)　→　rep(i, 0, N) rep(j, 0, 1 << N) if (!(j & (1 << i))) f[j] += f[j | (1 << i)];
      • 参考 高速ゼータ変換は環で動く（+, *, max, gcdなど）
    • メビウス変換（状態xの部分状態yを全列挙）
      • 高速メビウス変換でO(n2^n)
      • g[x] = sum{y⊆x}(-1)^|x-y| g[y]　→　 rep(i, 0, N) rep(j, 0, 1 << N) if (j & (1 << i)) f[j] -= f[j ^ (1 << i)];
      • （メビウス変換じゃないけど似てる）g[x] = max{y⊆x} g[y]　→　rep(i, 0, N) rep(j, 0, 1＜＜N) if(j & (1 ＜＜ i)) chmax(f[j], f[j + (1 ＜＜ i)])
  • normal comvolution
  • kazumaさんのgcd畳み込み（すごい）
  • 👊パンチ👊ゼータ変換👊パンチ👊

問題

https://twitter.com/uwitenpen/status/869609817794502656

【発展的話題】 NTT

CodeChef May Challenge 2017 問題と解説

競技プログラミング

https://www.codechef.com/MAY17

Chef and his daily routine

CESから成る文字列が与えられる。
それは1日のある時刻での作業を時系列順で伝えている。
その人は一日を料理する(C),食べる(E)、寝る(S)の順でこなす。
正しく時系列順で伝えられているかどうか判定せよ。

Courses in an university

N個の授業があり、i番目の授業を履修する為には[0,i)の中から少なくともA[i]個、履修してある必要がある。
全部の授業を履修可能にするために履修しなくても良い授業の最大個数は？

Median of adjacent maximum numbers

2N個の配列Aがある。
ここから、B[i] = max(A[2i-1], A[2i])として配列Bを作る。
配列Aを上手くシャッフルして配列Bの中央値を最大化したい。
中央値の最大値と、その時の配列Aを答えよ。

Chef and Sub Array

0と1からなる長さNの配列Aがある。
これについてP個のクエリに答える。

  • '?' : 配列中のある連続するK個に含まれる1の数の最大値を答える
  • '!' : 配列を左にシフトする

Chef and Subsequences

N個の配列Aがある。
この配列の部分列のうち、その積がK以下であるものは何通りか。

Blocked websites

N個の文字列がある。
各文字列は

  • ＋:通す
  • －:通さない

が決まっている。
フィルタリングは文字列を使うが、prefixが同じ文字列を通さないようにできる。
フィルタリングの文字列の長さの総和を最小化して、フィルタリングの文字列を決めよ。

Gotham PD

（問題文がかなり複雑なので本文を読んだほうがいいです）
N頂点の木がある（頂点は1～Nというわけではないので注意）。
各頂点には鍵があり、頂点Rを根とした木を構築している。
Q個のクエリを処理する。
しかし、このクエリは暗号化されており、初期鍵は0で全てxorすることで復元できる。

  • 0 u v k : 鍵kを持つ頂点uを作り、親は頂点vとする
  • 1 v k : 頂点vから頂点Rへのパスの全ての鍵について key[i] xor kを計算し、その最小と最大を返す。最小と最大のxorが次のクエリの鍵となる

Long Sandwich

長さNのサンドイッチがある。
これをK以下のまとまりになるよう切る。
まとまりの個数を最小としたときの、切り方は何通りあるか(mod M)。

以下、解説

続きを読む

競技プログラミングにおける最短経路問題まとめ [ダイクストラ, ベルマンフォード, ワーシャルフロイド]

競技プログラミング

最短経路を求めるには

  • ダイクストラ【単一始点最短経路】
  • ベルマンフォード（Bellman-Ford）【単一始点最短経路】
    • ダイクストラと違い、負のコストを含む辺があっても正しく動作する
    • 参考
    • アルゴリズム
      • 1. N-1回ループして最短経路を求める O(NM)
      • 2. N回ループして負のサイクルを見つける O(NM)
    • 最長距離を求めるようにも書け、その場合は正のサイクル検出ができる(ABC061D)
  • 幅優先探索 BFS【単一始点最短経路】
    • 辺のコストが1ならばBFSで十分
  • ワーシャルフロイド【全頂点間最短経路】

問題

発展的話題 KSP: k-th shortest path （裏取りできてない情報が含まれます）

コメントで指摘があったので、いったん取り下げた。
全く理解できてないですね…キーワードだけ残しておくことにした。
公開から5年くらい経って、ちょっと調べてみると日本語の記事も多く出ていたので、興味がある方は以下キーワードをもとにそちらを参照お願いします。

  • 問題
  • Yen's Algorithm
    • ↑の問題の想定解法。解説は細かく書いてあるので、見て理解してもいい
    • 計算量はO(KN(M+NlogN)), Kはk-thのk、Nは頂点数、Mは辺数
    • ダイクストラの派生っぽい。たぶんlaycrsさんのツイートで言及している方法と同じだと思う
  • Eppstein's Algorithm
    • ↑の問題で使えるかわからないが、こういうのもある。k shortest path routing - Wikipediaを見ると、Yenはlooplessで使えて、Eppsteinはloopyでも使えるとあるので、Eppsteinの方が上位互換なのかな？（未検証）

Google Code Jam Round 2 2017 問題と解説

競技プログラミング

https://code.google.com/codejam/contest/5314486/dashboard#s=p0

A. Fresh Chocolate

Nグループあり、それぞれG[i]人いる。
1パックにP個のチョコが入っている。
あるグループにチョコを上げる時はパックを開けてチョコを1人に1つ渡す。
もし、チョコが余った場合は次のグループに渡すのに使うが、その場合は新鮮でないチョコが次のグループの一部（または全部）にいってしまう。
適切な順でNグループにチョコを渡すことで、最大何グループが全員新鮮なチョコを受け取れるか。

B. Roller Coaster Scheduling

N行1列のコースター、C人の人間、M枚のチケットがある。
i番目のチケットにはB[i]さんが前からP[i]番目の席に座れると書いてある。
コースター運営者は"プロモート"を上手く行い、使うコースターの数を最小化した上で、プロモート回数も最小化したい。
以下のルールが満たされる必要がある。

  • 同じコースターに同一人物は複数人乗れない
  • 同じコースターの同じ席に複数人乗れない
  • プロモートをすると、あるチケットのP[i]をより小さい数に変更できる

C. Beaming With Joy

R行C列の盤面があり、以下の構成要素から成る。

  • / : ／となってる反射板(ビームを反射する)
  • \ : ＼となってる反射板(ビームを反射する)
  • - : 左右にビームを発射する発射機
  • | : 上下にビームを発射する発射機
  • # : 壁(ビームが止まる)
  • . : 何もない

2種類の発射機は回転させることで-を|に、|を-に変えることができる。
発射機を適切に回転させて、以下のルールを全て満たすようにできるか。
できれば、回転後の盤面も答えよ。

  • 全ての何もない所にビームが来ている
  • 発射機にビームが当たってはいけない

D. Shoot the Turrets

未読

以下、解説

続きを読む

Codeforces Round #413 問題と解説

競技プログラミング

http://codeforces.com/contest/799

A. Carrot Cakes

T秒でK個ケーキを焼ける装置が1つある。
同じ装置をもう一つだけD秒かけて用意できる。
用意すると、並行してケーキを焼ける。
同じ装置を用意することで、用意しない場合より早くN個のケーキが作れるか
（同時刻にできる場合はNOとする）

B. T-shirt buying

N個のTシャツがあり、i番目の値段はP[i],表がA[i]色,裏がB[i]色となっている。
M人の人が以下のルールでTシャツを買うとき、それぞれいくら払ったか(買わなかったら-1)

  • i番目の人の好きな色はC[i]
  • 表が裏が好きな色のTシャツの中で値段が最小の物を買う

C. Fountains

N個の噴水と、C枚のコイン、D個のダイアがある。
N個の噴水から丁度2個の噴水を買う。
i番目の噴水はP枚のコインorP個のダイアで買うことができ、美しさはB[i]である。
2つの噴水の美しさの和の最大値は？

D. Field expansion

H×Wの長方形の辺に幾つか数字を書けてA×Bの長方形が完全に乗るようにしたい。
数字はN個あり、最小で何個必要か。

以下、解説

続きを読む

競技プログラミングにおける最小費用流問題まとめ

最小費用流

  • Min Cost Flow
  • 最大流の辺にコストがついたもので、ソースからシンクへある量のフローを流す時の各辺のフローとコストの積の総和を最小化する
  • コストを損失と考えて最大化問題を解く考え方がよく使われる(こっちでそれを練習してからの方がいいかも)
  • アルゴリズムは2つあるっぽく、制約が厳しいときは使い分けないといけないかも（不確定な情報）

1. O(V^2UC)のやつ -> 辺の数が多いときはこっち 実装
2. O(fElogV)のやつ -> 費用が大きいときはこっち 実装

  • ネットワーク単体法が最速アルゴリズムらしいが、今まで上の2つで通らなかった問題はみたことがない
  • こういう発展的話題もある
  • 最小費用循環流というもある（ソースとシンクが無い最小費用流らしい、最小費用流に帰着できるらしい）
  • コストが「個数^2」とか「2^個数」とかに成るやつは差分のコストを追加していくと表現できる 例題

問題

コストが実数

難しくてまだ通してない

未処理

http://area.hateblo.jp/entry/2014/02/22/010536