htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Regular Contest 083 参戦記

o--- 1422 -> 1408

C - Sugar Water

結果:AC(2WA)
Submission #1598690 - AtCoder Regular Contest 083

コンテストではDPで解いたのだけど、DPを思いついてコードを書き始めるまでにすごい時間がかかってしまったのでダメ。最大F+1までのサイズのdp配列を用意して、

  • 水をA*100g追加する
  • 水をB*100g追加する
  • 砂糖をCg足しても溶け切るならばCg追加する
  • 砂糖をDg足しても溶け切るならばDg追加する

をFを超えない範囲で繰り返した。「現時点では砂糖が溶け切らないが後で水を足せば程よい濃度になる」という状態への遷移は、先に水を足して後から砂糖を足す遷移でもたどり着けるので切る。また、水も砂糖も0gはWA。これで2WAした。

実際はAもBも100g単位でFも高々3,000であるため、取りうる水の量を全列挙しその都度限界まで砂糖を足していけば良いだけであった。Pythonではitertools.productとか使えるとモテ系って感じね。

D - Restoring Road Network

結果:-

問題読んでワーシャルフロイドだなと気づいて300^3pythonでは明らかに無理だと諦めつつ別解を探しながら眺めてたのだけど、解説読んでも理解に時間がかかったのでNが少なくてもコンテスト中にACにたどり着けたかあやしい。

解くべきは2点:

  1. 与えられた表が本当に最短距離になっているか
  2. 表に書かれた最短距離を満たす範囲で最小の道の長さの総和

1はワシャフロすればいいんだけど、2はダイクストラでもかますのかしらとスットコドッコイなことを考えてた(通るわけない)。 f:id:htkb:20170917223144j:plain
こういう、迂回しても同じ距離でたどり着けますよという頂点間には辺を貼る必要がない(総和の最小を求めているため)ので、迂回路に最短距離が見つからない場合のみ辺を貼る(答えに距離を加算していく)。例では経由点が1箇所だけだけど、仮に1-2-4-3が最短距離だったとしても1-2-3ないし1-4-3で同じ距離が得られるはずなので、N回だけ回してA[i][k] + A[k][j]をチェックすればいい。ついでに、このチェックのときにA[i][j] > A[i][k]+A[k][j]なケースが見つかったならばそれはそもそもの最短距離表が間違っていることがわかる。つまり1のワシャフロは省略可能。

で、ワシャフロを省略してもi0~N-1ji+1~Nk0~Nの三重ループとなるため、(N-1)*(N-2)/2*Nで最悪1.3*10^7くらいでやっぱり絶望的なのだけれど、定数倍改善ゲームをがんばったら通った。

Submission #1604109 - AtCoder Regular Contest 083

2次元配列より1次元配列、配列より値で受けて触るほうがかなり速くなる(それはそう)。enumerateは基本だけど有効なところでピシッと使えると間違いなくモテる。