ツバサの備忘録

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

リベンジ

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

SoundHound Inc. Programming Contest 2018 -Masters Tournament-

コンテスト開始2分前ぐらいまでアイスを食べていて、乗り遅れそうになりました。 A - F 提出コード if文を使って、aとbの足し算、掛け算が15になるかどうかを調べます。どちらでもなければその時用の出力をして終わりです。 B - Acrostic 提出コード 入力用…

ABC101

最近忙しいですがICPCも近いので少しでもプログラミングに触っていたいですね。 A - Eating Symbols Easy 提出コード 0からスタートして、+が出現したら1をたし、-が出現したら1を引いていきます。sの長さの指定をよく見ていなかったので、sの長さだけループ…

ABC100

はい、記念すべき100回目です。 …だったのですが、本当にボロボロでした、過去の成績の中でもパフォーマンスがワースト2位です。 今日ABCに初参加だった大学のお友達にも負けてしまったので本当に悔しいです。猛省します。 A - Happy Birthday! 提出コード …