naoya_t@topcoder

SRM440

22:39 |

05.12.2009

続きを読む

SRM355 Div1 Easy (300points): MixingLiquids

過去問, 練習 | 03:36 |

続きを読む

SRM223 Div1 Hard: RevolvingDoor

過去問, 練習, Tutorials | 01:37 |

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

続きを読む

SRM207 Div2 Hard: CaptureThemAll

過去問, 練習, Tutorials | 21:05 |

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

Problem hints: At first sight this may seem like dynamic programming or backtracking. But as always, take a look into the text of the statement. After a while you should observe the following things:

• A table is given.
• The knight can jump from one cell to some of its neighbors.
• The cost of passing from a cell to another is always 1 (just one jump).
• You need to find the minimum number of steps (jumps).

Given this information we can see that the problem can be easily solved by the help of BFS. Don't get confused by the fact that connected points are represented by unconnected cells. Think of cells as points in a graph, or states (whatever you want) - and in order to pass from one point to another, the knight should be able to jump from the first to the second point.

Notice again that the most revealing hint about the BFS solution is the cost of 1 for any jump.

「ジャンプのコストが全て１」→BFSで解けるよというあからさまなヒント

続きを読む

SRM439

11:58 |

04.30+.2009

続きを読む

SRM233 Div1 Easy: PipeCuts

過去問, 練習, Tutorials | 04:15 |

同SRMのEasy問題にも手を出した

続きを読む

SRM233 Div1 Medium: SmartWordToy

過去問, 練習, Tutorials | 23:35 |

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

続きを読む