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

hamayanhamayan's blog

CSAcademy Round #21 問題と解説

競技プログラミング

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

問題

Min Coin Payment

https://csacademy.com/contest/round-21/#task/min-coin-payment
無限の1,5,50ドルがある。
これを使ってKドルを最小個数で作れ。

Prime Distance

https://csacademy.com/contest/round-21/#task/prime-distance
ある数Aに以下のどちらかの操作をする。
1. Aに素数を掛ける
2. Aから素数を割る
最小何回の操作でBにできるか

Max Wave Array

https://csacademy.com/contest/round-21/#task/max-wave-array
全ての要素が異なる数列Aがある。
これをA[1] > A[2] < A[3] > A[4] < ...のような規則で並べるとき、辞書順最大のものを答えよ

0-K Multiple

https://csacademy.com/contest/round-21/#task/0-k-multiple
ある数Nの倍数で全ての桁の数がKか0である最小の数を答えよ。

Special MVC

https://csacademy.com/contest/round-21/#task/special-mvc
N頂点M辺の無向グラフがある。
このグラフには奇数長の閉路しかない。
このグラフの最小頂点被覆数を求めよ。
最小頂点被覆 : 頂点の部分集合で全ての辺の端点のどちらかが必ずその集合に属す

Tournament Cycle

https://csacademy.com/contest/round-21/#task/tournament-cycle
N頂点のtournament graphのうち、長さKの閉路が少なくとも1つ含まれる個数を求めよ。
tournament graph : 完全グラフを有向グラフにしたもの

Catch the Thief

https://csacademy.com/contest/round-21/#task/catch-the-thief
N頂点M辺の無向グラフがある。
泥棒は

  • 初期頂点は分からない
  • 毎晩、隣接する頂点に移動する

自分は

  • 毎日夜まで任意の頂点で張り込みをする

どのような順番で張り込みを行えば捕まえられるか、張り込みをする頂点の順番を答えよ。
必ず捕まえられないなら"-1"

続きを読む

競技プログラミングにおける戻すDP問題

競技プログラミング

戻すDP

  • dp[i+1]からdp[i]を復元することで問題を解くテク
  • 間違ってたらごめんなさいメモ
    • ナップサックDPで順番を変えても問題なくて、一部なくすとかなら戻すDPかも
    • 多項式の母関数がDPになってる問題で使える（遷移が多項式の掛け算なので、多項式で割ることが”戻す”ことになる）参考
  • 参考

問題

以下、未整理

ARC 070 D. No Need

http://arc070.contest.atcoder.jp/tasks/arc070_b

https://codeforces.com/contest/1111/problem/D
https://community.topcoder.com/stat?c=problem_statement&pm=11026
http://mayokoex.hatenablog.com/entry/2016/01/03/165804
http://kmjp.hatenablog.jp/entry/2014/12/19/1030
http://kmjp.hatenablog.jp/entry/2014/12/23/0930
http://kmjp.hatenablog.jp/entry/2015/08/01/1030

Codeforces Round #405 問題と解説

競技プログラミング

http://codeforces.com/contest/790
http://codeforces.com/contest/791

A. Bear and Big Brother

http://codeforces.com/contest/791/problem/A
2つの数A,Bがある。
一回の操作でAは3倍、Bは2倍される。
最小何回の操作でA > Bとなるか。

B. Bear and Friendship Condition

http://codeforces.com/contest/791/problem/B
N頂点,M辺の無向グラフがある。
このグラフが以下の性質を満たすか判定せよ。
「全ての独立した3頂点(X,Y,Z)について(X,Y)と(Y,Z)間に辺があるとき(X,Z)間にも辺がある」

C. Bear and Different Names / A. Bear and Different Names

http://codeforces.com/contest/790/problem/A
http://codeforces.com/contest/791/problem/C
N人の兵士がいる。
この兵士の名前について、N-K+1個の情報が与えられる。
i番目の情報は[i, i+K-1]の範囲の兵士に名前がダブっている兵士のペアがあるなら"NO"、皆異なる名前であれば"YES"。
ありうる兵士の名前(10文字以内の英語大文字小文字)を出力せよ。

D. Bear and Tree Jumps / B. Bear and Tree Jumps

http://codeforces.com/contest/790/problem/B
http://codeforces.com/contest/791/problem/D
N頂点の木がある。
f(s,t) := 頂点sから頂点tへの最短距離/Kの切り上げ
全てのs＜tを満たす頂点のペア(s,t)についてf(s,t)の総和は？

E .Bear and Company / C. Bear and Company

http://codeforces.com/contest/790/problem/C
http://codeforces.com/contest/791/problem/E
文字数Nの文字列Sがある。
この文字列に対して、隣り合う文字をスワップする操作を行う。
"VK"という連続文字列が出てこないようスワップするときの最小スワップ数は？

D. Bear and Rectangle Strips

http://codeforces.com/contest/790/problem/D
縦2横Nの配列がある。
各マスには整数が書かれている。
このマスから内部の和が0となる長方形を最大何個被らず作れるか

続きを読む

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. 数列全体について反転数を答える

続きを読む

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

競技プログラミング

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

問題

反復法

ガウスの消去法

わからない

続きを読む