htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Beginner Contest 097

B - Exponential

Submission #2496124 - AtCoder Beginner Contest 097

どうやって求めるかぱっと出てこなかったのでめっちゃループを回した。

for i in Xから1まで
  for j in ルートiから1まで
    for k in 1から9まで
      i == jのk乗だったら答えはi

みたいな。kが1~9なのは制約X <= 10002^9 < 1000 < 2^10のため。

C - K-th Substring

Submission #2498311 - AtCoder Beginner Contest 097

|s| <= 5000なので全列挙は無理。1 <= K <= 5なので若いアルファベットの周辺だけちょこちょこ探索して済みそう。辞書順問題の基本として、先頭に近いアルファベットが若ければ必ず辞書順も小さくなるので、文字列の中に"a"が含まれるなら必ずそれを先頭に使った部分文字列が辞書順の先頭の方に来る。なので文字列sにアルファベットaが含まれるインデックス番号を列挙し、そこから後ろ5文字くらいまで範囲を伸ばして(k <= 5なので)aが頭文字となる部分文字列を列挙して、重複を排除し、部分文字列の個数がk個以上だったら辞書順k番目の文字列が答え、k個未満ならその個数分kを減らして次のアルファベットを同じように探索……を繰り返した。

D - Equals

Submission #2500414 - AtCoder Beginner Contest 097

多分プロの人らは一目見て即グラフ問題だと気づくんだろうなあ。スワップは何回でも可能なので、入力例2を見てもわかるとおり1 22 3が繋がってるなら1 2 3は自由に並べ替え可能。したがってスワップ可能なM個のペアを辺としてグラフを構築し、DFSなどで繋がっている頂点を調べる。繋がっている頂点の値は任意に並べ替え可能なので、繋がっている頂点番号の集合と頂点の値の集合の論理積を取るとかなんかそんな感じでp[i] == iにできる個数を数える。

{5, 3, 2, 4, 1} のうち1番目と3番目と5番目が繋がっている
↓
頂点番号:{1, 3, 5}
頂点の値:{5, 2, 1}

繋がっている頂点の値は任意に並べ替え可能なので、
頂点番号と頂点の値で被っているものがあればそれはp[i] == iにできる。

{1, 3, 5} & {5, 2, 1} = {1, 5} ←2個の頂点がp[i] = iにできる

最後に全く繋がっていない(スワップできない)頂点もチェックしなければならない。繋がっていない頂点は並べ替えできないので最初からp[i] == iになってないとダメ(1WA)。