AtCoder Beginner Contest 293参加記

A - Swap Odd and Even

問題

https://atcoder.jp/contests/abc293/tasks/abc293_a

 

文字列をこのように入れ替えます。問題文に加えて

入力例、出力例で何をするかはっきりしました。

 

B - Call the ID Number

問題

https://atcoder.jp/contests/abc293/tasks/abc293_b

 

仕様に従ってコード化するような印象でした。

I番目の人が呼ばれたかどうかをboolで管理して

問題通りのコードを書きました。

 

C - Make Takahashi Happy

問題

https://atcoder.jp/contests/abc293/tasks/abc293_c

 

H行W列のマス目が最大でも10x10程度、入力例2を見ると

最大でも48620個と書かれていましたので、全通り試して数え上げようと思いました。

数え方はこのようなイメージで、深さ優先探索で解きました。

 

D - Tying Rope

問題

https://atcoder.jp/contests/abc293/tasks/abc293_d

 

コンテスト後、この考えは余分だった気もしますがi番目のロープを

このようにグラフ化しました。

 

問題の制約(同じ色の端が複数回結ばれることはありません)というところから、

このような結び方は無いと読み取りました。

 

それをもとにUnionFindでロープを連結し、すでに連結成分になっているものに

ロープを結ぶ処理が行われたら環状になっているものとして計上します。

 

E - Geometric Progression

問題

https://atcoder.jp/contests/abc293/tasks/abc293_e

入力例1を眺めてひらめきがあり、試しに X = 9くらいで以下のように式変形をしました。

\displaystyle (A^{0}+A^{1}+A^{2}+A^{3}) + (A^{0}+A^{1}+A^{2}+A^{3})A^{4} + A^{8}

もう少し式を一般化して、

\displaystyle F(A, X, M) = \left\{ \begin{array}{} 1 \;\;\; (X=1)\\ F(A, \lfloor \frac{X}{2}\rfloor, M) + F(A, \lfloor \frac{X}{2}\rfloor, M) A^{\lfloor \frac{X}{2}\rfloor} + Y \;\;\; (X \gt 1) \end{array} \right.
\displaystyle Y = \left\{ \begin{array}{} 0 \;\;\; ( X \equiv 0 \pmod 2 )\\ A^{X-1} \;\;\; ( X \equiv 1 \pmod 2 ) \end{array} \right.

と、式を立てられましたので繰り返し二乗法のように再帰することで解けました。

 

コンテスト後、kyopro_friendsさんの解説に驚かされました。

もしMが素数でしたら、私はこの式がコンテスト中思いつかず、

もっと順位が下がっていたかもしれません。

 

結果

A〜Eの5完でした。個人的に最高のパフォーマンスが出せて、

再度水色に戻ることができました。



今年の目標にしていたパフォーマンス1600にはわずかに届かず

残念でしたが、取れそうな手応えが得られたのは嬉しかったです。