The Last Ant | Aizu Online Judge 問題概要 長さ cmのトンネルに蟻が 匹いる。最初、蟻 はトンネルの左端から cmの場所に向き の状態でいる。トンネルは広い場所と狭い場所があり、狭い場所はトンネルの端から1cmおきのところにある。トンネルのある場所で…

Shredding Company | Aizu Online Judge 問題概要 整数 と数字のみからなる文字列 が与えられる。文字列 をいくつかの箇所で分割し、分割後の数の総和が 以下になるようにするとき、総和の最大値とそのときの分割の仕方を答えよ。なお、分割後の数の総和が …

Ginkgo Numbers | Aizu Online Judge 問題概要 Ginkgo Numbersは整数 のペア です。 Ginkgo Numbersの掛け算は・ = で定義されます。 ・ = となるとき、はの約数です。どんなGinkgo number にも少なくとも8つの約数が存在し、それらは , , , , , , , です。 …

Step Step Evolution | Aizu Online Judge 問題概要 3*3のマスを左右どちらかの足で順番に踏むゲームをする。与えられる指示に従って左右の足で交互にマスを踏んでいきたいが、右足よりも右側のマスを左足で踏んだり、左足よりも左側のマスを右足で踏んだり…

The Sorcerer's Donut | Aizu Online Judge 問題概要 ドーナツ状の物体の表面に文字列が書かれている。ある文字から8方向に移動し続けてできる文字列のうち、2度以上出現する文字列で長さが最長のものを答えよ。複数存在する場合は辞書順最小のものを答えよ…

Bit String Reordering | Aizu Online Judge 問題概要 長さ のビット列 を、となりあう2つのビットをswapすることを繰り返してランレングス符号が であるようなビット列に変換するときの最小のswap回数を求めよ。 ランレングス符号は0または1が連続する最大…

Expected Allowance | Aizu Online Judge 問題概要 個の 面サイコロを振って出た目の総和から を引いたものの期待値を求めてください。ただし、出た目の総和から を引いたものが0以下になるときは1として計算します。 制約 解法 制約を睨むと目の出方を全探…

Minimal Backgammon | Aizu Online Judge 問題概要 0から までのマスがあるすごろくをします。マスには何も書いていないマス、止まると1ターン休みになるマス、止まるとスタートのマスまで戻るマスがあります。マス0がスタートのマス、マス がゴールのマスで…

Quality of Check Digits | Aizu Online Judge 問題概要 0000~9999の4桁の数の後ろにチェックディジットを1つつけて5桁の数を作る。チェックディジット は、4桁の数の数字を上から としたとき、 と定義される。ここで は与えられた表の 行 列目の数字を指す…

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 問題概要 人それぞれの寝坊する確率と、連絡先を知っている人が与えられる。 起きた人が連絡先を知っている人すべてにモーニングコールをするとき、全員が起きられる確率を求めよ。 解法 誰にも起こしてもらえない人（…

PHP触ったのでメモ拡張子は .php で、 php と ? > の間にコードを書く。 test.phpという名前で以下のコードを書く。 実行は php コマンドでできる。 $ php ./test.php Hello World! $

3/26-28に立命館大学で行われたRUPC2018に参加したので参加記を書きます。 day ? ATND（https://atnd.org/events/94033 ）を公開したら尋常じゃないスピードで埋まったので怖かった。（例年の参加者は40人くらいなのに公開3日で60人に到達するというバグが発…

B - 異世界数式これ自力で思いつけたの嬉しい。 問題概要 数式 が、単なる数字の列か、もしくは演算子 （+, -, *, / のいずれか） の直後で括弧（(） を開き、その中に数式をいくつかカンマ （,） で区切って並べ、その後括弧 （)） を閉じるという形式で表…