kwm_t

kwm_tのメモ

ARC-C問題埋め(051~057)

■51:C - 掛け算
ある程度まで揃えてから、
全てに同じ数を掛ける

■52:C - 高橋くんと不思議な道★★★
難しかった。
枝刈りダイクストラ
O(N^2)だとTLEするので、なにかの工夫が必要
まず特定の頂点に到達するまでにタイプBの辺を最低でも何回使う必要があるかを調べる。
すると、それをneedBとでも置くと
needB[v](needB[v] + 1 )/2 + N 以下にコストが収まることがわかる。
なので実際に使うタイプBの辺の回数は
needB + 150程度もあれば十分だとわかる。(150は√2 * N+余裕)
以上の情報を持ってダイクストラを行う。

■53:C - 魔法使い高橋君
グループに分けてしてソート

■54:C - 鯛焼き
行列式の偶奇と完全マッチングの偶奇は一致する

■55:C - ABCAC★★★
Z-algorithm

■56:C - 部門分け
状態SからSの部分集合TとS/Tでdp
類題
abc187:F - Close Group
EDPC:U - Grouping

■57:C - 2乗根
//多倍長整数
#include
namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;


<<完結>>