ツバサの備忘録

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

リベンジ

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

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

AOJ 1604 - デッドロック検出

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

AOJ 2642 - 夕食

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

AOJ 1619 - 弁当作り

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

AOJ 1132 - Circle and Points

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

ABC128 E - Roadwork

問題 提出コード 解法 0.5うんぬんという条件がありますが、結局は時刻の間で座標に到着した場合、その人はそれ以上進めない、ということになります。 これを言い換えると、時刻の間に座標を出発する人は、少なくともより先に進むことができなくなります。 …

ABC127 F - Absolute Minima

問題 提出コード 解法 は、とりあえず答えに加算すれば良いので、ほとんど無視して問題ないです。ということで、とについて考えていきます。 の総和を最小化する問題は、をの中央値にすればよいです。現在のがわかっているとき、となるようなについては、そ…

Tenka1 Programmer Beginner Contest 2019 D - Three Colors

問題 提出コード 解法 まず、三角形の成立条件を思い出すと、長さの三角形が存在するには、 が全て成立している必要があります。 逆に、が最長の辺かつを満たしているとき、三角形を作成することはできません。両辺にを追加した後に2で割ると、 という条件が…

AtCoder Petrozavodsk Contest 001 D - Forest

問題 提出コード 解法 まずは、全ての木を連結にするには、それぞれの木について、頂点を少なくとも1つ選んで連結にする必要があるので、それぞれの木から、最もコストが小さい点を1つずつ選んでおきます。 また、コストを最も少なくして全てを連結にするに…

九州大学プログラミングコンテスト2018 F - Team Making

問題 提出コード 解法 制約にbitDPをしてくださいと書いてあります。 ので、実際にbitDPを考えてみます。 今チームを組み終わっている人の状態がであるときの、これ以降のチームの組み方 とすると、まだチームを組めていない人の中で組めるようなチームの集…

ABC020 D - LCM Rush

問題 提出コード(100点) 提出コード(満点) 100点から満点にもっていくことができず、解説を見ました… 言われれば確かにそうだけど~って感じですね。 解法 まずは100点までです。 の制約が少ないので、について何かをするんだろうな、という気持ちになります…

ABC077 D - Small Multiple

問題 提出コード 桁和関連の問題は本当に解ける気がしないです…方針が立ちません。解説を読んでもわからないので、数日寝かせていました。 解法 について、基本的には1を足すと桁和が1増加し(例外があります)、10倍すると桁和は据え置きです。 ということで…

グランディ数の問題の解き方メモ (ARC072 D - Alice&Brown)

あまりに苦手なので、やまさん(@yamasangamasan)に解き方のコツを聞いたのでメモしました。文章だらけなのでかなり読みづらいです... グランディ数を使う問題は、 二人零和有限確定完全情報ゲームです(!) AとBの2人がいて、ある操作行うようなゲームをしま…

ABC044 D - 桁和 / Digit Sum

問題 提出コード これが500点?という感じの難易度でした。苦手意識があり、全く違うベクトルの考察を始めてしまうので解ける気がしません… 解法 のとき、になります。それ以外でになるようなは存在しません。ということで、の場合は、が答えになります。こ…

Tenka1 Programmer Contest (2018) C - Align

問題 提出コード 時間内に解きたかったですね… 解法 解説に詳しい証明が載っているのですが、並べた後の数列が凸凹になっていると、効率がよりよくなります。 みたいな感じです(逆もあり得ます)。 このとき、以下のような図で表現できます。上にある頂点は隣…

AOJ 2233 - Carrot Tour

問題 提出コード 解法 これ自力で解ききれなかったの悔しいですね… dp[i][j][k] = k回目の移動でiからjに移動するときの、それまでの移動距離の合計の最小値 とします。こうすることで、持っているにんじんの個数は自動的にkになります。 そして、 dis[i][j]…

AGC027 B - Garbage Collector

問題 提出コード 解法 ゴミを回収しに行く回数(=ゴミを捨てる回数)を回と決め打ちし、そのときの最小値を求めます。 そして、最後にについて全探索して答えを求めることを考えます。 回ゴミを回収しに行くとき、ゴミを拾う回数は回、捨てる回数は回なので、…

ARC087 E - Prefix-free Game

問題 提出コード 解法 グランディ数の問題かつ、二分木が関係していて…と割と惜しいとこまではいけた(つもり)なのですが、最後がうまくまとまらなかったので解説を見てACしました。 完全二分木を組み立て、そこに今回の文字列をうまく落とし込むと、現在選…

ABC009 D - 漸化式

D - 漸化式 提出コード かなり難しいです。ほぼ数学です。 漸化式をうまく行列に落とし込んで表現する方法を考えます。 まず、前提条件として非負整数はXORとANDに関して半環をなす、ということを理解している必要があります。 XORを足し算、ANDを掛け算のよ…

ABC011 C - 123引き算

C - 123引き算 提出コード 何故かハマってしまいまったく歯が立たなかった問題になります。 100回”以内”でゴール(0にする)すればいいので、とりあえず3をどんどん引いて行ってしまうのが最善の手になります。 もし3引いたときにNG数字にひっかかってしまうよ…

ARC102 D - All Your Paths are Different Lengths

D - All Your Paths are Different Lengths 提出コード n進数を利用する、というところまではよかったのですがそこから歯が立ちませんでした。 結論から言うと2進数を利用します。 まずは大元となる2進数のグラフを作成します。 となるうちの最大のxを求めま…

ABC107 D - Median of Medians

D - Median of Medians 提出コード 初めてBITを使った問題です。 この問題では、中央値となる条件をうまく言い換えていき、最終的に転倒数を求める問題に帰着させます。転倒数を求める段階で、BITを利用します。蟻本をみたらそこにも載っていた問題になりま…

ABC008 C - コイン,D - 金塊ゲーム

C - コイン 提出コード 重要なのは、あるコインについて、その数字の約数となっているコインが左側にどれだけあるか、です。 なので、それぞれのコインについて、その数字の約数となっているコインの枚数をまず数えておきます。 あとは、それぞれのコインに…

ARC028 D - 注文の多い高橋商店

D - 注文の多い高橋商店 提出コード 満点を取るには、ほぼでクエリにこたえていかないといけません。 そこで、 ans[i][j] = i番目の品物を使わずにj個選ぶ方法 とすると、与えられたk、xを用いてans[k][m-x]を参照するだけで答えを出すことができます。 まず…

京都大学プログラミングコンテスト(KUPC)2013

競プロの練習会で、こちらのセットを使用したバチャコンをチームで行ったので解いた問題についてのメモをしていきます。 チームメイトはICPC出場時と同じくやまさん(@yamasangamasan)、べるくん(@dora_marutation)でした。加えて、相手チームがICPC本戦出場…

ABC003 C - AtCoderプログラミング講座,D - AtCoder社の冬

今回もバチャコンで解いたC問題とD問題のメモです。 C - AtCoderプログラミング講座 提出コード まずは動画のレートを降順でソートします。 そうしたら、大きい方から動画を見る個数だけ持ってきて、それを小さい順に見ます。 動画を見るたびに現在のレート…

ABC041

バチャコン3回目です。初めてbitDPの問題に触れました。 A - 添字 提出コード 今回のA~Cはかなりシンプルでした。 A問題は、素直に文字列sのi番目の文字を出力すれば良いです。配列の最初が0になっていることだけ気を付ければ大丈夫です。 B - 直方体 提出コ…

ABC104

unratedでよかった… 人生初のABCunratedでした。爆死しました A - Rated for Me 提出コード 最初の問題からなんかとっつきにくいなぁって思いました。 少し思考が停止しましたがきちんと3つの場合分けをしてなんとかACでした。 以下と未満に惑わされないよう…

Mujin Programming Challenge 2018

目標は200位でした。レート順400位ぐらいだったので運次第、と思ってました A - コンテスト名 提出コード 頭が真っ白になったので素直に全部書き出しました。与えられる文字の長さがそもそも5に満たない場合の条件を途中まですっかり書き忘れていたので危な…

AGC26

二回目のAGCでした。 A - Colorful Slimes 2 提出コード まず入力時に、どの色のスライムがいるかを調べます。前から順番にスライムをチェックしていって、一個前のスライムと色が同じだったらその都度色を現時点で使ってない色に変えていけば、最短手数で合…