ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)に参加しました。
結果
A,B,C,D問題の4問正解でした。
もう少しでE問題も解けそうだったから悔しい。
あと、何故かキー入力の調子が悪かった。相変わらず英字のHHKBを使っているけれど記号とFnキーの入力でどこだっけと考える時間が入って思うように入力できなかった。いつもはもう少しスラスラ入力できるのにどうしたんだろう。
A - Range Swap
問題文のとおりに処理する。
数列Aのコピーを用意して、P~QとR~Sをコピーへ移してから出力する。
B - Cat
問題文のとおりに処理する。
naをnyaに置き換えた文字列を出力するだけで良いので、 1文字ずつ出力しながら、今出力した文字がnで次の文字がaの時aの前にyを出力するだけで回答できる。
C - Rotate and Palindrome
全通り探索してコストが最小のものを答える。
操作は2つあるけど任意の1文字を置き換える操作は最後にまとめて行えば良い。
任意の文字列を後ろへ移動させる処理は、元の文字列を2つ続けたものをi文字目を先頭にN文字抜き取ったものを対象にすれば1回ずつ文字列の操作をしなくて済んで楽だと思った。
文字入れ替え後の文字列は先頭と後方から順番に1文字ずつ比較していけば文字置き換えの回数は簡単に求められる。
なので各回で必要なコストは簡単に計算できるのでminとかで最小値を更新し続けて最後に結果を出力する。
D - Money in Hand
ただのDPで解く問題。
DP[i番目の硬貨まで確認した][残り金額ｊ円]=ブール値 としてi番目の硬貨までを使ってj円が支払い可能かどうかを計算していった。最後に残り金額0円でtrueとなっているものがあるかどうかを探して支払い可能かどうかを答える。
E - Souvenir
有向グラフで最短経路問題を解きつつ、別途設定されている価値を最大化する問題。
ダイクストラで最短経路を計算しつつ、合わせて価値の最大値を計算していけば解けそうだと思った。 なので普段のダイクストラでホップ数と次ホップノードだけ管理しているところに、そこまでの価値を追加して管理しようとして調べながら拡張していたら時間が切れた。
