問題文 https://icpcarchive.ecs.baylor.edu/external/42/4210.pdfグラフが与えられる。最短経路に含まれる辺をひとつも使わない経路の中で最短のものを求めよ。ただし最短経路は複数ある場合もある。 ダイクストラを2回やる。一回目で最短経路に含まれる辺…

問題文 https://icpcarchive.ecs.baylor.edu/external/42/4212.pdfn*mのグリッドが与えられる。マスの数字はそのマスにあるキャンディーの個数だ。このグリッドのあるマスからそのマスにあるキャンディーを全てとるとき、図のようにそのマスの左右のマスと上…

問題文 https://icpcarchive.ecs.baylor.edu/external/56/5689.pdf色のついた円が与えられる。各データセットには色が400.0の円と789.0の円がひとつずつ含まれる。この円の上を通って、400.0の円から789.0の円に行って戻ってくることができるかどうか判定せ…

問題文 http://uva.onlinejudge.org/external/109/10991.html3つの円の半径が与えられる。図のように3つの円に囲まれた部分の面積を求めよ。 3つの円の中心を頂点とする三角形の面積から、その三角形の内部の扇型の面積を引いてやればよい。三角形の面積はヘ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1140&lang=jp 幅優先探索でスタート位置と汚れについて全点対間最短距離を求めておいて、パスを全部試す。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<queue> #define INF 100000000 #define </queue></string></algorithm></vector></iostream>…

問題文 http://poj.org/problem?id=3468 蟻本でも紹介されている問題。 セグメント木を実装した。各節点は次の2つのデータをもつ。 whole[ ] その節点の区間全体に一様に加えられた値 part[ ] その節点の区間に一様でなく加えられた値 #include<iostream> #include<vector> #in</vector></iostream>…

問題文 http://poj.org/problem?id=3692 最大クリーク問題。 二部グラフになっているので補グラフの最大独立集合を求める。 最大クリーク=補グラフの最大独立集合 が成り立つ。また二部グラフなら、 最大独立集合=頂点数-最大マッチング が成り立つ。 #inclu…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415 Monge DP。 週刊spaghetti_sourceさんにわかりやすい説明があったので参考にしながら解いた。 http://topcoder.g.hatena.ne.jp/spaghetti_source/20120915dp[ 左端 ][ 右端 ] := その…

問題文 http://poj.org/problem?id=1967 宝の位置とその宝を取れる制限時間が与えられる。任意の位置からスタートして、宝を全て拾うときの最短時間を求めよ。 区間DP。 l[訪れた区間の左端][右端]:=訪れた区間の左端を終端とする最短時間 r[訪れた区間の左…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1262無限にエネルギーのある車でレースをする。距離0の地点からスタートし、途中n個のチェックポイントがある。チェックポイントではタイヤの交換ができる。タイヤの交換にはb秒かかる。タ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1266 星と望遠鏡が与えられる。すべての望遠鏡を使って見える星の数を数えよ。 aとbをそれぞれ望遠鏡の方向ベクトルと星の位置ベクトルとすると、 cosθ=a•b/|a||b| θ=acos(a•b/|a||b|) で…

問題文 https://icpcarchive.ecs.baylor.edu/external/61/6139.pdf数列とクエリが与えられる。クエリは以下の2種類である。C a b 数列のa番目をbに更新する。 P a b 数列の区間[a,b]の積が負であれば-、0であれば0、正であれば+を出力する。 セグメント木を…

問題文 https://icpcarchive.ecs.baylor.edu/external/61/6138.pdf与えられた数字が、時計の短針と長針が作る角度に含まれるかどうかを判定せよ。短針は長針が12進んだときに1進む。 短針と長針が作る角度を全て生成しておく。工夫は必要ない。 #include<iostream> #in</iostream>…