ACM/ICPC 国内予選 2011 参加記録

ICPC

同じサークルに所属するaru先輩(id:aru0101)とclear先輩とともに"-Dint=char"というチーム名で参加しました．
結果は5完(1WA)で13位でした．全員初参加の割に健闘出来た気がします．

Practice Session

  • "Milky Holmes"がMを一番最初に通していて盛り上がっていた．
  • 自分達のチームはJ,Lをショートコーディングして遊んでいたり…．

A問題

やるだけだったので実装．
篩のソースをもっと短くかけるようにしておくべきだった．
AC

B問題

最初std::reverseとか頓珍漢なことをしていたが，最終的に，replace("()","")とreplace("[]","")を収束するまで行なって文字が残るかで判定した．
用意していたreplace関数にミスがあったのが残念だった．
AC

C問題

aru先輩に全探索するだけだよと言われたので実装．
BFSの処理でローカル変数にHを取ってしまい，グローバル変数のHと被ってしまうという残念なミスを発見するのに凄く時間がかかった．
また全探索で明らかに最適解にならないものがあったので其を取り除いた．
AC

D問題

aru先輩にDPするだけだよと言われたけど，上手い実装の仕方が思い浮かばずずっと悩んでいた．
また，他のチームに追い付かれてきたので結構焦りもあった．
結構今まで取った物をbit演算を使ってint型変数に記録し，上のものが全て無くなっているかをor演算を用いて判定した．
自信は無かったけどAC

E問題

DFSをまず考え，結局ある範囲のDFSは他の範囲の数値に影響されないことに気づいたのでメモ化再帰することにした．
二次元累積和を用意していなかったのでまずは単純にやってみる→累積和にもDPを適用としたらサンプルが通らないコードが出来てしまった．
そしてそれに気づかずそのまま提出してしまい1WA．
累積和のメモ化を解除して，提出してAC．

F問題

場合分けは大体出来たけど，幾何ライブラリを写すのに疲れてしまい終了．

G問題

無理ゲー臭がしたので逃亡．

反省点

  • ライブラリのVerifyが弱く，Replaceでミスがあったりした．
  • ライブラリがあまり早く書くということが重視されていなかった．
  • Eをあまりにも確認せずに出してしまった．
  • Dよりも先にEを考えてみるべきだった．

感想

  • 今回実装は私，アルゴリズムは先輩方という風な役割分担をしたが非常にやりやすかった．
  • アジア予選では他のぱないチームと戦えるように精進していきたい． //英語力も付けないと…