その他のコンテスト
メモ。 立命館合宿企画者さまとAOJの管理者さまには大変お世話になりました。 コンテスト参加者のみなさまと、かなり無理なスケジュールを押し付けてしまったスタッフのlyoz君とfura2君と、インフラ用意してくれたhasi君と、それからついでに自分もお疲れさ…
問題概要 N(区間がある(区間の座標 解法 dp[t][i] = {時刻tに、i時間連続で起きているときのスコアの最大値} とするとO( (N+MAX_X)*(T+L) )で解ける。
問題概要 単純な文法に従う式が与えられる。評価せよ。 解法 pythonでevalするとオーバーフローも構文解析も気にせずかけてとても良い。
結果。 前回に続いてICPC現役組とチーム参加して7/11完。前回に比べて順位的にはそこそこだったけど、内容的には解ける問題を確実に通しただけ、という気がしなくもない。もちろんそれはとても大事なことなのだけれど。
問題概要 2次元格子上にN( 解法 x座標でソートしてからx座標最小の1点を中心に角度でソートする。このとき、全てが同一直線上にならんでいるときは解なし。それ以外のときは角度が小さい順に拾っていけばよい。角度が同じ複数の点については距離の遠いところ…
結果。 20+100+28の148点。部分点が細かく付いたコンテストってどの時点で満点解法諦めるか結構迷う。
問題概要 解法 力がfのときに脱出までかかる日数の期待値をO(F*N)のDPで計算する。
問題概要 重み付き区間がN(区間を選んで重みの和を最大化する問題。 解法 隣同士5離れているとかは全ての区間で右端を5伸ばせば良い。後は座標圧縮して重み付き区間スケジューリングに落とす。 コード略。
問題概要 1~N(N 解法 BITを使う典型問題。
問題概要 長さN(区間[l, r]を右から走査していったとき最初に2回出現する数を答える。どれも1回しか現れないなら指摘する。 解法 各iについて、自分より左側で最も近くに現れるindexを持っておく。後は区間内でRMQして最大のindexを取り出し、それが区間内に…
結果。 ICPC現役勢と組んで出場。6/10完。問題そのものは結構好きなんだけど、入力の読み取りが面倒だったり、解釈のしようがない入力がデータに含まれたりしていたのが個人的には苦手だった。
問題概要 頂点数V( 解法 各ノードに対して、そこを通った蟻がk匹死んだときにゴールまでたどり着ける確率をdpで計算できる。更新式は各ノードで左右の部分木のサイズごとの積だけ計算する必要があるけど、このタイプの木DPは計算量がO(V^2)で抑えられている…
問題概要 頂点数N( 解法 BFSするだけ。ただしEの補集合を陽に持つことはできないので、その部分だけ気をつける。
問題概要 文字列を,で結合する。
問題概要 フィボナッチ数を求める。
問題概要 n( 解法 最適ルートは、右→左か左→右なので、今いる位置から右に進んだ場合と左に進んだ場合でそれぞれDPして最適解を求めておき、最後にその2つをマージするようにすればよい。うまく実装する自信がなかったので、初期位置をとる場合ととらない場…
問題概要 頂点数n( 解法 どれを潰すか全探索して毎回強連結成分分解して間に合う。
問題概要 長さN( 解法 半分全列挙でよい。
問題概要 N個の重み付き区間[a[i],b[i]), w[i]が与えられる。a = {0,1,2,...,n-1}である。[1,n)を全て被覆するのに必要な最小コストを求める問題。n 解法 dp[i] = {i個目の区間を使う場合、それ以降を全て被覆するのに必要な最小コスト}とすると、dp[i] = w[…
結果。 uwiさんとチームで参加。全完で1位という素晴らしい結果だった。自分が書いたのはG,I,J,K。デバッグの調子が良かったのでWAは1個に抑えることができた。
問題概要 H*W(H,W 解法 よく理解できていない…。各マスについて、自マスを含む同じ行、列についてxorをとったものを反転したものが答えになっている。パリティ符号みたいなもの？
問題概要 N(3*Rが成り立っている。dist(i,j) 解法 異なる連結成分の点は距離が離れているので、ランダムに回転してx座標でソートした後適当に近いところだけを調べていけばよい。 R置きのグリッドを引いて最も近くにある格子点を考えるのが綺麗な解法。
問題概要 1日1円ずつ貯金する。貯金額がw[i]円を越えたら以後x日間さらに1 or その日からの経過日数 or 経過日数の2乗だけさらに貯金する。目標額w[i]を達成するのが何日になるかとy[i] (y[i] 解法 一日ずつシミュレーションする。区間への定数、1次式、2次…
問題概要 N( 解法 とりあえず目標点が低いので強さに関して極大な手の中からランダムに選ぶ解答で通った。
問題概要 M(区間がある。[0, N)を被覆するのに最小いくつ必要か求める問題。 解法 最初に区間を左端でソートしておいて、dp[i][j] = {iまでで、区間[0, j)を被覆するのに最小いくつ必要か}とするとO(N^2*M)で解ける。 真面目にやればO(N*M)でも解ける。 また…
問題概要 N( 解法 愚直に実装する。
問題概要 1次元のオセロで連結な初期状態が与えられるので以後最善を尽くした場合どちらが勝つか判定する問題。 解法 両端が同じになればその色が勝つ。両端が異なれば初手で両端を同じ色にできる先手が勝つ。
問題概要 配列Xがある。Xの要素のうち、[T-E, T+E]に倍数が含まれるようなものがあればそのインデックスを求める問題。 解法 modとかとらなくても倍数全部調べて自明な枝を刈ればよい。
結果。 8完+部分点で8位。無駄なWAはそんなに多くなくてよかった。今年もおもしろい問題が多くてさすがだと思ったし、去年に比べると全体的に難易度は上がっているにも関わらず参加者の正答数は全体的に増えているようで驚いた。 以下コンテストの流れ。 開…
問題概要 H*W(H 解法 男の数、女の数、値、負の値の個数について累積和を計算しておく。そうすると矩形を決定すればO(1)で判定できて嬉しい。後はyhighとylowを全探索してx方向にしゃくとりすれば全体の計算量O(H^2*W)で間に合う。
