トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）に参加しました。
結果
A,B,C問題の3問正解でした。
D問題が難しかった。コンテスト後に解説を読むと割と惜しいところまでは考察があってたっぽい。
A - Print 341
101010・・・101のように0をN個と1をN+1個交互に出力する問題。
特に悩む要素はなくN個10を出力してから1を出力すれば良いだけの問題。
B - Foreign Exchange
N種類の通貨があって、通貨i Si単位をを通貨i+1 Ti単位に両替できる。このとき通貨Nは最大いくつ取得できるかを答える問題。
通貨はiからはi+1にだけ両替できるので、通貨1から順番に両替できるだけ両替していけば 通貨N-1を通貨Nに両替できるだけ両替すれば通貨Nの量を最大にできるようになる。
C - Takahashi Gets Lost
グリッドがあって、各マスは海か陸のどちらかでできている。陸だけを移動した時の上下左右の移動情報が与えられるので初期位置の候補数を答える問題。
ある位置が初期状態としてあり得るかどうかは、そこから移動情報通りに移動させたときに1度も海の上を通過しないかどうかでしか判断できないので、全通り確認して判断した。
制約を見ても全通り確認するのは処理時間的に十分余裕があるので、 初期位置を渡すと候補としてあり得るかどうかを検証して結果を返す関数を作ってから 全通りの確認を実装することにした。
D - Only one of two
NとMの倍数のうち、公倍数を除いたものの小さい方からK番目のものを出力する問題。
あれこれ考えて実装してみたけど制約ギリギリの場合だとTLEになるばかりで全然解けなかった。
最小公倍数以下だと条件を満たす数がいくつあるか数えつつ、K番目の数は公倍数何倍分＋αなのか計算して α分をどうにかして求めようとして解いてた。
最小公倍数以下の条件を満たす数を一通り求められれば簡単に算出できるけど、 ”最小公倍数以下の条件を満たす数”を一通り求めるのが簡単にはできなくて解ききれなかった。 制約ギリギリの入力があった場合に候補となる数が多すぎて配列の要素数が上限を超えててエラーになったり、 その部分だけでTLEになってだめだった。
