0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

7/2 ICPC模擬国内予選2017に参加してきた

ICPC模擬国内予選に参加してきた. 結果は4完で学内2位. M1チーム, B2チームと解いた問題数は一緒だったけれど, ペナルティで勝ったみたいな感じ. どっちも予選本番では強敵なので油断はできないですね. なお, 某チームに関してはさすがですって感じ. WA出さなかったことに関してはよかったなぁと.

自分はBを解いたのだけれど, 思いの外実装で手間取って時間をかけてしまった, 反省.

C問題は結構チーム内で「え〜、それほんとにあってる〜？」みたいなやり取りがあったのだけれど, 思い切って投げてみるとAC. ちょっと慎重になりすぎたかも(？).

D問題はペアプロみたいな感じでコーディングしてる横で一緒に考察してた. ぱっと見で二分探索ってことはわかったのだけれど, 「ゲームをクリアできない」状況ってのが理解できてなくて問題の本質をつかむまでに時間がかかってしまった. あと, データセットの解答に-1が多すぎてこれも「いや〜、これほんとか〜？」って言ってたのだけれど, 投げてみたらAC. 普通に歓声をあげて喜んでた.

この時点で残り1hあったのでもう1問解きたかったなぁという感じ. Fを考察していたのだけれど, 最小費用流(？)ってことに気づいたのが残り15分ぐらいでライブラリの準備もしていない状態だったので撤退. 他チームがACしないのを祈ってた. Eの方は幾何のライブラリがあんまり準備してなかったので選ばなかったのだけれど, こっちを選んでもよかったなぁという気持ち. 本番も4完した後にだれてしまう可能性あるので気を引き締めていきたいところ.

いろいろトラブルあって開始時間が遅れたりコンテスト時間が伸びたりしたけれど, 運営さんお疲れ様です.

本番はうちからプリンタ担いでいくぞい.

 

AOJ-ICPC(これで130問)

ARC077(起きたらコンテスト終わってたので, 後から解いた)

  • C: pushpush - AtCoder Regular Contest 077 | AtCoder [解答]
    vectorを二つ用意して, 交互にpushしていく. 全部pushしたら片方をreverseして出力.

  • D: 11 - AtCoder Regular Contest 077 | AtCoder [解答]
    重複する要素の間に挟まれない要素の数を数える. 仮にその数をsとすると, k - 1 <= sのときはcombination(N + 1, k) - combination(s, k - 1)が答え. それ以外のときは, combination(N + 1, k)が答え. というのも, 同じ組み合わせができるときっていうのは重複する要素を含む組が2つできるときだけなので. そういう組の数は, 重複する要素の左右の要素数から(k - 1)個選んで, それに重複する要素を加えた構成になっているはず.

  • E: guruguru - AtCoder Regular Contest 077 | AtCoder [解答]
    Eは自力ではわからなかったので解説を見た. お気に入りを1にしたときの回数を求めておいて, i + 1のときの回数をiのときの回数から計算すると時間制限に間に合う. (i + 1)の回数 = iの回数 + (お気に入りボタンで直接ジャンプしたときに飛ばしていた数) - (iを含む区間の数)で計算できる. 足している部分はi番目ではお気に入りボタン一発で変更ができていたクエリで, i + 1になることでボタンをぽちぽちしないといけなくなる分になっている. 引いている分はお気に入りがiのときにはお気に入りボタンとボタンをぽちぽちしていたクエリで, お気に入りがi + 1になると全て1回分ボタン操作が減る. 後者はimos法で求めてあげればOK. 輪っかみたいになった状況でのimosって初めてだったけれど, M - 1と0の間を跨ぐときは, (A[i], M - 1), (0, A[i + 1])っていう二つのクエリに分割すればよさそう. ちなみにINFの値が小さすぎて1時間WA出し続けた().

 

明日は卒検ですねぇ............