naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Regular Contest 103

9/29(土) 21:00 - 22:40
1ヶ月ぶりぐらいのARC

1.5完で427位、レーティング微減 (1718→1714)

C - /\/\/\/ (300)

偶数グループ、奇数グループごとに頻度を取って
最頻のやつ2つに合わせる
最頻のやつがかぶった場合、最頻と次頻、次頻と最頻の組み合わせで良いほうを取る
→AC
https://beta.atcoder.jp/contests/arc103/submissions/3291856

D - Robot Arms (600 (300))

偶奇がすべて等しい場合にのみ可能、というのは自明(だよね)

出現する折り目の長さを全部調べて
折れる必要があるなら折れるようにして
最後に余りを折り返して
これならm=高々4000ぐらいで行けるじゃん

問題読み返して
m≦40って書いてあるじゃん
おい

諦めて部分点を取りに行く(長さ1のアームを必要数用意して組むだけ。300といってもC問題より楽なのでは)
→部分点300
https://beta.atcoder.jp/contests/arc103/submissions/3296247

E - Tr/ee (700)

サンプルが親切で、Nは無理というのを教えてくれている
(木なので)1は必ず出来る。nが出来たならN-nも当然出来る。
てことはN/2までについて考えればいい

1つのノードに3本以上枝があればそれは分離できない、ということを利用する。

例えば
2が出来て3が出来なくて4が出来て、というのはどういうことか

o-o-o-o-(残り沢山)
    |
    o

こんな感じか

2が出来て3,4が出来なくて5が出来て、だったら、ぶら下げるのが1つ増える感じか
(あとでGraphvizで描くか)

Nが偶数のとき・奇数のときとか気になる。N/2が行けたとき、行けないとき。

時間ぎりぎりで、手元のやつをとりあえず投げて
→WA

終了後にデバッグして通せた…(方針は合っていただけに悔しい)
→AC
https://beta.atcoder.jp/contests/arc103/submissions/3303439

F - Distance Sums (900)

開いてない