トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)に参加しました。
結果
A,B,C,Dの4問正解でした。
E問題は単純な最小全域木を求める問題だと思って解いてたけど勘違いしてた。 勘違いに気づいたのが残り5分のところで、どうにか対応させられないかと考えたけど5分じゃ無理だった。
A - Not Too Hard
問題文のとおりに処理して答える問題。
数値を受け取ってX以下なら合計に加えて、という処理をN回繰り返して最後に合計を出力すれば解ける。
数値の入力とif文、数値の加算と標準出力ができれば解ける問題。
B - 11/11
月日がゾロ目かどうかを判定して、ゾロ目の月日の日数を答える問題。
解き方を考えていると月と日それぞれを10進数表記としたときにゾロ目になるかどうかって言うのが面倒だなと思った。 月日を4桁表記にして何種類の数字が出てくるかで判断できれば簡単だけど、11/01の時4桁表記だと1101だけど、月と日それぞれを10進数表記にすると11と1になってゾロ目ってことになる。
結局愚直に解くことにした。10進数表記の月と日を受け取ってそれぞれに対して、10の余りを取ってsetに入れて10で割ってを繰り返して、最終的にsetの要素数が1かどうかでゾロ目だったかどうかを判定した。
C - Consecutive
文字列が与えられるので指定された区間で同じ2文字が連続する回数をQ回答える問題。
Qの最大値がそこそこ大きくてO(Q)で解けないとTLEしそうだなと思った。 と言うことは1回の質問ではO(1)で解きたい。
先頭から任意の位置までで同じ2文字が連続するのは何回かを予め数えておけば、
区間[l,r]が指定されても事前に数えた結果からO(1)で答えられると考えて解いた。
前もって計算した累積和を使って解くのと同じ様だなと思った。
D - Take ABC
A,B,Cのみからできた文字列に対して最初に出てきたABCを削除するという処理を再帰的に行った結果残った文字列を出力する問題。
C++だと文字列の削除はちょっと面倒だなとか、ABCを空文字に置き換えれば良いのかなあとか、C++のreplaceだと指定した1文字を置き換えたり、正規表現に一致した箇所全部を一括で変換するからちょっと違うなあとか思いながら解き方を考えた。
最終的には、
文字列を先頭から順番にスタックに入れていく。Cが出てきたらスタックの上2つを見てABCの文字列が完成していればCはスタックに入れないし確認のために取り出したABもスタックには戻さない。ABCになっていないなら順番に気をつけながらスタックに戻してCをスタックに加える。最後にスタックから文字を取り出して文字列を復元して答えた。
E - Modulo MST
最小全域木を求める単純な問題かと思いきやそうではなかった。
与えられたKで割った余りがグラフのコストになるので、単純な最小全域木に余計な辺を加えてもKで割った余りが単純な最小全域木より小さくなることはあり得る。 このことに気づくのが遅かったので解ききれなかった…
どの辺を選んでどの辺を選ばないかを考えないといけなくなるので、全通りの探索が必要っぽい。
