ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2152 - Restrictive Filesystem

問題 提出コード 解法 手で連結リストを作成していきます。 setで現在存在しているファイルの識別子を管理しておくことで、リストの中身を毎回書き換えずとも、削除のクエリを処理できるようにします。 あとは、リストを毎回前から探索していき、空きスペー…

AOJ 1604 - デッドロック検出

問題 提出コード 解法 まずは、すでにロックを獲得した資源と、次に獲得する資源を対にした頂点を作成していきます。 10個程度しか資源は存在しないので、ビットで情報を持たせることができます。 その後、2つの頂点を選んだときのパターンを見ると、今回は3…

AOJ 2642 - 夕食

問題 提出コード 解法 日間で、日目に自炊を行ったと仮定します。 このとき、得られる幸福度は以下のようになります。 はじめの2つの項が食堂で食べることによって得られる幸福度、最後のΣの部分が自炊によって得られる幸福度になります。 これを式変形する…

AOJ 1168 - ぐらぐら

問題 提出コード 解法 愚直に、それぞれのピースに対して条件を満たしているか確認していきます。 ピースそれぞれを頂点、上下で接しているかどうかを辺としたグラフを作成していき、あるピースに対してのバランスを調べる際は、そのグラフを辿って見ていき…

AOJ 2511 - 沈みゆく島

問題 提出コード 解法 まずは前から見ていき、移動経路が確保できなくなるタイミングを探します。 そして、その直前からさかのぼって行き、今構築済みの木に最小限の辺を足して、全域木になるようにしていけばよいです。 基本的には最小全域木と同じ考え方で…

みんなのプロコン2019 D - Ears

問題 提出コード 解法 適当に実験をすると、散歩後の石の個数は、座標が小さい順に、次のような区間でわけることができます。 石が0個の区間 石の個数が2個以上の偶数の区間 石の個数が奇数の区間 石の個数が2個以上の偶数の区間 石が0個の区間 ただし、それ…

AOJ 1619 - 弁当作り

問題 提出コード 解法 制約にと書いてあります。これがすべてです。 が大きいパターンとが大きいパターンで場合分けをします。 なので、実はが、簡単にビットで情報を持つことができます。 が小さいパターン 全探索をします。 それぞれの材料について、その…

COLOCON -Colopl programming contest 2018- C - すぬけそだて――ごはん――

問題 提出コード 解法 あらかじめ、ある数とが同時に存在しうるか、を調べておきます。 使用できる数を、前半の20個と、残りの2つの部分に分け、それぞれに処理をしていきます。 最終的には、前半の状態を1つ決めた時の、後半の場合の数を高速に計算して、前…

AOJ 2200 - Mr. リトー郵便局

問題 提出コード 解法 まずは、陸路と海路それぞれについて、ワーシャルフロイド法を用いて、任意の町間の最短距離を計算しておきます。町から町の最短経路について、陸路を、海路をとします。 そして、DPを行います。 回目の集配を終えた時点で、船が町にあ…

AOJ 1132 - Circle and Points

問題 提出コード 解法 1個のみ円の中に入るパターンは明らかなのでここでは2個以上のパターンのみ考えます。 円の中に入る点の個数が最大の円の配置方法があるとき、その個数を減らさないまま、ある2点を同時に円周上に乗せることができます。 ということで…

AOJ 1176 - 輪番停電計画

問題 提出コード 解法 はじめに、2次元累積和を用いて、ある長方形の範囲の需要の合計をで求めることができるようにしておきます。 ここから、DPを行います。 長方形の左上が,右下がとなるような範囲のグループの分け方の最適解 とします。最適解、なのでグ…

AOJ 0570 - ジグザグ数 (Zig-Zag Numbers)

問題 提出コード 解法 以下のジグザグ数の個数から、以下のジグザグ数の個数を引くと答えになるので、あとは以下のジグザグ数の個数を求める方法がわかればよいです。 桁が明らかに大きいので桁DPをしていきます。 について、 : 今見ている桁の番号 : 以下が…

AGC036 C - GP 2

問題 提出コード 解法 まず、最終的な数列の中に奇数が個存在するときについて考えます。は最大でとなります。 すると、残ったに1加算する操作を2つまとめて、に2加算する操作回分に置き換えることができます(もちろん、残った回数が奇数の際は端数が発生す…

AGC036 B - Do Not Duplicate

問題 提出コード 解法 同じ状況になる部分をどんどん取り除き、最終的に残る数回を愚直にシミュレーションします。 まずは、空の数列に対して番目の数字をに入れたときに、を取り除くことで再び数列が空になるタイミングはどこか、を調べます。 これは、の種…

AOJ 1161 - 覆面算

問題 提出コード 解法 愚直に見ていきます。 下の桁から順番に文字を決めていきます。 式が成り立っているかどうかを最後に番目の文字列と比較するとTLEをします(した)が、それぞれの桁についての数字を確定させた時点で、番目の文字列で対応する桁と比較し…

AOJ 1169 - 最強の呪文

問題 提出コード 解法 それぞれの頂点にたどり着くときに文字数がになっているような呪文の中では、最強の文字列が常に一意に決まります。 ループをしない場合、文字数は最大でも240文字程度にしかなりません(頂点数が40、辺に与えられた文字列の長さは最長…

AOJ 1140 - Cleaning Robot

問題 提出コード 解法 基本的にはBFSをしていけばよいです。 にいるときに、掃除済みの汚れたタイルの状態がになるような掃除の手順の中での最短手順 とします。 汚れたタイルは高々10枚なので、掃除済みかどうかの情報をbitで持っても、1024通り程度にしか…

AOJ 1611 - ダルマ落とし

問題 提出コード 解法 区間DPをします。 区間の中で落とせるブロックの最大値 とすると、答えはとなります。 まず、となります。続いて、ならばとなります。 では、を求めていきます。 まず、 (すなわち、区間のブロックをすべて落とせるということです)かつ…

AOJ 1163 - カードゲーム

問題 提出コード 解法 フローの典型っぽいマッチング問題です。 始点、終点と、赤青のカードそれぞれを表す頂点を用意し、始点→赤の頂点、青の頂点→終点に重み1の辺を張っておきます。 そして、任意の赤と青のカードのペアについて、取り除くことができるも…

AOJ 1162 - 離散的速度

問題 提出コード 解法 都市から都市に速度で移動してきたときにかかる時間の最小値 とすると、現在の都市、1つ前の都市、現在の速度、現在経過した時間をひとまとめにしつつダイクストラをすればこの配列を埋めることができます。 キューから取り出した要素…

ICPC 2019 国内予選 参加記

ICPCの国内予選に参加しました。模擬国内はこちら ICPC、@Wp120_3238@mi_tesseract と僕の3人でチーム"CoprimE"で出場します!— ツバサ (@emtsu_ba) 2019年7月12日 名前の由来は、チームメンバーに共通点がほとんどなかったことです(1999年生まれということ…

ABC133 E - Virus Tree 2

問題 提出コード 解法 探索か何かをしつつ、今いる頂点について色を決ようとすると、その頂点から距離2以内で、すでに色が決まっている頂点がいくつあるかを調べる必要があり、とても大変です。 そこで、今いる頂点から行くことができる頂点について、色を決…

ABC133 D - Rain Flows into Dams

問題 提出コード 解法 番目の山に降った雨の量をとします。 すると、以下のような式が成り立ちます。 ということで、これらの式をまとめてを求めることを考えてみます。 上の式から順番に、式1,2,...Nと名付けると、 式番号が奇数のものはそのまま、偶数のも…

ABC133 C - Remainder Minimization 2019

問題 提出コード 解法 基本的には、区間から2つ数字を選び、の最小値を求めていけばよいです。 が、このままだと 回の計算が必要になってしまうので、この制約では間に合いません。 ここで、の長さに注目すると、この長さが以上の際は、確実にがとなるような…

ICPC2019模擬国内予選参加記

ICPC2019模擬国内予選に参加しました。 いろいろあって今年のチームメンバーは Tsuzu君(@Wp120_3238)とmi_tesseract君(@mi_tesseract)です。 チーム名はCoprimEです。 コンテスト中の動き ざっくりと… 開始直後 予定通り、自分がAを解き、残りの2人がB,C以降…

AOJ 2298 - Starting Line

問題 解法 解法 が間に合うことに注目すると、任意の距離1の区間区間それぞれについて、速度で走るかで走るかを決めていけば良いです。 にんじんを食べるタイミングは貪欲に決めることができ、 今スピードアップしてなければ拾ったタイミングで食べる 今スピ…

AOJ 2151 - 勇敢なお姫様またも現る

問題 提出コード 解法 頂点を増やします。 都市に着いた段階で予算のうちだけ消費するような経路の中で、襲われる人数の最小値 とすると、今いる都市、消費した予算、襲われる人数を一緒に持った状態でダイクストラ法を適用すれば良いです。 次の都市に遷移…

ABC131 D - Megalomania

問題 提出コード 解法 やることから先に言うと、 をの昇順でソートし、を満たす任意のについて、 が成立すれば答えがYesになり、1つでもこれが成立しなければNoになります。 結局、時刻の時点では、締め切りが以下の仕事については全て終えている必要がある…

ABC131 C - Anti-Division

問題文 提出コード 解法 ベン図を見ると見通しが良くなります。 を求めるには、 全体のから、を引き、を足せばよいです。 これが全体の図です。 という式になります。 、というのは からを引けばいいので、 答えをつらつらと記述すると、 となります。 とい…

ABC130 E - Common Subsequence

問題 提出コード 解法 LCSや編集距離に近いものを感じたので、似たような遷移のDPを考えていきます。 までを見終えた段階でできる、問題の条件を満たす整数列の個数 とします。 初期値としては、です。いずれのパターンでも、共に1つも選ばない1通りの整数列…