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

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

JAG

AOJ 2171 Strange Couple (JAG 夏合宿 2009 day3-G) (600 点)

ランダムウォークな問題! 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…

AOJ 2444 Substring (JAG 夏合宿 2012 day3b-E) (450 点)

ロリハそのものな問題!!! 問題へのリンク 問題概要 長さ の文字列 が与えられ、 の連続する部分列が 個指定される。こうして作られる 個の文字列のうち、相異なるものは何通りあるか答えよ。 考えたこと ロリハで頑張る #include <iostream> #include <vector> #include <string> #i</string></vector></iostream>…

AOJ 2720 Identity Function (JAG 夏合宿 2015 day4-D) (600 点)

この問題の原案やってました!高校の頃、時刻表同好会の友達から 「f(n) = n15 を 15 で割った余りとすると任意の整数 n に対して f(f(n)) = n になるんだけど、これって暗号の危機じゃない?」 というメールを受け取って、あれこれ考えたことがキッカケにな…

AOJ 2442 Convex Cut (JAG 夏合宿 2012 day3b-C) (400 点)

面積二等分系問題、こないだ ICPC アジア 2019 にも出ていた。そっちは超むずいけど、こっちは簡単。 問題へのリンク 問題概要 頂点の凸多角形が与えられる。以下の条件を満たす点 P を求めよ: P を通る任意の直線によって、凸多角形は面積の等しい 2 つの凸…

AOJ 2136 Webby Subway (JAG 夏合宿 2008 day2-F)

最大 22 頂点のグラフの彩色数を求める問題 問題へのリンク 問題概要 本の折れ線が与えられる。折れ線に対応した 頂点のグラフを考える。対応する折れ線同士が交差するところに辺を張る。 このグラフの彩色数を求めよ。 制約 解法 前半の幾何は虚無。実質的…

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

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

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

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

AOJ 2237 The Castle (JAG 夏合州 2010 day3-F) (500 点)

一目見て bitDP なのはわかるのだけど、手こずった...ウチ弱すぎるのん... 問題へのリンク 問題概要 匹の猫をステージ に順番に送り込む 猫 がステージ をクリアできる確率は 猫 がステージ をクリアしたら、次のステージ もその猫で挑まなければならない 猫…

AOJ 2336 スプリング・タイル (JAG 夏合宿 2010 day2-G) (600 点)

グリッド系は苦手意識あるけど解けてよかった 問題へのリンク 問題概要 二次元マップが与えられて、各マスは 床 ('.') 壁 ('#') バネ ('*') の 3 つの属性がある。スタート ('s') とゴール ('g') が設定されていて、いずれも床属性である。 s から g へ最速…

AOJ 2370 RabbitWalking (JAG 冬合宿 2010 day3-B) (600 点)

これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる。 このグラフが「奇数長のサイクルがない」とい…

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

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

AOJ 2727 M and A (JAG 模擬地区 2015 A) (200 点)

これ、問題文を一目見て簡単な問題だと気づけるようになるには、それ自体のトレーニングが必要そうなん 問題へのリンク 問題概要 文字列 S, T が与えられる。 S のうち偶数番目だけを抜き出してできる文字列を S1 S のうち奇数番目だけを抜き出してできる文…

AOJ 2610 Fast Division (JAG 夏合宿 2013 day3-D) (250 点)

人工的過ぎる設定であまり自然じゃない問題だけど、整数の整除についての注意点を学べる教育的良問なんな。 問題へのリンク 問題概要 整数 が与えられる。 を 回二乗した数より大きい最小の素数を とする。 を で割ったあまりを求めよ。 制約 < 1000 考えた…

AOJ 2730 Line Gimmick (JAG 模擬地区 2015 D) (300 点)

星 1 個ついてるし、面白かった。「予想」を正しく立てられるかどうかがポイント。最初はカッコ列系の考察するのかと思って迷走した。 問題へのリンク 問題概要 >><><<< みたいな文字列が与えられる。最初にどこを踏んでも良い。踏んだパネルは消えて、その…

AOJ 2613 Unordered Operators (JAG 夏合宿 2013 day3-G) (350 点)

構文解析練習第三弾。AOJ-ICPC 350 点。 問題へのリンク 問題概要 (5-3*4)*(0-2+1) のような以下の BNF で定義される計算式が与えられる: <expr> ::= ( <expr> ) | <number> | <expr> <op> <expr> <op> ::= + | - | * ただし、通常の演算の優先順位は「*」 -> 「+」「-」であるが、今回はどのように優</op></expr></op></expr></number></expr></expr>…

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

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

AOJ 2427 ほそながいところ (JAG 夏合宿 2012 day2-D) (800 点)

「全探索でもここまで難しいやつもある」という例としてよく挙げられる問題。 ここのページに僕なりの 全探索 重み付き Union-Find 木を使いながら判定 をした解法を記した。

AOJ 2589 North North West (JAG 模擬地区 2014 A) (200 点)

とにかく言われた通りにやるん 問題へのリンク 問題概要 northnorthwest (北北西) のように言われて、それを真北方向から何度ずれているかを既約分数で表示せよ (上の例の場合は 45/2) 考えたこと 詳細仕様が問題文中にあるので、とにかく言われた通りに頑張…

AOJ 2224 Save your cat (JAG 夏合宿 2010 day4-C) (500 点)

これ面白いん!!!!!!!!好き!!!!!!! 問題へのリンク 問題概要 平面上に 個の点の座標 と、それらを結ぶ 本の線分がある。 線分のある部分は通過ができないので、線分に囲われた領域とその外側の領域とは行き来することができない。 そこでいく…

AOJ 2706 幾何問題を解こう (JAG 夏合宿 2015 day2-A) (200 点)

問題へのリンク 問題概要 整数 があたえられる。 進法で有理数 p/q を小数で表したときに有限小数となるような最小の 2 以上の整数 を求めよ。 制約 < < 考えたこと とりあえず p/q を約分しておく。 そして、q を素因数分解したときの、指数部を全部 1 にし…

AOJ 2441 FizzBuzz (JAG 夏合宿 2012 day3b-B) (450 点)

AOJ-ICPC で無作為に問題を選んで実装する練習するなん。いや、つらいのんな^^; あと、桁 DP でやってしまったけど、もっとずっとはるかに楽な方法があったん。。。 問題へのリンク 問題概要 1 から順に FizzBuzz をやって得られる文字列を FizzBuzz 文字列…