def yasuharu519(self):

日々の妄想

みんなのプロコン 2018 C - 駆引取引 on Haskell

AtCoder で開催されてた 「みんなのプロコン 2018」で、勉強がてら Haskell で解いてみた。結果としては C問題で躓いてしまって、時間かけても解けてないのでまだまだ修行が足りない。

サンプルの問題が通せてないので、回答としては間違いだけど記録として残しておく。

問題

C: 駆引取引 - 「みんなのプロコン 2018」 | AtCoder

考察

Haskell での競技プログラミングは初めてだったので、入出力だとか 型定義をどうつくるかについては試行錯誤でなんとかやってみた。なんとなく書いた後 hlint に通すとそれっぽいサジェストももらえるし、新しい関数も知れるので便利。

問題を読んでみると

  • 高橋君は番号の若い順にしか商品を売れない
  • 一つ商品を売る度に青木君は一つ商品の販売を停止する
  • 商品を買うのは最後に一度だけ

と理解したので、

  1. 高橋くんが商品をいくつ売るかのパターンごとに得られる資金を計算
  2. 高橋くんがいくつ商品を売るかに応じて、青木くんが販売停止する商品を選択
  3. 高橋くんが商品を売る個数ごとに 2の計算と、残った商品の中で最大価値の計算

という流れで進めようとし、計算を行なった。コードはこんな感じ。

出力例4 のパターンが通らないので、コード自体は間違っている。

青木君が販売停止する商品を選択する際に、 その時点で高橋君が持ってる金額以下で最大価値となる組み合わせ を計算してみたが、売る個数が多くなってくると 高橋くんがその時点で持っている金額以下 という選び方ができなくなってしまう様子。ただ、高橋くんがその時点で持っている金額以下 という制限を外してしまうと高橋君が到底買えないものを販売停止してしまい、青木君は高橋くんの結果が最小となるように動く条件を満たさなくなるように思った。

が、結果間違ってるので他の人の回答参考にどこが間違ってるか見るしかないか~~。

AtCoder しばらく見ないうちに開催されてるコンテストも増えてるみたいなので、定期的に出て頑張ってみよう 🙏