ARC109の感想

AtCoder Regular Contest109に参加しました。

問題はこちら。

Tasks - AtCoder Regular Contest 109

結果はこんな感じでした。

順位：2095 / 4084
パフォーマンス：879

でした。なんとか緑色パフォーマンスが出ました。ただし、緑色になるためにはこれを最低スコアとして、さらに上を出さないといけないので、もう一段階レベルアップしないとなーって感じです。

今回は1時間ほどでa,bが解けたので、みっちりcに1時間臨むことができたことはよかったです。ただし、解けませんでしたが。

感想を書いていきます。

A 問題

2つの建物があり、現在1塔a階から2塔b階まで移動します。移動には、「同じ塔のi階とi+1階を繋ぐ階段」と「1塔i+1階から2塔i階までの通路」「1塔i階から2塔i階までの通路」があります。階段移動は y、通路移動はxの時間がかかります。さて、移動に掛かる最小時間はいくつでしょう。

という問題。

縦方向の移動として「階段」と「通路を2回」という2つ方法があります。直感として、階段移動の時間が長いなら通路を通って、通路が長いなら階段で登りましょう。という考えになりました。おそらくこれは、合ってるはずです。

しかし、その条件を分岐させて書くと間違えそうだと思いました。

そのため、両方の方法で時間を求めて、その結果の小さいほうを答えとしました。このとき、塔を登る場合（a<b）と降りる場合（a>b）で若干動きが違うことに注意です。

B 問題

1~nの長さの丸太をそれぞれ1本ずつ計n本入手したいです。お店には1~n+1までの丸太が1本ずつ売っています。また、私は丸太を何回でも好きな長さに切断できます。さて、目標達成のために購入しなければならない丸太の最小数は何本でしょう。

という問題です。

これは、長い丸太(n+1)で小さい丸太を作り出して、何本分節約できますかという問題に置き換えることができるなーって思いました。

n+1の丸太で最も多くの丸太を作り出せるのは、小さい丸太から順番に切り出した場合です。

1+2+3+...+m <= n+1

この式が成立するような最大の自然数 m が作り出せる最大数となります。

愚直に求めたいのですが、制約が

1 <= n <= 10^18

ですので、 間に合いません。工夫しました。

1~mまでの和は

m*(m+1)/2

です。mが0の時は<=n+1が必ず成立し、mがめちゃくちゃ大きいときには不成立となります。式は連続ですので、mを増加させると成立から不成立切り替わる値が存在することになります。

その値を2分探索にて求めましょう。

注意点として、m*mがあるためオーバーフローに気を付けましょう。私は10^9以上なら不成立としましたが、これだとwaでしたので、long longに入るギリギリの値のsqrtを取って閾値としました。

こんなことをするぐらいだったら、pythonで書いた方がミスもなく、高速にかけるなーと試験後に思いました。使える武器は余すことなく使って、少しでもよいスコアを取りたいものです。

C 問題

1時間ありましたがあんまり考察ができませんでした。愚直にやると大変なことになるので、何とか工夫しようと考えました。

RPSRPSのループで何が残るのか。
2^k上で区切ると？
ループ長が偶数か奇数で場合分け？

この程度でした。

今回はCまでは多くの方が解いていて、Dからが壁となっているように感じました。Cまでは解きたかったなーと思いつつも、実力不足を認めてしっかりと復習しておきます。

あと、前回のabcの解説をさぼっているのでちゃんと書きます。既に解き終わってはいますので、、、