チーム Chabashira (NOSS, まほろば, まつした)としてICPC国内予選に参加しました。 追記(2020/11/09) チームメイトの参加記 - ICPC2020国内予選参加記 - まほろば精進日誌 - ICPC2020国内予選に出場しました｜MacaronBLOG 開始前 開始直前まで研究室のタス…

問題 文字列Sを部分列に含む回文であって長さが最小であるもののうち、辞書順でk番目のものを求めよ。 問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1362 解法 まずは最小長さを求め、最小長さとなるような回文の個数を数え上げる…

問題 bitからなる異なる 個のbit列が与えられる。1回の質問でbitを1つ明らかにできるとき最悪でも何回の質問でbit列を1つに特定できるか求めよ。 問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302 解法 まず前計算として、 cnt[S…

問題 8点の座標が与えられるので(x,y,z)を自由に並びかえたとき立方体の頂点できるか判定せよ。 問題リンク：http://codeforces.com/problemset/problem/465/D 解法 各点の座標の並べ方は 通り。1点固定して他を全探索しても高々 通りなので全探索できる。 …

問題 JOI 2010 本戦の問題 問題リンク：AOJ 0552 解法 かなり難しかった。 そのままの座標だとマンハッタン距離が扱いずらいので45度回転をする。すると、例えばと変換すれば距離はで求められるようになる。点群の最遠点対の距離はで求まり、s,tで分離して考…