ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ゆるふわ競プロオンサイト参加記

2/9に東京で行われました、@matsu7874さん主催の競プロオンサイトイベント、に参加してきました!
コンテスト自体は全8問で、2時間のセットでした。自分は、ABCDEGの6完でした!

B式A+B

問題
提出コード
えー、最初の問題がかなり鬼実装でした。
自分は問題を読むのにまず数分かかりました。
結局は、"B"と"b"のみからなる文字列を、"b"=0、"B"=1とみなし、その足し算をした結果をまた"B"と"b"からなる文字列にしてください、というものです。
自分は、数字に直して計算、それを直す、という操作をするとバグらせる自信があったので、文字列をそのまま筆算して文字列のまま計算しました。
最初に2つの文字列をリバースし、簡単に前から見ていけるようにします。
その後、先頭から順番に見ていき、
(0,0)なら0を、(1,0)なら1を、(1,1)なら0を入れる&桁上がりフラグを立てて次の桁に加算、というようにしていき、答えの値を決定していけば良いです。最後に、答えの文字列をもとに戻せば完成です。
おそらく難しい部分は、2つの文字列の長さが異なる場合の処理方法、そして桁上がりの処理と、文字列を反転させるひらめきかなと思います(反転させなくてもできますが、かなりめんどくさいかなと)。

集合写真

問題
提出コード
Aと比べるといきなり実装が軽くなった気がします。
一番前の人から数えて自分が何番目なのか、というのを求めれば、あとは5で割り算したあまりと"yfkpo"の文字列を照らし合わせることで、答えを求めることができます。
自分が何番目か、を数えるには、自分より上にいる人の人数と、自分の行において自分が何番目か、という情報に目を付けると調べることができます。
自分より上にいる人たちは、 K \times (Y - 1)で求めることができます。
自分と同じ行の人は、Yの偶奇で場合分けをする必要があり、奇数ならば左から数えるのでそのままX番目、偶数なら右から数えるのでK-X+1番目にいることになります。
あとは、上の二つの数字を足し、5で割った余りを求めることで、どの文字のポーズをするかを求めることができます。
"yfkpo"という文字列をstring型か何かで保持して上の数と比較する場合、文字列が0-indexedであることに気を付けましょう。

線香

問題
提出コード
求める答えは、簡単に言うと
(i本目が燃えた長さ)/(1本目が燃えた長さ)
となります。ですが、このままだと8/6のように、まだ約分できる数になっている可能性があるので、約分をします。
ということで、分母分子の最大公約数を求め、それぞれを割れば答えとなります。これをすべての線香について行えばよいです。

最短経路は何本ありますか

問題
提出コード
この問題が類題です。
ダイクストラをしながらDPをしていきます。
dp[i] = 頂点iに行く最短経路の数、とします。
すると、iに行く最短経路の一手前の頂点をjとすると、
dp[i] = \sum dp[j]
となります。
まずはダイクストラ法を開始します。priority_queueから頂点jを1つ取り出し、そこからいける頂点iを1つ選び、そこまでの合計距離を求めます。 次に、合計距離と、iまでの現在の最短距離を比較して、場合分けをします。

  • iまでの最短距離を更新する場合
    dp[i] = dp[j]とし、頂点iを新しくキューに格納します。

  • 現在の最短距離と等しい場合
    dp[i] += dp[j]とし、キューは操作せずに次の操作にすすみます。

  • 現在の最短距離の方が短い場合
    何もせず次に進みます。

基本的には、この操作を繰り返していくことで、答えを求めることができます。
ここで注意が必要なのが、iまでの最短距離が途中で更新される可能があるということです。つまり、キューから取り出した頂点jまでの現在の合計距離が、既にjまでの最短距離ではなくなっている可能性がある、ということです。そのため、キューから取り出した時点で、合計距離がjまでの最短距離になっているかを改めて確認してあげて、最短距離でなければスルーをする必要があります。
あとはこのダイクストラを行っていくことで、答えを求めることができます。

ガソリンスタンド

問題
提出コード
幅優先探索を行います。
あるガソリンスタンドから行くことができる、かつまだどのルートでも行ったことがないガソリンスタンドに行く、という操作を繰り替えしていきます。
その際に、どのガソリンスタンドから来たか、という情報を記録していきます。
行くことができるかどうかは、純粋に2つのガソリンスタンドの距離を計算し、それがD以下かどうかを調べればよいです。
あとは、ガソリンスタンドNについた後、どこから来たか、という情報を元にNから逆順に1まで辿って行き、それを記録します。
最後に、その記録をさらに逆順に出力していくことで、答えとなる経路の出力が完了します。

射的

問題
提出コード
RMQについて知っていれば瞬殺できる問題です。
狙う手前の的を固定したときの最大値を求め、それを全探索します。
i番目の手前の的を狙うと決めた時、後ろ側の的の最大値は、[i-K,i+K]番目の的の得点の最大値になります。これを、RMQを利用して高速に求めれば、i番目の手前の的を撃った時の得点の最大値を求めることができます。
あとは、N通りの手前の的の撃ち方を試し、一番得点が高くなるものを選べばよいです。

Fは後日追加…できたらいいなと思っています。半分ぐらい?考察が終わっていたみたいなので少し悔しいです。

感想

最終的には19/40位という結果になりました。だいたい半分ですね。
f:id:emtubasa:20190211234437p:plain
個人的な難易度の感想としては、
B \lt C \lt A \lt G \lt E \lt D \lt F \lt H
という感じでした。実装でよくバグらせるタイプなので、考察がすんなりいけた問題の難易度が低くなっている気がします。
懇親会は、基本大学の友人と話をしていましたが、主催者様や他の数名ともお話できて楽しかったです!また次があればぜひ行きたいですね。
雪の心配もありましたが、特に何も起こらなくてよかったです。

おまけ

ピザ!おいしかったです、ごちそうさまでした。