蟻本練習問題まとめ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

蟻本練習問題まとめ2

3章

二分探索

最小値の最大化

• POJ3258 – River Hopscotch
• POJ3273 – Monthly Expense
• POJ3104 – Drying
• POJ3045 – Cow Acrobats

平均最大化

• POJ2976 – Dropping tests
• POJ3111 – K Best

k番目の値を探索

• POJ3579 – Median
• POJ3685 – Matrix

k番目を最小化

• POJ2010 – Moo University – Financial Aid
• POJ3662 – Telephone Lines

その他

• POJ1759 – Garland
• POJ3484 – Showstopper

その他テクニック

しゃくとり法

• POJ2566 – Bound Found
• POJ2739 – Sum of Consecutive Prime Numbers
• POJ2100 – Graveyard Design

反転

• POJ3185 – The Water Bowls
• POJ1222 – Extended Lights Out

弾性衝突

• POJ2674 – Linear world

半分全列挙

• POJ3977 – Subset
• POJ2549 – Sumsets

座標圧縮

• AOJ0531 – Paint Color

データ構造

BIT

• POJ1990 – MooFest
• POJ3109 – Inner Vertices
• POJ2155 – Matrix
• POJ2886 – Who Gets the Most Candies?

Segment Tree、バケット法

• POJ3264 – Balanced Lineup
• POJ3368 – Frequent values
• POJ3470 – Walls
• POJ1201 – Intervals
• UVa11990 – Dynamic Inversion

DP

bitDP

• POJ2441 – Arrange the Bulls
• POJ3254 – Corn Fields
• POJ2836 – Rectangular Covering
• POJ1795 – DNA Laboratory
• POJ3411 – Paid Roads

行列累乗

• POJ3420 – Quad Tiling
• POJ3735 – Training little cats

データ構造を用いて高速化

• POJ3171 – Cleaning Shifts

ネットワークフロー

最大流・最小カット

• POJ3713 – Transferring Sylla
• POJ2987 – Firing
• POJ2914 – Minimum Cut
• POJ3155 – Hard Life

二部マッチング

• POJ1274 – The Perfect Stall
• POJ2112 – Optimal Milking
• POJ1486 – Sorting Slides
• POJ1466 – Girls and Boys
• POJ3692 – Kindergarten
• POJ2724 – Purifying Machine
• POJ2226 – Muddy Fields
• AOJ2251 – Merry Christmas

最小費用流

• POJ3068 – “Shortest” pair of paths
• POJ2195 – Going Home
• POJ3422 – Kaka’s Matrix Travels
• AOJ2266 – Cache Strategy
• AOJ2230 – How to Create a Good Game
• POJ3068 – “Shortest” pair of paths
• POJ2195 – Going Home
• POJ3422 – Kaka’s Matrix Travels
• AOJ2266 – Cache Strategy
• AOJ2230 – How to Create a Good Game

計算幾何

ギリギリを考える

• POJ1981 – Circle and Points
• POJ1418 – Viva Confetti
• AOJ2201 – Immortal Jewels

平面走査

• POJ3168 – Barn Expansion
• POJ3293 – Rectilinear polygon
• POJ2482 – Stars in Your Window

凸包

• POJ1113 – Wall
• POJ1912 – A highway and the seven dwarfs
• POJ3608 – Bridge Across Islands
• POJ2079 – Triangle
• POJ3246 – Game
• POJ3689 – Equations

数値積分

• AOJ2256 – Divide the Cake
• AOJ2215 – Three Silhouettes

蟻本練習問題まとめ1

2章

全探索

DFS

• POJ1979 – Red and Black
• POJ3009 – Curling 2.0
• AOJ0118 – Property Distribution
• AOJ0033 – Ball

WFS

• AOJ0558 – Cheese
• POJ3669 – Meteor Shower
• AOJ0121 – Seven Puzzle

全列挙

• POJ2718 – Smallest Difference
• POJ3187 – Backward Digit Sums
• POJ3050 – Hopscotch
• AOJ0525 – おせんべい

貪欲法

• POJ2376 – Cleaning Shifts
• POJ1328 – Radar Installation
• POJ3190 – Stall Reservations
• POJ2393 – Yogurt factory
• POJ1017 – Packet
• POJ3040 – Allowance
• POJ1862 – Stripies
• POJ3262 – Protecting the Flowers

DP

• POJ3176 – Cow Bowling
• POJ2229 – Sumsets
• POJ2385 – Apple Catching
• POJ3616 – Milking Time
• POJ3280 – Cheapest Palindrome
• POJ1742 – Coins
• POJ3046 – Ant Counting
• POJ3181 – Dollar Dayz
• POJ1065 – Wooden Sticks
• POJ1631 – Bridging signals
• POJ3666 – Making the Grade
• POJ2392 – Space Elevetor
• POJ2184 – Cow Exhibition

データ構造

Priority Queue

• POJ3614 – Sunscreen
• POJ2010 – Moo University – Financial Aid

Union-Find Tree

• POJ2236 – Wireless Network
• POJ1703 – Find them, Catch them
• AOJ2170 – Marked Ancestor

グラフ

最短路

• AOJ0189 – Convenient Location
• POJ2139 – Six Degrees of Cowvin Bacon
• POJ3259 – Wormholes
• POJ3268 – Silver Cow Party
• AOJ2249 – Road Construction
• AOJ2200 – Mr. Rito Post Office

最小全域木

• POJ1258 – Agri-Net
• POJ2377 – Bad Cowtractors
• AOJ2224 – Save your cats
• POJ2395 – Out of Hay

数学的な問題

互除法

• AOJ0005 – GCD and LCM
• POJ2429 – GCD & LCM Inverse
• POJ1930 – Dead Fraction

素数

• AOJ0009 – Prime Number
• POJ3126 – Prime Path
• POJ3421 – X-factor Chains
• POJ3292 – Semi-prime H-numbers

繰り返し二乗法

• POJ3641 – Pseudoprime numbers
• POJ1995 – Raising Modulo Numbers