Codeforces Beta Round #13

Codeforces

CodeforcesにICPCを控えた研究室の後輩たちが参戦。負けじと頑張ってみました。

  • -

A. Numbers

問題：数字Aを2進からA-1進で表した場合の各桁の数の和の平均を求める

  • やるだけ。
  • 結果は分数表示だけど，分子・分母をそれぞれ最大公約数で割れば良い。
  • やるだけと言いつつ，一瞬焦ったのでメモ。


B. Letter A

問題：与えられた3本の線分が文字"Ａ"を構成するかを判定する

  • 幾何の問題とかICPC以来解いて無い気がする・・・。
  • とりあえず，線分が"Ａ"を構成する条件をまとめると
    • 線分1と2が1点を共有し，線分3の端点はそれぞれ線分1, 2上に存在する
    • 線分1と2のなす角は0°より大きく，かつ90°を超えない
    • 線分3の短点による線分1, 2の内分比は1/4を下回らない
  • とりあえず，半年ぶりくらいにcomplexとか使う。
  • 仕様通り実装するだけなのに，いろいろミスして3WA。ちょっと泣いた。


C. Sequence

問題：与えられた数列aを非減少列にするために必要な最小の操作回数を求める

  • 操作とは1つの要素を選び，1増加させるか1減少させる事。
  • 数列の各要素の絶対値は10^9以下・・・なのでシミュレーションではなさそう。
  • というわけで、考えた結果DPを組んでみる事に。
  • 最適解では1個くらい値を動かさない要素がありそうな気がするので，
    • v[i] : 元の数列のうちi番目に小さい要素の値
    • DP(i, j) : a[j]の値をv[i]として，j番目の要素まで非減少列にするための操作回数
    • DP(i, j) = min( DP(0, j-1), ..., DP(i, j-1) ) + |v[i] - a[j]|
    • 答えは，min( DP(0, n-1), ..., DP(n-1, n-1) )。nは数列の要素数。
  • 実装するとO(n^2)。nは5000以下なので大丈夫そう。提出してみたら通った。


D. Triangles

問題：内部に青い点を含まない，赤い点からなる3角形の数を数える

  • 青い点の数Mも赤い点の数Nも500以下。
  • 三角形全てについてナイーブに判定するとO(MN^3)・・・無理。
  • 打開策も思い浮かばぬまま時間切れ。これは解きたかったなぁ・・・。
  • -

結果：0:04(+0) / 1:03(+3) / 1:22(+0) / -- / -- ，41位
レーティング：1783 -> 1844

学内の見知ったアカウントには勝ってそうなので，とりあえず安心。