読者です 読者をやめる 読者になる 読者になる

簡単な説明

主に競技プログラミングの問題について、自分のコードの記録などの記事を掲載していきます。「問題概要」「解答・解説」「自分の思考過程のメモ」あたりをベースに記事を書いていきます。

AGC 012 - A: AtCoder Group Contest

問題 agc012.contest.atcoder.jp

AOJ2709 Dark Room

問題 個の部屋があり、そのうち個が暗い部屋である。 各部屋には[tex1]〜に番号付けされたドアがある。 順に進むべきドアの番号を指示する列を与える。一度明るい部屋に到達したら、その続きの指示は無視される。 部屋のどこからスタートしても明るい部屋に…

AGC005 A - STring

問題 'S'と'T'からなる文字列がある。文字列のうち左から"ST"があればそれを繰り返し削除する。最後に残る文字数を答えよ。

AGC007 A - Shik and Stone

問題 グリッドを左上から右下まで移動した。移動したマスは'#'であり、そうでないマスは'.'である。何度も同じ場所を行き来することもある。右または下にだけ移動した可能性のある場合は"Possible"、そうでない場合は"Impossible"を出力せよ。

AGC007 B - Construct Sequences

問題 の順列がある。数列は単調増加、数列は単調減少するような数列で、 $$ A_{P_i}\ +\ B_{P_i} \lt A_{P_{i+1}}\ +\ B_{P_{i+1}} $$ であるようなを1つ求めよ。

ARC 064 C - Boxes and Candies

問題文 個の箱が一直線上にあり、各々に個の玉が入っている。隣接する箱の玉の数の和を個以下にするために、取り出す必要のある玉の数を答えよ。

C++でinsertやeraseが高速な配列を作る

この記事は Aizu Advent Calendar 2016 2日目の記事です。 前の人は、@___deraさん、次の人は @hnjk さんです。 C++でよく使われる動的配列に、std::vectorがあります。std::vectorはで配列の要素へのアクセス、push_backなどの操作が可能なデータ構造です。…

AOJ 2217: Let's JUMPSTYLE

問題 の2次元グリッドがあり、各マスにはワープする先のマスの座標が与えられる。ループの数を数え上げよ。

AOJ2249 Road Construction

問題 Road Construction | Aizu Online Judge 頂点、辺の連結グラフが与えられる。各辺には距離と建設コストが与えられる。0番目が首都であり、各ノードから首都までの距離を与えられたグラフと同じにするものとして、一から連結グラフを生成するための最小…

AOJ2102 Rummy

問題 9枚のカードがある。そのうち3枚が、同じ色で、かつ同じ数字または連番のとき、3枚を1セットとみなす。3セット揃っているかどうか調べよ。数字は1〜9までの値で、連番とは3,4,5のようなものを指す。9,1,2は連番ではないことに注意せよ。

AOJ2104 Country Road

問題 Country Road | Aizu Online Judge 限界集落には一直線上の道があり、電気の通らない家々が立ち並ぶ。 個の家が数直線状に並び、個の発電機が与えられる。全ての家に発電機から出る電気を行き渡らせたい。 発電機から出る電気は家同士を電線で結ぶこと…

AOJ2741 Invisible

問題 インビジブル | Aizu Online Judge 2人でカードゲームをする。各々デッキを持つ。カードには数字がかかれている。-1は妨害カードで、それ以外は正の得点となるカードである。2人は交互にプレイする。プレイヤーは、カードを場のスタック上に置くか、パ…

AOJ2035 It Prefokery Pio

問題 文字列から部分列を取り出し、最長の回文を作れ。複数ある場合はそのうち1つを出力せよ。

AGC 006: B Median Pyramid Easy

問題 B: Median Pyramid Easy - AtCoder Grand Contest 006 | AtCoder 段目に個のブロックがあり、ピラミッド型に積まれている。 ブロックには数字がかかれていて、あるブロックの数字はその左下と真下と右下のブロックに書かれた数字の中央値である。 ブロ…

LiveArchive 5874 Social Holidaying

問題 一般グラフにおいて辺数最大マッチングのサイズを求めよ。 解法 蟻本P198や組合せ最適化P271 系10.9 に載っているTutte行列を用いて最大マッチングを求めるLovaszのランダム化アルゴリズムを使う。 別の解法としては、Edmondsの辺数最大マッチングアル…

LiveArchive 5875 Orienteering

問題 巡回コースの通過点のリストが与えられる。個の通過点と人のプレイヤーがいる。各通過点は座標に存在し、得られる得点がである。各プレイヤーは名前と移動できる最大距離を持つ。各プレイヤーは原点から移動を始め、入力の通過点のうち幾つかの通過点の…

AOJ2397 Three-way Branch

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2397 縦に長いグリッドが与えられる。の位置からの位置に移動したい。移動の方法は、左下に、真下、右下のいずれかである。途中、個の障害物が有り、その場所は移動できない。移動の方法は何…

CODE FESTIVAL 2016 qual C - C: 二人のアルピニスト

問題 山脈の高さの列が与えられる。山を登るときは高さの最大値を記録して登る。左から登った人と右から登った人の記録が与えられる。このとき、本当の高さの列としてありうるパターン数をで求めよ。記録に矛盾がある場合もあるので、そのときは0と出力せよ。

CODE FESTIVAL 2016 qual C - B: K個のケーキ

問題 個のケーキが種類ある。各種類個ずつ存在する。毎日1個ずつ食べるとして、全てのケーキを食べ終えたとき、前日と同じケーキを食べる回数の最小値を出力せよ。

CODE FESTIVAL 2016 qual C - D: Friction

問題 D: Friction - CODE FESTIVAL 2016 qual C | AtCoder のブロックがある。各ブロックは赤、緑、青のいずれかである。1度の操作で、一番下の行あるブロックのうち1つを消すことができる。消すときにかかるコストは、消した列の各ブロックの横に隣り合うブ…

ICPCOOC2016 E: Infallibly Crack Perplexing Cryptarithm

問題 http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2016/E.pdf 以下のような文脈自由文法()が与えられる。 これに沿って書かれた1つの等式を表す文字列 がある。各文字は '0', '1', '(', ')', '+', '-', '*', '=' で構成される。等式の一部または…

ICPCOOC2016 D: Hidden Anagrams

問題 http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2016/D.pdf 2つの文字列 がある。一つの部分文字列のアナグラムが、他方の部分文字列に一致するような文字列の最長の長さを求めよ。

ICPCOOC2016 C: Distribution Center

問題 長いレーンのベルトコンベアが 列ある。はじめ各ベルトコンベアにはその番号の種類の品物のみが乗っている。隣接するベルトコンベアの間の位置に、 個のアームが存在する。これらは上下に隣接するレール間で品物を動かすことができる。レーンを抜けたと…

AOJ2679 Decoding Ancient Messages

問題 Decoding Ancient Messages | Aizu Online Judge のグリッドの各マスに文字が書かれている。ここから 文字抽出する。抽出する文字は同一行または同一列に存在してはいけない。任意の順番で抽出して並べたとき、作ることのできる辞書順最小の文字列を求…

ABC041 D: 徒競走

問題 D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder の順列を考える。数 は、数 の前にあるという情報が 個与えられる。条件を満たす順列の総数を求めよ。 のペアはすべて相異なる。 全ての情報に合致する並びが少なくとも1つ存在する。

AOJ1079 Cosmic Market

問題 Cosmic Market | Aizu Online Judge のグリッドがある。各マスには人がいて、はじめ全員が座っている。指定された行、または列に対して「立つ」または「座る」というクエリが回与えられる。最後に立っている人の数を答えよ。

D - アンバランス / Unbalanced

問題 D: アンバランス / Unbalanced - AtCoder Beginner Contest 043 | AtCoder文字列について、過半数を超えている文字があれば、その文字列はアンバランスであるという。 文字列が与えられる。の部分文字列について、アンバランスなものがあれば、その始点…

AOJ2090 Repeated Subsequences

問題 Repeated Subsequences | Aizu Online Judge文字列が与えられる。適当な位置で分割したとき、最長共通部分列をとる。 最適な位置で分割したときの最長共通部分列となる文字列を出力せよ。

LiveArchive 6905 Two Yachts

問題 https://icpcarchive.ecs.baylor.edu/external/69/6905.pdf2隻の船がある。また、(船の運用期間, 得られる金額) のペアで表された企画が個与えられる。 2隻の船だけを用いて運用できるようなスケジューリングをして、得られる金額の総和を最大化せよ。 …

LiveArchive 6904 Travel Card

問題 何日目に対して、バスに乗る回数と電車に乗る回数が与えられる。 バス、電車それぞれに1回乗る券の他に、 1日バス乗り放題券、1日バス・電車乗り放題券 7日バス乗り放題券、7日バス・電車乗り放題券 30日バス乗り放題券、30日バス・電車乗り放題券 が存…

2-SAT

解いたことあるような気がする問題 d.hatena.ne.jp No.274 The Wall - yukicoder 説明 codeforces.com

重み付き区間スケジューリング

まずは蟻本から Intervals (POJ No.3680) 個の重み付き閉区間がある。i番目の区間はをカバーし、重みを持つ。この中から個より多くの区間で覆われている点が存在しないように幾つかの区間を選び、重みの和を最大化せよ。 の場合、個の区間から互いに交差しな…

Data Structures and Network Algorithms: 8.4 最小費用流

増加パスの概念は、より一般的なネットワークフローの問題に拡張できる。 Gを各辺[u, w]が容量とフローの1ユニットごとのコストcost(v, w)を持つグラフとする。 簡単のため、コストを歪対称的(skew symmetric)とする。すなわち (1) フローfのコストは、(2) …

UoA練習会 2016 VC 035 メモ

Regionals 2014 :: Asia - Daejeon B - 6895 Deduction BruteForceっぽい I - 6902 Three Squares 似た問題がTopCoderであったな…TopCoder SRM614 DIV1 EASY - MinimumSquare - ゲームにっき(仮)別館(仮) K - 6904 Travel Card 状態はバスと電車それぞれ…

UVa1229 Sub-dictionary

問題 https://uva.onlinejudge.org/external/12/1229.pdf 個の単語が載っている辞書がある。すべての単語を理解したい。 サンプルの場合、 5 aue oizer piqoi oizer doy oizer hweqlo hweqlo hweqlo piqoi aue oizer piqoi piqoi aue aue 0 となっていて、「…

UVa410 Station Balance

問題 https://uva.onlinejudge.org/external/4/410.html Given chambers which can store 0, 1 or 2 specimens, specimens and a list of the masses of the specimens, determine which chamber should store each specimen in order to minimize imbalance.

AOJ0091 Blur

問題 にじみ | Aizu Online Judge 布に染料を垂らす。染料は小中大の三種類あり、それぞれ広がる幅が異なる。 N滴落とした布の状態が与えられるので、染料を落とした座標を復元せよ。 染料は同じ場所に何度も落とすことが出来る。 N

AOJ2328 Mobile Network

問題 Mobile Network | Aizu Online Judgeネットワークが与えられる。帯域幅として各辺にxの多項式が重みづけられている。 1番目のノードからN番目のノードまでトラフィックを流したとき、流れる量を最大化せよ。

LiveArchive 7230 Log Jumping

問題 https://icpcarchive.ecs.baylor.edu/external/72/7230.pdfN個の丸太を円形に並べる。それぞれ高さH[i]を持つ。隣接する丸太の高さの最大値を最小化せよ。

LiveArchive 7227 Equilibrium State

問題 https://icpcarchive.ecs.baylor.edu/external/72/7230.pdfXY平面に、M個のばねとN個の物体が釣り合って、K個の定点で固定されている。物体の重さはなく、バネのたるみもない。 ばね定数と、定点の座標が与えられるので、物体の座標を順に求めよ。 バネ…

LiveArchive 7226 Coin Swap

問題 https://icpcarchive.ecs.baylor.edu/external/72/7226.pdf白または黒の何れかが塗られたノードを持つグラフがある。 はじめ、白または黒のコインが、ノードの色の数と同じ数だけバラバラのノードの1つずつ置かれている。 コインを隣接するノードのコイ…

AOJ0069 Drawing Lots II

問題 あみだくじ | Aizu Online Judgeあみだくじをする。縦棒の数と段の高さと、初めに選ぶ縦棒と当たりの縦棒の情報が与えられる。 この状態で当たりを引くことは出来るか。 また、一本だけ横棒を引くことが出来る。一本引いた場合に、あたりを引くことが出…

AOJ0037 Path on a Grid

問題 格子状の経路 | Aizu Online Judge 右手法で壁をつたう。はじめの位置からスタートして、元の位置に戻ってくるまでの移動方向を逐次出力せよ。 詳しくはリンク先の図と入出力を見て下さい。

AOJ2680 LR

問題 LR | Aizu Online Judge'L', 'R', '?', '数字', ',' で構成された文字列が与えられる。, であるとき、文字列の出力を最大化せよ。 また、正しい数または式が生成できない場合はinvalidとせよ。 文字列長

AOJ2613 Unordered Operators

問題 二項演算子の優先度を自由に設定した時、以下のBNFで表される式から導かれる値の最大値を求めよ。ただし、結合性は左結合である。 <expr> ::= ( <expr> ) | <number> | <expr> <op> <expr> <op> ::= + | - | *</op></expr></op></expr></number></expr></expr>

AtCoder Begginer Contest #040 D - 道路の老朽化対策について

問題 D: 道路の老朽化対策について - AtCoder Beginner Contest 040 | AtCoder頂点、辺の重み付き無向グラフが与えられる。 個のクエリがあり、初期位置と辺を通れる境界のコストが与えられる。 通れる境界のコストより大きいコストを持つ辺のみ、通ることが…

AOJ2255 6/2(1+2)

背景 結局は9なのでしょうか 6÷2(1+2)とは (ロクワルニカッコイチタスニカッコトジとは) [単語記事] - ニコニコ大百科問題 6/2(1+2) | Aizu Online Judge優先度が括弧しか決まっておらず、四則演算は任意の順で計算してよいような計算方法で、与えられた式を…

ACM-ICPC模擬国内2016B - C

問題 問題文は以下から参照できます http://acm-icpc.aitea.net/index.php?2016%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8B%2F%E5%95%8F%E9%A1%8C%E6%96%87%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E3%82%BB%E3%83%83%E3%83%88

AOJ2607 Invest Master

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2607初めX円所持している。株式は1つも所持していない。N種類の株式がある。 i日目に株式jに購入すると1つの株式jを入手でき、P[i][j]だけ掛かる i日目に株式jを1つ売却するとP[i][j]円入手…