ツバサの備忘録

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

全探索

ARC087 C - Good Sequence

問題 提出コード 解法 xは数列の中にちょうどx個存在しないといけないのですが、今回数字を増やす操作ができないので、xの個数がx未満であったら、全て取り除かなければなりません。 ここで制約をみると、数列の長さは以下なので、この時点でこれを超える大…

ABC087 C - Candies

問題 提出コード 問題の制限をきちんと見れば、全探索で間に合うということがわかります。 が、特に何も考えていなかったので累積和をとりました。 この問題では、下に1回、右に回移動する操作を行うだけなので、回右に移動して下に移動、そして最後に残りの…

AOJ 2900 - 凸凹数列

問題 提出コード 解法 半分ぐらい貪欲です。 前から貪欲に、凹凸がズレていたら操作、ということを行うだけで条件を満たす数列を作成できます。 なので、最大でも数字の個数分の回数しか操作を行うことはありません。 ということで、基本的には貪欲に操作を…

AOJ 2889 - Aizu Competitive Programming Camp 2018 Day 3 A IPアドレス (Internet Protocol Address)

問題 解法 分ける点が3つのみなので、for文の3重ループで点をうつ場所を決めてから、それぞれが条件を満たしているかどうかチェックすることになります。 開始位置と終了位置、そして細かい条件のどれかでミスが生じると、デバッグが大変になるので気を付け…

AOJ 2898 - Aizu Competitive Programming Camp 2018 Day 1 C 素数

問題 解法 まずはエラトステネスの篩を適用して範囲内の素数をすべて求めます。 次にpとqのペアですが、素数同士の和が素数になるには、奇数と奇数の素数の和が偶数になる関係上、片方は2で固定されてしまいます。 ということで、片方を2に固定して、もう片…

ABC013 C - 節制

C - 節制 提出コード 数学に強い系か、実装のほうができる系によって解き方がかわる面白い問題です(これに限らず時々おこりますが...) 素直に全探索について考えてみます。 普通の食事をi日、質素な食事をj日、食べない日をk日として3重ループすると、間に合…

ABC007 C - Candles

C - Candles 提出コード 連続するk本のろうそくに火をつけたいです。 正の座標にあるろうそくと、負の座標にあるろうそく両方に火をつける場合、どちらか一方は折り返して原点に戻ってくる必要があります。 ですので、片方のろうそくをi本、もう片方はk-i本…

ABC011 D - 大ジャンプ

D - 大ジャンプ 提出コード まずはゴールにいくために最低何回、上下左右に移動するかを調べる必要があります。 この問題では上下、左右は反転しても何ら問題がないので、X、Yの入力は最初の時点で正に直してしまって問題ありません。 ということで、上下、…

ABC005 D - おいしいたこ焼きの焼き方

D - おいしいたこ焼きの焼き方 提出コード mp[i][j] = からまでの、長方形の部分の美味しさの総和 (ただし、添え字が0以下のときは0) として、入力と同時に累積和をとっていきます。 すると、ある長方形をl,r,u,d(それぞれ長方形の左、右、上、下の辺の番号)…

ABC004 C - 入れ替え,D - マーブル

C - 入れ替え 提出コード これは実験をある程度すると法則性が見えてきます。 重要なのはNを5で割った数と、そのあまりです。 この操作は5回で1セットになっていて、1セット完全に行うことで、当時先頭にいた数字が一番後ろまで移動します。 このセットが完…

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

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

ABC104

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

ICPC国内予選2018に参加してきました

というわけでとりあえず参加だけしてきました。 べるくんとやまさんの三人チームで出場しました。基本的にやまさんが考察をし、僕が実装して、困ったらべるくんがデバッグやほかの問題の実装をするというスタイルでいきました。 A問題 所得格差 提出コード …

ABC100

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

ABC099

ABC100の一歩手前になりました。自分はABC88から参加し始めたのでまだ日は浅いですが、100回になっても今まで通り頑張っていこうと思います。 さて、前回のABCですが、久しぶりにD問題が解けてかなり嬉しかったです。ただ噂のC問題が解けず全完には至ってな…

ABC098

すごく今更ながら前回のABCの結果を。 先に言ってしまうと、前々回に続き二回連続でレートが落ちました。ただ、自分の中ではいいところまでD問題が解けていたのであと一歩かなぁ、と。Aから一応見ていきたいと思います。 A - Add Sub Mul 素直にといて問題な…