こんにちは。金恋GTが届いてウキウキのとーです。「とー」と申します。はじめましての人は初めまして。
解くに至った問題（9問）
ARC:042A/054B/074C
ABC:036C/037C/079C/118A,B,D
Typical DP Contest:A
ここ二週間でたまった直しを消化していく
ABC037C
数列の部分和の問題再び 以前の問題では「部分和が0になる区間の選び方はいくつあるか」という話で、第i項までの和をリストに保持しておいて一致する部分の二個の選び方を求めればよいというものだった
今回は、数列のK項の和をどんどんずらして足していくとなんぼになるんじゃいという問題
愚直に足すと、最悪O(N**2)かかって間に合わないが、今回も和をリストに保持しておくやり方が使える
第i項までのリストはO(N)で計算でき、それから区間Kの和は、和のリストLの要素から、L[i+K]-L[i]とO(1)で計算される これなら間に合う
数列の和の問題は総和のリストを作ることを頭に入れておく
Typical DP Contest A
与えられた数字を足し合わせて作ることができる数字は何通りありますかという問題
制約は「与えられる数字は100以下、100個以下」
これをDPを使って解くときは、
①0が10001個あるリストdpを作る
②dp[0] = 1にする（1は「その数字が作れる」ことを意味する）
③与えられた数字kに対し、dp[10000]から下っていくように見ていき、dp[i] == 1であればdp[i+k] = 1（つまり和が作れる）とする
（ここでdp[0]からではなくdp[10000]から見ていくことに注意。もし下から見ていくと、例えばdp[0] == 1だからdp[k] = 1となり、今度はdp[k] = 1だからdp[2*k] = 1となり......と実際には作れない数字も作れることになってしまう）
④リストdpには作れる数字の所のみ1が立っているので、総和を計算すれば作れる数字の個数が分かる
という流れ
ABC118D
数直線上にある寺と神社を、スタート地点からどちらも一件だけ訪れるのに必要な最短経路を求める問題
コンテスト中にACできなかったのは悔しい 二分探索や、神社→寺or寺→神社で場合分けすることを思いついたものの根本的なところが間違えていた模様
まず第一の失敗として、二分探索で自分の居場所を特定する際に、普通に与えられた入力だと、例えば自分が一番西にある神社より西にいる場合、訪れる神社が一つしか候補にあがらず、場合分けが非常にめんどくさくなるというものだった
これを回避するために、両サイドに一番西/東にある座標よりとてつもなく大きいものを座標として仕込んでおく方法がある これを番兵（ばんぺい）という
こうすれば、どこに始点があっても自分の両側に神社/寺が存在し、余計な場合分けを考えなくてすむようになる
さらに第二の失敗として、最短経路の出し方を、「まず自分がいるところから最も近い神社に向かう→そこから最も近い寺に向かう、この距離を求める、これを神社と寺を入れ替えてもう一度やる」というものだったが、これには普通に例外があり（サンプルケースでは通ってしまう）
例えば
寺 x 寺 神社 寺
0 1 3 5 6
というケースを考えたとき、（xは初期位置、下の数字は座標）
上の考え方では
寺(0)→神社(5)と神社(5)→寺(6)という経路が採用され、経路の長さ自体は各々6,6である
しかし、右に進めば寺(3)→神社(5)となり、経路の長さは4でより短く、これは上のやり方からは漏れてしまうような場合である
結局、一意に最小を決定するのは難しいので、自分より右、もしくは左にある最も近い神社と寺(どちらも2つある）を見て、
「神社と寺、どちらを先に訪れるか」*2
「神社と寺、自分より右にあるものを訪れるのか、それとも左を訪れるのか」*2*2
の計8通りをすべて試し、その中で最短のものを答えとして採用すればよいということになる
自分でもとめたやり方は案外間違っていることが多いので、複数候補がある（どれが答えになるか決めがたい）ときは、一回候補を全部挙げてみて、その中で比較するというやり方をちゃんと使えるようになりたい
