トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）に参加しました。
結果
A,B,C,D,E問題の5問正解でした。
久々に5問正解できた。
F問題は見てみたらDPっぽいなあと思いつつどうやって解くか詰めていたら時間切れになった。
コンテストのパフォーマンスが1200超えてた！これが毎回できれば水色に上がれるのかあ。
A - Spoiler
|が2つ混じった英字の文字列が与えられるので|と|に囲まれた部分を除去した文字列を出力する問題。
問題文の通り処理すれば解ける問題。
Pythonならsplitを使って|で文字列を分割して最初と最後の要素だけ出力すれば解けそう。
C++にはsplit関数はないので、文字を解答として出力するかどうかのフラグを用意して、|が出てくるたびにフラグを反転させて文字を出力するかどうかを制御した。こうすることで|で括られている部分はフラグにより出力しないので、 出力結果は欲しい文字列になる。
A問題にしては普段に比べてちょっと難しい気がする。
B - Delimiter
最終項が0で要素数が不明な数列が与えられるので数列を逆順に出力する問題。
問題文の通り処理して出力すれば解ける問題。
最終項が0なのはわかっているので、0が出てくるまで入力を受け付け続ける。 0を受け付けたら、数列を逆順に全部出力した。
C - A+B+C
数列が3つ与えられるので各数列から数字を1つずつ選んで指定された値が作れるかどうかをQ回答える問題。
制約を見るとQはなので各質問は
で答えられないとTLEしそう。
各数列のサイズはなので全通り計算すると最大
回計算が必要になる。
これはTLEしないで処理できる量なので1回だけなら全通りの計算ができる。
なので、あらかじめ全通り計算して作り出せる値をすべて求めておきで回答することにした。
計算した結果を連想配列を使って管理して、数値を引数にしてその数が作れるかどうかを判断できるようにした。
D - String Bags
問題文を読んでDPで解く問題っぽいなと思いながら考察していった問題。
袋がいくつかあって、各袋の中にそれぞれいくつかの文字列が入っている。順番に各袋の中の文字列を選択したりしなかったりして、指定された文字列を作れる場合の最小コストを答える問題。（コスト=文字列を選んだ個数）
袋の数は最大で100あって、各袋の中に文字列は最大10個あるので、全通り計算するには通りの計算が必要になるので試すまでもなくTLEになりそう。
ということで全通りの探索は諦めてDPで解くことにした。
DP[袋iまで選択][j文字目まで作った]=最小コスト
としてDPで処理していくことにした。
E - Insert or Erase
与えられた数列に対していくつかクエリを実行して最終結果を出力する問題。
クエリの種類が、指定されたある値の後ろに別途指定された値を追加するか、指定された値を削除するかの2種類。
色々考えたけど、双方向リストみたいに自分の値の前後の値を管理すれば解けそうだなと思ったので頑張って実装した。
具体的にはUnion-Findみたいな発想で、ある値の前の値と後ろの値をそれぞれ連想配列を使って管理した。
a → x → A にyを追加するなら a → x → y → Aと参照を更新して、
削除するなら a → Aと参照を更新した。
双方向リストを知っていれば、どう実装すればよいかの考え方を持っているので実装方針は悩まずに時始められると思う問題。
-
