読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ABC010を解いてみた

ABC 競技プログラミング

A問題

 入力と"pp"を連結して出力しました。

B問題

 疑似Do-Whileループで2nでも3n+2でもなくなるまで-1していきました。-1した回数を数えてその回数を出力しました。

C問題

 n個の家に対して全探索を行い、それぞれの家に寄ってから移動が終了するまでの距離と移動可能な距離の大小から寄り道ができるかどうかを判定しました。計算量はO(n)でn <= 10^3なので全探索でも実行可能だと判断しました。

D問題

 全探索で部分点を取れ、最小カット最大フロー定理を利用することで満点を取れる。(by解説)
 全探索はitertools.permutations()を使って全ての組み合わせを列挙し、その組み合わせでマークされている女の子に到達できる人数を幅優先探索で求めて一番少なくなるパターンを出力すればできそう。
 NetworkXってライブラリに最小カット最大フロー定理の関数があるらしい。
ネットワークフロー — 読書ノート v1.4.0dev

雑感

 ABCはすぐに解けました。D問題見てグラフとかネットワークフローについても勉強しないとと感じました。