ツバサの備忘録

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

数え上げ

AGC036 C - GP 2

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

ABC133 E - Virus Tree 2

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

AGC034 B - ABC

問題 提出コード 解法 ABCがBCAになるので、これが連鎖的に続くことを考えると、 AAA...BCがBC...AAAになる、もしくはA...BCBCがBCBC...Aになる、の2通りです。 後者のパターンは、前者のパターンをBCが連続している個数だけ繰り返す、とみなすことができる…

ABC127 E - Cell Distance

問題 提出コード 解法 ある位置に置かれた2つの駒のマンハッタン距離が何回加算されるかを考えると、個の残りの駒を配置する種類数そのものになります。ということで、これは回です。任意の位置にある2つの駒について、同じ回数だけ加算されるので、あとは任…

BAPC2019 E - Entirely Unsorted Sequences

問題 提出コード 問題 個の数字が与えられるので、その数字を使って作れる数列のうち、以下のような条件を満たす数列の個数をで割った値を求めてください。 全ての数字について、その数字より左側に自分より大きいものが存在する、もしくは右側に小さいもの…

ABC021 D - 多重ループ

問題 提出コード 解法 答えの本質となる部分は問題文にすでに書いてあります。 求める数は、となるようなの組み合わせの個数です。 さて、以上以下の数字を個重複を許しつつ抽出すると、それらの数字を利用して作成したの組み合わせは一意に決まります。なぜ…

ABC114 D - 756

問題 提出コード バグを生やしやすい問題です。相変わらずこういう問題でバグを生やしてしまいます。 解法 をまずは素因数分解し、それぞれの素因数が何回登場しているかを調べます。 これは、それぞれについてで調べることができるので、全体でになります。…

ABC071 D - Coloring Dominoes

問題 提出コード 解法 縦になっているドミノ1本と、横になっているドミノ2本をそれぞれ1セットとして考えていきます。これは、文字目の上下が一致しているかどうかを調べるだけで簡単に判断できます。横になっているセットについては、次のセットに行くとき…

第5回 ドワンゴからの挑戦状 予選 C - k-DMC

問題 提出コード WAしていたコードの冗長な部分をコンパクトに書き直していたら、バグが消えていたのに提出しなかったので、結局時間内にACすることができませんでした…パフォが400ほど変わるのでめちゃくちゃ悔しいです。知らぬ間にバグが消えていたパター…

ABC077 C - Snuke Festival

問題 提出コード 中段について、番目のパーツを使うとしたときに、使うことができる下段のパーツはとなるパーツ番号の場合です。このようなのうち最小のものをもとめれば、それより大きい個のパーツはすべて使用できます。 ということで、まずはそれぞれのパ…

codeFlyer (bitFlyer Programming Contest)予選 C - 徒歩圏内

問題 提出コード これを自力で解けなかったのは結構悔しいです…最近思い通りになかなか解けないですね 解法 ,,となるようなの組を探します。 要素が3つ存在するので、まずは真ん中を決め打ちしたときののペアの個数を求めることを考えます。 あるについて、…

codeFlyer (bitFlyer Programming Contest)予選 D - ハンコ

問題 提出コード 解法 基本方針は、いもす法を利用して移動したときに黒くなる部分を求めていくことです。 紙の左上にまずはハンコを合わせます。すると、 マスが黒かったとき、右にマス、下にマスの範囲内がすべて黒く塗られることになります。 ということ…

ARC077 D - 11

問題 提出コード 解法 ダブっている数字は数列に1つ必ず存在します。 ダブってる数字のうち左側にあるものを,右側にあるものをとしたとき、数列は次のようになっています。 ここで、はそれぞれ0個以上の要素を持っている数列です。 長さの部分列を数え上げる…

ARC065 D - 連結 / Connectivity

問題 提出コード 解法 UnionFind木を貼ると解ける問題です。 鉄道について、辺をそのままUnionFind木に反映させると、根が同じ都市については、連結であることになります。 道路についても同様です。ということで、まずはUnionFind木を2つ用意し、鉄道と道路…

ABC113 D - Number of Amidakuji

問題 提出コード DPをします。 まずは、下準備をします。 ある高さについて、幅がのとき(つまり、本の棒があるとき)に、横線の置き方がいくつあるかを計算します。 これをとします。 のとき、横線はおけないのでです。 のとき、横線を置くか置かないかの2通…

ABC045 D - すぬけ君の塗り絵 / Snuke's Coloring

問題 提出コード 想定解の方がスマートでした。 自分は、mapを使ってごり押しをしました。 解法 素直に全探索することをまず考えてみると、 9マスのうち、左上のマスを決め打ってから9個のマスを確認する、という動作は、左上のマスの候補が となるので、も…

ABC042 D - いろはちゃんとマス目 / Iroha and a Grid

問題 提出コード 解法 modとコンビネーションが出てくるので、例によって逆元の知識を使用します。 例によってけんちょんさんの記事を載せておきます。 qiita.com 問題の条件を図で表すと次のようになります。 Sがスタートの位置、Gがゴールの位置で、黒く塗…

AGC028 B - Removing Blocks

問題 提出コード 解法 サンプル2がすごい実験に使いやすいのでこれを利用していくことで解けました。 まず、は、番目が足される回数に最後に掛け合わせるだけでいいので、これ以降は無視をします。 ということで、番目の数字が何回足されるか、を調べます。 …

CODE FESTIVAL 2018 qual A C - 半分

問題 提出コード 解法 動的計画法で答えを求めていくことを考えていきます。 まずは特徴についてです。 この問題では、0がとても重要なものになっています。 数列に0が存在していた場合、0は何回2で割っても0になるので、この部分を利用して与えられたの調整…

ABC110 D - Factorization

問題 提出コード 解法 まずは素因数分解をし、それぞれの素因数についていくつ使われているかをカウントします。 こちらの記事と似たようなことをします。 ~までを全探索し、がの約数である限りをで割り続け、その数をカウントしていきます。 探索後に、がま…

AOJ 3042 - Aizu Competitive Programming Camp 2018 Day 2 D Gridgedge

問題 解法 縦と横に分けて考えます。 座標aからbに移動するとき、考えられるパターンは3つあり、 そのままaからbに直接いくパターン 座標0に移動してからbにいくパターン 座標r-1(およびc-1)に移動してからbにいくパターン になります。 また、座標をワープ…

SnackDown 2016 - Coloring A Tree

問題 N-1本の辺とN個の頂点からなる連結無向グラフが与えられます。それを、ある条件を満たすようにK色以下で塗り分ける場合の数を、の余りで出力しなさい、というものです。 条件が、任意の頂点と同じ色の別の頂点は、ほかの同じ色の頂点のみをたどってそこ…

AOJ 2372 - IkaNumber

問題 提出コード 自力でなんとか解けました!時間は4時間くらいかかりました… くコ:彡 くコ:彡 くコ:彡 くコ:彡 解法 問題を読んだだけではかなり自由度が高いので、一つ一つ見ていくことにします。 まず、Taroの家の位置を固定します。 Taroの家、にんじん…

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

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

ABC105

今回もunratedでした!(結局全体でunratedになったみたいです) A - AtCoder Crackers 提出コード nがkで割り切れるとき、最大と最小が1ずれるので1を出力します。割り切れないとき、n人に均等に配ることができるので0を出力します。 トランプのカードを全員…

ABC104

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

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の長さだけループ…