ツバサの備忘録

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

AOJ 1232 - Calling Extraterrestrial Intelligence Again

問題 提出コード 問題概要 3つの整数が与えられます。 かつとなるようなのうち、が最大となるようなペアを求めてください。 制約は、です。 解法 まずはエラトステネスの篩を利用して、素数を洗い出します。 について全探索をすると、の最適解は、あるに対し…

ABC142 F - Pure

問題 提出コード 解法 方法は、番目から番目に戻ってくるサイズが最小の閉路について、問題の条件を満たしているかどうか調べる、というものです。 これを全てのについて調べ、存在すればそれを答えればよいです。 何故なら、与えられたグラフの中で、最小の…

ABC142 E - Get Everything

問題 提出コード 解法 制約がbitDPをしろと言っているので、bitDPをします。 現在開けた宝箱の状態がのときに、そこからかかる費用の最小値 とします。 を整数型の変数1つで表し、2進数の桁に宝を割り振り、0:まだ開いていない、1:開いている、とすると 初期…

会津大学競技プログラミング合宿2019参加記

1日目 行き コンテスト コンテスト後 2日目 朝 コンテスト 懇親会 懇親会後 3日目 朝 コンテスト 帰り 全体のまとめ おまけ と言うことで、昨年も参加したACPCに再び参加しました。 1日目 行き 最小費用流の勉強をします pic.twitter.com/TmeDe6DpZ0— ツバサ…

ACM-ICPC Japan Alumni Group Summer Camp 2019 Day 1 - D Permutation Sort

問題 問題概要 長さの順列が与えられます。 1回の操作で、 に変換する、という操作を全てのについて行います。 全てのがとなるまでの操作回数の最小値を求めてください。 解法 何回か操作をするといずれループすることがわかります。 操作して初めてとなるよ…

ACM-ICPC Japan Alumni Group Summer Camp 2019 Day 1 - B Not-trivial Common Divisor

問題 問題概要 個の数が与えられます。 その中で、全ての要素がで割り切れるような集合を作り、そのの総和を最大化してください。 解法 を合成数にするよりも、素数にした方がお得(と選ぶと、が約数ではあるがが約数に含まれない数の分だけ損をしてしまう)な…

ACM-ICPC Japan Alumni Group Summer Camp 2019 Day 1 - J Rooks Game

問題 問題概要 の盤面に、個の駒が配置されています。それぞれの駒は、縦か横方向に好きなだけ移動させることができ、他の駒にぶつかったら、その時点で停止してぶつかった駒を獲得することができます。ただし、他の駒が存在しない方向へ動かすことはできま…

JAG夏合宿2019参加記

1日目 2日目 3日目 感想 1日目 なぜか平日ダイヤで時間調べてた!!!危ない— ツバサ (@emtsu_ba) September 14, 2019 蟻本忘れた!!— ツバサ (@emtsu_ba) September 14, 2019 1日目からポンコツをたくさんしました。 目的地に向かう途中、goodbatonさんに…

ABC132 F - Small Products

問題 提出コード 解法 番目にを置くような数列の場合の数(ただし、 ) 番目に、を満たすようなを置く数列の場合の数 とします。 以下で最大の整数を、を満たすようなの個数をとすると、それぞれ次のように遷移を行うことができます。 あとは、全てΣの形になっ…

ABC128 F - Frog Jump

問題 提出コード 解法 とすると、実際の遷移は図のようになります。 ということで、距離おきに、前から個、後ろから個の蓮の得点を得ると決めた時のは自動的に決まります。 をある値に固定したとき、はだいたい個の候補が存在し、について全探索を行ってもに…

ABC138 F - Coincidence

問題 提出コード 解法 が問題の条件を満たすには、これらを2進数に直した時に、 最上位桁が一致している それぞれの桁について、の桁目との桁目が一致している、もしくはのみ0でのみ1になっている という条件を満たす必要があります。 ということで、最上位…

ABC138 E - Strings of Impurity

問題 提出コード 解法 に含まれ、に含まれない文字が存在する場合、答えは-1になります。逆に、それ以外の場合は、必ず答えを見つけることができます。 の部分列でを作る際、お互いの先頭から順番に、一致する部分を選んでいけばよいです。 作りたい文字列は…

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をします。 区間の中で落とせるブロックの最大値 とすると、答えはとなります。 まず、となります。続いて、ならばとなります。 では、を求めていきます。 まず、 (すなわち、区間のブロックをすべて落とせるということです)かつ…