大観音programming

\主に競プロ備忘録/

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