Educational Codeforces Round 15: A-E
つい最近 Haskell の練習を始めたので、一部の問題を Haskell で解き直しました。本番中はすべて C++ で解いています。
- A. Maximum Increase
- B. Powers of Two
- C. Cellular Network
- D. Road to Post Office
- E. Analysis of Pathes in Functional Graph
A. Maximum Increase
http://codeforces.com/contest/702/problem/A
a[i]<a[i+1] のリストを作り、連続する True の最大長 +1を求める。
zipWith (<) a (tail a)
でa[i]<a[i+1] のリストが作れる。後は地道な合成。ポイントフリーで書けるのだろうか。
map read の型指定の書き方が良くわからなかったので、toint という関数を新たに置いた。コンパイルエラーメッセージを読むのに慣れない。
B. Powers of Two
http://codeforces.com/contest/702/problem/B
それぞれの i に対して a[i]+x=20, a[i]+x=21, a[i]+x=22, ... を満たす x の個数を数えて足し合わせればいい。二重カウントしないように注意。
Haskell の Map は非破壊的な平衡二分探索木になってるので良い。
insertWith
は (a -> a -> a) -> k -> a
で一つ目の引数に更新用の関数 \newval oldval -> newval
を渡せる。今回は 1 ずつカウントするので (+)
を渡しておけばいい。
C. Cellular Network
http://codeforces.com/contest/702/problem/C
それぞれの地点における最寄りの基地局との距離を求め、その最大値を答えればいい。
D. Road to Post Office
http://codeforces.com/contest/702/problem/D
よく考えると最適になり得る移動方法は次の 3 通りしかない。
- ひたすら車で移動する
- 最初の 1 回だけ車を使って後は歩く
- ギリギリまで車で移動して、最後だけ歩く
時刻と移動距離の関係を表すグラフを作れば極端な始点以外は最適にならないことは明らか。
E. Analysis of Pathes in Functional Graph
http://codeforces.com/contest/702/problem/E
この辺からは手続き的に解かないと辛そうなので C++。
LCA でお馴染みのダブリングをする。
- succ[i][j] = 頂点 j から 2i 回移動した先の頂点
- sum[i][j] = 頂点 j から 2i 回移動したときのコストの総和
- mini[i][j] = 頂点 j から 2i 回移動したときのコストの最小値