Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-24SRM340, SRM341, SRM342 (Practice)

SRM340 (Practice)

SRM340 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM340 (Practice) - hama_DU@TopCoderへの道

DP回 こういうセットばっかりだったらいいのに

問題結果ポイントその他
250ProblemsToSolveAccepted231.59DP
500CsCoursesAccepted329.54DP
1000VegetableGardenOpened0.00

SRM 340 ProblemsToSolve

|  SRM 340 ProblemsToSolve - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 340 ProblemsToSolve - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7504

  • 動的計画法
    • 座標圧縮して [現在位置][最大][最小] でDPする

続きを読む

SRM 340 CsCourses

|  SRM 340 CsCourses - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 340 CsCourses - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7505

  • 動的計画法+辞書順最小経路復元
    • 状態は [month][theoreticalValue][practicalValue]
    • 経路復元付きの場合はメモ化再帰すると楽。

続きを読む

SRM 340 VegetableGarden

|  SRM 340 VegetableGarden - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 340 VegetableGarden - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7507

  • 面白い問題。
    • グラフに帰着できるような気がするが、どうすればいいかわからない
    • 答えは必ず偶数になる?
  • あとで解く。

SRM341 (Practice)

SRM341 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM341 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250KLastNonZeroDigitsAccepted246.14実装
550LandAndSeaOpened0.00実装、BFS
1000ValidPlatesOpened0.00

SRM 341 ValidPlates

|  SRM 341 ValidPlates - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 341 ValidPlates - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6876

  • DP
    • 行列累乗すればいい気がする
  • まだ解いてない

SRM342 (Practice)

SRM342 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM342 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250TagalogDictionaryAccepted181.71実装、ソート
500ReverseResourcesOpened0.00DP
1000DrivingAroundTLE0.00グラフ

SRM 342 TagalogDictionary

|  SRM 342 TagalogDictionary - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 342 TagalogDictionary - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7411

  • やるだけ。
    • Comparatorの中に変数を仕込む方法が分からなかったので仕方なくバブルソートでやった

続きを読む

SRM 342 ReverseResources

|  SRM 342 ReverseResources - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 342 ReverseResources - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7415

  • 動的計画法
    • 典型っぽいのでこのぐらいはサクッと解けるようになりたい

続きを読む

SRM 342 DrivingAround

|  SRM 342 DrivingAround - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 342 DrivingAround - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7412

  • 既視感のある問題。
  • だが、この問題は辺に重みがついているので違う問題になっている
    • 待てよ、重みが w >= 2 の時はダミーの頂点を w-1 個はさんでやることで重みなしのグラフにできるのでは
    • これで簡易版「いけるかな?」に帰着できた
  • しかし、最大でノードが 10 + 90 * 4 = 370個必要になる。
    • 相当スパースな行列になるが、累乗すると 370^3 のコストが重くのしかかる
    • しかも、「いけるかな」とは違い場合の数を求めなきゃなので、MOD操作のコストがものすごく重い。
      • YES/NO 問題だったらまだ救いはあったが・・・
  • この考え方ではダメのようだ。
    • 一応、書いて出してみるか・・・問題の条件を見落としてるかもしれないし。
      • 案の定TLE。dsyn-

その後

  • ノード数は実は50個用意すれば十分
    • あるノードから他のノードに向かう途中のダミーノードは共通にして使いまわせるため

続きを読む

2012-04-21SRM343, SRM344 (Practice)

SRM343 (Practice)

SRM343 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM343 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250CDPlayerAccepted228.59実装
500MoneyGameWA0.00ゲーム
1000RefactorableNumberAccepted860.09実装

SRM 343 MoneyGame

|  SRM 343 MoneyGame - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 343 MoneyGame - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6802

  • ゲーム木実装するだけかな?
  • 書いたらサンプル通ったので出した
    • 愚直にやると計算量的に厳しいと思ったのでポットから取り出すコインの選択を貪欲法でやった
  • WA

その後

  • 愚直にやっても充分間に合った。
    • O(12^6) = 2Mちょい

続きを読む

SRM 343 RefactorableNumber

|  SRM 343 RefactorableNumber - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 343 RefactorableNumber - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6784

  • これ(難易度的に)250だろ・・・
  • 当時の本番後どんな反応だったかは想像に難くない

続きを読む

SRM344 (Practice)

SRM344 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM344 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250VolleyballTournamentAccepted192.23全探索
500QuantumAlchemyTLE0.00探索
1000FairTournamentOpened0.00動的計画法

SRM 344 VolleyballTournament

|  SRM 344 VolleyballTournament - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 344 VolleyballTournament - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7252

  • 0点、1点、2点を取った試合数を全探索する。

SRM 344 QuantumAlchemy

|  SRM 344 QuantumAlchemy - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 344 QuantumAlchemy - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7540
  • 逆から考えていけばいいのではと思った
    • つまり、'X' だけの状態から反応を逆向きにして戻していく
  • 終了条件は、文字列が initial の subset になること。
  • TLEが不安だが他に思いつかないのでこのまま出してしまおう。

後で

  • wataさんのコード見た
    • 基本的な考え方は同じっぽい・・・
    • よく見ると、一度展開した文字は再度展開しないようにしてる
      • 無限に展開されるのを防ぐためか
    • また、状態を文字列そのものではなく残り必要な文字数で管理している
      • うまいなぁ

続きを読む

2012-04-20SRM345 (Practice)

マラソンマッチが終わったので練習再開。

問題結果ポイントその他
250PathfindingAccepted134.08場合分け
500StoneGameAccepted398.14数学
1000ByteLandOpened0.00グラフ

SRM 345 Pathfinding

|  SRM 345 Pathfinding - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 345 Pathfinding - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7649

  • 探索で解こうと思った
    • 無理だった
  • 結局場合分けした。
    • xとyは対称性を持つので片方が負の場合だけを考えれば良い
  • 解法の検討に色々迷走したので時間がかかってしまった。

続きを読む

SRM 345 StoneGame

|  SRM 345 StoneGame - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 345 StoneGame - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7238

  • 手で実験してみる
    • これ、総取りできるか、全部相手に取られるかのどちらかなのでは
      • 石の総数の偶奇で決まる気がする(奇数なら総取りできる)
  • でも、石の数が1の場合はまずそちらを取った方がいい
    • 複数ある場合は当然価値が高いものを取った方がいい
    • 相手も当然価値が高いものを優先して取るはず
  • 石の数が1の山をすべて取り終えたときゲームが始まる
  • 書いたらサンプル合った。
    • 証明はできないが正しい気がするのでそのまま出した

続きを読む

SRM 345 ByteLand

|  SRM 345 ByteLand - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 345 ByteLand - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7239

  • 貪欲で行ける気がするが、証明ができない
    • 距離を決めうちしてDPする系なのかな?
  • 後で解く

2012-04-10SRM346 (Practice)

三日ぐらい前にやった。

500が難しい回。1000に逃げたのは正解だと思ったがWAを食らう。

問題結果ポイントその他
250CommonMultiplesAccepted236.48最小公倍数
500HeightRoundOpened0.00貪欲法
1000MeteoritesWA0.00幾何

SRM 346 HeightRound

|  SRM 346 HeightRound - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 346 HeightRound - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7682

  • 貪欲法。難しい
    • editorialや他の人のコードを見ながら書いた。
    • 要復習

続きを読む

SRM 346 Meteorites

|  SRM 346 Meteorites - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 346 Meteorites - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7683

  • 各隕石ごとに他の隕石で覆われている部分をラジアンの区間で持つ。
    • 角度の計算はatan2を使うと場合分けしなくて済み楽。
  • 隕石が他の隕石に完全に含まれている場合に注意する

続きを読む

2012-04-05SRM347 (Practice)

数学回。

問題結果ポイントその他
250AircraftOpened0.00数学
450FlightSchedulerOpened0.00探索
1000MetroNetworkUnopened0.00???

SRM 347 Aircraft

|  SRM 347 Aircraft - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 347 Aircraft - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7741

  • ふつーに三分探索しようとした
    • 式が間違ってて答えが合わなかった。ひどい
  • editorial見ると二次方程式を解くのがいいらしい。なんと

続きを読む

SRM 347 FlightScheduler

|  SRM 347 FlightScheduler - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 347 FlightScheduler - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7584

  • 問題文が正しく読めず、editorialを読むまで意味不明だった
  • 式変形して1回のフライトでR飛ぶときの必要燃料を求める。
    • n回に分けて飛行する場合の必要燃料を考えた時最適な回数を三分探索で探す。

続きを読む

2012-04-04SRM349 (Practice)

問題結果ポイントその他
250LostParenthesesAccepted208.64DP
500RailwayTicketsOpened0.00最小費用流
1000NormalizingTreesUnopened0.00見てない

SRM 348 LostParentheses

|  SRM 348 LostParentheses - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 348 LostParentheses - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7754

  • Greedyなアルゴリズムなんて思いつかないので、区間DPをする

続きを読む

SRM 348 RailwayTickets

|  SRM 348 RailwayTickets - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 348 RailwayTickets - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7760

  • 蟻本第二版p220と同じ問題。
    • そのままやるとTLEするが、座標圧縮するとうまくいく。

続きを読む

SRM 348 NormalizingTrees

|  SRM 348 NormalizingTrees - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 348 NormalizingTrees - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7751


問題結果ポイントその他
250RadarFinderAccepted225.03幾何、場合分け
500DiceGamesAccepted481.35数え上げ
1000LastMarbleWA0.00ゲーム

SRM 349 RadarFinder

|  SRM 349 RadarFinder - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 349 RadarFinder - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7766

  • 場合分け。
    • 一方の円が他方の円を完全に含む場合などに注意する
    • オーバーフローにも注意する
      • あらかじめ引数をlongに再代入しておく

続きを読む

SRM 349 DiceGames

|  SRM 349 DiceGames - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 349 DiceGames - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7601

  • ソートして数え上げるだけ
    • メモ化再帰を実装した

続きを読む

SRM 349 LastMarble

|  SRM 349 LastMarble - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 349 LastMarble - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6067

  • ゲーム木実装するだけ?
    • 書いてみた。最後以外サンプル通った。
    • 最後以外、removed = 0 だった
  • あとは remove >= 1 の場合を考慮するだけ。
    • 100C50ぐらいの値が必要になるような・・・
    • 工夫することで組み合わせ計算を省略できた
  • サンプル合った。提出
  • WA。何故・・・
    • ランダムに取り除く時、その結果は観測できないらしい
    • そもそも考え方が間違っていた・・・

続きを読む

2012-04-03SRM350, SRM351, SRM352 (Practice)

SRM350 (Practice)

SRM350 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM350 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250SumsOfPerfectPowersAccepted215.74列挙して探索
500StarsInGraphsWA0.00グラフ
1000PlaneDivisionOpened0.00幾何

SRM 350 SumsOfPerfectPowers

|  SRM 350 SumsOfPerfectPowers - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 350 SumsOfPerfectPowers - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7613

  • 求めるべき数の中で、m >= 2 で a^m となってる数はそんなに多くない。
    • なので、全て列挙し、2つの数の組み合わせを全部試せる。

続きを読む

SRM 350 StarsInGraphs

|  SRM 350 StarsInGraphs - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 350 StarsInGraphs - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7593

  • まず、全頂点のstar numberを求める。
  • 「今どこにいるか」を状態としたダイクストラをする
    • 経由頂点数が100を超えるようだったらループしてるので、-1を返す。
  • 練習ではDPの更新部分でバグっててWAした。

続きを読む

SRM 350 PlaneDivision

|  SRM 350 PlaneDivision - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 350 PlaneDivision - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7788

  • 幾何。典型問題っぽい?
  • あとでやろう。

SRM351 (Practice)

SRM351 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM351 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250CoinsExchangeAccepted185.39貪欲法
500BoxesArrangementAccepted317.47DP
1000NewMagicSquareUnopened0.00最大流

SRM 351 CoinsExchange

|  SRM 351 CoinsExchange - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 351 CoinsExchange - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7773

  • 貪欲法
    • 足りないGold、Silver、Bronzeの順に両替を行いながら埋め合わせる
  • 通ったのがいいがきれいな実装ができなかったので後で確認する。

続きを読む

SRM 351 BoxesArrangement

|  SRM 351 BoxesArrangement - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 351 BoxesArrangement - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7772

  • 要は、A,B,Cをルールに則り並び替えた時元の位置と一致する最大数が分かればいい
    • 普通に数を並べるDPで書ける。
    • [Aを使った数][Bを使った数][Cを使った数][直前の文字][直前の文字が何個連続したか]
      • 多めに見積もって 51*51*51*4*4 = 2M程度。
  • 練習ではメモ化再帰で書こうとした
    • (文字数) >= 30 程度になると間に合わなくなったのでループDPに書き換え。

続きを読む

SRM 351 NewMagicSquare

|  SRM 351 NewMagicSquare - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 351 NewMagicSquare - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7247

  • 見てない

後で

  • やってみた
    • これただの最大流だ
  • 辞書順最小に数字を当てはめながら最大流するだけ。

続きを読む

SRM352 (Practice)

SRM352 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM352 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250NumberofFiboCallsRE0.00DP
500FibonacciKnapsackOpened0.00DP、枝刈り
1000PaperRacingUnopened0.00見てない

SRM 352 NumberofFiboCalls

|  SRM 352 NumberofFiboCalls - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 352 NumberofFiboCalls - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=2292

  • やるだけ
    • 練習では配列のサイズ指定ミスでREをくらう

続きを読む

2012-04-02SRM353, SRM354 (Practice)

SRM353 (Practice)

SRM353 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM353 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250GlossaryAccepted180.29実装
500PlatformJumperAccepted373.88グラフ
1000FurnitureRobberyOpened0.00???

SRM 353 Glossary

|  SRM 353 Glossary - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 353 Glossary - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7838

  • 問題文の通りに正しく実装する。
    • 文字列の比較はcase insensitiveなのに注意(サンプルにあって助かった)

続きを読む

SRM 353 PlatformJumper

|  SRM 353 PlatformJumper - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 353 PlatformJumper - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7847

  • ある台からある台に飛び降り可能な時、元の台に戻ることはできないはず。
    • なので、状態として「今どこにいるか」だけ分かっていればよい
  • グラフにしてダイクストラ。

続きを読む

SRM354 (Practice)

SRM354 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM354 (Practice) - hama_DU@TopCoderへの道

3つとも探索(DP)という珍しい回。

問題結果ポイントその他
300DateFormatAccepted172.73DP
500RemissiveSwapsAccepted452.96DP
900RooksPlacementOpened0.00DP

SRM 354 DateFormat

|  SRM 354 DateFormat - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 354 DateFormat - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7654

  • 日付を4桁の数にエンコーディング
  • DPと経路復元(めんどい)をするだけ。
    • 状態は [今考えてる日付の位置][直前の日付]
      • 状態数は 2500 * 1300 ≒ 50^4 / 2 としてまぁ大丈夫でしょう。
      • そもそも使わない日付もあるんだし。(1050とか)
  • 月ごとの最大日付のインデックス指定をミスってハマる

続きを読む

SRM 354 RemissiveSwaps

|  SRM 354 RemissiveSwaps - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 354 RemissiveSwaps - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7248

  • 素直にDPするだけ。
    • 3問の中で一番簡単かも
    • Math.pow(10, n)とかしてると定数倍に重く効いてくるので配列に持たせておくとよい

続きを読む

SRM 354 RooksPlacement

|  SRM 354 RooksPlacement - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 354 RooksPlacement - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7658

  • シンプルなDPのはずだがなかなか答えが合わず。
    • 考えてる状態数が足りないことに時間切れ直前になって気づいた
  • 通した。
    • 考察が足りなかった

続きを読む

2012-04-01SRM355 (Practice)

全体的に難しい回。

問題結果ポイントその他
300MixingLiquidsWA0.00貪欲法
600TetrahedronOpened0.00幾何
900BeautifulHexagonalTilingsOpened0.00ブルートフォース

SRM 355 MixingLiquids

|  SRM 355 MixingLiquids - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 355 MixingLiquids - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7886

  • 一度すべての溶液を混ぜる。
    • 濃度がぴったりだったら、合計をそのまま返す。
    • 濃度が薄すぎたら、一番薄いものから減らしていく。
    • 濃度が濃すぎたら、一番濃いものから減らしていく。

続きを読む

SRM 355 Tetrahedron

|  SRM 355 Tetrahedron - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 355 Tetrahedron - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7539

  • 幾何。点をA, B, C, Dと置く
    • まずどれかの3点について、三角形が作れないなら "NO"
    • それ以外の場合、A(0, 0) B(dist[A][B], 0) として、C, Dの座標を求める
      • このとき余弦定理を使うと楽に求められる
    • CDの最小最大を求め、dist[C][D]と比べて検証する

続きを読む

SRM 355 BeautifulHexagonalTilings

|  SRM 355 BeautifulHexagonalTilings - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 355 BeautifulHexagonalTilings - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7761

  • editorial曰くバックトラックで解けるらしい
    • あとでやる