問題 提出コード ある区間を0にしつつ、うまいこと累積和を計算していきます。 今回は、DPを使って考えました。 i+1 ~ i+Kが0の区間だった場合、i+1~i+Kは無視してよく、i+Kに、iまでの累積和が存在することと同じになります。 ということで、今iについてみ…

問題 提出コード 解法 とにかく最近300点問題で割とつまづきます！！！！ C ~ D -1の数字をそれぞれ2で割っていくのでは間に合わないので、逆に140 ~ 170という区間に、2をかけていきます。 ということで、140と170に繰り返し2をかけていき、その区間と、C ~…

問題 提出コード 解法 自分が人生初のno submissionを決意した諸悪の根源(二度としません)です。 基本的には奇数番目と偶数番目に分けて、それぞれで個数の多い数字を1つずつ選べばそれが答えになります。 ただ、コーナーケースがサンプルの最後にあるような…

問題 提出コード 解法 後ろから攻めていき、最後が空文字列になるかどうかで判定します。 猫の鳴き声をCATとすると、mCATeCATw となっているはずなので、まず両端がそれぞれmおよびwになっているかどうか判定します。この時点で辻褄があっていなければ答えは…

問題 N個の都市があり、任意の頂点を2つとったときに両方の向きの有向辺が1つずつ存在します。 これを、ハミルトンパスが存在するように、全てどちらか片方のみ取り去ったときの、取り去るコストの最小値を求めなさい、というものです。 提出コード 解法 WA…

問題 提出コード 解法 考えられるパターンは2つあります。 1つは三平方の定理を使うパターン、もう1つは台形を考えるパターンです。 三平方の定理を使うパターン 出発地点を座標(0,0)として到着地点を(x,y)とすると、求める答えはx+yの最大値になります。 ま…

問題 提出コード 解法 似たような問題が有名なはずです。 今回は愚直に実装をします。 とにかく3つに分けて、その中での最大値が最悪の手数になるので、 nが1になるまで3で割り(切り上げ)続けた回数が答えになります。

問題 提出コード 解法 ある文字が最後の1文字となるには、ある文字が先頭となっている単語をすべて使い切った上で、その文字が最後の文字となっている単語にいきつくことが必要になります。 a～zまでの文字をそれぞれ頂点としたグラフを考えます。すべての単…

問題 提出コード 解法 まず、求める直線はすべて原点を通ります。ので、もともとあったドーナツは、その直線によって常に半分に切り分けられます。 ということは、1日目に食べた部分を2等分するような直線が、求める直線になります。 1日目に食べた部分は常…

問題 提出コード 解法 (先に解説を見ています) 片方のチームの人数を最速で0人にしたいので、 負けるチームはどんどん人数を減らす 勝つチームはできるだけ生き残って攻撃回数を残す というようにすればよいです。 これは、勝つチームと負けるチームの選択肢…

問題 提出コード 解法 この問題は先に解説を聞いてしまっていたので自力で答えを求めたわけではありません… 制約を見ると、A

問題 提出コード この問題、個人的にはD問題より難しかったです… 解法 Sの中から1つ文字を選択したとき、Sの中の同じ文字はすべて、置換後も同じ文字になってしまいます。そのため、S="aa"、T="bc"のようなものは答えがNoになります。 なので、Sの中である文…

問題 提出コード 解法 散らばっている情報を、まずはK×Kマスの中に押し込みます。 例えば、(x,y)がWという希望は、(x+K,y)、もしくは(x,y+K)がBという希望と同じであり、また(x+K,y+K)がWであるという希望とも同じです。 これを利用すると、白を0、黒を1と表…

問題 解法 サンプルの最後のケースで実験をすると、なんとなく見えてきます。 まず、移動の手段をすべて書くと、 01 → 10 10 → 01 10 → 11 11 → 10 の4通りしか存在しません。 そして、SとTが一致していない、一番左側の部分を一致させるには、それより右側…

問題 提出コード なんか最近すごい似た問題を見たような…(前日の練習会でこの問題を解いていました) ある頂点から、AとBが書かれている頂点どちらか片方にしかいけなくなった時点でその頂点を消してしまいます。 これを繰り返していき、頂点が残っていればYe…

問題 提出コード 数ヶ月放置してから考察しなおしたらすんなりいきました。 解説がなくてわからない問題は寝かせるのも大事だと思います。 解法 まず、サンプルケースなどを利用して手元で計算すると、 (縦における原点からの距離×縦の辺の長さ、の総和)×(横…

問題 縦と横が長さR,Cの長方形があり、それをいくつかの条件に基づいて切断し、指定された3つの面積(M,J,K)になるように分けろ、という問題です。 切断の条件は3つで、 長方形の辺と平行に切断する 一度切れ込みを入れたら、その部分は端から端まで切断する …

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

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

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

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

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

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

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

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

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

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

Water Tank | Aizu Online Judge 提出コード そのまま実装するとかなり重くなりそうなので、なにかいい手がないかを調べます。 初見で解けなかったときに、こちらのブログ( Water Tank (AOJ1133) - sigma425のブログ )に一度目を通していたため、トップダウ…

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

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