AtCoder Beginner Contest214に参加しました。
結果
A,B,C問題の3問正解でパフォーマンスが1249でした。 C問題が早く解けるかどうかでパフォーマスンスがかなり変わるなあ
A - New Generation ABC
問題文のとおりに実装するだけの問題。if文を使って出力する値を制御するだけ。
B - How many?
制約的に3重ループで探索しても問題ないので3重ループで全探索を行う。の制約からa,b,cそれぞれ0から100までの範囲で探索すれば良い。最大でも
程度なので時間には収まるので問題なさそう。
C - Distribution
要するに隣の人からもらうのが早いのか直接もらうのが早いのかを計算して答える問題。
1番目から順番に計算しつつ2周分計算する。
D - Sum of Maximum Weights
TLEになって解けなかった問題。
全対地間分の経路計算をして辺の重みの最大値を計算して最後に足し合わせたら良さそう。だけどNが大きくて全対地間分のデータは保持できないので、逆に最大がどの重みの対地間が何組あるのかをmapとかに持たせて、最後に合計を計算すれば処理できそうまでは考えて実装できた。
経路計算するのにダイクストラを使ったけどN回実行しないといけない上に、ダイクストラ1回実行後に各宛先への辺の重み最大値を確認するので結局になってTLEにしかならなかった...
F - Substrings
解き方がわからなかった。具体的には文字列が被る場合の重複分を除く方法がわからなかった。
同じ文字でも元の文字列の場所が異なれば別の文字列して扱ってくれるならとDPで解けるし実装できたけど、答えるべきなのはできた文字列が何種類かなので、DPの途中で文字列の被りを考慮して進める必要がありそうまでは考えた。
