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

hamayanhamayan's blog

Codeforces Round #404 問題と解説

競技プログラミング

http://codeforces.com/contest/785

A. Anton and Polyhedrons

http://codeforces.com/contest/785/problem/A
"Tetrahedron"なら4面体, "Cube"なら6面体, "Octahedron"なら8面体, "Dodecahedron"なら12面体, "Icosahedron"なら20面体である。
N個の上の5つの内の立体の種類が与えられるとき、全ての立体の面数の総和は？

B. Anton and Classes

http://codeforces.com/contest/785/problem/B
N個のチェスの授業、M個のプログラミングの授業がある。
各授業で開始時間と終了時間が決まっている。
チェスとプログラミングの授業を1つずつとる時、2つの授業の間の休み時間の最大値は？
（必ずかぶる場合は0とする）

C. Anton and Fairy Tale

http://codeforces.com/contest/785/problem/C
N個収容できる倉庫がある（最初はN個入っている）。
以下の行動が毎日繰り返される時、何日目で終了するか。

（i日目とする）
1. 倉庫からi個取り出す（取り出し切れないor空っぽから終了）
2. M個倉庫に入れる（N個を超える時は満杯のN個が倉庫に入った状態にする）

D. Anton and School - 2

http://codeforces.com/contest/785/problem/D
文字列Sの（非連続OKの）部分列のうち、RSBSである部分列は何通りあるか(mod10^9+7)。
※ RSBS: (),(()),((())), (((()))), ... みたいな文字列

E. Anton and Permutation

http://codeforces.com/contest/785/problem/E
N個の数列があり、中身は{1,2,3, ... ,N}である。
これについてQ個の以下のクエリを処理する。

1. L[i]番目とR[i]番目の要素をスワップする
2. 数列全体について反転数を答える

続きを読む

競技プログラミングにおける連立方程式問題まとめ

競技プログラミング

連立方程式を使った解法について

問題

反復法

ガウスの消去法

わからない

続きを読む

Codeforces Round #403 問題と解説

競技プログラミング

http://codeforces.com/contest/782

A. Andryusha and Socks

http://codeforces.com/contest/782/problem/A
1～N番のN組の靴下がある。
左右合わせて2N個の靴下をある順番で受け取る。
もう片方の靴下を受け取るまで机の上にもう片方の靴下を置いておき、もう片方が来たらどちらも片付ける。
机の上に最大何個の靴下が置かれることになるか。

B. The Meeting Place Cannot Be Changed

http://codeforces.com/contest/782/problem/B
N人いる。
それぞれ位置X[i]で歩く速さはV[i] m/秒である。
どこか一箇所に集まる時に最短何秒かかるか。

C. Andrysha and Colored Balloons

http://codeforces.com/contest/782/problem/C
N頂点の木がある。
各頂点に色をつけるが、a - b - cと連結している場合はa,b,cは違う色で塗る必要がある。
つまり、2頂点先までで同じ色があるとダメ。
必要な色数の最小数と、その場合の塗り方を答えよ。

D. Innokenty and a Foodball League

http://codeforces.com/contest/782/problem/D
N個のクラブ名（三文字）と町の名前の組がある。
以下のルールで全ての組に対して三文字の名前を決めることができるかを判定せよ。
できるならば、そのパターンを示せ。
1. 「全てクラブ名にする」か「クラブ名の先頭2文字と町の名前の先頭1文字を合わせる」
2. クラブ名が同じ他のクラブが存在する場合は「全てクラブ名にする」ことで命名ができない

E. Underground Lab

http://codeforces.com/contest/782/problem/E
N頂点M辺の無向グラフがある。
長さfloor(2N/K)以下のパスをK本用意することで全ての頂点を通るようにする。
そのパスの構成を答えよ。

F. Axel and Marston in Bitland

http://codeforces.com/contest/782/problem/F
N頂点M辺の有向グラフがあり、辺には0か1が書かれている。
これに対しPとBから成るパターン文字列を考える。

S[0] = P
S[i] = S[i - 1] + inv(S[i - 1])
inv関数はPとBを反転させる関数
つまり、S = {P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP}

Pは0にBは1に対応している。
頂点1からスタートしてパターン文字列に沿って頂点を移動していく時、移動できる距離の最大値を答えよ。
もし、移動距離が10^18を越える場合は-1と出力せよ。

続きを読む

HackerRank Game Theory の勧め

競技プログラミング

HackerRank Game Theory

https://www.hackerrank.com/5-days-of-game-theory
Typical DP Contestというのがありますが、それのゲーム理論版

ゲームの勝敗判定をする問題を解く選択肢
  • 必勝法・貪欲法（必勝の条件・法則がある）
  • バックトラッキング（遷移先に負け状態が1つでもあれば勝ち状態）
  • Nim/Grundy数

hamayanhamayan.hatenablog.jp

問題

Game of Stones

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-game-of-stones
T個のクエリがある。N個の山があり、そこから2,3,5個のいずれかを取る。
取れなくなったら負け。初手が勝ちならFirst, 後手が勝ちならSecond

Tower Breakers

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers
T個のクエリがある。N個、数Mがある。各数をその数の約数のどれかに変換する操作をする。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2

A Chessboard Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-1-a-chessboard-game
T個のクエリがある。15*15のマスに1つ駒がある。
この駒は、(x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2)に移動できる。
移動できなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond

Nim Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-2-nim-game
T個のクエリがある。各クエリは、N個の石の個数がS[i]の石の山がある。
順番に石が残っている山から1つ以上の石を取り除く操作をする。
取り除く石がなくなったら負け。先手が勝ちならFirst, 後手が勝ちならSecond

Misera Nim

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/misere-nim
T個のクエリがある。各クエリは、N個の石の個数がS[i]の石の山がある。
順番に石が残っている山から1つ以上の石を取り除く操作をする。
最後に石を取り除いた方が負け。先手が勝ちならFirst, 後手が勝ちならSecond

Nimble Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/nimble
T個のクエリがある。0～N-1個の番号がついた箱にC[i]個の石が入っている。
順番に1以上の番号の箱から石を1つ取り出し、それよりも小さい番号の箱に入れる。
操作が行えなくなった方が負け。先手が勝ちならFirst, 後手が勝ちならSecond

Poker Nim

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-2-poker-nim
T個のクエリがある。N個の石の個数がS[i]の石の山がある。
順番に「石を増やす」か「石を減らす」かする。
ただし「石を増やす」はK回しか行えない。
操作ができなくなった方が負け。先手が勝ちならFirst, 後手が勝ちならSecond

Tower Breakers, Revisited!

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers-2
T個のクエリがある。N個の数列があり、各要素はM[i]。
各数をその数の約数のどれかに変換する操作をする。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2

Tower Breakers, Again!!

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers-3
T個のクエリがある。N個の数列があり、各要素はM[i]。
ある数Xを選び、それをY個の数Zに分ける(Y*Z = X, Y > 1)。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2

A Chessboard Game, Again!

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-chessboard-game
T個のクエリがある。15*15のマスにk個の駒がある。
この駒は(x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2)に移動できる。
移動できる駒がなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond

Digits Square Board

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/digits-square-board
T個のクエリがある。N*Nの板にA[y][x]の数が書いてある。
合成数が1つでも書いてある板を選び、縦横どちらかに割る。
割れなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond

Fun Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/fun-game
T個のクエリがある。長さNの数列A[i],B[i]がある。
0<= i＜Nとあるiを1つ選ぶと、自分はA[i], 相手はB[i]得られる。
各iは1度しか選べない時、初手が勝ちならFirst, 後手が勝ちならSecond, 同点ならTie

Powers Game

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/powers-of-two-game
T個のクエリがある。*2^1*2^2*2^3*...*2^nというアスタリスクと2の累乗から成る列がある。
順番に*を+か-かに変える処理を行う。
全て変換後の計算結果が17の倍数なら後手Secondの勝ち、そうでないなら先手Firstの勝ち

Deforestation

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/deforestation
T個のクエリがある。N頂点の根が1の木がある。
互いに辺を1つ選び、その辺で繋がっている子の部分木を削除する。
部分木を消せなくなったら負け。先手が勝ちならFirst, 後手が勝ちならSecond

続きを読む