cafelier@SRM

SRM (Member Pilot 1)

SRM | 11:12 |

SRM445 の成績・ソース (要ログイン) : -/-/WA? : 燃え尽きた

1000開く

• レートに影響しないβテストらしいので、点数気にせず心置きなく難しい問題に挑んでみようかと
• 『壁にでっぱりが散らばってる。長さLの腕が4本あるロボットが、3本を支えに残りの腕を動かす感じで動いていくときに、最高どのくらいの高さまで行けるか？』
  • でっぱりは16個

• 状態数 16^4 = 65536 で、それぞれからの移動先もせいぜい 16 状態
• なので、上っていける状態かどうかは普通に幅優先探索できる

• 4点選んだときに可能な状態かどうかの判定は
  • 各点から半径Lの円を描いたときに共通部分があるかどうか
  • 共通部分があるとすればどれかの円と円の交点を含むので
  • 2円の交点を式で求めてそれすべてを中心と思って半径Lの円に4点が含まれるか判定

• 最後の状態から限界まで腕を伸ばしてどの高さに行けるか、は…
  • 3点から半径Lの円を描いたときの共通部分の一番高いところ、プラスL
  • 3点から半径Lの円を描いたときの共通部分の一番高いところってどこだ
    • 交点とは限らないよなあ。
    • adaptiveなメッシュ切って近似解求めるとか。凸領域だから微妙に動かしていけばなんとかなるんじゃ
    • でもめんどい
    • 交点か、円が一番ふくらんでいるところだからつまり3点のどれかから真上にLあがった点、のどっちかが最高点のような気がする

• そう組んだ
• サンプル通った
• 出しちゃえ
• というのを1時間悩みつつ書いてました

250開く

• 間に合うかなー
• 『論文の著者名リストが与えられる。全著者のエルデシュ数を求めよう』

• 100人までって書いてあったのでWarshall-Floydぶん回す
• 書けた。あと2分！
• サンプル合わない！！
• なぜか一人だけ有限なはずのエルデシュ数が無限になってる。なんで？
• うーむーむー
• タイムアップ

感想

• 1000も落ちてた。なんだろ
  • いちおうそれっぽいとこまでは行けたので満足
• 250は名前をユニークな整数IDに変換するのに

map<string,int> id;

if(id.count(name)==0)

id[name] = id.size(); //←

• こんなコード書いててこれは鼻から悪魔がでます。バカだ…