mayoko’s diary

プロコンとかいろいろ。

2015-03-20から1日間の記事一覧

SRM 650 div2 hard:TheKingsRoadsDiv2

完全二分木であることの必要十分条件が足りなくて何回もWAを出してしまった。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13667&rd=16314解法:どの辺を取り除くかを全探索し、そのそれぞれについて完全二分木になる/ならないを判定する…

SRM 650 div1 easy: TaroFillingAStringDiv1

そんなに難しくないが結構時間を食ってしまった。問題:http://community.topcoder.com/stat?c=problem_statement&pm=13669&rd=16314解法:まずpositionの順に文字をソートする。そして、確定した文字と文字の間に最適な文字の入れ方が何通りあるかを調べてい…

SRM 651 div2 hard:FoxConnection4

同じ回のdiv1medと同じ発想だったので早く解けてよかったのだが、mod 1000000009に惑わされて結構時間がかかった。問題:一部のセルが埋められたH*Wの2次元グリッドが与えられる。空白セルのうちK個を選択したとき、それらが隣接セル同士で連結しているよう…

yukicoder No.168 ものさし

問題:http://yukicoder.me/problems/296 解法:それぞれの点から点への距離をソートする。そして、距離が短いものから順につなげていき、グループを作る。そして、0とN-1が同じグループになった時のものさしの長さが求める答えとなる。これを実装するためにUn…

SRM 651 div1 easy: RobotOnMoon

ただの引掛け問題なのでソースコード貼るだけ。 struct P{ int y; int x; P() {} P(int y, int x) : y(y), x(x) {} }; class RobotOnMoon { public: int longestSafeCommand(vector <string> board) { int n = board.size(), m = board[0].size(); P start; for (int</string>…

SRM 651 div1 med: FoxConnection3

一つ一つのロジックは単純だけど、ぱっと見では全く方針が立たなかった。問題:abs(x), abs(y) 解法:全探索する。具体的には、 ①n匹の狐がどのような形をとることがあり得るかを調べる(createShapeのところ) ②それぞれの形について、狐の総移動量が最小になる…