I should put more effort into these surely

• A: trivial
• B: trivial
• C: trivial (altho somewhat annoying)


• D: state machine thing; track # of X, XY, then for each character i of string, update i, Xi, and find number of iY (which turn into iYi)


• E: no idea how to handle the 'move min # of people' part


• F: bruteforce clearly doesn't work, idk speedup


• G: pretty nice by dijkstra:
  
  observe that for an edge to result in two different values, it must be part of all optimal-length paths. by dijkstra, we can find distance from node 1 to all nodes. notice that we can then determine all optimal paths in an efficient manner:
  
  the union of all optimal paths must form a DAG. we can reconstruct this graph by inductively selecting some node i that we know to be on the DAG, and then finding all edges j -> i such that dist(1 -> j) + dist(j -> i) == dist(1 -> i), where dist(a -> b) denotes the shortest path length between a, b.
  
  setting our base case to be i = n, this suffices to reconstruct the optimum-path DAG. then notice that for an edge to be present in all optimal paths, it must be a bridge in the DAG; we can find these edges by using another dijkstra pass (or dfs).

gonna take ARC tomorrow I think

tags: programming atcoder contest-logs