Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2011-12-24

[]Xmas Contest 2011 02:20 はてなブックマーク - Xmas Contest 2011 - TopCoderの学習のお時間

http://atcoder.jp/contest/26/detail

一風変わった問題楽しいです

  • A
    • まず探索が思いつく
    • 最初150以下の全ての数から探索していて、この方針では時間的に無理そうだなあとなっていた
    • ちょっと考えたら素数だけ調べれば良いことに気づく
    • 大丈夫な速度になったので提出
    • X=0の場合でミスっていて一度再提出したがAC
  • B
    • ダイクストラやるだけ
    • 通常のコストで一気に遠くの町へ移動するのは1つずつ移動するのと一緒なので隣の町への移動だけ考えれば十分
    • 入力でTLEしたのでScannerからBufferedReaderに変えて通した
  • C
    • うわぁあガチ数学(たぶん)だー
    • とりあえずNが素数の場合だけ、mod Nでの和と積を使うという解を提出してみる
    • がやっぱり0点。そうですよねー
    • 逃げだした
  • D
    • dp[i][j][k] = i文字目からj文字目までの部分文字列の中からk文字取り除いた場合の辞書順最小の文字列
    • というDPをやった
    • TLEした(部分点は取れた)
    • C++に書き換えてもだめだった、というか答えが変わってWAになってしまった。なぜ…
    • 同じ方針で通してる人もいるようなので、何も考えず実装して文字列を作りまくってたからだろうなあ
  • E
    • 面白い問題です
  • F
    • これは! Advent Calendarの記事で言及した「珍しい制約がある問題」ではないか
    • 辺の数は合計N^2のオーダーなのに苦手な辺の数は最大N個しかない
    • 苦手な辺はかなり疎にしか分布せず、たいていの場合は普通の辺だけを通って巡回できそう
    • ただし1つの頂点に苦手な辺が集中していた場合はどうしても通らないといけない
    • そしてそのような頂点を作るには苦手辺のほとんどをその頂点への辺で使ってしまわないといけないから、その条件に当てはまる頂点はたかだか1つしかない
    • その頂点に行くために苦手辺を使うのは、コストが1番小さいパスを行ってすぐ戻る場合とコストが1番目・2番目に小さいのを辿るのとの2通りある。合計のコストが小さい方を選ぶ
    • この議論はNが小さいと成り立たないので、その場合は現在位置と訪問済み頂点を状態にしてダイクストラする
      • Nが大きい場合よりもこっちのNが小さい場合の回答のほうが考えるのも書くのも時間かかってしまった
  • G
    • 独立に変化するビットをグループ化してマッピングするようなのをうだうだ考えたけどだめだった
  • H
    • 答えにHが含まれる場合自己言及だなあ、面白い、後でじっくり考えよう
    • と思っていたけどその「後」はコンテスト中には来なかった…
    • 必ずどれかの問題の正しい出力になっているというあたりに優しさが

  • 8問中4問正解+1問部分点
  • 10位/100人くらい

[]SRM526.5 01:37 はてなブックマーク - SRM526.5 - TopCoderの学習のお時間

http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14762&rm=310932

  • 250
    • 一番後ろが落とされる場合の回数を数えれば良いんじゃないの、と直感して約√N回のループを書く
    • サンプル通ったので提出
  • 500
    • DPで外側のエリアから順に、0個積もる場合、1個積もる場合、…の確率を計算した。
    • そのままだと計算量50*10000*50*10000とかでダメだけど、極端に1箇所に何個も集まる場合の確率は無視できるだろうから途中で切り落とせないか? と思っていた
    • がだめだった
  • Challenge
    • 250で微妙に違う方針の人が多い。いまひとつどういうつもりのコードなのかわからない
    • +50しても順位的にあまりおいしくなさそうなので何もせず
  • System Test
    • 250は通った
    • いまさらになって、この解法ではN-1個目が取り除かれた後にN個目が取り除かれる場合を考慮してない! 大丈夫なの!? と気づく
    • 結果的に大丈夫だったわけですがかなり良くない
  • 239.75 + 0.00 + 0.00 + (50*0-25*0) = 239.75
  • 59位/614人
  • 1933->2023

500は往年の毎回難問だった時代を思い起こさせる感じで良かった

 |