hotpepsiの練習帳

Codeforces 170

22:13

Div2 A. Circle Line

問題

• N駅からなる環状線がある
• 駅から駅への時間が与えられる
• どちらの方向へも行ける
• 最短の時間を求める
• ただし出発駅と到着駅が同じ場合もあり

方針

• 足して一つ進める、と、一つ戻して足す、の合計の少ないほう
• オーバーフローしないようにindexにNを足してmodを取る
• Passed System Test

Div2 B. New Problem

問題

• 今までにない問題を出題したい
• 過去に出題されたタイトルの部分文字列でない文字列を求める
• ユニークかつ辞書順最小の文字列を求める

方針

• 長さが短いほうが良い
• 同じ長さなら普通に比較する
• 1文字ずつ進めて総当り
• Passed System Test

Div2 C. Learning Languages

問題

• N人の従業員とM種類の言語がある
• それぞれの従業員は0以上の種類の言語を話せる
• 任意の従業員同士がコミュニケーションを取るために必要な学習回数を求める

方針

• 少なくとも誰か1人以上と話せればよいのかなと思って書き始める
• 全員とコミュニケーションを取れないとだめっぽい
• union find木でいけそう
• それぞれの人が話せる言語をunion find木に格納しておく
• 誰かが話せる任意の言語Xを一つ選ぶ
• 従業員Yがその言語を話せないなら+1
• 全ての従業員が何も話せないケースもありうる(その場合答えはN)
• Passed System Test

結果

ooo-- 2208pt 51st/1874 rating 1680 -> 1755 (+75)

wrong answerなしで、比較的早く提出できた。割と良い出来。

Aは、総和と順方向を求めておけば、逆方向は総和から順方向を引けば求まるのだった。

Cはunion findでやればBより簡単だったかもしれない。解いた人が多かったらしく最終的にBと同じ点数だった。

順位が良かったのでdiv1に上がった。div1 Bくらいまで練習したい。