pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Educational Codeforces Round 15: A-E

つい最近 Haskell の練習を始めたので、一部の問題を Haskell で解き直しました。本番中はすべて C++ で解いています。

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. ひたすら車で移動する
  2. 最初の 1 回だけ車を使って後は歩く
  3. ギリギリまで車で移動して、最後だけ歩く

時刻と移動距離の関係を表すグラフを作れば極端な始点以外は最適にならないことは明らか。

f:id:pekempey:20160731171552p:plain

f:id:pekempey:20160731171556p:plain

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 回移動したときのコストの最小値
E で周期性云々を最初考えてしまってハマった。