トヨタ自動車プログラミングコンテスト2023#3(AtCoder Beginner Contest 306)に参加しました。
結果
A,B,C,Dの４問正解でした。
B問題が珍しく手間取った…
あとは、E問題が解けそうで解ききれなかった。解説をちらっと見たら解き方の方向性は合ってたっぽい。
A - Echo
与えられた文字列の各文字を２文字続けて出力する問題。
各文字を２文字ずつ出力すれば良いので、ループさせつつ 各文字を２回出力させて次のループに移動すれば良い。
ループと文字列の扱い方の練習問題っぽい。
B - Base 2
２進数表記で64ビット分の0,1が与えられるので10進数整数に変換して出力する問題。
2進数から10進数に変換させるのは今まで何度も出てきていたから実装自体は難しくなかった。 ただ、64ビット分の入力があるから64ビット整数を使えば良いと思ったけどこれが失敗だった。 通常の整数型は1ビットは符号用に使われるから通常の64bit整数だとオーバーフローする。
しばらくこの事に気付かなかったのでそこそこWAを出しちゃった… C++のlong longは64ビットだからlong longで足りると思っていてWAなのはアルゴリズムが原因かと思ってた。
数回WAになった時点でPythonとかに乗り換えて提出すれば良かったかも。
2進数と10進数の変換問題かと思いきや実は型をどうするかの問題なんだと思う。
C - Centers
１～Nがランダムに3回ずつ現れる数列が与えられるので、各値の2回目出てきた順番を答える問題。
数値別に登場位置を2次元配列で管理して、 priority_queueに（登場位置、値）のペアを入れて、順番に取り出しずつ値を順番に出力させてみた。
priority_queueに勝手にソートしてもらおうとしてこうやって解いたけど、解説にあるように１～Nそれぞれの登場回数を数えつつ、2回目が出てきた値を順番に出力させれば簡単に解けるなあ。
D - Poisonous Full-Course
DPで解く問題。料理ごとに毒入りと解毒剤入りがあって、 毒入りを食べると、通常状態なら毒状態に遷移、毒状態ならゲームオーバーに遷移する。 解毒剤入りを食べると、通常状態なら通常状態のまま、毒状態なら通常状態へ遷移する。 最後までゲームオーバーにならないように料理を食べる/食べないを選択しつつ、料理ごとに設定されている料理の美味しさの総和を最大にしていく問題。
DP[i番目の料理まで選択が終わった][毒状態かどうか] としてDPを進めていった。 i番目の料理が毒入りかどうかで処理が分岐するのと、毒状態のときに毒入り料理は選択できないのを気をつけると 特に詰まることなく実装できると思う。
普段のD問題に比べると簡単な方だと思う。（DPに慣れていればだけど）
E - Best Performances
数列を1項ずつ更新しつつ、更新後の数列から大きいものK個の和を出力する問題。
数列の更新は1項ずつなので1度和を計算しておけば、それ以降は更新された項にだけ注目して和から1項分引いて足してをすれば計算量控えめで処理ができると考えて解いていった。 そのために合計の計算対象となっている値を管理するデータ集合と計算対象外の値を管理するデータ集合を用意して、これらをメンテしつつ合計を計算していこうとした。
考えていくうちにこの場合はどうするというのがいくつか出てきて、うまく整理できなくて時間切れになっちゃった。
