競技プログラミング
Carpenters' Language | Aizu Online Judge 問題概要 括弧列がvalidであるとは、文脈自由文法で以下のように定義される。 S -> SS | (S) | )S( | εあなたは最初、空の括弧列Sを持っている。 回のクエリが与えられる。 番目のクエリで が与えられるので、Sの …
Strange String Manipulation | Aizu Online Judge 問題概要 線形合同法を使って擬似乱数を生成します。線形合同法は mod で計算します。ここで は定数で、この問題では 、です。いま、文字列 を、乱数列 を使って別の文字列 に変換したいです。文字列 は mo…
Make a Sequence | Aizu Online Judge 問題概要 2人のプレイヤーが白と黒の石を使って交互にゲームをプレイする。黒が先手。 * 本のペグ(杭)があり、それぞれ 個までボールを重ねることができる。 ゲーム開始時にはどのペグにもボールはない。ターンになると…
Miscalculation | Aizu Online Judge 問題概要 1行目に0~9の数字, +, *の文字からなる数式が与えられます。この数式は奇数文字目は数字、偶数文字目は演算子(+または*)です。数式の長さは奇数で、最大17文字です。 数式の計算方法は 乗算(*)を加算(+)より優…
Grey Area | Aizu Online Judge 問題概要 個のデータからヒストグラムを作ります。 それぞれのヒストグラムの棒の幅は で、棒の高さは、ヒストグラムの棒の長さの最大値を1としたときの割合で定義されます。 ヒストグラムの棒はそれぞれ色の濃さが異なり、ヒ…
9/15から1週間の競プロ旅行をして、JAG夏合宿2018（2018/Practice/夏合宿/案内 - ACM-ICPC Japanese Alumni Group）と会津合宿2018（会津大学競技プログラミング合宿2018 : ATND）に参加してきました。コンテストの時系列はだいぶあやしいので間違っていても…
C - Cheating Nim 問題概要 2人でNimをする。 はじめに 個の山があり、 番目の山には石が 個ある。 ゲームが始まる前に、それぞれの山から石を0個または1個取り除く。 後手が必ず勝つために取り除く石の数の最小値を求めよ。 制約 解法 Nimで後手が勝つため…
A - Uncommon 問題概要 個の異なる整数 と整数 が与えられる。 以上 以下のそれぞれの整数 について、 のうち と互いに素であるものの個数を求めよ。 制約 解法 ある数 について、 のうち と互いに素であるものの個数を求めるとき、愚直に1つずつ試して でや…
Problem - E - Codeforces 問題概要 頂点の根付き木が与えられる。根は1である。 ある頂点が命令を与えられると、自分の子のうちまだ命令が与えられていない1つの頂点（複数あれば頂点番号が最も小さい頂点）に命令を与える。命令が葉まで伝搬すると、自分の…
Problem - D - Codeforces 問題概要 長さ の2つの文字列a,bが与えられる。文字列はともに小文字のアルファベットから構成される。 はじめに、好きな回数だけ以下の置換操作を行うことができる。 となる を一つ選び、 を任意のアルファベットに置換する その…
Problem - C - Codeforces 問題概要 長さ の数列dが与えられる。 この数列dをA,B,Cの3つの連続する区間に分割する。（長さ0の区間が存在しても良い）Aの長さをa、Aの要素の総和をsum1とする。 同様に、Bの長さをb、Bの要素の総和をsum2、Cの長さをc、Cの要素…
Problem - B - Codeforces 問題概要 長さ の数列Aを 個の連続した区間に分割する。 分割後の各区間の最大値の合計を最大化せよ。 解法 数列Aの要素の大きい方から 個が、それぞれの区間の最大値となった時が答えである。 よって、そうなるように分割すれば良…
Problem - A - Codeforces 問題概要 長さ の数列Aが与えられる。 次の操作を順番に行う。 数列Aに出現するを全てに置き換える 数列Aに出現するを全てに置き換える 数列Aに出現するを全てに置き換える 数列Aに出現するを全てに置き換える 数列Aに出現するを全…
C - Fountain Walk 問題概要 東西方向と南北方向にそれぞれ本の道路があり、となりあう道路間の距離は メートルである。すべての東西方向の道路はすべての南北方向の道路と直交し、すべての交差点は、交差する南北方向の通りの番号を 、東西方向の通りの番号…
問題概要 はじめジュースの在庫が 本ある。 毎日 本購入され、購入後 本以下になると夜に 本補充する。 永遠にジュースを 本購入され続けるか。 クエリは 個。 制約 解法 まず、 の場合は、初日に 本購入できないので、必ず No になる。 また、そうでなくて…
問題概要 個の箱が与えられる。 番目の箱は縦 cm × 横 cmで、縦と横を入れ替えることはできない。 ある箱は縦・横ともにより大きいサイズの箱にのみ入れることができ、ある箱は1つまでしか他の箱を入れることはできない。 このとき、箱を最大で何重の入れ子…
「priMe.caT*1」というチームで人生3回目の国内予選に参加しました。 2018年国内予選 | ACM-ICPC 2018 Asia Yokohama Regional チームメンバー ixmel先輩…主に実装担当。 T.M先輩…主に考察担当。 ぼく…テンプレ写経やサンプル図示やデバッグなどを担当。 雑…
夏合宿の朝は早い | Aizu Online Judge 問題概要 人それぞれの寝坊する確率と、連絡先を知っている人が与えられる。 起きた人が連絡先を知っている人すべてにモーニングコールをするとき、全員が起きられる確率を求めよ。 解法 誰にも起こしてもらえない人（…
3/26-28に立命館大学で行われたRUPC2018に参加したので参加記を書きます。 day ? ATND（https://atnd.org/events/94033 ）を公開したら尋常じゃないスピードで埋まったので怖かった。（例年の参加者は40人くらいなのに公開3日で60人に到達するというバグが発…
B - 異世界数式これ自力で思いつけたの嬉しい。 問題概要 数式 が、単なる数字の列か、もしくは演算子 （+, -, *, / のいずれか） の直後で括弧（(） を開き、その中に数式をいくつかカンマ （,） で区切って並べ、その後括弧 （)） を閉じるという形式で表…
A - YahooYahooYahoo 問題概要 文字列 が与えられるので、 'yahoo'の繰り返しの文字列にするための編集距離を求めよ。制約 解法 dp[ ][ ] := ] を「 'yahoo' の繰り返し + 'yahoo' の先頭 文字」の文字列にするための編集距離としてDPする。dp[0][0]は0、そ…
C - 広告 問題概要 縦 マス 横 マスのグリッドがあり、それぞれのマスには ' * ' か ' . ' が書かれている。 ' . ' のマスに、それぞれがとなり合わないように広告を打つとき、打てる広告の最大数を求めよ。制約 解法 ' . ' のマスを頂点とし、となり合う ' …
D - すぬけ君の塗り絵 / Snuke's Coloring 問題概要 縦 マス 横 マスの盤があり、すべて白く塗られている。 この状態から マスを黒く塗りつぶした。 番目の黒いマスは上から 行目で左から 列目のマスである。を満たす全ての について、盤の中に完全に含まれ…
D - いろはちゃんとマス目 / Iroha and a Grid 問題概要 縦 マス 横 マスのグリッドの左上のマスから、右と下の移動を繰り返し右下のマスに移動する。 下から マス以内かつ左から マス以内のマスには移動できない。 移動する方法が何通りかを で割った余りを…
D - Score Attack 問題概要 頂点 辺の有向グラフが与えられ、 番目の辺は 頂点 から頂点 をコスト でつないでいる。 頂点1から頂点 に行くときの合計コストの最大値を求めよ。なお、合計コストをいくらでも大きくできるときはinfを出力せよ。制約 解法 コス…
D - 大ジャンプ 問題概要 スタート地点の座標は で、ゴール地点の座標は とする。 1回のジャンプで、それぞれ の確率で以下の4つのうちどれかを行う。 軸方向に だけ移動する 軸方向に だけ移動する 軸方向に だけ移動する 軸方向に だけ移動する ちょうど …
D - 経路 問題概要 縦 横 のマス目があり、それぞれのマスには整数 が書かれている。 このグリッドの中の好きなマスから開始し、今いるマスの上下左右に隣接しているマスのうち、今いるマスより大きな整数が書かれたマスに移動することができる（移動しなく…
B - Inscribed Bicycle幾何。 問題概要 三角形の頂点が与えられる。 三角形の内部に半径の等しい円を重ならないように2つかくとき、円の半径の最大値を求めよ。制約 解法 まず、三角形の内部に半径 の円がかけるとはどういうことかを考えてみる。 円の中心と…
D - 塗り絵はじめての木DPです。 問題概要 頂点の木が与えられる。 両端の頂点が黒で塗られるような辺がないように、頂点を白または黒でぬるとき、塗り方の通り数を で割ったあまりを答えよ。制約 解法 漸化式を立てて木の上でDPをしましょう。 := 頂点 を親…
A - 不完全迷路 問題概要 高さ 幅 の迷路が与えられる。 壁のマスを1マスのみ道のマスに変えたとき、スタートのマスからゴールのマスへの最短経路長が最長となるようにしたい。 そのときのスタートからゴールまでの最短経路長を求めよ。制約 TLE解法 それぞ…
