2016-12-24
SRM 694
https://competitiveprogramming.info/topcoder/srm/round/16766/div/1
Div1 Easy (250) TrySail
問題
- N人の生徒がいる
- 各生徒の強さが非負の整数で与えられる
- 3グループにわける
- 各グループの強さは、グループ内の生徒の強さのXORである
- 3グループの強さの最大値を求める
方針
- DPっぽい全列挙
- 最大でも255までしかないので、到達する可能性のある値を全て列挙する
- グループ3の値はグループ1と2の値から求まるので、256^2を調べれば良い(グループ1にも2にも所属しない人は3にいるものとして扱う)
- dp[i番目の生徒][グループ1][グループ2] = 到達可能性(0: 不可能、1: 可能)
- 最後に、到達可能性のある値から最大値を求める
- Passed System Test
- htts://github.com/firewood/topcoder/blob/master/srm_6xx/srm_694/TrySail.cpp
結果
o-- +1 110.22 + 50 = 160.22pt 177th/358 rating 1478 -> 1500 (+22)
なんとか解いて黄色復帰。
必ず3チームにわかれると考えて良い。なぜなら、2チームにわけてから、誰か一人を3チーム目に行かせても、合計は同じか大きくなるかのどちらかで、3チームにわけて損することはないため。
2016-12-23
SRM 693
https://competitiveprogramming.info/topcoder/srm/round/16748/div/1
Div1 Easy (250) BiconnectedDiv1
問題
- 任意の頂点u,vについて、任意の辺eを取り除いてもuからvに到達可能なグラフを、2辺連結グラフと呼ぶ
- N個の頂点が与えられる
- 頂点iとi+1には重みw1[i]の辺がある
- 頂点iとi+2には重みw2[i]の辺がある
- 2辺連結グラフを維持しながら、辺を除去するとき、重みの合計の最小値を求める
方針
- DPでできそう
- ある頂点の状態として、入ってくる辺と、出ていく辺と、その頂点を追い越して次の頂点に接続している辺がある
- 制約条件は、必ず2辺以上を持つこと
- 最初の頂点は必ず2辺が出ていく(自分を追い越す辺はない)
- 最後の頂点は必ず2辺が入る(自分を追い越す辺はない)
- dp[頂点][辺の状態]＝コスト として、辺をつないでいない状態からスタートし、1頂点ずつ処理していく
- 自分に2辺接続していたら(2つ前か一つ前の頂点から辺が出ていたら)、出ていく辺の本数は任意
- 自分に1辺接続していたら、1または2本の辺を出す
- 前の頂点から辺がなければ、2本の辺を出す
- Passed System Test
- (終了後)
- 複数の場合をまとめた
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_693/BiconnectedDiv1.cpp
結果
o-- 99.77pt 160th/373 rating 1429 -> 1478 (+49)
DP書くのに1時間くらいかかったが、4連続0点から脱出できた。
2016-12-21
TCO16 Algorithm Round 2C
https://competitiveprogramming.info/topcoder/srm/round/16760/div/1
Easy (250) BearBall
問題
- 2次元平面上にN匹の熊がいて、それぞれの座標が与えられる
- 1ターン毎に熊から熊へボールを投げるゲームを行う
- ボールの軌跡は直線である
- ボールの軌跡上にいて、ボールをさわったことのない熊がキャッチする
- 熊iからはじめて、熊jがボールをキャッチするまで行う
- iとjの全ての組み合わせについて、最短ターン数の合計を求める
方針
- (終了後)
- 全ての点が一直線上にあるか、そうでないかで場合分け
- 全てが一直線上にあるときは、途中の点をスキップできないので、全ての点同士の距離の組み合わせになる
- Σi×(i+1) = (N-1)×N×(N+1)÷6×2
- 全てが一直線上にないとき
- 始点からゴールまでの一直線上に他の熊がいなければ、1
- それ以外の場合、始点とゴールをさえぎらずに直接結ぶ1点が必ず存在するので、2
- https://github.com/firewood/topcoder/blob/master/tco_2016/BearBall.cpp
結果
--- 0pt 215th/510 rating 1467 -> 1429 (-38)
AM2時からの回。
二つくらい気づかないといけないので難しかった。
2016-12-19
SRM 692
https://competitiveprogramming.info/topcoder/srm/round/16747/div/1
Div1 Easy (250) HardProof
問題
- 0からN-1までのN問の命題がある
- 任意の言明x,yについて、xならばyを証明することの難易度が与えられる
- 直接または間接的に、全ての任意の二つの言明x,yについて、xならばyを証明することにする
- 最も難しい証明と最も易しい証明の差を最小化するとき、差の最小値を求める
方針
- (終了後)
- 命題0ならば[各命題]
- [各命題]ならば命題0
- の両方を満たせば、任意の命題を満たすことになる
- コストの差の上限を決め、それ以下の辺だけを使って、コストの差を二分探索
- 命題0ならば[各命題]は、ある辺nからDFSする
- [各命題]ならば命題0は、ある辺nへ入ってくる頂点へのDFS
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_692/HardProof.cpp
結果
--- 0pt 88th/196 rating 1510 -> 1467 (-43)
2-SATやSCC使っても解けるらしい。
2016-12-17
SRM 691
https://competitiveprogramming.info/topcoder/srm/round/16730/div/1
Div1 Easy (300) Sunnygraphs
問題
- 0～N-1までのN個の頂点がある
- 各頂点iは、頂点a[i]と辺を持つ
- 0本以上の任意の辺を頂点Nとつなぎ直すとき、頂点0と1が連結である場合の総数を求める
方針
- (終了後)
- pekempeyさんの解説を読む
- 0から行ける頂点に1、1から行ける頂点に2をORしていく
- 値が0,1,2,3の頂点をそれぞれw,x,y,zとする
- (1)xをNにつなぎかえるとき(2)yをつなぎかえるとき(3)xとyをつなぎかえるとき(4)xとyをつなぎかえないとき、それぞれで計算して、最後に2^w倍する(wの状態は連結に無関係なので全ての場合がありうる)
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_691/Sunnygraphs.cpp
結果
--- 0pt 118th/411 rating 1523 -> 1510 (-13)
これは全く手が出なかったが、コードはシンプル。