11/20 PKU
2132 Cow Math
辺に重みがついているグラフが与えられる。起点から終点までの各経路について、通った辺の重みの最大公約数を考える。すべての経路について最大公約数を求めた時、それらの最小公倍数を求めよ。
答えをRとして、Rがある整数iで割り切れるかどうかは、重みがiで割り切れる辺のみ使えるとすればどうにでも求まる。iを素数冪について動かして、多倍長乗算を行えば解ける。
3941 Expected Allowance
「M面のサイコロをN回振って出た目-K」枚の1000円札がもらえるらしい。この値が0以下でも1枚もらえる。もらえる1000円札の枚数の期待値を求めよ。
DP
3802 Cubist Artwork
立方体を積み重ねてできた立体を左、前からみたときの様子がそれぞれ与えられるので、立体に最小で何個の立方体が含まれるか求めよ。
ソートしてgreedy
3193 Cow Phrasebook
会話集と、実際になされた会話が与えられる。会話のうち、会話集のいずれかの会話の接頭辞になっているものの数を求めよ。
Trieやるだけ
3037 Skiing
グリッド上のスキー場がある。各地点標高が決まっている。初速はVだが、標高Aの地点から標高Bの地点に移動すると速度が2^(B-A)倍になる。左上から右下までの最短時間を求めよ。
Dijkstraやるだけ
2454 Jersey Politics
3K個の町を、K個ずつ3つのグループに分ける。各町には1000頭の牛がいて、そのうち何頭かがジャージー牛である。3つのグループのうち最低2つのグループで、そのグループの牛の過半数をジャージー牛が占めるようにグループ分けせよ。
町をジャージー牛の数でソートして、少ないK個の町を1つのグループにする。
残りの2つのグループは過半数のジャージー牛を含まないといけないが、DPを用いて計算する。グループの数に制約があるので今グループに何個の町を含んでいるかもDPの要素にしないといけないが、64ビットのビット演算で無理やり計算した。
実際は探索で解くものらしい。
2359 Questions
質問が与えられる。質問に対して、「N-1文字スキップ（末尾の次は先頭）して、N文字目を削除して、次の文字に移る」行為を1文字になるまで行った時、残った文字に応じてYesやNoやNo commentsを出力せよ。
やるだけ
