JAG
ランダムウォークな問題！ 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…
ロリハそのものな問題！！！ 問題へのリンク 問題概要 長さ の文字列 が与えられ、 の連続する部分列が 個指定される。こうして作られる 個の文字列のうち、相異なるものは何通りあるか答えよ。 考えたこと ロリハで頑張る #include <iostream> #include <vector> #include <string> #i</string></vector></iostream>…
この問題の原案やってました！高校の頃、時刻表同好会の友達から 「f(n) = n15 を 15 で割った余りとすると任意の整数 n に対して f(f(n)) = n になるんだけど、これって暗号の危機じゃない？」 というメールを受け取って、あれこれ考えたことがキッカケにな…
面積二等分系問題、こないだ ICPC アジア 2019 にも出ていた。そっちは超むずいけど、こっちは簡単。 問題へのリンク 問題概要 頂点の凸多角形が与えられる。以下の条件を満たす点 P を求めよ: P を通る任意の直線によって、凸多角形は面積の等しい 2 つの凸…
最大 22 頂点のグラフの彩色数を求める問題 問題へのリンク 問題概要 本の折れ線が与えられる。折れ線に対応した 頂点のグラフを考える。対応する折れ線同士が交差するところに辺を張る。 このグラフの彩色数を求めよ。 制約 解法 前半の幾何は虚無。実質的…
問題文長い... 問題へのリンク 問題概要 頂点、 辺の重み付き無向グラフが与えられる。各辺は「陸路」「海路」の属性がある。このグラフを、最初頂点 にいて、 の順番に最短時間で巡りたい (順番的に後の頂点を先に通ってもよいが、その頂点より前の指定頂点…
コピペできる環境だったからライブラリで殴ったけど、ICPC 環境だったらタイピング量を減らす工夫せなアカンかな... 問題へのリンク 問題概要 下図のような、五角星 個があって、 個目の五角星から 個めの五角星までの最短距離を求めよ。 制約 考えたこと 五…
一目見て bitDP なのはわかるのだけど、手こずった...ウチ弱すぎるのん... 問題へのリンク 問題概要 匹の猫をステージ に順番に送り込む 猫 がステージ をクリアできる確率は 猫 がステージ をクリアしたら、次のステージ もその猫で挑まなければならない 猫…
グリッド系は苦手意識あるけど解けてよかった 問題へのリンク 問題概要 二次元マップが与えられて、各マスは 床 ('.') 壁 ('#') バネ ('*') の 3 つの属性がある。スタート ('s') とゴール ('g') が設定されていて、いずれも床属性である。 s から g へ最速…
これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる。 このグラフが「奇数長のサイクルがない」とい…
共通接線ライブラリの整備 問題へのリンク 問題概要 互いに重ならない円が N 個ある。 直線を考えたとき、そのスコアは 各円に対して、その円と共有点を持たず、その円との距離がある一定 (円に依存して決まる値) 以下であるとき 1 を加算、そうでないとき 0…
これ、問題文を一目見て簡単な問題だと気づけるようになるには、それ自体のトレーニングが必要そうなん 問題へのリンク 問題概要 文字列 S, T が与えられる。 S のうち偶数番目だけを抜き出してできる文字列を S1 S のうち奇数番目だけを抜き出してできる文…
人工的過ぎる設定であまり自然じゃない問題だけど、整数の整除についての注意点を学べる教育的良問なんな。 問題へのリンク 問題概要 整数 が与えられる。 を 回二乗した数より大きい最小の素数を とする。 を で割ったあまりを求めよ。 制約 < 1000 考えた…
星 1 個ついてるし、面白かった。「予想」を正しく立てられるかどうかがポイント。最初はカッコ列系の考察するのかと思って迷走した。 問題へのリンク 問題概要 >><><<< みたいな文字列が与えられる。最初にどこを踏んでも良い。踏んだパネルは消えて、その…
構文解析練習第三弾。AOJ-ICPC 350 点。 問題へのリンク 問題概要 (5-3*4)*(0-2+1) のような以下の BNF で定義される計算式が与えられる: <expr> ::= ( <expr> ) | <number> | <expr> <op> <expr> <op> ::= + | - | * ただし、通常の演算の優先順位は「*」 -> 「+」「-」であるが、今回はどのように優</op></expr></op></expr></number></expr></expr>…
せっかく構文解析の練習を少ししたので 問題へのリンク 問題概要 -(a+b)=(-a*-b) (a->b)=(-a+b) ((a*T)+b)=(-c+(a*-b)) のような式たちが恒等式かどうかを判定せよ。すなわち、a や b や c に true と false をどのように当てはめても結果が一致するかどうか…
「全探索でもここまで難しいやつもある」という例としてよく挙げられる問題。 ここのページに僕なりの 全探索 重み付き Union-Find 木を使いながら判定 をした解法を記した。
とにかく言われた通りにやるん 問題へのリンク 問題概要 northnorthwest (北北西) のように言われて、それを真北方向から何度ずれているかを既約分数で表示せよ (上の例の場合は 45/2) 考えたこと 詳細仕様が問題文中にあるので、とにかく言われた通りに頑張…
これ面白いん！！！！！！！！好き！！！！！！！ 問題へのリンク 問題概要 平面上に 個の点の座標 と、それらを結ぶ 本の線分がある。 線分のある部分は通過ができないので、線分に囲われた領域とその外側の領域とは行き来することができない。 そこでいく…
問題へのリンク 問題概要 整数 があたえられる。 進法で有理数 p/q を小数で表したときに有限小数となるような最小の 2 以上の整数 を求めよ。 制約 < < 考えたこと とりあえず p/q を約分しておく。 そして、q を素因数分解したときの、指数部を全部 1 にし…
AOJ-ICPC で無作為に問題を選んで実装する練習するなん。いや、つらいのんな^^; あと、桁 DP でやってしまったけど、もっとずっとはるかに楽な方法があったん。。。 問題へのリンク 問題概要 1 から順に FizzBuzz をやって得られる文字列を FizzBuzz 文字列…
