4完。構築パラダイスだ。
No.687 E869120 and Constructing Array 1
本来なら1とn-1を出力したいところだが、nが20になり得るところ10以下で出力する必要がある。n/2と(n+1)/2にした。これは感覚的に上手く行くはず。nが1増えると和も1増える。こんな難しいことをせずともn/2とn-n/2にすればよかったか？いや、あっちのが簡単だろう。見えた答えが一番簡単だ。
No.688 E869120 and Constructing Array 2
状況がつかみにくいが、合計が2というのは1を2個と0を任意個選ぶということだ（ここまでにかなりの時間がかかった）。Nが30以下でできると保証されているので、Nと1の個数を全通り試せばいい。1がM個として、M個の中から2個を選びN-M個の各0について選ぶか選ばないか。
No.689 E869120 and Constructing Array 3
素数というのは難しそうだが、どうせ素数の性質は使わないのだろうと予想。Kは10000以下と比較的小さい。とりあえず1を140個でそのくらいになる。ここで、5,8というペアを使えば、1との組み合わせで素数になることはないので独立に個数を増やせる。5を1個とすれば8の個数で1ずつ調整可能。しかしNが250以下という制約に微妙に引っかかる。なので同じことをもう一段やる。こういうペアがもう一つあれば、今度はわりと余裕を持って構成できる。なかなか見つからない。素数って意外と多いんだよね。見つけるプログラムをパッと書いてというのが本来の姿だと思うが、プログラムを書く面倒臭さが手計算の面倒臭さを上回ってしまい、結局手で見つけた。1,5,8,13,34。あとは書くだけだが、ここはパターン化されていないので厄介だ。まあ空のfor文を書いて堅実に作っていった。
No.690 E869120 and Constructing Array 4
木か？と思ったけど木じゃない。どうやって組合せを爆発させるかわからない。2乗っぽく見える。Kが10^9でNが32なので、スタートとゴールの2頂点を除いて2^30を作るということか？実際、その30頂点のそれぞれを通るか通らないかで2^30通りにできそう。本当か？いやあ、慣れないと感覚が全然だね。そもそも、パスカルの三角形的な、経路を数えるやつと同じなんだけど、グラフという形で目の前に現れても、それが同じものだと気づかない。気づいても確信できない。
さて、どうやってKを作るか。けっこう複雑そうに思える。とりあえず全ての辺を張ってから、スタート地点からの1本を切ってみる。それで減るのは、そこからゴールまでの各頂点を通るかどうか。2冪を簡単に引ける？こんな簡単なの？感覚と違ったが、解けてることに反論できないので実装する。スタートからゴールへの辺はナシにする。これで2^30-1まで作れる。
No.691 E869120 and Constructing Array 5
難しそうなので撤退していた（やる気ないときは無理しないのだ）。まず、解けそうだと思った。方針としては、30個のe_iにほぼ均等に割り振り、大きさ順に並べたとき隣との差29個が対数のグラフ的になってるくらいにして、差が大きいほうから順に調整していく。しかし、10000と10000を10001と9999にしても10^-10には届かない。調整できたとして調整回数が大きくなりそう。3個や4個を組み合わせればもっと精度が出るんだろうけど。解けそうという感覚は変わらないものの、自分には無理だという感覚になった。
