ARC(AtCoder Regular Contest) 030 C - 有向グラフ
C: 有向グラフ - AtCoder Regular Contest 030 | AtCoder
[問題]
n個の頂点とm本の辺の有向グラフがある。各頂点には'a'-'z'のアルファベットが１個ある。任意の頂点から開始してグラフをたどり、アルファベットを合計k個順番に取る。各頂点では取っても取らなくてもいい。循環していれば一回スキップして後で取ってもいい。取得した文字列の辞書順最小を求める。存在しなければ-1を返す。
[解答]
(終了後)
強連結成分分解でループしているところをグループ化する。各グループの文字はどの順番でも取れるのでソートしておく。
グループを順にたどり、文字数ごとに、それまでに作成できた最小の文字を記録する。
(DP[グループ][文字数]で最小の文字列を記録)
[コード](C++)
https://paiza.io/projects/icf5SNr67K43_VO65QhPzg
[感想]
O((N+M)*N*K*26)かな。他の人の解答や解説を見ながらだけど、はじめての強連結成分分解。少し慣れないと競技中には難しそう。DPの初期値文字列は"~"とする方法もありそう。
ARC(AtCoder Regular Contest) 030 B - ツリーグラフ
B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder
[問題]
n頂点のツリーグラフがある。いくつかの頂点に宝石がある。頂点xから開始して、全部の宝石を取ってxに戻るには、最短で何個の辺を通ればいいか。
[回答]
頂点xから出発してDFS(深さ優先探索)で各頂点をたどる。
宝石が見つかった場合、その頂点およびその頂点からの戻りの頂点は必ず通る必要があるので、戻りの経路では+1をする。
また、宝石が見つかった場合、既に必ず通ることになっている頂点からの距離を追加する。
[コード](Ruby)
https://paiza.io/projects/YBHSiCwcpiyQyX020mRuvg
[感想]
最初、戻りのことを忘れていた。
もう少し簡単な方法ないかな。。
ARC(AtCoder Regular Contest) 030 A - 閉路グラフ
A: 閉路グラフ - AtCoder Regular Contest 030 | AtCoder
[問題]
N個の頂点が円のように線で結ばれて並んでいる。
ここからいつくかの頂点を取り除いて、K個の線分に分割することはできるか？できれば"YES",できなければ"NO"を返す
3<= n <= 10^5
1<= k <= 10^5
[回答]
頂点の個数が偶数の場合、一個おきに取り除けば半分(N/2)になる。
奇数の場合、まず１個取り除き、その後一個おきに取り除くと、その半分((N-1)/2)になる。
最大で上記の数に分割できるので、それ以下なら"YES"。それ以外は"NO"
[コード](Ruby)
https://paiza.io/projects/07nBvShKF9KTToyITHTg-w
[感想]
説明する方がコードより難しい。。。
TopCoder SRM 639 Div1 Easy AliceGame
問題:
何回かAliceとKirtoでゲームをする、それぞれの回ではAliceのKirtoの勝った方が1,3,5,7,... 2i-1点となる。負けた方は0点。
最終的にAliceはx点、Kirtoはy点になる。
Aliceの勝利回数は最小で何回か。存在しなければ-1を返す
0<= x,y <= 1,000,000,000,000
回答:
1+3+5+...+(2n-1) = n^2 なので、x+yからnを求める。整数nが存在しなければ-1を返す。
xについて、i=n..1をとし、x>=i*2-1ならxから引いていく。
ただし、残りが"2"になってしまうと、その後消去することができないので、"2"にはならないようにする。例えば9が残っている場合、9-7=2とするとダメだけど、7を飛ばして9-5-3-1=0で0にすることができる。
コード:
https://paiza.io/projects/eiZmkvH3lqANJttOilEtqQ
感想:
残りが2の場合を無視することに気付けなかった。。。
ほとんどの人が気付けなかったようで、ほとんどの人が撃墜されてひどい結果に。。。
yukicoder No.78 クジ付きアイスバー
問題
はずれ、あたり１個、あたり２個のいずれかのアイスバーが箱にN個順番に入っている。
K本のアイスバーを食べるには、何個買う必要があるか？
1<=N<=50, 1<=K<=2*10^9
解答
後で。
1個目の箱と最後の箱は一個ずつ調べる。
その間の箱は繰り返しなので掛ける、ただしもらえる数がアイス数より多い場合は
買わなくてよい。
感想
OffByOneを合わせるのが結構面倒。。。
yukicoder No.77 レンガのピラミッド
問題:
N列分のレンガ(Ai)が並んでいる。
1列目からピラミッド型([1,2,3....L-1,L,L-1,....1])に並べるには
レンガを何回移動させるか捨てればいいか？
1<=N,Ai<=100
回答:
L段のピラミッドの個数は
1 + 3 + 5 + ... = L * (1 + (2L-1))/2 = L * L
となる。
ちょうど全てのレンガを使うか、ちょっと余るぐらいがいいので、
Sqrt(レンガの合計数).floor
がピラミッドの段数
感想:
最初、１列目以外の任意も場所(マイナスを含む)からもピラミッドをはじめていいと勘違いして戸惑う。
