トヨタ自動車プログラミングコンテスト2024#4（AtCoder Beginner Contest 348）に参加しました。
結果
A,B,Cの３問正解でした。
D問題は、これで解けるだろうと思ったアルゴリズムを実装してもTLEが出て最後まで解決できなかった。 解説を斜め読みした感じだと、思っていたアルゴリズムだとダメだったみたい。
A - Penalty Kick
問題文のとおりに処理して答えるだけの問題。
１～Nまでの整数のうち３の倍数ではない数の個数を答える問題。 剰余演算で１個ずつ３の倍数かどうかを確認して数えれば良い。
ループ処理と剰余演算ができれば解ける問題。
B - Farthest Point
N個の点の座標が与えられるので全組み合わせで２点間の距離を計算して、 各点から１番遠い点の番号を順番に答える問題。
指定されている距離の定義はユークリッド距離だけど、ルートが出てくるので距離は小数点以下の値が出てくることになる。 小数点以下に値があるということは誤差が出てくるかもしれないので、できるだけ整数の範囲で解きたい。 問題をよく読んでみると、答えには求めた距離を出力する必要はなく値の大小関係だけが必要なので、わざわざルートを取る必要はない。
なので２重ループで全組み合わせを試しつつ、ユークリッド距離の２乗を元に各点から１番遠い点の番号を求めて、 順番に出力していった。
C - Colorful Beans
色と美味しさがセットになった情報がN個あるので、色でグルーピングしつつ、各グループの美味しさの最小値を求めてから、最小値の中の最大値を出力する問題。
色ごとに美味しさの最小値を管理したいので連想配列を使って色ごとにグループを作る。 あとはグループごとの最小値を集めて、その中の最大値を求めて出力すれば良い。
連想配列が扱えるかどうかな問題だと思う。
D - Medicines on Grid
グリッドの一部に障害物があってエネルギーを１消費して隣接するマスへ移動できる。一部のマスには薬があって、使えばエネルギーを指定の値に変更できる。
この時指定されたスタートからゴールへ移動できるかどうかを答える問題。
ただの指定されたスタートからゴールへ移動可能かどうかを答える問題なら深さ優先探索とかで解けば良い、よくある問題。それに対して今回はエネルギーという設定があるのがちょっと違う部分。
だと思って各マスに到達できる最大のエネルギー残量を更新しながら幅優先探索で解いてみたらTLEになった。そのあといろいろ試行錯誤してたけど全然解消できなかった。
