Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 254

4完2WA。

各問題

A - Last Two Digits

文字列で取って後ろ二文字を出力します。

B - Practical Computing

問題文の漸化式をそのまま実装します。

C - K Swap

iをKで割って余りが同じになる位置は任意に移動できるので、iをKで割って余りが同じになる位置毎に配列を作ってソートしてから元の配列を復元します。

それがソートされていればYesです。

D - Together Square

1からNまでのそれぞれについて以下の処理を行います。

  • 素因数分解
  • 素因数が奇数個のものの素因数をかけ合わせる
    • これが組にできる最も小さい数
  • その数に4, 9, 16, 25,... を掛けたものも組にできる数なので(平方数に平方数を掛けても平方数)、N以下でそれがいくつあるか数える
    • 多分二分法をするのが筋だと思いますが、この問題の制約だと4から順番に探索しても間にあいます

これで見つかった数の合計が答えです。

E - Small d and k

解説どおり実装しているつもりなんですが、なぜかTLE...。なぜなのかまだわからず。

(追記)

TwitterのTLに流れてきた情報によると、訪問済みかどうかを管理する配列を毎回初期化していたのがだめだった模様...。

// だめ
while (q--) {
    vector<int> visited(n, -1);
}

// だめじゃない
vector<int> v(n, -1);
while (q--) {
    vector<int> visited = v;
}

なるほどなー。

まとめ

Eが解けているはずなのに解けていないという悔しい結果に。BFSを実装しそこなっている?そんなことある?