ツバサの備忘録

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

実装系

AOJ 2640 - 不審者

問題 提出コード 解法 言われた通りに実装をしましょう。 感想 最後に出力すべきものを誤読していたため、時間がかかってしまいました… 行う操作によって手数が変わるかもしれない、とdpっぽくやっていったのですが、(本来の)答えが一意に決まることに気づい…

AOJ 2152 - Restrictive Filesystem

問題 提出コード 解法 手で連結リストを作成していきます。 setで現在存在しているファイルの識別子を管理しておくことで、リストの中身を毎回書き換えずとも、削除のクエリを処理できるようにします。 あとは、リストを毎回前から探索していき、空きスペー…

AOJ 2002 - X-Ray Screening System

問題 解法 解法 まずは、それぞれの文字が、隠れている部分を含めて長方形になり得るかを調べます。そして、その後で、重なっている部分が矛盾していないかどうかのチェックをします。 ということで、まずは長方形になりうるかどうかのチェックをします。い…

AOJ 2311 - お菓子の魔女

問題 提出コード 解法 あんまり書くことはないです。 たかだか64ターン、そのときにクッキーを置く候補がたかだか64マス、 1つの候補について、置き換わるクッキーの個数や場所を調べるのに、縦横斜めの8方向を調べればよく、多くても20マス前後です。 とい…

ABC076 D - AtCoder Express

問題 提出コード 終わってから解説を見たのですが、あまりよくわかりませんでした() 解法 実装系だと思います。 まず、加速度は、常に1v/secで増加or減少させて、さっさと目標の速度に直すほうが効率がいいです。 そして、入力がすべて整数なので、この時点…

第4回 ドワンゴからの挑戦状 予選 B - 2525文字列分解

問題 提出コード 解法 シミュレーションをしていきます。 現在の文字列をSとします。その中で作成できる最長の2525文字列をSから取り除き、残った中でまた文字列を取り除き…と繰り返していきます。 最終的に、Sが空になれば完了です。 Sの文字に対し、残すか…

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

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

AOJ 2899 - 遭難

問題 提出コード 夏休みの宿題です。 この問題は、会津合宿で既読だけつけていたので、そのときにちらっと解説を聞いてしまっています。 くコ:彡 解法 解き方は2パターンあり、どちらも右手法を使用します。簡単に説明すると、迷路などで、右手を壁に当て続…

ABC112 C - Pyramid

問題 最近のC、やっぱり難しいです... 提出コード n個の情報に対して、ありうるすべてのx座標についての高さの候補を書き出す、という動作が間に合うぐらい制約が緩いので、とりあえず書き出します。これは、任意の座標とのマンハッタン距離を、現在の高さに…

AOJ 1190 - つながれた風船

問題 提出コード 二度とやりたくないです。。。 今回は諸事情でC言語となっています。 自分は高校数学がとてもできないので、今回もさまざまなサイトにお世話になりました。 四面体の体積を求める2つの公式with行列式 | 高校数学の美しい物語 ヘロンの公式…

AOJ 1249 - Make a Sequence

問題 立体的な五目並べのゲームをシミュレーションして、先手と後手のどちらがどのタイミングで勝利したか判定してください、というものです(引き分けも存在します)。 提出コード 解法 本当にバグらせないように愚直に実装するだけです… まずは3次元配列を用…

AOJ 2890 - ピボット (Pivots)

問題 提出コード 解法 双方向リストを作成します。 すべての数字について、1つ前と1つ後の数字を記録しておき(先頭、もしくは最後尾の数字だったら-1などをいれておきます)、その上でリストの先頭と最後の数字を何かしらの変数に記録しておきます。 そうした…

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

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

Benelux Algorithm Programming Contest 2016 B Battle Simulation

問題 敵が3つの技をうってくるので、それに対応したコマンドをこちらが入力してください、という問題です。 RにはS、BにはK、LにはHを出力します。 基本的に、1対1でコマンドが対応していますが、それとは別に、 3つすべて違う技を連続してうってきた場合の…

AOJ 2372 - IkaNumber

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

ABC109 D - Make Them Even

D - Make Them Even 実装の難易度もみつつ、実装方法を選択できるようにしたいですね。明らかに効率わるいけどまぁいけるでしょう、と思っていたのですが明らかに無謀でした... 提出コード1 提出コード2 もちろんどっちも時間外です! 提出コード1は、コンテ…

ABC013 D - 阿弥陀

D - 阿弥陀 提出コード こういう系の問題は思いつかなければとにかく自作のケースでもテストケースでもいいので実験をしてみるのが一番かなと思っています。 ということでサンプル1および2で実験をしてみると、 左から2番目以外の縦線は、あみだくじをどんど…

ABC001 C - 風力観測,D - 感雨時刻の整理

バチャコンで解いたのでC問題とD問題についてのメモを。 C - 風力観測 提出コード 素直に実装しました(の、つもりです)。方位と風力それぞれの最大値を配列にメモし、それを超えているかどうかをループなりなんなりで調べていけばいいです。 量は多いですが…

ABC104

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

Mujin Programming Challenge 2018

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

AOJ 1133 - Water Tank

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

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

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