問題 自然数m, Kが与えられる。mと互いに素なK番目の自然数を返せ。 やりかた 逐一調べると当然間に合わない。ここは二分探索+包除原理。まず二分探索で解の候補を上げ、その解の候補に対して、それ以下の自然数でかつmと互いに素なものの個数を計算し、その…

問題 二次元座標上に点がN個与えられる。この座標上から一点を指定し、N個の点との距離の総和を最小化せよ。 やりかた 解析的に答えが求まりそうにないので、数理最適化。自分は最急降下法でやった。 選んだ座標をとし、与えられたN個の点の座標をすると距離…

問題 NxNのグリッドがあり、各マスに0以上の整数が書かれている。グリッドの左上のマスからスタートして右か下に一つずつ移動して右下のマスまでたどり着きたい。通ったマスの数字は得点となり、一度通ったらそのマスの数字は0になる。K回スタートからゴール…

問題 与えられた自然数を、それ以下の自然数の数列の和で表現する。これを自然数の分割と呼ぶ。回文となるような分割をPalindromic Partitionという。そのうち以下の条件を満たす分割をRecursively Palindromic Partitionsという。 条件：分割の左右それぞれ…