AtCoder Beginner Contest 180 振り返り
結果
ABCDEの5完でパフォ2307。初の黄パフォです！
EFの間に大きめの壁があったおかげで早解きがパフォーマンスに直結しました。
Eは巡回セールスマン問題ほぼそのままの問題で、過去の提出コードをコピペして提出しました（汗
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0:21 | 1:26 | 2:39 | 7:34 | 20:39 | - |
問題
C - Cream puff
問題概要
約数を昇順に出力する。
感想
問題文を読まずに入力例2を見て約数列挙をコピペしました。
練習のときはちゃんと書いてるので、本番コピペは許されます（は？
D Takahashi Unevolved
問題概要
整数が与えられる。A倍する or Bを足すの操作を行うことができるが、整数がY以上になったらそこで終了。最大何回操作を行うことができるか。
感想
読解に少し手間取りました。Bを足してからA倍するより、A倍してからBを足すほうが操作回数は多くなるので、最初に何回A倍するかを全探索。
後半でBを連打するので実質Bボタンキャンセル。
E - Traveling Salesman among Aerial Cities
問題概要
巡回セールスマン問題。典型との違いは、1つの都市に複数回立ち寄ることができる点。
ただし、移動コストがマンハッタン距離のような形で与えられ、三角不等式が成り立つので同じ都市に複数回立ち寄る必要はない。
感想
コピペゲーでした。すみません…。
F - Unbranched
問題概要
N頂点M辺のグラフ(単純とも連結とも限らない)で、次の上限を満たすものの個数を答えよ。
- 自己ループを持たない
- すべての頂点の次数が2以下
- 各連結成分の大きさの最大値がちょうどL
感想
時間はあったものの、ほとんど考察が進みませんでした。
考察のステップ一つ一つが未履修という感じで、現時点での実力では解けそうになかったです。
いかにも教育的な問題という気がするので、しっかり復習しておきます。
考察ステップ
頂点の次数が2 → パス or サイクルの言い換え
最大値がちょうど%%L%%の場合の数 → %%f(x) =%% 最大値がx以下の場合の数として、 %%f(L) - f(L - 1)%% を求める
重複なく数え上げるために、ラベルの最も若い頂点を固定する
%%dp[n][m]%%: %%n%%頂点%%m%%辺のグラフのうち連結成分の大きさの最大値が%%L%%以下であるものの数
