AtCoder Beginner Contest199に参加しました。
会社都合で引越すことになって3週間くらいネット環境がない生活をしてたからすごく久々な気がする。 実際にはABC198の1回だけしか飛んでなかったけど。
結果
A,B,C問題の3問正解でパフォーマンスが1155でした。もう少しで緑色に戻れそう。3週間位何もしてなかったけどパフォーマンス落ちてなくてよかった。
D問題から急に難しくなった気がした。Cまではサクッと解けたけどDからむずくて全然わからなかった。
A - Square Inequality
問題文通り計算して判定するだけ。
IF文と2条の計算がというか掛算ができれば解ける。
B - Intersection
の候補は
の最大値～
の最小値の範囲の数値になる。
この範囲の数が何個になるかを数えて答える。
= {1,2,3,4}とすると1,2,3は
=4より小さい。
の候補を{1,2,3,4}とすると{4}以外は
x を満たせない。よって境界値としては
の最大値以外は気にしなくて良い。
同様に考えるとの最小値以外は気にしなくて良くなる。
C - IPFL
問題文にあるとおりに処理をすれば良い。ただし、の場合の、文字列の前半と後半を入れ替える処理は時間がかかる。
のたびに処理をしていたらTLEになるのでこの処理が重い部分を工夫して間に合うようにする。
最終的に入れ替える処理が偶数回だったら途中で入れ替える必要はない。結局元に戻るならその処理は無駄になるから。奇数だったら最後に入れ替えれば良い。
とりあえず、入れ替え処理が起きている回数が奇数が偶数か管理しておいて入れ替え処理自体は行わない。入れ替え処理が奇数の間はのときの処理で交換する文字のインデックスを注意して文字を交換する。
一通り処理が終わった後に入れ替えが必要かどうか確認して、入れ替え処理が奇数回のときは前半後半の入れ替えを行う。
D - RGB Coloring 2
さっぱりわからない。条件を満たす色の塗り方が存在するかどうかなら幅優先か深さ優先探索で求められると思うけど、今回は条件を満たす色の塗り方が何通りあるかなので全探索が必要な気がする。
もしくはDPかなあ。
問題文を読んで4色問題を連想したけど、今回は3色だからグラフの形次第では条件を満たせない場合があるのかが気になった。
全探索なら計算量は最大でN=20の場合の = 3486784401通り確認が必要だと思うけど、これだと
だからTLEしそう。
