Codeforces Beta Round #11
2回目のCodeforces。前回よりは良い結果となりました。
- -
問題：与えられた数列を単調増加列にするとき，1つの要素に値dを加える作業は何回必要？
- 先頭から順に，増加列になるようにdを最低限加えるだけ。
- さすがにWAは出さなかった。
問題：直線上の移動で，i回目は任意の方向にi進むとき，地点0から地点xに行くには何ステップ必要？
- 何か法則があるに違いないと思って、各ステップで行ける地点を列挙してみた。
- 奇数ステップ目で，いられる場所の偶奇が入れ替わる。
- 偶奇さえ一致してれば，Σi以下の場所にはいける。
- みたいなので，そんな判定をしてみたら通った。
問題：与えられた0-1行列中の1からなる正方形の数を数える作業．
- 正方形が満たすべき条件は，
- 正方形は行方向または対角線方向に水平な辺をもつ事が必要。
- 正方形を構成する1以外に，辺や角で接する1が存在してはいけない。
- メンドクセ…と思ってしばし放置。
- が，よく考えたら連結成分が正方形を構成するか調べるだけで良さそう。
- こうなれば実装あるのみ。
- 不安だったので色々テストしてから提出し，なんとか1発でAC。
問題：単純グラフ中の長さ3以上の閉路の数を求める問題．
- 重複しないように数えるのメンドイなぁ…としばし悩む。
- 悩んだ結果，
- ハミルトン閉路数え上げDPの変形。
- [現在地][訪問済みノード集合]をキーに，その状態へ行く経路数をカウント
- 初期条件は，各ノードからのスタートで，DP[i][1<
- 移動時に，スタート地点より番号が小さいノードへは移動しない
- 経由ノード数が3以上の時，現在地からスタート地点に戻る経路があれば解に経路数を加える
- 1つの経路につき，逆回り分で2回カウントされるので，最後に数え上げた分を2で割る
- とやったらサンプルは通った．最大ケース(ノード数19の完全グラフ)も時間は良さそう。
- が，提出したらWA。なん・・・だと・・・？
- 最大ケースを良く考えると，
- ハミルトン閉路だけでも，19!/(19*2)通りある・・・
- long longを使えば良いんですね，分かります。
- ということで，何とか通すことができました。
- -
結果：0:10(+0) / 0:19(+0) / 1:18(+0) / 1:49(+1) / -- ，28位
レーティング：1661 -> 1783
今の自分の実力を考えると上々な結果に。
オーバーフローは気づいておきたかったですが・・・。
