問題概要 与えられるN個の点の内K個以上の点を含む長方形の面積の最小値を求める。 atcoder.jp 解法 簡単に言うと、全探索する。愚直にやるとO(N^5)となるがN<=50という制約に救われる。 しかし、最小値を更新していく系の問題なので、long long ansの初期値…

問題概要 高橋君がM個の辺を書き加えた後の根付き木のグラフが与えられるので元の根付き木を復元する。 atcoder.jp 解法 いわゆるトポロジカルソート(蟻本とか参照)をするだけ(本当か?(大体それが本質なので))。 atcoder.jp 超余談 この問題の最初の提出で、…

問題概要 N個の料理には高橋くんと青木さんが感じる美味しさが決まっている。2人とも最終的な自分の獲得した美味しさの総和-相手のそれを最大化するように料理を食べる。最終的な高橋くんの美味しさの総和-青木さんの美味しさの総和を出力する。結構な醜い闘…

問題概要 N匹の猫の自分以外の猫の被っている帽子の種類数が与えられるのでそれがあり得るか判定する。 atcoder.jp 解法 まず、与えられる数列aはsortしても解答に何ら影響を及ぼさないので以下aはsort済みであるとする。 最初に、aの最小値と最大値の差が2…

問題概要 1ヵ所に集まっているN個の襖を隙間も重複も無いように並べる。1個の襖を動かすには動かす距離をyとしてB[i]*y消費する。この時、条件を満たす並べ方にするまでの体力消費量の最小値を求める。 beta.atcoder.jp 解法 2つの数値が1つの物に与えられて…

問題概要 N個の数列AとBに対し、Aの総和と総和が等しく、且つB[i]<=C[i](0<=i<=N-1)となる数列Cを構成する時のA[i]からC[i]への書き換える個数を最小化する。 atcoder.jp 解法 まず、明らかにAの総和がBの総和よりも小さい場合、Cは総和がAと同じでなければ…

問題概要 与えられるT個の非負整数を負の整数であるB進数に変換する。 yukicoder.me 解法 正整数の進数変換と同じようなやり方で変換する。具体的には、文字列にどんどん余りを格納していく。ただ、負の整数でのmodがこの問題の要点なので(余りが負の数にな…

1個前の記事でそれっぽく解いたのの振り返りをしましたが、さすがにこんな調子で全問はできないので ・AtCoderで300点以上 ・個人的に面白いなあと思った問題 ・点がついていないor他サイトは適当(適切)に選ぶ を基本方針とします。

・問題概要 出力すべきマス目の縦、横の数及び長さNの数列Aが与えられるので、A[i](0-indexed)の要素の数だけi+1の数を使い、尚且つその数同士は全て上下左右連結になるようにマス目を構成せよ。(圧倒的まとめるのの下手さ) atcoder.jp ・解法 まず、同じ数…

3記事目ですね。あ、あけましておめでとうございます。 はじまり 突然ですが私にはTwitterのアカウントがあります。 twitter.com このアカウントで数日前、私は調子に乗ってしまいました。それがこちらのツイート。 1月5日までにこのツイートについたいいね+…