hotpepsiの練習帳

SRM 705

21:37

https://competitiveprogramming.info/topcoder/srm/round/16856/div/1

Div1 Easy (225) AlphabetOrderDiv1

問題

• aからzまで26種類の文字を使う言語がある
• 便宜的にaからzで表すが、各文字の序列は不明である
• ある単語の文字が、文字の序列順になっているものを、良い単語とする
• N個の単語が与えられる
• 全ての単語が良い単語になるような文字セットが存在するかどうかを求める

方針

• 各文字の大小関係を記録していき、矛盾が生じたらImpossibleとする
• 文字pが文字qより前にあり、文字qが文字rより前にあるとき、文字pは文字rより前になければならない、という判定をがんばる
• Challenge Succeeded
• 同じ文字が連続するときの判定が抜けていた
• (解き直し)
• 考察
  • hama_duさんに聞く
  • グラフで
  • 文字p、文字qの順に出現したとき、文字pからqへ辺を張る
  • ただし同じ文字が連続するときは無視する
  • あとで全部たどるので、辺を張るのは前後の文字だけでよい
  • 辺をたどって、ループしているときはImpossible
  • ループするときには同じ文字に到達する
• 解法
  • 一つ前の文字に(片方向の)辺を張る
  • Warshall-Floydをかけて、自分自身に戻ってくる文字があるかどうかを判定
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_705/AlphabetOrderDiv1.cpp
• 別解として、トポロジカルソートして、ループが残るかどうかで判定してもよい

Div1 Medium (450) MovingTokens

問題

• N個の容器があり、それぞれに駒が入っている
• 駒の行先を示す表M[i][j]がある
• 各ターンにiをひとつ選ぶ
• 容器jに駒が入っていれば、それをM[i][j]に移動する
• 移動は同時に行う
• 駒が入っている容器の数を最小化するとき、10^100ターン後の容器の数を求める

方針

• 合流と移動がある
• 合流はunion findで同じと見なす
• 合流しているもののどちらかに移動するものがあれば、それも合流と見なす
• サンプル通ったので提出
• Challenge Succeeded
• (解き直し)
• Codeforcesのフォーラムを読む
• 2つの容器が合流するかどうかをDFSで見つけて、合流するときは、その手順を覚えておく
• 容器の初期状態を1として、任意の2つの容器のうち、合流するものがなくなるまでループする
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_705/MovingTokens.cpp

結果

xx- +1 50pt 141st/262 rating 1414 -> 1434 (+20)

clock()で1.7秒までがんばるコードが落とされていた。アリーナではclock()やtimes()は常に0を返すようだ。sleepもsleepせずにすぐに戻ってくる。

gettimeofday()またはRDTSC(インラインアセンブラ)は使えた。

mediumは、交換か減るかしかないので、貪欲的にやってよい模様。

https://togetter.com/li/1069702