2016-09-21から1日間の記事一覧
問題 問題概要 省略 解法 2分探索でとく。関数はだいたい増加しているような関数であるので、解をもつ範囲の左端をL、右端をR、真ん中をM とすると、t=Mの時に、関数の値が100を超えるなら、中間地の定理より(あたりまえ)、左側の部分に解を必ず一つはもつ…
問題 問題概要 省略 解法 上司から直属の部下に対して辺を張り、有向グラフを作成する。それを利用して、dfsを行う。部下がいないとき、つまり、グラフ上で葉の部分に該当する部下の給料は1なので、1を返す。部下が存在するとき、つまり、葉以外の頂点では、…
問題 問題概要 省略 解法 aは昇順に並んでいるので、時系列に沿った形で見ていく。ドアが開き始めた時間をl、閉じる予定の時間をrおき、aiがrより小さいなら、なら、時間がtよりすくないが延長され、rより大きいなら、一度ドアが閉じ、そのあと、時間がtだけ…
問題 問題概要 x軸上をスタートからゴールまで到達するのにかかる最短時間を求める問題。ただし、時間ごとに、動けるx軸上の位置が与えられる。 解法 ループが存在するわけでなく、ただ単にx軸上を動くだけなので、実験すると貪欲にやればいいことがわかる。…