ツバサの備忘録

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

コーナーケース

AOJ 0570 - ジグザグ数 (Zig-Zag Numbers)

問題 提出コード 解法 以下のジグザグ数の個数から、以下のジグザグ数の個数を引くと答えになるので、あとは以下のジグザグ数の個数を求める方法がわかればよいです。 桁が明らかに大きいので桁DPをしていきます。 について、 : 今見ている桁の番号 : 以下が…

AOJ 2933 - 矢 / Arrow (RUPC2019 Day3 D)

問題 提出コード 解法 簡単のため、にも送風機があるとしてよいです。 矢の長さがのときの損失回数がわかっていれば、各クエリに対して二分探索をして答えを求めることができます。 ということで、長さがのときの損失回数を頑張って求めます。 送風機と送風…

ABC023 C - 収集王

問題 提出コード 解法 まずは行目を選択すると固定して考えてみることにします。 行目を選択した場合にアメが個得られるとします。 同様に、列目を選択した場合に個得られるとします。 この時、個のアメを得るには、を満たすものならばいいように見えるかも…

ABC074 C - Sugar Water

問題 提出コード 解法 全探索が間に合わないので、ある1箇所だけを探索せずに計算でぱっと求めるパターンです。 操作1~3を探索し、操作4はある1~3のパターンに対する最善手を計算によって求めます。 操作1をx回、2をy回、3をz回行ったとします。 このとき、…

ABC061 D - Score Attack

問題 提出コード1 提出コード2 提出コード1は愚直にメモ化再帰をしたものです。実装に2時間以上かかっているのでお話にならないです… 提出コード2は解説PDFと同じものになります。ベルマンフォード法を使ったことがなかったので実装しました。 解法 提出コー…

AOJ 3043 - Donut Hole

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

ARC102 C - Triangular Relationship

ARC初参加でした。 C - Triangular Relationship 提出コード ガッチガチの考察系ですね。 条件を満たすa,b,cの作り方として、ぱっと思いつくのが、 a,b,cのすべてがの倍数である というパターンです。 の倍数の個数は、 (切り捨て)で求めることができ、a,b,c…

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

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

ABC101

最近忙しいですがICPCも近いので少しでもプログラミングに触っていたいですね。 A - Eating Symbols Easy 提出コード 0からスタートして、+が出現したら1をたし、-が出現したら1を引いていきます。sの長さの指定をよく見ていなかったので、sの長さだけループ…