足跡-sokuseki-

りかの日進月歩の記録

競技プログラミング

AOJ 2642 Dinner

Dinner | Aizu Online Judge AOJ-ICPC 550点…? 問題概要 日間の夕食を食堂か自炊のどちらかで済ませる。 日目に食堂で夕食をとると幸福度が 得られる。 各日に自炊をすると得られる幸福度は、 (自炊をした時点での自炊パワー) である。 自炊パワーは、初期…

AOJ0310 枠

枠 | Aizu Online Judgeこの高速化テクは典型らしいです。 問題 のグリッドがあり、各マスに数が書かれている。 このグリッドに太さ1マス分の長方形の枠をのせ、枠が覆っているマスの数の総和を最大化する。 ただし、枠は や や のように、中央に穴が空いて…

競プロ合宿の開き方

はじめに 競プロ合宿といえば RUPC (立命館大学競技プログラミング合宿)や ACPC (会津大学競技プログラミング合宿)が有名だと思います。*1 最近、競プロ合宿の需要が増えている気がしていて、たとえば RUPC の参加登録はページ公開後1時間もしないうちに…

競プロで Σi*f(i) を求める問題

競プロで Σi*f(i) ( Σi/f(i) でもよい)を求める問題で、f(i)のとる値が少ない場合、「f(i)の値ごとにiの総和を求めてからf(i)をかけて、それらをすべて足す」というテクを使えばよいという知見を得た。最近解いた問題でいうと、yukicoder No.737 PopCount…

RUPC2019(立命合宿)参加記

3/5(火)から3/7(木)に行われたRUPC2019(立命館大学競技プログラミング合宿2019 : ATND)に参加しました。 Day0 今年は前泊をしていたので、同じく前泊していた北大の人とまぜそばを食べました。北大勢とRUPC前夜祭!! pic.twitter.com/0IhQux5xXf— そすう…

Codeforces Round #540 Div.3 F1: Tree Cutting (Easy Version)

Problem - F1 - Codeforces 問題概要 頂点からなる木が与えられ、各頂点は赤・青のどちらかで塗られているか、何も塗られていないかのいずれかである。木の辺を 1 つだけ取り除き、同じ連結成分内には色が高々 1 種類まで登場するようにしたい。これを達成で…

技術室奥プログラミングコンテスト #3 E - デフレゲーム

E - デフレゲーム 問題概要 面のサイコロがあり、前に出た面がもう一度出るまでサイコロを振り続ける。 前に出た面がもう一度出るまでの出た目の総和の期待値を求めよ。 解法 期待値の線型性より (サイコロを 回振ったときの目の総和) ( 回目で初めて目が…

競技プログラミング2018総括

2017の総括を書き忘れていたことに最近気付いたので2018の総括を書きます。 今年あったこと 1月 RUPC2018のATNDを公開したら1日くらいで枠がいっぱいになって競プロ人口の増加を感じた 2月 競プロサークルの部長になってしまった… 3月 学内の理系ゼミサーク…

Suffix ArrayのO(NlogN)構築

この記事はCompetitive Programming (1) Advent Calendar 2018 - Adventar の25日目の記事です。 はじめに 競技プログラミングの問題でSuffix Arrayを使う場合、蟻本で紹介されている の構築で間に合う問題がほとんどです。しかし、では定数倍高速化をしない…

ICPC2018 アジア地区横浜大会 参加記

12/8~10に行われたICPC2018アジア地区横浜大会にpriMe.caTというチームで参加しました。 Asia Yokohama Regional Contest 2018 | ACM-ICPC 2018 Asia Yokohama Regional国内予選の様子→ACM-ICPC 2018 国内予選 参加記 - 足跡-sokuseki-ぼくは初めてのアジア…

AOJ2321 Butterfly

Butterfly | Aizu Online Judge 問題概要 個の用事があり、 個目の用事は時間が 区間拘束され、 個目の区間は 時から 時である。また 個目の用事をすると満足度が 得られる。 時間がかぶらないように行う用事を決めるとき、得られる満足度の最大値を求めよ。…

AOJ1336 The Last Ant

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

AOJ1237 Shredding Company

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

AOJ1325 Ginkgo Numbers

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

AOJ2243 Step Step Evolution

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

AOJ1316 The Sorcerer's Donut

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

AOJ1345 Bit String Reordering

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

AOJ1286 Expected Allowance

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

AOJ1277 Minimal Backgammon

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

AOJ1368 Quality of Check Digits

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

AOJ2340 Carpenters' Language

Carpenters' Language | Aizu Online Judge 問題概要 括弧列がvalidであるとは、文脈自由文法で以下のように定義される。 S -> SS | (S) | )S( | εあなたは最初、空の括弧列Sを持っている。 回のクエリが与えられる。 番目のクエリで が与えられるので、Sの …

AOJ2165 Strange String Manipulation

Strange String Manipulation | Aizu Online Judge 問題概要 線形合同法を使って擬似乱数を生成します。線形合同法は mod で計算します。ここで は定数で、この問題では 、です。いま、文字列 を、乱数列 を使って別の文字列 に変換したいです。文字列 は mo…

AOJ1249 Make a Sequence

Make a Sequence | Aizu Online Judge 問題概要 2人のプレイヤーが白と黒の石を使って交互にゲームをプレイする。黒が先手。 * 本のペグ(杭)があり、それぞれ 個までボールを重ねることができる。 ゲーム開始時にはどのペグにもボールはない。ターンになると…

AOJ1346 Miscalculation

Miscalculation | Aizu Online Judge 問題概要 1行目に0~9の数字, +, *の文字からなる数式が与えられます。この数式は奇数文字目は数字、偶数文字目は演算子(+または*)です。数式の長さは奇数で、最大17文字です。 数式の計算方法は 乗算(*)を加算(+)より優…

AOJ1285 Grey Area

Grey Area | Aizu Online Judge 問題概要 個のデータからヒストグラムを作ります。 それぞれのヒストグラムの棒の幅は で、棒の高さは、ヒストグラムの棒の長さの最大値を1としたときの割合で定義されます。 ヒストグラムの棒はそれぞれ色の濃さが異なり、ヒ…

CODE FESTIVAL 2016 Grand Final C - Cheating Nim

C - Cheating Nim 問題概要 2人でNimをする。 はじめに 個の山があり、 番目の山には石が 個ある。 ゲームが始まる前に、それぞれの山から石を0個または1個取り除く。 後手が必ず勝つために取り除く石の数の最小値を求めよ。 制約 解法 Nimで後手が勝つため…

「みんなのプロコン 2018」決勝 A - Uncommon

A - Uncommon 問題概要 個の異なる整数 と整数 が与えられる。 以上 以下のそれぞれの整数 について、 のうち と互いに素であるものの個数を求めよ。 制約 解法 ある数 について、 のうち と互いに素であるものの個数を求めるとき、愚直に1つずつ試して でや…

Codeforces Round 498(Div.3) E. Military Problem

Problem - E - Codeforces 問題概要 頂点の根付き木が与えられる。根は1である。 ある頂点が命令を与えられると、自分の子のうちまだ命令が与えられていない1つの頂点(複数あれば頂点番号が最も小さい頂点)に命令を与える。命令が葉まで伝搬すると、自分の…

Codeforces Round 498(Div.3) D. Two Strings Swaps

Problem - D - Codeforces 問題概要 長さ の2つの文字列a,bが与えられる。文字列はともに小文字のアルファベットから構成される。 はじめに、好きな回数だけ以下の置換操作を行うことができる。 となる を一つ選び、 を任意のアルファベットに置換する その…

Codeforces Round 498(Div.3) C. Three Parts of the Array

Problem - C - Codeforces 問題概要 長さ の数列dが与えられる。 この数列dをA,B,Cの3つの連続する区間に分割する。(長さ0の区間が存在しても良い)Aの長さをa、Aの要素の総和をsum1とする。 同様に、Bの長さをb、Bの要素の総和をsum2、Cの長さをc、Cの要素…