AtCoder Beginner Contest 347に参加しました。
結果
A、Bの2問正解でした。
C問題がわからなかった。考えれば考えるほど、この解き方だとこのパターンをうまく落とせないとか、解けはするけどTLEになるなあとか出てきてダメだった。
C問題だけど一旦飛ばしてD問題とかを解きに行ってたほうが良かったのかも。 (C問題が解けないなんて思ってもいなかったけど。)
A - Divisible
指示通りに処理する問題。
大体の言語だと%を使えば倍数かどうかの判定ができるので、知っていれば特に困らない問題。 標準の入出力と数値計算ができれば解ける問題。
B - Substring
文字列が与えられるので部分文字列の種類数を答える問題。
種類数を答える問題なので重複を除去して答えの候補となる部分文字列を管理したい。なのでsetを使いたい。
setさえ使えれば、部分文字列をsetに入れていき最後にsetのサイズを出力するだけで済む。
C - Ideal Holidays
1週間が休日A日間、平日B日間ある世界で、N個の予定がそれぞれ今から日後にある。 今日が1週間のいつなのかわからないけど、予定全てが休日の可能性があるかどうかを答える問題。
考えれば考えるほど難しいなあと思った問題。
とりあえず何日後と言う情報はそれほど重要じゃなく、何曜日かが重要なので、 をA+Bで割ったあまりに置き換えて、何曜日に予定があるかどうかで考えることにした。 ついでに、その曜日に1度でも予定が入っていればそこの曜日は休日になって欲しい曜日候補になるので、 setにをA+Bで割ったあまりの情報を入れて重複を除去することで扱うデータ量を減らすことにした。 ここからが全然うまくいかなかった。
愚直に解くなら
x番目の曜日を休日の始まりとしてそこからA日間で全ての予定が収まるかどうか をで確認して1度でも予定が全部休日に収まるxがあれば計算終了で、解答できる。
でもこの方法だとの制約的にTLEするパターンがあり得る。
他の方法もいくつか考えてみたけどTLEするパターンしか思いつかなかった。
予定のある曜日と曜日の間が何日空いているかを元になんとかならないかなとも思ったけどうまくいきそうな方法が思いつかなかった。