https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_e 解説 https://atcoder.jp/contests/joi2017yo/submissions/8141535 まず、順当に考えると、座標を全探索して、シミュレーションをして、その座標が尾根であるかを判定する。 どのようにシミュレー…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_a 解説 https://atcoder.jp/contests/joi2017yo/submissions/8138403 場合分けをする。 Aが凍っている場合は解凍するまでの時間を追加で計算する。 あとは、凍っていないときにかかる時間を追加で計…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_b 解説 https://atcoder.jp/contests/joi2017yo/submissions/8138857 N≦A[i]であれば、当たりとなり、当たりとなるようにM-1個選んでいく。 どれを当たりカードとすべきか考えたときになるべく、A[i]…

https://atcoder.jp/contests/abc144/tasks/abc144_f 前提知識 期待値DP 解説 https://atcoder.jp/contests/abc144/submissions/8180528 グラフ全体はDAGになっているので、期待値DPをすることで答えが求まる。 まずは、通路を塞がないパターンを考えてみよ…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_f 解説 https://atcoder.jp/contests/joi2017yo/submissions/8142007 パット見てダイクストラ感はある。 状態を考えると、(どの部屋にいるか, 寒すぎる・暑すぎるのどっちが最後か, 寒すぎる・暑すぎ…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_e 解説 https://atcoder.jp/contests/joi2017yo/submissions/8141535 まず、順当に考えると、座標を全探索して、シミュレーションをして、その座標が尾根であるかを判定する。 どのようにシミュレー…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_d 解説 https://atcoder.jp/contests/joi2017yo/submissions/8140685 何から始めようかという感じになるかもしれないが、M≦20というところがまずはヒントになりそうだ。 種類について何かうまくやる…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_a 解説 https://atcoder.jp/contests/joi2017yo/submissions/8138403 場合分けをする。 Aが凍っている場合は解凍するまでの時間を追加で計算する。 あとは、凍っていないときにかかる時間を追加で計…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_b 解説 https://atcoder.jp/contests/joi2017yo/submissions/8138857 N≦A[i]であれば、当たりとなり、当たりとなるようにM-1個選んでいく。 どれを当たりカードとすべきか考えたときになるべく、A[i]…

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_c 解説 https://atcoder.jp/contests/joi2017yo/submissions/8139896 重複なく数えるために、かぶらないような特徴を見つけることが大切である。 今回で言えば、休憩スペースの左上端とする座標につ…

https://atcoder.jp/contests/abc144/tasks/abc144_e 前提知識 二分探索 解説 https://atcoder.jp/contests/abc144/submissions/8164566 まず、最大値の最小化ということで二分探索かというところ。 最大値が決まっていれば、各メンバーについて何回修行が必…

https://atcoder.jp/contests/abc144/tasks/abc144_c 解説 https://atcoder.jp/contests/abc144/submissions/8157943 まず、制約を見ると、掛け算表を作るのは現実的ではない。 Nが書かれているマスはどんなマスだろうと考えたときに、ij=Nを満たすマスであ…

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_a 解説 https://atcoder.jp/contests/joi2016yo/submissions/8142856 物理、科学、生物、地学から点数が高いものを3つ選んで総和を取るが、 これは、「(総和)-4つのmin」と実は等しい。 こっちのほう…

https://atcoder.jp/contests/abc144/tasks/abc144_d 解説 https://atcoder.jp/contests/abc144/submissions/8169237 数学的な問題のようだ。 0°の状態から傾けていくと、水の形は最初長方形だが、台形の柱となり、三角柱となりと遷移する。 三角柱になる前…

https://atcoder.jp/contests/abc144/tasks/abc144_a 解説 https://atcoder.jp/contests/abc144/submissions/8153919 A,Bのどちらかが10以上なら計算できないので-1 そうでないならできるので、A*Bを答える。 int A, B; //---------------------------------…

https://atcoder.jp/contests/abc144/tasks/abc144_b 解説 https://atcoder.jp/contests/abc144/submissions/8155035 2つの整数の積として表現できるかということなので、その2つの整数を全探索する。 それぞれ9種類なので、全体で81通りなので、間に合う。 …

https://yukicoder.me/problems/no/919 前提知識 Wavelet Matrix 解説 https://yukicoder.me/submissions/393919 何から考えたものかという感じだが、Kを全探索しよう。 あるKについて、全て左端からK人グループを作っていくと、N/K回操作を行うことになる。…

https://yukicoder.me/problems/no/918 前提知識 トポロジカルソート 解説 https://yukicoder.me/submissions/393911 Eのお絵かきのようす pic.twitter.com/oeQdMigeea— satanic@競プロ (@satanic0258) October 25, 2019 天才だ…わかり易すぎる どう手をつけ…

https://yukicoder.me/problems/no/917 前提知識 動的計画法 解説 https://yukicoder.me/submissions/393368 制約が少し特殊っぽい。 よくある方針として、全通りからgcdが1とならないものを引く方針で考える？ 包除原理な感じもする。 いや、1つ使う要素を…

https://yukicoder.me/problems/no/915 解説 https://yukicoder.me/submissions/393231 よーく見ると、C進数っぽく見える。 なので、C進数っぽく考えて最小コストを作ろう。 と思ったら合わない！ 最後の12 2 3は(2 + 2) * 3の3手が最短。 ★2だしなぁと思っ…

https://yukicoder.me/problems/no/916 解説 https://yukicoder.me/submissions/393553 dがとても小さいので、深さ起点で考えれば良さそうな感じがする。 lが書き込まれる頂点の深さ、rが書き込まれる頂点の深さ、その2つのlcaの深さを全探索して、組み合わ…

https://yukicoder.me/problems/no/914 前提知識 動的計画法(yes/no) 解説 https://yukicoder.me/submissions/393060 やりすぎ感があるが、DPしよう。 dp[i][k] := 国iまでお土産を買っていて、残りの金額がkである場合があるか int N, M, K, A[10][10]; boo…

復習するのにむちゃくちゃ時間かかった。途中で力尽きた。 Option-Cmd-U ソースコードを見ると、file_get_contentsが使われていて、SSRFで攻撃しようという問題 SSRFの対策として「スキーム（プロトコル）チェック」「ホスト名部分のチェック」がある 参考 …

復習したので、まとめた。 CTFの復習をすると毎回学びがあるので、面白い。 coffee_break 解法 flagを「独自の暗号化→AES→Base64」したものが与えられるので、デコードする Base64はやるだけ AESもキーはわかっているのでやるだけ 独自の暗号化に対して頑張…

https://atcoder.jp/contests/abc143/tasks/abc143_f 前提知識 調和級数計算量 解説 https://atcoder.jp/contests/abc143/submissions/8049281 Kと答えansが固定されているときに何が起こるかを考える。 ansが固定されていると、ある種類の数は最大ans回しか…

https://atcoder.jp/contests/abc143/tasks/abc143_c 解説 https://atcoder.jp/contests/abc143/submissions/8036277 連続する同じ色（文字）を1つにまとめると何グループできるかという問題。 ランレングス表現というのがある。 これは連続してどれだけの文…

https://atcoder.jp/contests/abc143/tasks/abc143_f 前提知識 調和級数計算量 解説 https://atcoder.jp/contests/abc143/submissions/8049281 Kと答えansが固定されているときに何が起こるかを考える。 ansが固定されていると、ある種類の数は最大ans回しか…

https://atcoder.jp/contests/abc143/tasks/abc143_e 前提知識 ワーシャルフロイド 解説 https://atcoder.jp/contests/abc143/submissions/8041800 問題としては最短経路問題に似ている。 似ているが、燃料が足りなくなったらコストが1かかるという部分。 燃…

https://atcoder.jp/contests/abc143/tasks/abc143_d 前提知識 累積和 解説 https://atcoder.jp/contests/abc143/submissions/8038987 まずは全探索を考える。 a,b,cを全探索して、条件を満たすか考える。 これは組み合わせが109くらいなのでダメ。 でも、a,…

https://atcoder.jp/contests/abc143/tasks/abc143_c 解説 https://atcoder.jp/contests/abc143/submissions/8036277 連続する同じ色（文字）を1つにまとめると何グループできるかという問題。 ランレングス表現というのがある。 これは連続してどれだけの文…