1/16 PKU
3767 I Wanna Go Home
いくつかの都市とそれらを結ぶ双方向の道がある。道にはそれぞれ所要時間が決まっている。また、都市は支持するリーダーによって2つに分かれている。異なるリーダーを支持する都市同士をまたぐのは、1回までに抑えたい。都市1から都市2までの最短の時間を求めよ。
都市1と都市2のリーダーが同じか異なるかで場合分けしてDijkstra。
3740 Easy Finding
高々16行300列の行列において、いくつかの行を選んで、その行の集まりの中ですべての列がちょうど1つの「要素が1であるような行」を持つような選び方が存在するかどうか判定するだけの簡単なお仕事。
全探査っぽいもの。行の集まりを上半分と下半分に分けてやった。
2171 Amusing Numbers
1からNまでの整数を辞書順に並べて、整数KがM番目に現れるような最小のNを求めよ。
二分探索
3725 I know the k-th integer
1からNまでの整数を辞書順に並べて、K番目の整数がMであるような最小のNを求めよ。
2171と全く同じ
3724 Find the parameter
ai(0<=i<=9)は1以上10以下の整数で、a_i <= a_i+1が成り立つ。N個のxiに対して、yi=exp(a0xi)+exp(a1xi)+…+exp(a9xi)が定められている。a0〜a9を決定せよ。
全探査。誤差判定に注意