今日解いた競プロの問題。
競プロ典型90問
070 Plant Planning: ぱっと見で分かんなかったので次元を落として考えてみる。1次元の場合を考えてみるとなんかU字型のグラフになって、片半分の工場の数=もう片半分の工場の数となるあたりで良い感じになる図が見える。そして2次元の場合を考えると、これxとy独立に考えられるじゃんという話になるので、xとyを別々にソートして真ん中の地点に発電所を置けばおわり。
ゲームフリーク・プログラミングチャレンジ ピカチュウ サトシとおつかいチュウ！:
とりあえず最短経路となる道は、都市A/Bそれぞれから距離を出してやれば絞られる。トレーナーの遭遇数の最大化も、それぞれの道をどのトレーナーが見ているかを事前に調べておけば(これはO(HW)で出来る)どこを通ればどのトレーナーと出会うのか判定できるので、適当にDPすれば良い。問題はトレーナーの二重カウントを避けるところ。
「同じトレーナーの視線上にいる間は新たにカウントしなければよい」というやり方が真っ先に考え付くが、同じトレーナーの視線からいったん外れてもう一回入る場合があり得る。この場合は二重にカウントしてしまう。しかし考察すると、このような可能性は考える必要がないことが分かる。
まず問題の設定として「最短経路を通らなければならない」「トレーナーの視線はまっすぐな道しか通らない(壁で遮られる)」という前提がある。仮にあるトレーナーの視線からいったん外れてもう一回入ったとする場合、視線上(道なので明らかに通れる)を移動することで必ず経路が短縮できる。そのためそのような移動経路は最短経路ではありえず、考慮する必要はない。
コード生成というものをいい感じにやってみたいと思い、C++でmustacheを扱えるライブラリを探したところ、なんか4つくらいあることが分かった。
- kainjow/Mustache: vcpkgに登録されてないので微妙。
- bustache: C++20のformatに依存しているのと、書き方があまり好みじゃない。
- plustache: メジャーバージョンが1に上がってないのはこわい。
- mstch: 書き方が好みで良さそうだった。というかmustache公式ページでリンクされてるのがこれ。
ということでmstchを使ってみた。結構手軽で便利に扱えてよかった。
2.5kmほどジョギングした。フォームとかなにも考えないで気の向くままに走ったせいか脚が痛い…
数日前に腹筋ローラーをやったときの筋肉痛が明らかにもう完全になくなっていたので腹筋ローラーをやった。数えてみたら6日前だった。そりゃ筋肉痛も終わるわ。
前回と同じく10回×3セット。それなりにつらい。明日筋肉痛とかどう出るか。
Categories: 未分類