microbeの活動日記

プログラミングコンテストとかいろいろ

日本情報オリンピック2017/2018 予選参加記

本選参加有資格者として参加しました.今年が最後のJOI予選になります.(高校から存在を知った人にはチャンスが2年しか残されてないの罠じゃないですか)

この記事は熊本高専Advent Calendar 11日目の記事も兼ねています.

 

結果

A,B,C,Eの4完 + D部分点で410点でした.3完で終わると思っていたので4完出来てうれしかったです.

 

解説

1問目 鉛筆(Pencils)

問題:
鉛筆をN本以上買うときにA本でB円のセットとC本でD円のセットのどちらかのセットのみをいくつか購入するときの必要な金額の最小値を求める.

方針:
やる
問題文をよく読むとどちらか一方のセットしか買うことができないことに注意する.

gist4cc34e3387c4d0dbae738baa0e552aa6

 

2問目 双六(Sugoroku)

問題:
スタートとゴールを除いて1と0から構成されるN個のマスがあるので,1のマスを踏むことなくゴール出来るサイコロのうち最も面の数が少ないサイコロを求める.

方針:
考察するのが面倒だったので全探索した.
面の数が小さいサイコロから見ていき,出る可能性のある面をすべて再帰で求めていきゴール出来たらそれが答え .計算量が怖いので1を踏んだらそれ以上は枝刈りした.

gist60247aaaa2a52c1e59dfdb998382e5aa

あとから考えたら1が最多くも連続している箇所さえ超えられればいいので最も多く1が連続している個数+1で求まると気付いた.

 

3問目 幹線道路(Trunk Road)

問題:

南北にのびるW本の道路と東西に延びるH本の道路があって各交差点に人が住んでいる.南北,東西にのびる道路のうちそれぞれ1本の計2本を幹線道路とするとき,各交差点から最も近い幹線道路までの距離の総和の最小値を求める.

方針:
どれを幹線道路にするかを決めて各交差点からの距離*各交差点に住む人数をすべての組み合わせにおいて全探索する.O(H^2 W^2)

gistdb0f1ff0fa9465a8fff11b23bf6a3c95

 

4問目 水ようかん(Mizuyokan)

すぐにDPだと察したので部分点(10点)だけとって逃げました.予選終わってから各プロが話してるの見て解いた.

問題:
N本の切れ目がある水ようかんをどこかの切れ目でいくつかに切った時の長さ最大のピースと最小ピースの長さの差の最小値を求める.

方針:
dp[i][j] := i本の切れ目までの切り方を確定し,長さ最大のピースがjであるときのこれまでの最小のピースの最大値.
Lの累積和をとっておくと切った区間の長さをO(1)で求められるので計算量が減る.別にしなくても十分通るだろうけど.

gist91fce8a135515b29a854b7616cc02090

 

5問目 森林伐採(Deforestation)

何とか時間内にACして100点.

問題:
H*Wのマスで森林が構成されていて木が生えていないマスのみ1マス移動するごとに1分で移動でき,木が生えているマスはそのマスに隣接したマスから1分かけて1本切ることができる.北西から南東まで移動できるようになるまでにかかる時間の最小値を求める.ただし,木を1本切るたびに北西まで1度戻らなければならない.

方針:
問題見た瞬間に最短経路問題に帰着できることに気づき,拡張Dijkstraっぽいことをする.
北西から(i,j)までの最小時間とそこまでに行くことができる最小のマス数を持たせておく.すると1本木を切って北西に持って帰るまでの時間も簡単に計算できる.
グラフを構成してもいいけどグリッドでそのままやったほうが考えるのも実装も楽そう.楽しかった.

gistce24420dd3dc1e39657bbc53c74eb421

 

6問目 L番目のK番目の数(LthKthNumber)

部分点も取れなかった

問題:
横一列にそれぞれ数が書かれたN枚のカードが並べられており,連続するK枚以上のカードの列すべてに対して次の操作を行う

  • 選んだカードを,書かれている整数が小さい順に左から並べる.
  • 並べたカードのうち,左から K 番目のカードに書かれた整数を紙に書き出す.
  • 選んだカードを,すべて元の位置に戻す.

これから書き出された整数を昇順に並べた時,L番目の数を求める.

方針:
わかんないや!(放棄)
プロたちによると二分探索でうまくやるといけるらしい.

 

感想

最初にも書いてますが,3完で終わると思ってましたが4完出来てうれしかったです.ただ問題の雰囲気が今までと少し違って感じたので少し戸惑いました.難易度的には僕の感覚では全然わからないですが5問目が楽しかったです.いい加減DP問題を本番中に解けるようになりたいなあ...
ボーダーもさまざまな情報が飛び交ってますが全然予想できなくて怖いですね.400以上は確定と願いたいんですが1度だけボーダー420の年があるので余計怖い.頼むから通っててくれ.

 

余談ですが景気付けにHHKBを購入しました.おかげで気分が高揚してます.

 

 

 

追記(2017/12/14)

Aランク通過してました.