蟻本練習問題まとめ3

4章

数学的問題

mod

• POJ1150 – The Last Non-zero Digit
• POJ1284 – Primitive Roots
• POJ2115 – C Looooops
• POJ3708 – Recurrent Function
• POJ2720 – Last Digits
• GCJ Japan 2011 決勝B – バクテリアの増殖

行列

• POJ2345 – Central heating
• POJ3532 – Resistance
• POJ3526 – The Teacher’s Side of Math

数え上げ

• POJ2407 – Relatives
• POJ1286 – Necklace of Beads
• POJ2409 – Let it Bead
• AOJ2164 – Revenge of the Round Table
• AOJ2214 – Warp Hall

ゲーム

考察、DP

• POJ1082 – Calendar Game
• POJ2068 – Nim
• POJ3688 – Cheat in the Game
• POJ1740 – A New Stone Game

Nim、Grundy数

• POJ2975 – Nim
• POJ3537 – Crosses and Crosses
• Codeforces 138D – World of Darkraft
• POJ2315 – Football Game

グラフ

強連結成分分解

• POJ3180 – The Cow Prom
• POJ1236 – Network of Schools

2-SAT

• POJ3678 – Katu Puzzle
• POJ2723 – Get Luffy Out
• POJ2749 – Building roads

LCA

• POJ1986 – Distance Queries
• POJ3728 – The merchant

頻出テクニック

スタック

• POJ3250 – Bad Hair Day
• POJ2082 – Terrible Sets
• POJ3494 – Largest Submatrix of All 1’s

デック

• POJ2823 – Sliding Window
• POJ3260 – The Fewest Coins
• POJ1180 – Batch Scheduling
• AOJ1070 – FIMO sequence

賢く探索

枝刈り

• POJ1011 – Sticks
• POJ2046 – Gap
• POJ3134 – Power Calculus

A,IDA

• POJ3523 – The Morning after Halloween
• POJ2032 – Square Carpets
• UVA10181 – 15-Puzzle Problem

分割統治法

列の分割統治

• POJ1854 – Evil Straw Warts Live

平面の分割統治

• GCJ 2009 World Finals B – Min Perimeter
• Codeforces 97B – Superset

ツリーの重心分解

• POJ2114 – Boatherds
• UVa12161 Ironman Race in Treeland
• SPOJ QTREE5 – Query on a tree V

文字列

DP

• AOJ2212 – Stolen Jewel
• Codeforces 86C – Genetic Engineering

文字列検索

• Codeforces 25E – Test
• AOJ1312 – Where’s Wally

接尾辞配列

• POJ1509 – Glass Beads
• POJ3415 – Common Substrings
• POJ3729 – Facer’s string
• AOJ2292 – Common Palindromes
• Codeforces 123D – String