れとろのメモ置場

とあるSEのメモ置場

HHKB プログラミングコンテスト 2022(AtCoder Beginner Contest 235)

HHKB プログラミングコンテスト 2022(AtCoder Beginner Contest 235)に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスがXXXでした。 D問題がずっと1WAでどんなパターンで間違っているのか全く検討がつかなかった...

A - Rotate

1桁ずつ数値を取り出せれば簡単に解ける問題。

文字列として取得して各桁の文字から'0'を引くか、数字として取得後、10の余りを取得して10で割るを繰り返せば1桁ずつ値が取得できる。

取得できればあとは数式通りに計算して結果を出力する。

B - Climbing Takahashi

問題文のとおりにシミュレートすれば解ける問題。 台の数は10 ^ {5}程度なので線形探索で十分間に合う。

C - The Kth Time Query

x _ {i}をキーにa回目は何番目の要素かをメモして各クエリに答えていけばいい。

map>でメモを用意して処理した。

D - Multiply and Rotate

ずっと1WAが取れなくてACできなかった。

作れる値をノードとしたグラフで1からNへの最短経路の距離を求める問題とみなせる。 グラフの最短経路なので幅優先探索で解けば良さそうなのはわかった。あとは1から計算すると数値がどんどん大きくなるので大きくなりすぎると探索を打ち切る必要がある。

もしくはNから始めて1を目指す。

方針は間違ってないと思うけどずっと1WA。一体何を見落としていたのかわからない...

(追記) コンテスト中はNから1を目指す方法で解いてたけど、1からNを目指す方法でとき直すと1回でACできた... コンテスト中も始めは1からNを目指す方法で解いてて、サンプルケースでTLEしそうなケースが出てきたからNから1を目指す方法に方針転換したけど、それが裏目に出たみたい...
悲しい