第１０回日本情報オリンピック予選 E チーズ 解説
問題文
https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_e
・盤面上のチェックポイント1~nのすべてを番号順に通過するときの移動回数の最小を求める。
・Xで記されているのは障害物で、ここを通ることはできない。
ACコード
https://atcoder.jp/contests/joi2011yo/submissions/4819003
解説
・pair型の配列を用意する。配列の添え字0にはSの座標、それ以降はチェックポイントnの座標を格納する。
・for文を回し、その中でスタートする座標と次のチェックポイントの座標を更新する。
・スタートの座標から次のチェックポイントまでの最短経路を幅優先探索により求める。
解いた感想
体感難易度:☆4
・初めて幅優先探索を使った問題を解いた(バグらせまくったため最終的にはACコードの写経に近くなってしまった)
・配列に格納される座標はx,yではなくy,xの順番になっていることに注意する。
・基本的な原理は理解できたつもりなので実装に慣れる。
ABC118 C Monsters Battle Royale 解説
問題文
・数列が与えられる。
・2つの数を選び、片方の数からもう片方の数の分引くという操作を繰り返す。
・1つだけ1以上、他は0以下になるまで操作を繰り返すものとするとき、残った1つの値の最小値はいくつになるか求める。
ACコード
解説
まずこの問題を見て同じ数を何度も引くという操作を繰り返しているので、除算や商に関係があるものを使う可能性を考えておく。その上で色々なケースを考えてみる…
たとえば {2,4}のとき、4から2を引く⇒2から2を引く操作により{2,0}、つまり2が最小。
{2,4,6},{2,4,6,8}…でも同様にやることで最小の値は2になる。全ての数がnの倍数の時の最小の値はnになると考えられる。
では{2,3,4}のときはどうなるだろうか。この場合3から2を引くことで1が最小になる。
{2,4,5}や{2,4,5,7}などでも同様のことがいえる。
このようにいろいろな場合を考えたり、入出力例の内容から推測したりすることで、答えは数列の数全てについての最大公約数になることに気付く。よってそれを実装すればよい。ユークリッドの互除法を用いる。
解いた感想
体感難易度:☆2
最大公約数になることに気付けるかどうかの問題だった。入出力例と操作を見て法則に気付けるようになる訓練を重ねていきたい。
ABC120 C Unification 解説
問題文
赤いキューブと青いキューブがいくつか縦に積まれている。赤いキューブと青いキューブが隣り合っているところを取り除くことができ、だるま落としのように取り除かれたぶん上のキューブが下のキューブへと落ちる。この時最大で何回キューブを取り除く操作ができるだろうか。
ACコード
解説
赤いキューブと青いキューブが隣り合っているならば弾き飛ばせるということは、逆に言えば赤と青のキューブが不足していれば弾き飛ばせないということである。
したがって、赤いキューブと青いキューブの総数を求め、その最小値×2回操作を行うことができる。
解いた感想
体感難易度:☆1
かんたんな考察をするだけで一瞬にして解ける問題もある。
ABC121 C Energy Drink Collector 解説
問題文
Ai円のドリンクがBi本売っているお店がN軒ある。
M本のドリンクをちょうど買うには最低何円必要かを求める。
ただし、全てのお店を回ってもドリンクが足りなくなることはない。
ACコード
解説
できるだけ少ないお金でドリンクを買うには、できるだけドリンクが安く売っている店から買い占めていけばいい。
なので、ドリンクを売っているお店を安いお店から順番に並ぶようにソートして、上から買っていくことをシュミレーションすればよい。実装にはpairを使用する。
解いた感想
体感難易度:☆1
オーバーフローにとにかく注意する。intをlong longにするだけでなく、firstなどから得られた値は一度値を別の変数に代入してから使うことで回避できるものもある。
ABC096 D Five, Five Everywhere 解説
問題文
・55555以下の素数がN個(5<=N<=55)ある。
・N個のうち、どの5つを取っても合成数(素数でない数)となり、さらにN個全ての数がそれぞれ異なる。このようなN個の素数の組み合わせを求める。
ACコード
解説
・合成数ということは、2つ以上の素数の積で表せる数ということになる。例えば、ある素数の倍数はその数自身を除いてすべて合成数になる。
・また、この数列の最小値は2+3+5+7+11 = 28となる。
・5つの素数の和を合成数にするには、5つの素数の和がある数の倍数になればいいことに気が付く。例えば、5で割って1余る素数を5つ集めれば、かならず和は5の倍数となる(=合成数となる)。これを実装すればよい。
・素数はエラトステネスの篩を実装して求める。
解いた感想
体感難易度:☆4
・気づくとスカッとする問題だった。余りをかきあつめて一つの倍数を作るイメージを使う時もあることを覚えておく。
ABC040 C 柱柱柱柱柱 解説
問題
・N本の柱が立っており、i番目の柱の高さをaiとする。
・はじめ1本目の柱にいて、その次か2つ隣の柱のいずれかに飛べる。
・このとき、2本の柱の差の絶対値の分のコストがかかる。
・コストを最小化する。
ACコード
解説
・例えば棒1~4の4本があったとして、棒1から棒4に行くための最小コストを考えてみる。棒4には、棒2から1つ飛ばしで行くか棒3から行くかの2通りの行き方がある。この2通りの行き方のうちコストが小さいものが求めるべき値になる。
・さらに、棒3に行くための最小コストは、棒1から1つ飛ばしで行くか棒2から行くかの2通りの行き方があり、そのうちコストの小さい方が求めるべき値。棒2にいくための最小コストも同様に考えていく。
・このように考えると、以下の式が浮かんでくる:
棒[n+1]に行くための最小コスト =
min(棒[n]にいくための最小コスト+n⇒n+1間のコスト,棒[n-1]にいくための最小コスト+n-1⇒n+1間のコスト)
・for文や再帰関数を用いるなどして、最小コストを1本ずつ求めていくと答えが得られる。
解いた感想
体感難易度:☆3
・dpに使う配列の要素数は少し多めにとる。
・dp[0]やdp[1]はfor文内に回さず、あらかじめ値を入れておく。
・配列の添え字を間違えないようにする。forはちゃんと0から始めたほうがバグらない
ABC116 C Grand Garden 解説
問題文
・花がN本植えられている。
・連続している好きな区間を選んで、その区間内の花の高さを+1する。
・N個の数列が与えられていて、それらは各花の目標の高さを表している。
・すべての花を目標の高さにしたい。最短何回水やりをすればいいか求める。
ACコード
解説
・この手の問題は、やることと真逆のことを考えるとうまくいくことがある。
・つまり、もともと目標の高さに生えている花に、好きな区間の花の高さを-1する枯葉剤をまくことを考える。
・最短回数を求めるので、できるだけ多くの花に枯葉剤をまいたほうがいい。しかし、すでに高さが0になっている花に枯葉剤をまいてはいけない。
⇒実際には高さを上げているので、目標の高さを超えてしまうから
・なので、基準の花(最初は左端の花)から高さを調べていって、高さが0の花が初めて出てくるまでの範囲内に枯葉剤をまいて、0が出てきたら再び基準まで戻りまた同じように枯葉剤をまく。そして、基準の花も0になったならば、その時点で一番左にある高さ1以上の花を基準にして高さを調べていくと最短で花を枯らす(実際には水をやって高さを上げる)ことができる。
解いた感想
体感難易度:☆4
・JOI予選で同じような問題に遭遇したので考察自体は楽だった。
・for文とbreak文を使うことでスマートに0になるタイミングを調べられる(0が出てきたらそこでbreak)。これはほかの問題にも応用できそうな気がした。
