Codechef Cook 101 Editorial

Codechef Cook 101 で自分が解いた部分までの解説です (Div2 の4問目、Div1の3問目まで)。

各問題にはテストケース数T の制約があるけど省略しています。

Camp Or Not

概要

競プロキャンプに向けて問題を解く。 問題を解くスケジュールはD \leq 31 日決まっていて、 d _ i 日目に p _ i 問を解く予定である (1 \leq i \leq D, d _ i \leq 31, p _ i \leq 100)。

キャンプの選抜方法の候補は Q \leq 100 個あり、各候補には締め切り dead _ i と 必要問題数 req _ i が与えられている。 dead _ i 日目を含むその日までに req _ i 問以上解いていれば、キャンプに行くことができる。

スケジュール通りしたときに、各候補日についてキャンプに行けるかどうかを判定せよ。

解法

制約が小さいので愚直にやってもよいし、累積和を計算してもよい。

提出コード : Solution: 25750755 | CodeChef


Yalalovichik Numbers

概要

10進数で桁数がD の数 N が与えられる (D \leq 10 ^ 5, N の各桁は0でない)。 この数を i 回左に回した数を L _ i とする (例えば N=123 のとき、L _ 0 = 123, L _ 1 = 231, L _ 2 = 312)。

このとき L _ 0, L _ 1, \ldots L _ {D-1} の順で結合した数を M=10 ^ 9+7で割った余りを求めよ (N=123 なら 123231312 が答え)。

解法

答えは


(L _ 0 * 10 ^ {(D-1)D} + L _ 1 * 10 ^ {(D-2)D} + \ldots + L _ {D-1} * 10 ^ {0 \cdot D}) \bmod M

となる。10のベキの方は簡単に計算できるため x _ i := L _ i \bmod M が分かれば良い。

まず x _ 0 = N \mod M はそのまま計算できる。 次に x _ {i+1} については、 x _ i の先頭の桁を d _ i とすると x _ {i+1} = (x _ i * 10 - d _ i * 10 ^ D + d _ i) \bmod M という関係が成り立つので、d _ i さえ分かれば i=0,1,2,\ldots と順に求めることができる。

今、N を順番に左に回しているので d _ iNi 桁目である。 N は文字列として与えられているので d _ i はすぐに求められる。

提出コード : Solution: 25751450 | CodeChef


Yalalovichik Strings

概要

文字列 Tのすべての部分文字列(連続)の集合と Tのすべての部分列(連続とは限らない)の集合が一致するとき、 文字列 TYalalovichik string であるという。

長さN の文字列S が与えられる (N \leq 10 ^ 6)。 S の空でない部分文字列のうち Yalalovichik string であるものの個数を求めよ。

解法

どのような文字列が Yalalovichik string になるかを考える (以降、省略してY文字列と呼ぶ)。

まず1種類の文字が続く場合 (aaaaaa など) は明らかにY文字列になる。 そして文字列が2種類の連からなるとき (aaaabb など) もY文字列になる (どのように部分列をとっても a*b* の形になるため)。

逆に文字列が3種類以上の連からなるときはY文字列になることができない。 SS = c _ 0 \ldots c _ 0 c _ 1 \ldots c _ 1 c _ 2 \ldots と3つ以上の連からできているとする。 このとき部分列として c _ 0 \ldots c _ 0 c _ 2 \ldots を選ぶと、これは S からどのように部分文字列を 選んでも一致させることができないからである。

このことからSの部分文字列のうち

  1. aaa... のように1種類の文字からなる文字列
  2. a...ab...b のように2種類の連からなる文字列

のどちらかの形をした部分文字列の総数が答えになる。 重複を考慮して数えなければならないが、1 と 2 は独立に考えることができる。

(1) はアルファベット \alpha ごとにS 中の\alpha の最長の長さ l _ \alpha をもっておけば、 その総数は \sum _ {\alpha \in {a,b,\ldots,z}} l _ {\alpha} になる。

(2) は2種類のアルファベット \alpha, \beta (\alpha \neq \beta) とそれぞれの長さだけが重要になる。 そのためすべてのアルファベットの対ごとに、S 中で取りうるすべての長さの組の集合 P _ {\alpha, \beta}を計算する。 例えば aaabb と aabbb の2種類の部分文字列が Sに現れるとき、 P _ {a,b} = \{(3,2), (2,3)\} となる。

f(P _ {\alpha, \beta})\alpha, \beta をこの順に少なくとも1つずつ使って作れる文字列の個数としよう。 上の例だと f (P _ {a,b}) = |\{ab, abb, abbb, aab, aabb, aabbb, aaab, aaabb\}| = 8 になる。

基本的には各 (x,y) \in P _ {\alpha, \beta} について x*y の和を取ればよいが、これだと 重複を数えてしまうことがある (上の例だと ab, abb, aab, aabb の4種類)。 この問題は2次元平面上に点 (x, y) がいくつか与えられ、各点ごとに点と原点を隅に持つ長方形を 描いたときの面積の総和を求めることと等価である。 これはそれぞれの点 (x,y) をx座標でソートして、x座標が小さい方から順に点を見ていくことで計算できる。

異なる \alpha, \beta は独立に計算できるため、求める総数は \sum _ {\alpha,\beta \in {a,b,\ldots,z}, \alpha \neq \beta} f(P _ {\alpha, \beta}) である。

計算量はソートの部分が一番重くて O(N \log N) である (アルファベットの個数は定数個なので)。

実装は S を最初にランレングス符号化しておくと簡単になる (気がする)。

提出コード : Solution: 25753643 | CodeChef


Swag Subsets

概要

長さN の数列 A _ 1, A _ 2, \ldots, A _ NB _ 1, B _ 2, \ldots, B _ N が与えられる。

集合 {1,2,\ldots,N} の空でない部分集合S について、その swagness v _ s を以下のように定める。


v _ S = (\max _ {p \in S}{A _ p})(\max _ {p \in S}{B _ p})

このとき X = \sum _ {S \subseteq \{1,2,\ldots,N\}, S \not=\emptyset}{v _ s}10 ^ 9+7で割った余りを求めよ。

解法

簡単のために A _ i, B _ i はすべて相異なるとする。

まず B を無視した問題 v _ s = \max _ {p \in S}{A _ p} の総和を求めることを考える。 数列 A の順序に意味はないのでソートして A _ 1 \lt \cdots \lt A _ N と仮定してもよい。

このとき v _ S = A _ N となる S2 ^ {N-1} 個ある (N を取ればそれ以外は取っても取らなくても良いので)。 同様に v _ S = A _ {N-1} となる S のとり方は 2 ^ {N-2} 通りある (N は取らず N-1 は取る、それ以外はどちらでもよい)。

これはv _ S = A _ 1 となるまで同じように考えることができるので、答えは


X = 2 ^ 0 A _ 1 + 2 ^ 1 A _ 2 + \cdots + 2 ^ {N-1} A _ N

である。

もとの問題も今の考え方と同じようにする。 まず A _ i, B _ i のペアをA _ i をキーでソートして A _ 1 \lt \cdots \lt A _ N にする。 B についてはソートされているとは限らない。

また、B の値だけでソートした列を B' _ 1 \lt \cdots \lt B' _ N とする。

A _ N = \max _ {p \in S}{A _ p} となるS のとり方は、 N を取りそれ以外はどちらでもよいので 2 ^ {N-1} 通りある。 また B _ N をすでに選んでいるので B _ N \leq \max _ {p \in S}{B _ p} が成り立つ。 それらのうち

  1. B _ N \lt \max _ {p \in S}{B _ p}
  2. B _ N = \max _ {p \in S}{B _ p}

で場合分けする。

またk


B' _ 1 < \cdots < B' _ {k-1} < B' _ k = B _ N < B' _ {k+1} < \cdots < B' _ N

となる数とする。

ある集合S について(1) が成り立つ条件は B' _ k よりも右側にある数に対応する添字を取るときである。 B' _ lB' _ k より右にあるものとして、 B' _ {l} = \max _ {p \in S}{B _ p} となる場合を考える。 これは l より右にあるものは取らず、l (とすでに選んでいる N)を選び、それ以外はどちらでもよい取り方になるので、 S の選び方は2  ^  {l - 2} 通りある。

つまり任意の k \lt l \leq N についてB' _ {l} = \max _ {p \in S}{B _ p} となるS の取り方は 2 ^ {l-2} 通りある。 よって (1)の場合の求める数は A _ N * (2 ^ {k-1} B' _ {k+1} + 2 ^ {k} B' _ {k+2} + \cdots + 2 ^ {N-2} B' _ {N}) である。

(2) が起きるのは k より右側はすべて取らず、左側はどちらでもよい取り方になるので、 2 ^ {k-1} 通りある。よって求める数はA _ N * B' _ k * 2 ^ {k-1} となる。

以上からA _ N = \max _ {p \in S}{A _ p} となるときの答えは (1), (2) を合わせて


A _ N * (2 ^ {k-1} B' _ {k+1} + 2 ^ {k} B' _ {k+2} + \cdots + 2 ^ {N-2} B' _ {N}) + A _ N * B' _ k * 2 ^ {k-1}

である。

次にA _ {N-1} = \max _ {p \in S}{A _ p} となる場合を計算したい。 これはB' の列から B' _ kを削除してから、同じ方法で計算することができる。

以上よりX の計算方法は分かった。あとはこれを高速に計算できるように実装する必要がある。 数列 B' _ 1, \ldots, B' _ N に対して、上で必要になる操作は

  1. 与えられた区間 [l,r) について 2 ^ 0 B' _ l + 2 ^ 1 B' _ {l+1} + \cdots 2 ^ {r-l-1} B' _ {r-1} を求める (上の計算式と少し違うが、全体に2 ^ {何か} を掛けて調整できるためok)
  2. 要素の削除

の2種類。しかし(2) の要素の削除を考えると面倒なので、B' _ i が0 となる部分は無視するように (1) の計算方法を下のように変える。これで(2)の処理も簡単になる。

  1. 与えられた区間 [l,r)B' _ l, B' _ {l+1}, \ldots B' _ {r-1} のうち、非0 の要素を集めたものを B'' _ 0, B'' _ 1, \ldots B'' _ k として 2 ^ 0 B'' _ 0 + 2 ^ 1 B'' _ {1} + \cdots + 2 ^ {k} B'' _ {k} を求める
  2. B' _ i = 0 にする。

(1)の計算は次のように言い換えられる。 要素e _ i = (x _ i, c _ i):= (B' _ i, B' _ i \neq 0\ ?\ 1 : 0) とし、その上の 演算{\circ}e _ i \circ e _ j := (B' _ i + 2 ^ {c _ i} B' _ j, c _ i + c _ j) で定める。 このとき(1)の計算は e _ l \circ e _ {l+1} \circ \cdots \circ e _ {r-1} の第一成分と一致する。

この演算はモノイドになっている(単位元(0,0)) のでセグメント木が使える。 この演算は2 ^ i を前計算することで O(1) で計算できるので、(1)は O(\log N) で計算することができる。

これをB _ N, B _ {N-1}, \ldots, B _ 1 と順番に処理していけば良いので全体の計算量は O(N \log N) である。

また、A _ i, B _ i はすべて相異なるとしていたが、上の計算方法では重複した要素があっても問題なく計算できる。

提出コード : Solution: 25832307 | CodeChef

CodeChef Cook100 Editorial

CodeChef Cook100で解いた問題の解説です(div2の4問目、div1の3問目まで)。

Truth and Dare

Contest Page | CodeChef

概要

集合T_r, D_r, T_s, D_sが与えられる。 T_s \subseteq T_r かつ D_s \subseteq D_r のとき "yes"と、そうでないとき"no"と答えよ。

解法

set<int> で集合を管理して愚直に部分集合になっているか調べる。 制約が小さいのでvectorでも十分。

ソースコード: Solution: 24027534 | CodeChef

英語がとても読みづらい(というか未だに詳細を理解していない)。


Beautiful Garland

Contest Page | CodeChef

概要

R,Gの2種類からなる文字列s ( 2 \leq |s| \leq 10^5) が与えられる。 このsは先頭と最後がつながった一つの輪と考える。 この輪に対して以下の操作が高々1回できる。

  • 輪を2つの文字列s1, s2に分解する。 そしてs2を前後反転させてから再度s1とつなぐ。

この輪をRとGが交互に現れるようにできるか。

解法

まずRとGの数が同じでないとどうやっても交互にはできない。

次にRとGの数が同じときを考える。 この操作は同じ箇所に対して2回行うともとに戻ることがわかる。 そのためこの操作でsをRとGが交互になるようにできたならば、sはRとGが交互になっている文字列から操作を1回だけして作ることができる。逆も同じ。

そのため、 sをR, Gが交互になっている文字列から操作を1回だけして作ることができるか分かれば良い。

両端が同じ文字の位置で反転させると変化しない。そうでないなら部分文字列"RR", "GG"がちょうど一回ずつ現れる形になる。

以上からsの中のR,Gの数が同じであり、かつsがすでにRとGが交互になっている or 部分文字列"RR", "GG"がちょうど一回ずつ現れるときに"yes"、そうでないなら"no"である。

ソースコード: Solution: 24027634 | CodeChef


A-B Game

Contest Page | CodeChef

概要

A, Bの二人でゲームをする。このゲームは長さN \leq 10^5の一直線上に並んだマスの上で行われる。 各マスにはAのコマかBのコマが置かれているか何も置かれていないかのいずれかである。 プレイヤーAはAのコマを、プレイヤーBはBのコマを動かすことができる。動かすことができるのは駒があるマスから移動する先のマス までに何もないときに限る。つまり、すでに置かれているコマを飛び越すことはできない。

またコマごとに動かすことができる方向が事前に決まっており、マスの左端から順番に右方向、左方向、右方向、・・・である。 これはゲームの間変わることはない。

マスの初期状態が文字列sとして与えられ、ゲームはAの手番から始まる。このときAが勝つかBが勝つか答えよ。

 解法

大体のゲーム問題はNimに帰着できるのでNimにならないか考える。

まずコマを動かすことができる方向が右・左と交互になり、またコマを飛び越えて動かすことはできないので、 コマを左から2個ずつのペアにするとそれぞれ個別の独立したゲームが複数あるとみなすことができる (ただし奇数個あるときは別に考える必要がある)。

例えばs="A..B.A....B.BB"のときは次の3つの独立したゲームとみなせる:A..B, A...B, BB

ここで1つのペアに着目する。ペアにある空きマスの個数をLとする。 個別のゲームには次の2種類のパターンがある。

  • 両端が同じ文字のとき: これはNimではコマを動かすことができるプレイヤーだけが自由に取り除くことができる石の山とみなせる。石の個数はLである。
  • 両端が違うとき: どちらのプレイヤーも自分のコマを動かすことで任意の L' \lt Lについて空きマスがL'個である状態に持っていける。これはNimでは石の数がL個ある山と同じ性質をもち、Nimとみなせる。

これらからこのゲーム全体は次のようなゲームに言い換えられる:

プレイヤーA,Bのどちらも自由に取ることができる石山(普通のNim)、プレイヤーAだけが石を取り除ける山、プレイヤーBだけが石を取り除ける山の3種類があるNimの亜種

このゲームの戦略としては、普通のNimでゲームを行い、何もできない状態になったら 自分専用の山から石を1つずつ取り除くのが最善である。

普通のNimの石山はAが勝つならばA専用の1つの石、Bが勝つならば無とみなせるので、 A,B専用の石の山の数の大小のみでゲームの勝敗を決められる。

最後にコマの数が奇数のときは右端のコマ専用の石の山とみなせばよい(この処理をしていなくて1WA)。

ソースコード: Solution: 24042766 | CodeChef


Tree Unattractiveness

Contest Page | CodeChef

概要

N \leq 100 頂点からなる木Tと\{0,1,2\}のうちいずれかの数字が書かれたN 個のマーカーがある。 これらのマーカーを各頂点にちょうど一つずつ置いていく。 頂点vに置かれたマーカーの数字をn_vとする。

このときあるマーカーの置き方に対してそのスコアは \max\{|n_u - n_v| \mid 頂点u, vは木T 上で隣接している\} で定められる。 マーカーを適当においたときに得られるスコアの最小値を求めよ。

解答

ありうるスコアは0,1,2のいずれかであり、0かどうかはすぐ分かる (すべてのマーカーか同じときに限る)。 そのため1が作れるかどうかを判定すればいい。

スコアが1になるように置くためには、マーカー0と隣接するのは0か1、マーカー2と隣接するのは2か1でなければならない。また1は何と隣接しても良い。

このことから、木に置いた1のマーカーがある頂点で木を分断すると、分断されたあとの各連結成分に置かれるマーカーはすべて0か2になっていなければならない。

この性質から根を適当に決めて木dpができる。 パラメータは今の頂点に何を置いたか、部分木で0,1を使った個数となる (2を何個使ったかは部分木のサイズから計算できる)。 ただし愚直に"dp[頂点][置いたマーカー][0の数][1の数]=スコア1が作れる/作れない"というtrue/false としてしまうと計算量的に間に合わない。

ここから次元を減らすことを考える。上で説明したように1は何と隣接しても良いためできるだけ使わないほうが良いと 直観的に分かる。 そこでdp[頂点][置いたマーカー][0の数]="スコア1にするために必要な1のマーカーの個数の最小値"としても正しく計算できる。

このとき遷移は頂点vの子をc_1, c_2, \ldots, c_nとしたとき

  • 
dp[v][1][z] = dp[c _ 1][m' _ 1][z _ 1] + \cdots +  dp[c _ n][m' _ n][z _ n] + 1

    ただし、1 \leq k \leq nに対して 
m' _ k \in \{0,1,2\}, z _ 1 + \cdots + z _ n = z

  • 
dp[v][0][z] = dp[c _ 1][m' _ 1][z _ 1] + \cdots +  dp[c _ n][m' _ n][z _ n]

    ただし、1 \leq k \leq nに対して 
m' _ k \in \{0,1\}, z _ 1 + \cdots + z _ n + 1 = z

  • 
dp[v][2][z] = dp[c _ 1][m' _ 1][z _ 1] + \cdots +  dp[c _ n][m' _ n][z _ n]

    ただし、1 \leq k \leq nに対して 
m' _ k \in \{1,2\}, z _ 1 + \cdots + z _ n = z

このdpの計算量は一見O(N ^ 4)に見えるが、二乗の木dpの形なので(参考リンク: https://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594) O(N ^ 3)になる。

ソースコード: Solution: 24095010 | CodeChef

AtCoderのコンテストカレンダーを作った

この前AtCoderで非公式コンテストがあったけれども、メールはないし公式のカレンダーにも載ってなかったので 危うく出損ねるという事案があった。 非公式だししょうがないかなぁというのもあるけどやっぱりカレンダーは欲しいので自前で作った。

GitHub - okaduki/AtCoderAllContestCalendar

AtCoderのホームページの「予定されたコンテスト」にある項目を取ってきて突っ込んでるだけ。 いくつか問題点としては

  • コンテスト名をキーにしている → 後から時間などが変わったりしても反映されない
  • 終了時間は適当に設定している → ページには開始時刻しかないため

気になったらそのうち直す。

ABC020 D LCM Rush

問題

D: LCM Rush - AtCoder Beginner Contest 020 | AtCoder

1 \leq N,K \leq 10^9 が与えられるので \sum_{i=1}^{N}\mathrm{lcm}(i,K)を計算せよ。

解法

\displaystyle
\begin{align}
\sum_{i=1}^{N}\mathrm{lcm}(i,K) &= \sum_{i=1}^{N}\frac{i*K}{\gcd(i,K)}\\
&= \sum_{g \mid K} \frac{K}{g} \sum_{\substack{1 \leq i \leq N\\\gcd(i,K)=g}}i\\
&= \sum_{g \mid K} \frac{K}{g} \sum_{\substack{1 \leq gi \leq N\\\gcd(gi,K)=g}}gi\\
&= K\sum_{g \mid K}\sum_{\substack{1 \leq i \leq N/g\\\gcd(i,K/g)=1}}i
\end{align}

となるので後はKの約数 gごとにN' = N/g, K' = K/gとして

\displaystyle \sum_{\substack{1 \leq i \leq N'\\\gcd(i,K')=1}}i

が計算できればいい。

式変形が何をしているかと最後の総和の計算は解説 Editorial - AtCoder Beginner Contest 020 | AtCoder にあるので省略。

Game Theory (HackerRank)

この記事は 解説 Advent Calendar 2017の24日目の記事です。

adventar.org

以下のコンテストの解説です。 www.hackerrank.com

はじめに

競プロ!!Advent Calendarのこの記事 (競プロにおけるNim、Grundy数とNimK - かっさのなにか)に 触発されて書きました(というか解いてないことを思い出した)。

以下ではNim, grundy数などの知識を前提としています。 全く知識がない、あるいは不安な方は上の記事を読んでから解く and/or 解説を読むことを推奨します。 またxorを\oplusで表します。 特に記述がなければ、先手(プレイヤー1)と後手(プレイヤー2)が交互に手を打つゲームとし、 どちらのプレイヤーが勝つか出力する問題と思ってください。

Game of Stones

概要

Programming Problems and Competitions :: HackerRank

山に石がN個ある。 プレイヤーは山から2,3,5個いずれかだけ取り除ける。 取り除くことができなくなったプレイヤーの負けである。

解法

メモ化再帰

Tower Breakers

概要

Programming Problems and Competitions :: HackerRank

それぞれに石がM個ある山がN山ある。 プレイヤーは一つの山に石がX個あるとき、Y個に減らすことができる。ただしYXを割り切れなければならない。

解法

M=1のときは明らかに後手勝ち。 M>1とする。 Nが偶数ならば後手は先手と全く同じように操作ができるから後手勝ち。 Nが奇数ならば先手が最初に1つの山を1にすれば、上と同じ戦略が取れるから先手勝ち。

A Chessboard Game

概要

Programming Problems and Competitions :: HackerRank

15\times 15のチェス盤に石が1つ置いてある。 プレイヤーは(x,y)にある石1つを(x-2,y+1), (x-2,y-1), (x+1,y-2), (x-1,y-2)の いずれかに移動させる。ただし盤面外に移動させることはできない。 手を打つことができなったプレイヤーの負けである。

解法

メモ化再帰

Nim Game

普通のNimなので略。

Misère Nim

概要

Programming Problems and Competitions :: HackerRank

N山のNimをする。ただし普通のNimと違うところは 最後に石を取った人が負け (手が打てなくなったプレイヤーが勝ち) という点である。

解法

まずすべての山が1個の石からなるケースを考える。 このときは山の数が偶数なら先手勝ち、奇数なら後手勝ちである。

それ以外のとき、Sを(普通のNimと同じように)すべての山の石の個数の xorをとったものしてS = 0のとき、かつそのときに限り、後手勝ちであることを示す。

今、先手番でS = 0とし、先手が手を打つことでこれがS' \not= 0になったとする。

このとき、後手番ですべての山の石が1となることは無いことが分かる。 もしそうなったとすると、仮定から先手が選んだ山以外の石の数はすべて1であり、 先手が選んだ山はもともと1個より多くの石があったことが分かる。 しかしこのような状況はS=0の下では明らかに起こりえない。

これより、後手番では少なくとも1つの山は1個より多い石がある。 石が1個より多い山がちょうど1つあるときは、その山を01に減らすことで、 山の数が奇数となるようにすべての山を1にする ことができるので後手が勝つ。 そのような山が1つより多くあると、次の先手番ではすべての山が1個の石からなることはない。 従って通常のNimと同じようにしてS'' = 0となるように後手は手を打つことができ、 帰納的に後手勝ちであることがわかる。

逆に先手番でS \not= 0とすると、上の後手番の議論をそのまま適用できるので先手勝ちである。

よってすべての山が1個の石である場合を例外扱いすることで、普通のNimと同じように解ける。

解説だと全部1のときだけ場合分けすればいいとしか書いてないし、 それが正しそうな理由もよく分からなかった。 自分は実験してなんとなく規則性を見つけて適当に投げた。 実験せずに気付けるかと言われると微妙。

Nimble Game

概要

Programming Problems and Competitions :: HackerRank

N個の箱が一列に並んでいて、0,1,2,\dotsと番号が付いている。 各箱には石がc_i個入っており、プレイヤーはi番目の箱にある石1つを箱j \lt iに移すことができる。 先に手を打つことができなくなったプレイヤーの負けである。

解法

位置iにある石はそれより小さいj \lt iのどこへでも動かせる。 これはNimの1つの山にある石の個数がi個であるときの状況とちょうど対応している。 よってS = \displaystyle\bigoplus_{c_i \bmod 2 = 1}{i}0なら後手勝ちである。

Poker Nim

概要

Programming Problems and Competitions :: HackerRank

N山にそれぞれc_i個石がある。 プレイヤーは各ターンで1つの山から1個以上の石を取り除くか、あるいは追加することができる。 ただし、石を追加できる回数は各プレイヤー、各山に対して高々K回までである(個数は任意)。 最後の石を取り除いたほうが勝ちである。

解法

石を追加しないNimと全く同じ結果になる。 つまり、S = \bigoplus_i c_i = 0のとき、かつそのときに限り、後手必勝となる。 S=0のときは先手が石を取り除こうが追加しようが、後手は先手と同じことをすればNim和は0になる。 また石の追加は高々K回までしかできず、必ず有限回で終わるので後手必勝。

S \not= 0のときは適当に石を取り除いてS = 0の状態に持っていけるので先手必勝である。

Tower Breakers, Revisited!

概要

Programming Problems and Competitions :: HackerRank

N山にそれぞれh_i個石がある。 プレイヤーは1つの山にあるX個の石をY \lt Xまで減らすことができる。ただしY \geq 1Xの 約数でなければならない。 最後の石を取り除いたほうが勝ちである。

解法

山が1つでx個石があるとする。 このときのgrundy数がどうなるか考える。 xのある約数dgrundy数をg_dとすると、dの任意の約数d'にも xから遷移できるので、xgrundyg_xは少なくともg_d + 1以上である。 これをxのすべての約数にわたって考えればg_x = \displaystyle \max_{d \nmid x}{(g_d+1)}となる。

よくよく考えるとこれはxの重複を含めた素因数の個数(例えばx = 2^2\times3^1なら2+1=3)と一致することがわかる (素因数pxを割ったものならどれでも最大になるため) ので、各h_iのこれを調べて最後にそれらのNim和をとればよい。

Tower Breakers, Again!

概要

Programming Problems and Competitions :: HackerRank

N山にそれぞれh_i個石がある。 プレイヤーは1つの山にあるX個の石を、Z個の石からなるY個の山に分けることができる。 ただしY > 1, Y \times Z = Xでなければならない。 最後の石を取り除いたほうが勝ちである。

解法

基本的に1つ前の問題と同じで重複を含めた素因数の個数がgrundy数となる。 ただし2を素因数にもつときは一度だけしか数えない(2^iのグランディ数が1となるから)。

Chessboard Game, Again!

概要

Programming Problems and Competitions :: HackerRank

15\times 15のチェス盤にいくつか石が置いてある。 1つのマスに石が複数置いてあっても良い。 プレイヤーは(x,y)にある石1つを(x-2,y+1), (x-2,y-1), (x+1,y-2), (x-1,y-2)の いずれかに移動させる。ただし盤面外に移動させることはできない。 手を打つことができなったプレイヤーの負けである。

解法

素直にgrundy数を計算すれば良い。 盤面が15 \times 15で、ありうる遷移が高々4なので愚直に計算しても十分に間に合う。 位置(x,y)から動かせる手(x',y')についてx+y > x'+y'が成り立つから、 x+yが小さいものから順に計算することができる。

Digits Square Board

概要

Programming Problems and Competitions :: HackerRank

N \times Nのマスに整数x (1 \leq x \leq 9)が書かれている。 プレイヤーは盤面の面積が1より大きく、かつ素数でないような数字が少なくとも1つ書かれているとき、 盤面を水平方向か垂直方向に2つに分割することができる。 手を打つことができなくなったプレイヤーの負けである。

解法

素直にgrundy数を計算すれば良い。 dp(x_1,y_1,x_2,y_2) = \text{「元の盤面の部分長方形で左上が}(x_1,y_1)\text{で右下が}(x_2,y_2)\text{のgrundy数」} でメモ化再帰する。 素数でないものが部分長方形に入っているかを累積和で前計算しておけば、盤面が分割できるかどうかは\mathcal{O}(1)で判定できる。 上の状態が\mathcal{O}(N^4)あり、各状態からの分割方法は\mathcal{O}(N)あるので、 全体で\mathcal{O}(N^5)で計算できる。

Fun Game

概要

Programming Problems and Competitions :: HackerRank

長さN2つの数列A=(a_1,\dots), B=(b_1,\dots)がある。 プレイヤー1Aから、プレイヤー2Bから交互に数字を選んでいく。 ただしa_iがすでに選ばれていたらb_iを選ぶことができず逆も同様。 なのでちょうどN回の操作でゲームは終わる。

各プレイヤーが選んだ数の総和を計算し、大きい方が勝ち、同じなら引き分けである。

解法

この手の2つの数列から片方を選ぶみたいな問題は適当な評価値を決めて、 大きい方から選んだりdpしたりすることが多い気がするのでそうする。

このゲームは次のようなゲームに置き換えられる。

  • プレイヤー1は初期点として\sum_i{a_i}を持っている。
  • 数列C = (a_1+b_1, \dots) がある。
  • プレイヤー1Cから数字を一つ消すことができ、プレイヤー2は選んだ数だけプレイヤー1の点数を減らせる。
  • 最後にプレイヤー1の点数が正ならばプレイヤー1の勝ち、0なら引き分け、負ならプレイヤー2の勝ち。

なのでCを計算、ソートして、数字が大きいものから順番に消す、点数を減らすことを交互にすればよい。

Powers Game

概要

Programming Problems and Competitions :: HackerRank

文字列\heartsuit 2^1 \heartsuit 2^2 \heartsuit \dots \heartsuit 2^nがある。 プレイヤーは交互に\heartsuit+-のどちらかに1つずつ書き換える。 最後にすべての\heartsuitが無くなったら数式を計算し、17で割りきれたら後手勝ち、そうでなければ先手勝ち。

解法

x_i = 2^i \bmod 17だけを気にすればいいから、現れる数字は実質0 \leq x_i \lt 17だけとみなせる。 また、x_i = x_j (i \not= j)なるものがあれば、お互いに打ち消すように手を指すことができる (片方が+に書き換えたらもう片方は-に変える)ので、奇数個あるものだけ着目すれば良い。

あとはdp(i,r,B) = \text{「プレイヤー}i\text{が今までの和が}r\text{であり、残り使える集合が}B\text{から始めるときに勝てるか」} のようにBをbitとして使いメモ化再帰で解ける。 n \leq 10^6なのでn=1から順番に前計算しておけば良い。

Deforestation

Programming Problems and Competitions :: HackerRank

既出。同じ問題がhttps://beta.atcoder.jp/contests/agc017/tasks/agc017_dにある。 ハッケンブッシュ(Hackenbush)というゲームがあってそれの特殊な形である。

Tower Breakers - The Final Battle

概要

Programming Problems and Competitions :: HackerRank

N個の石がある。N=1となるまでプレイヤーは以下の操作を交互にする。

  • プレイヤー1N = n_1 + n_2 + \dots + n_k,\; k \geq 2となるように自由に石を分割する。
  • プレイヤー2はこの中からi番目の山を選び、N = x_iとしてゲームを続ける。このときコインi^2枚を得る。

プレイヤー1はプレイヤー2が得られるコインの枚数を最小化、プレイヤー2は最大化しようとする。 このとき最終的に得られるコインの枚数はいくらか。

解法

小さいケースで実験するとNがある程度大きくなっても答えは大きくならないと予想ができる。

そこでf(m) = \text{「答えがmとなるような最大のN」}とする。 明らかにfは単調増加になるから、f(m) \leq Nとなるような最大のmが求める答えである。 i番目の山を選ぶとコインをi^2払うことになるから、 f(m) = \displaystyle\sum_{m-i^2\geq 0}{f(m-i^2)}となる。 m=121f(m) \gt 10^{18}となるから愚直に計算しても実行時間は十分間に合う。

Rubyで競技プログラミング

最近Ruby on Rails チュートリアル:実例を使って Rails を学ぼうを終えてRubyの練習がてら競プロの問題をいくつか解いてみたので、 入出力の方法とかのメモ。

他に関連しそうな記事:

入出力

基本的なこと

  • getsで標準入力から1行文字列を受け取る
    • 改行も入るので取り除くにはgets.chopとかする
  • 整数への変換はto_i浮動小数to_f、文字列はto_s
  • str.splitで空白文字で分割
  • a.join(sep)で配列を区切り文字で連結した文字列を得る

よくあるパターン

  • 1行に整数が空白区切りであるとき
x_1 x_2 ... x_n
# 入力
# 個々の変数にとるとき
a,b,c = gets.split.map(&:to_i)
# 配列としてとるとき
xs = gets.split.map(&:to_i)

# 出力
puts xs.join(' ')
  • 複数行に整数があるとき
x_1
x_2
...
x_n
# 入力
xs = []
n.times { xs << gets.to_i }

# 出力
xs.map { |x| puts x }
  • 複数行に複数個数字があるとき
n_1 x_11 ... x_1(n_1)
...
n_m x_m1 ... x_m(n_m)
ns = [] # [n_1, ..., n_m]
xs = [] # [[x_11,...],...,[x_m1,...]]
3.times do
  line = gets.split.map(&:to_i)
  ns << line.shift
  xs << line
end

配列

  • Array.new(n,z)で長さn、初期値zの配列を作る
    • zを省略するとnilで初期化
    • 連番がほしければ(1..n).to_aでもできる
  • 二次元配列はArray.new(n){ Array.new(m) }で作る
  • <<で末尾に追加
  • popで末尾から、shiftで先頭から取り出す

AOJ 2403 The Enemy of My Enemy is My Friend

概要

問題文

頂点数Nの単純無向グラフが与えられる。 また各頂点には値B_iが割り当てられている。 このとき、頂点0を含む独立集合のうち値の総和の最大値を求めよ。

制約:  1 \leq N \leq 40 ,\ 0 \leq B_i \leq 10^3

解法

半分全列挙+高速ゼータ変換 (想定解法ではないらしい)。

頂点を半分に分けて、0を含む側をV_0、含まない側をVとする。 S \subseteq Vに対して関数ff(S) = 「SがVの独立集合ならば値の総和、さもなくば0」と定めて、 g(T) = \text{max}_{S \subseteq T}f(S)を高速ゼータ変換で求める。

あとはV_0側の独立集合Sを全列挙して\text{sum}(S) + g(Sに接続するVの頂点集合の補集合)の最大値を返せば良い。 計算量はO(\frac{N}{2}2^\frac{N}{2})