ツバサの備忘録

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

AtCoderで黄色になりました

青になってから半年と少しがたち、ようやく黄色になることができました。 振り返りをします。自分が書きたいことを書いているので、黄色になるための秘訣!みたいな記事ではないです。ご了承ください。 黄色になりましたーー!!! pic.twitter.com/XTVUlTpE…

ABC033 D - 三角形の分類

問題 提出コード 解法 直角三角形と鈍角三角形について、それぞれ直角、鈍角な角は1つの三角形につき1つです。それ以外は全て鋭角となるので、 直角三角形→直角の個数 鈍角三角形→鈍角の個数 鋭角三角形→から上2つの個数を引いたもの が答えになります。 あ…

Educational DP Contest / DP まとめコンテスト Z - Frog 3

問題 提出コード 解法 番目の足場へ行く最小コスト とします。すると、 となります。 これを式変形すると、 となります。は最後に足して問題ないことがわかります。 とすると、 という式になり、調べたいのは、 のの際の最小値 となります。 これは直線の式…

Educational DP Contest / DP まとめコンテスト Y - Grid 2

問題 提出コード 解法 包除原理を用いて解きます。 個以上の壁を通り、番目の壁に到達するような通り方の場合の数 とします。ここで、壁について、行、列の順で昇順ソートしておくと、番目の壁を通る際に、番目以降の壁を先に通ることはありえなくなるので、…

Educational DP Contest / DP まとめコンテスト X - Tower

問題 提出コード 解法 現在、積まれているブロックの重さの総和をとします。 ここに、2種類のブロックを、どちらの順番で新しく下に置くかを考えます。 の方がより上にくる場合 の方がより上にくる場合 1つめの条件は、結局2つのブロックを乗せることにした…

Educational DP Contest / DP まとめコンテスト W - Intervals

問題 提出コード 解法 文字目を"1"にした場合に、で得られる得点の最大値 を考えます。 すると、 が間に含まれているものを除いた区間達について計算した場合の、で得られる得点の最大値に、が間に含まれている区間の得点の総和が、の値になります。 これを…

ICPC 2019 Asia Yokohama Regional参加記

ということで、チーム CoprimEとして、ICPCのアジア予選に参加してきました。 チームメイトはTsuzu君、mi君です。 1日目 ~リハーサル前 リハーサル リハーサル後 2日目 本番 コンテスト後 3日目 感想 1日目 ~リハーサル前 一部コーチの奢りです、わーい pi…

Educational DP Contest / DP まとめコンテスト V - Subtree

問題 提出コード 解法 全方位木dpをします。 初めに頂点1が根である際の値を求めます。 を根とする部分木について、を黒で塗った際の部分木の塗り方 とすると、頂点の子の集合をとして、 となります。 を根とした際の求めるべき答え とすると、 となります。…

第16回JOI本戦 A - フェーン現象 (Foehn Phenomena)

問題 提出コード 解法 それぞれのタイミングでの、の差がわかれば、のどちらかをかけつつ総和を求めればよいです。 それぞれの差について注目すると、ある区間が与えられたときに、に影響が出るのは、の2つのペアのみになります。これ以外の部分、およびこれ…

第13回JOI予選 D - 部活のスケジュール表 (Schedule)

問題 提出コード 解法 日目に参加した部員の状態がであるような、から日目までの部員の組み合わせの通り数 とします。 すると、 の中に、責任者が含まれていなければならない という条件があるので、もしの中に責任者がいなければ、 となります。 そうでない…

ARC064 E - Cosmic Rays

問題 提出コード 解法 あるバリア内は好きな座標に移動できます。 ので、あるバリアから、別のバリアへと移動することを考えます。 そのとき、2つのバリアについて重複する箇所が存在すれば、そのバリア同士は自由に行き来することができます。そうでないと…

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 - 弁当作り

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