けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JAG模擬国内

AOJ 2828 マトリョーシカ (JAG 模擬国内 2017 F) (550 点)

DAG の最小パス被覆、忘れた頃に出て来るイメージ! 問題へのリンク editorials 問題概要 個の直方体があり、 番目の直方体の大きさは である。 今、ある直方体の中に他のある直方体を入れたりすることで、外部から見えている直方体の体積を小さくしたい。た…

AOJ 2584 壊れた暗号生成器 (ICPC 模擬国内 2014 C) (400 点)

BNF が書かれているので、LL(1)文法を再帰降下とかするのが標準みたいだけど、ad-hoc にスタックでなんとかしてしまった 問題へのリンク 問題概要 以下の BNF によって定義された文字列が与えられる。 <Cipher> ::= <String> | <Cipher><String> <String> ::= <Letter> | '['<Cipher>']' <Letter> ::= '+'<Letter> | '-'<Letter> | 'A' | 'B' |</letter></letter></letter></cipher></letter></string></string></cipher></string></cipher>…

AOJ 2403 敵の敵は味方 (JAG 模擬国内 2012 E) (550 点)

TLE が厳しかった... 問題へのリンク editorial 問題概要 頂点数 の単純無向グラフ が与えられる (連結とは限らない)。各頂点 には重み がついている。 頂点 1 を含む の安定集合をすべて考えたときの、安定集合中の頂点の重もの総和の最大値を求めよ。 制約…

AOJ 2200 Mr. リトー郵便局 (ICPC 模擬国内 2010 D) (500 点)

問題文長い... 問題へのリンク 問題概要 頂点、 辺の重み付き無向グラフが与えられる。各辺は「陸路」「海路」の属性がある。このグラフを、最初頂点 にいて、 の順番に最短時間で巡りたい (順番的に後の頂点を先に通ってもよいが、その頂点より前の指定頂点…

AOJ 2402 天の川 (ICPC 模擬国内 2012 D) (400 点)

コピペできる環境だったからライブラリで殴ったけど、ICPC 環境だったらタイピング量を減らす工夫せなアカンかな... 問題へのリンク 問題概要 下図のような、五角星 個があって、 個目の五角星から 個めの五角星までの最短距離を求めよ。 制約 考えたこと 五…

AOJ 2201 不死の宝石 (JAG 模擬国内 2010 E) (550 点)

共通接線ライブラリの整備 問題へのリンク 問題概要 互いに重ならない円が N 個ある。 直線を考えたとき、そのスコアは 各円に対して、その円と共有点を持たず、その円との距離がある一定 (円に依存して決まる値) 以下であるとき 1 を加算、そうでないとき 0…

AOJ 2401 恒等式 (JAG 模擬国内 2012 C)

せっかく構文解析の練習を少ししたので 問題へのリンク 問題概要 -(a+b)=(-a*-b) (a->b)=(-a+b) ((a*T)+b)=(-c+(a*-b)) のような式たちが恒等式かどうかを判定せよ。すなわち、a や b や c に true と false をどのように当てはめても結果が一致するかどうか…