Home > 一般 > 合宿2日目

合宿2日目

  • 2006-08-11 (Fri) 23:09
  • 一般

C:円周上の点を4つつないで出来る四角形の面積を最大化.

とりあえず2次オーダのアルゴリズムで実装してもらったが….対角線を一つずらしたときの残りの頂点の変更方をちゃんと理解してもらえていなかった模様.

D:最大15000個の宝物があるので定められたサイズの長方形でなるべく多くの宝物を囲め.

O(n^2) のアルゴリズムを実装して正解.y軸値ごとに宝ものリストをx軸でソートして,それを使うことで長方形の移動による囲まれた宝物数の変化をO(1)で求める形にした.とりあえず出題者の求める平衡木を利用した回答は絶対に2時間では実装できません.

E:リング状に和が1である様な数字が並んでいる.一つの数字を選んで左右の数字にその数字を足しこみ自身は符号を反転させるという操作を繰り替えすとき,すべてを正の数に出来る最小の手数を求めよ.

ここからメンバーが3人に.残りの二人に考えてもらって正しいものが出来上がる.ただ,真の正解にたどり着くには数学的に式を弄り回す必要があり… ちと時間内には無理ですよと.

F:コンビネータで書かれた式を評価するインタプリタを書け.

Haskell でパターンマッチで頑張る.簡約自体をHaskellにやらせたかったけど型の扱いが良くわからなくなり断念.とりあえず正解.

うーん,自分の書いたところは点が取れたが… 微妙な結果に.とりあえずAlgoは4人のペアプレイで2回とも勝利.

★下記に2つの英単語をスペースで区切って入力してください

Home > 一般 > 合宿2日目

Search
Feeds

Page Top