研究や趣味やらあれこれ

日々のあれこれをあれ

yukicoder No.4 おもりと天秤

さてNo4

 

それぞれ重さのわかるおもりN個があり、それらすべてを天秤にのせたときうまく水平にできるおもりの置き方があるかどうか

 

github.com

 

はいWA

 

重い順に天秤が軽い方へ載せていったけど…これだと

 

Left{10, 3, 3, 3} Right{9, 5, 5}

 

みたいとき見つけられてなかった

 

あとからだと気づくんだけどね笑

 

 

こういう問題ってシミュレートして結果うまくいった、いかなかったっていう方法はだめなんだなと気づいた

 

素因数ゲームのときもそうだったけど、答えを置き換えなきゃ…

 

今回は、

両方のおもさがおなじになる割当があればおっけー

全体の半分の重さを作ることのできる割当があればおっけー!

 

 

github.com

 

TLE…だと?

 

テストケースコピってローカルで試してみたけどなぜかchallenge8だけ実行が終了しない…

 

そもそも無限ループになるような書き方してないのになぁ…

 

やっぱりなれない再帰を使うとうまくいかない

 

 

先輩に相談してみたところ、メモ化再帰ならうまくいくのでは、とのこと

 

…が、ダメ!!

 

そもそもの無限ループっぽい

 

悔しいけどカンニング

 

やっぱりDPなのかぁ。DP大人気!考えは良かったっぽい

 

わかってきたのは、ある答えを追い求めるよりも、考えうる答えをリスト化した後に答えがあるかを調べるのがいいのかな?

 

github.com

 

ようやくAC

 

 

 

研究も忙しくなってきたし、5までやってこっちは一段落しよう