htkb-proconの日記

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

Good Bye 2018

ooo---- 1430 -> 1466

Codeforces久しぶりに出た。2018ラストなので。

A. New Year and the Christmas Ornament

AC: Submission #47733927 - Codeforces

あたまわるいのでこういう問題嫌いです。愚直に場合分けしたけどr, b-1, y-2の中で一番少ないものに引きずられるのは自明なので、min(r, b-1, y-2)*3 + 3で良いようだ。

B. New Year and the Treasure Geolocation

AC: Submission #47738516 - Codeforces

あたまわるいのでシミュレートして指してるマスが最多のマスを出力したが、「今回は目をつぶってやるが遅いpython使うならちったあ頭使えや」的な意思を実行時間から感じます。あたまのよい人は全ての座標を足して平均を出したり、x最小のオベリスク座標とx最大の距離座標を足したりしてO(1)で答え出してる模様。

C. New Year and the Sphere Transmission

AC: Submission #47747369 - Codeforces

なんとなく雰囲気で解いた問題。Nとkが互いに素だと結局全部の人を回ることになる?のでk=1のときと同じ結果になる。そうでなくkがNの約数だと、飛び飛びに回していってちょうど1周で1の手に戻ることになる。1-indexedで考えるとめんどくさいので一旦0-indexedで考えてみると、0 -> N * (k/N) * 1 -> N * (k/N) * 2 -> ...という感じ、例えばN=8, k=2だったら0 -> 2 (8*(2/8)*1) -> 4 (8*(2/8)*2) -> 6 (8*(2/8)*3)で0に戻る。各項の最後に掛けてある数は1〜N-1までの総和なのでN * (k/N) * (N-1) * N // 2となって、0-indexedにしていたのでその分回った人の数k/Nを足して1-indexedに戻して終わり。これを約数全てに対して行う。√Nまで見れば平方数を除き√Nを堺に約数が現れるので(略。もっと綺麗に解ける気がする。