ツバサの備忘録

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

未分類

AGC049 B - Flip Digits

問題 提出コード 解法 できる操作が、 1 をひとつ左に動かす 連続する1 を消す のどちらかとなっています。 また、右側にある 1 が、一つ左側の 1 を追い越すことはできません(そもそも、追い越したいのであれば、左側の 1 を動かせばよいです)。 そのため、…

AOJ 2435 - Zero division checker

問題 提出コード 解法 計算結果は、いずれのタイミングでも、どのように計算しても最大で256通りです。 毎回、2つの変数を用いて演算を適用するので、通りとなります。 演算は未満であることは確実なので、十分計算が間に合います。 よって、可能性のある計…

AOJ 2299 - Tiles are Colorful

問題 提出コード 解法 まずは、それぞれの文字について、2つの座標をペアで記録しておきます。 あとは、残っている文字のペアについて、消せるかどうかを確認→消せるなら消去、を繰り返せばよいです。 文字のペアは最大でも26しかないので、この操作を26回行…

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

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

ABC128 F - Frog Jump

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

AOJ 1604 - デッドロック検出

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

AGC036 B - Do Not Duplicate

問題 提出コード 解法 同じ状況になる部分をどんどん取り除き、最終的に残る数回を愚直にシミュレーションします。 まずは、空の数列に対して番目の数字をに入れたときに、を取り除くことで再び数列が空になるタイミングはどこか、を調べます。 これは、の種…

ABC126 C - Dice and Coin

問題 提出コード 解法 サイコロの目がであったときにすぬけ君が勝つためには、を超えるまでコインの表を出し続ける必要があります。 この回数をとすると、これはがを超えるまで2倍しつつカウントしていけば求めることができます。 ということで、を出した時…

AOJ 2825 - クイズ

問題 提出コード 解法 最終問に必要な得点が最大になるとき、の中で少なくとも1人は、その人が答えることができる問題に全て答えています。 同様に、少なくとも1人は、その人しか答えられない問題以外は全て答えられません。 ということで、それぞれの人につ…

ABC120 C - Unification

問題 提出コード 解法 積まれているキューブの中に、赤と青のものが少なくとも1つずつ以上存在しているとき、必ずどこかに操作を行える部分が存在しています。 ので、結局行うことのできる操作回数は、 となるので、これを二倍したものが答えになります。 感…

ABC115 C - Christmas Eve

問題 提出コード 解法 問題の答えになるようにするには、木の高さをすべてソート昇順でソートし、連続したK本を選ぶのがよいです。 連続したk本の選び方は、N-K+1通りあるので、その全てのパターンについて、最大値から最小値を引いたものを計算し、その中の…

ABC072 D - Derangement

問題 提出コード 解法 となっている部分は、もしくはとスワップをすることで、は条件を満たすことができます。 このとき、実はスワップ先のもしくはも条件を必ず見たします。なぜなら、この数列は順列なので、だった場合は、もしくはがとなり、中身の値がの…

ABC063 D - Insertion

問題 提出コード 解法 基本的に、"("を追加するのは文頭、")"を追加するのは末尾で大丈夫です。 正しい括弧列Xと任意のYが存在したとき、 "("を追加すべきパターンは X)Y, )XY, XY) のようなパターン(最後のパターンのみ、Yも正しい括弧列という条件付き)で…

ABC062 C - Chocolate Bar

問題 提出コード これの類題的な感じですね。 解法 縦と横については、向きを入れ替えて同じことを考えればよいので、とりあえず縦と横を固定した状態で考えます。 チョコレートを3つに分けるには、まず2つに分け、そのうち片方をまた2つに分ける、というよ…

ABC061 C - Big Array

問題 提出コード 解法 入れる個数と入れる数字をセットにした状態で、入れる数字の昇順でソートします。 そして、前から入れる個数を足していき、K個になった時点で入れた数字が答えになります。

ABC059 C - Sequence

問題 提出コード 解法 一番最初を正でスタートするか、負でスタートするかの2通り試し、より良い方を答えとして出力します。 までの総和が、次になるべき符号と同じであればそのままに進みます。符号が異なっていれば、 負になるべきならば、総和が-1になる…

ABC060 C - Sentou

問題 提出コード 人目の人がボタンを押したタイミングで、まだお湯が流れていた場合は、を追加、流れていなかった場合は秒が経過しているので、を追加していきます。 これを繰り返し、最後の人が押してから流れる秒分を最後に追加すればよいです。 結局は、 …

ABC057 C - Digits in Multiplication

問題 提出コード 解法 からまで順番に調べ、その中のがで割り切れたら桁数をそれぞれ計算し、答えの更新を行います。 桁数は10で割れる回数で、0になるまで10で割っていけばよいです。 と両方について桁数を求め、そのうち大きい方がの答えになりますので、…

ABC056 C - Go Home

問題 提出コード ジャンプする時刻の最大値をとすると、から順番に1ずつ減らしてみていき(今見ている時刻を とします)、よりが小さければ時刻がのときにジャンプすることにしてからを引く、という操作を繰り返していけば、ジャンプする時刻を求めることがで…

ABC055 C - Scc Puzzle

問題 提出コード 解法 cを2つ利用してSを作成するのは、Sの在庫がなくなってからでいいです。 ので、まずはSを1つ、cを2つ使ってSccを作成します。 この方法で作れるSccの個数は、Sの個数と、cを2で割ったもののうち小さい方になります。 これが終わってなお…

ABC019 C - 高橋くんと魔法の箱

問題 提出コード 解法 ある数字について、2でi回割る、もしくはi回書けたものは必ずすべて同じ数字が出てきます。ということで、それを手っ取り早くするために、同じ数字の中で最小のものを採用して重複の無いようにカウントしていきます。 なので、方針は次…

ABC053 D - Card Eater

問題 提出コード 素直に、余分なカードを最高効率で食べていくことを考えます。 1回の操作で、確実に余分なカードを2枚減らすことができます。 余分なカードは最低でも2枚あるので、そのようなカードが2種類あれば、数字をi,j(i

ABC047 C - 一次元リバーシ / 1D Reversi

問題 提出コード 解法 片側のみに石を置いて直しても、両側から石を置いて直しても手数は特に変わらないので、片側からのみで考えていきます。 すると、左から右向きに見ていったときに、 白から黒になる、もしくは黒から白になっている境界の個数 がそのま…

ABC047 D - 高橋君と見えざる手 / An Invisible Hand

問題 提出コード デバッグ出力と一緒に答えの出力を消してしまわないように注意しましょう。 解法 高橋君が最大の利益を得るとき、売る町と買う町は1つずつで、それぞれT/2だけ買い、T/2だけ売ることになります。 売値と買値の差が一番大きい場所が、その売…

ABC113 C - ID

問題 提出コード 解法 がすべて異なるので、まずは、、の3つの情報をセットにして、で昇順にソートしていきます。 その後、ナンバーを決めていきます。 が番目であったとき、左側の0を除いた市の認識番号は、 です。 あとは、左側に0を付ければ答えとなりま…

ABC016 C - 友達の友達

問題 提出コード 解法 幅優先っぽいことをしようと思いますが、2つ先のみを見ればいいので、そのようにします。 制限もとても小さいので、割と何をしても大丈夫です。 まずは、入力をしていきます。 memo[i][j] = iとjが友達かどうか、としていき、友達なら1…

ABC042 C - こだわり者いろはちゃん / Iroha's Obsession

問題 提出コード 解法 最悪のケースは、999999みたいなパターンです。 条件を満たしているかどうか愚直に調べるには、1桁ずつ確認していくだけなので、多くても6回ほどの確認で済みます。 よって、 Nから順番に、1桁ずつ確認していって条件を満たしていなか…

AOJ 2896 - Aizu Competitive Programming Camp 2018 Day 1 A テスト

問題 解法 最終的には全員前に詰めることになっているので、前からM人分をチェックして初期状態が空の椅子をカウントすると、それが答えになります。 提出コードはこちらになります。 #include <bits/stdc++.h> using namespace std; int n, m, cnt = 0; bool a[1005] = {0}</bits/stdc++.h>…

Benelux Algorithm Programming Contest 2016 I Older Brother

問題 整数が与えられたときに、なんかしらの素数をとおいて、となるかどうかを調べろ、という問題です(は1以上です)。 解法 まずは=1の場合をコーナーケースとしてはじきます。 次に、その他の数を調べていきます。 単純に素数を1つずつみていき最後までルー…

AOJ 2700 - 空港コード

空港コード 提出コード 制限がかなり緩いので、割と何をしても間に合うと思います。 自分は、kを1から順番に増やしていき、そのたびに空港コードを新しく作成していました。 一致するものがあるかどうかはmapを利用しました。