AOJ 2443 : ConvexCut

幾何

問題↓

ConvexCut | Aizu Online Judge

最遅コードを叩きだしたので上げます。

間違いなく想定解法ではありません。

問題概要

  • 凸多角形が与えられれます。
  • 凸多角形の内部にある点のうち
    そこから伸びる直線で多角形をカットした際に出来る2つの多角形の面積が等しいような点の座標を出力して下さい。
  • ない場合は"NA"
  • 頂点数 N = 50

解法

続きを読む

CODE FESTIVAL 2014 上海オープンコンテスト D : Maze

グラフ

クソ雑魚なので参加してません。

オンライン参加です。

問題↓


D: Maze - code festival 2014 上海（オープンコンテスト） | AtCoder

問題概要

  • 迷路があります。
  • ゴール２種類あります。(A,B)
  • スタートからゴールへ行く道のりは必ず最短でなければいけません。
  • 各ゴールへ行く時の道筋が被ってはいけません。
  • スタートから各ゴールへの経路を出力して下さい。
    （output は 問題を見た方が分かりやすいです。)

解法

続きを読む

AOJ 2022 : Princess, a Cryptanalyst

DP 文字列

練習で類題を解いたので解きました。

２・３年前にやって全く分からなかったけど今も解説見ないと分からなかった。

解法は同じ。

問題概要

  • N個の文字列が与えられます。( 1 <= N <= 10 )
  • N個の文字列全てを部分文字列とするような最小の文字数の文字列Sを作って下さい。
  • 文字数が同じ場合は辞書順最小の文字列を出力して下さい。

解法

続きを読む

SRM405 500 : AllCycleLengths

DP

諦めそうになった。

問題概要

  • 有向グラフが与えらます。
  • ある頂点を出発しk(k>0)回のステップで同じ頂点に戻れるならばk番目の文字は'1'、そうでなければ'0'となる文字列を求めて下さい。
  • ただし文字列は無限に長くなってしまうので循環する部分を()でくくって下さい。
  • 注意すべきは 

    A traveler starts from some city,
    つまり、各街から出発して一周するのを全ての街に対して行ったもののORを取らなければなりません。

解法

続きを読む

SRM404 500 : KSubstring

データ構造

さぼりすぎた

この調子で後、96回出来る気がしないぞ。

問題概要

  • 数列Aが面倒くさい形で与えれます。
  • s(i,k) = A[ i ] + A[ i + 1 ] + ... A[ i + k - 1 ] と定義されます。
  • abs( s(i,k) - s(j,k) ) ( j >= i+k ) の最小値とその時のkを返して下さい。
  • 複数の最小値があった場合kの最大を返して下さい。

解法

続きを読む