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

hamayanhamayan's blog

Tree Separator [JAG Practice Contest for ACM-ICPC Asia Regional 2017 E]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_e

N頂点の木がある。
ここから1つのパスを指定して、パスに含まれる頂点と辺を全て取り除く。
できる連結成分の中で良い成分(頂点数がK以上)の個数を最大化せよ。

続きを読む

RPG Maker [JAG Practice Contest for ACM-ICPC Asia Regional 2017 F]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_f

縦H,横Wの盤面がある
H = 4n-1, W = 4m-1である

  • '@'は始点
  • '*'は町
  • '#'は道路
  • '.'は何もない

始点と町はx,y座標がどちらも偶数番目にある。
現在の盤面は道路が無いので、以下のルールをみたすように道路を作り、一筆書きを考える。

1. 道路を使ってできるだけ多くの町に行けるようにする
2. The journey must consist of distinct non-empty cells in this map.
3. 一筆書きは始点から始める(始点からは道路が1つしか出ない)
4. 一筆書きは任意の町で終える(ある町は道路が1つしか出ない)
5. 一筆書きである必要がある(連結であれ)
6. 分岐があってはいけない(一筆書きなので)
7. 町を通る順番は考慮しない

続きを読む

Separate String [JAG Practice Contest for ACM-ICPC Asia Regional 2017 H]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_h

N個の文字列集合Sがある。
文字列Tもある。
Tを分解して、全て集合Sの要素となるようにする。
何通りの分割方法があるか(mod10^9+7)

続きを読む

Coin Slider [JAG Practice Contest for ACM-ICPC Asia Regional 2017 G]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_g

N個の円があり、それぞれ始点(sx[i],sy[i])、終点(tx[i],ty[i])、半径r[i]である。
最初、全て始点にある。
この円を適切な順番で終点に動かす。
動かす過程で他の円と交わってはいけない。
最大何個の円を動かせるか。

続きを読む

Prime-Factor Prime [JAG Practice Contest for ACM-ICPC Asia Regional 2017 C]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_c

[L,R]の数で素因数分解したときの素因数の個数(同じ素因数でも重複して数える)が素数の数は何個?

続きを読む

Tournament Chart [JAG Practice Contest for ACM-ICPC Asia Regional 2017 B]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_b

トーナメントが文字列で与えられる。
「[左-右]」で与えられる。
次にトーナメントに出てきたN人について、勝利回数が分かっている。
勝利回数が正しいかどうか判定せよ。

続きを読む

Window [JAG Practice Contest for ACM-ICPC Asia Regional 2017 A]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_a

縦H横Wの窓がN枚ある。
奇数番目はX[i]だけ右にずらし、偶数番目はX[i]だけ左にずらす。
空いている部分の面積は?
Nは偶数である。

続きを読む