Atcoder Beginner Contest 131参加記
問題
A - Security
連続してたらBad。
Submission #6056333 - AtCoder Beginner Contest 131
B - Bite Eating
味の絶対値の小さいものを食べる。
Submission #6060148 - AtCoder Beginner Contest 131
C - Anti-Division
all - (Cの倍数の数 + Dの倍数の数 - CとDの最小公倍数の倍数の数)
(かぶりが最小公倍数の倍数になることに気付かず。。。)
Submission #6103958 - AtCoder Beginner Contest 131
D - Megalomania
期限の近い順に貪欲。
Submission #6075069 - AtCoder Beginner Contest 131
納得感を持って投げるには証明したほうがよい。 (コンテスト中は見切りで投げても良いかも)
蟻本に区間スケジューリング問題が載っていて、その解法が期限近い順に貪欲だったのも、参考にした。
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る
E - Friendships
グラフ苦手。方針たたず。。
コンテスト中
全探索ではありうる全辺の組み合わせで、ある点からある点までの最短経路を求め、条件を満たす場合に経路復元するのだと思うが、 Mを1つずつ増やして、その数でありうる辺の組み合わせを全探索する方法がわからず。。
解説読んだ後
スター(うに)グラフを起点に考えるらしい。 AtCoder ABC 131 E - Friendships (500 点) - けんちょんの競プロ精進記録
第一歩目としてグラフを解くときに手元で性質を見てみるの大事。 Submission #6105858 - AtCoder Beginner Contest 131
F - Must Be Rectangular!
たどりつけず。
解説読んだ後
drkenさんの解説をC#で焼き直しさせていただきました。 AtCoder ABC 131 F - Must Be Rectangular! (600 点) - けんちょんの競プロ精進記録
はじめてのUnionFind。はじめての二部グラフ。 Submission #6138324 - AtCoder Beginner Contest 131
2次元上の座標の問題が来たらこの問題を思い出したい。
Tips
LCMとGCDの関係
ある数a, bの最小公倍数lcmと最大公約数gcdの関係は以下となる。