進捗どうですか

進捗の足跡

第9回情報処理選手権で5位を獲得した


2017/8/1にオンライン上で行われた情報処理選手権に参加した。

johoshori-senshuken.net

ITパスポート試験基本情報技術者試験相当の問題の正答数を競う大会である。

参加動機

友人から情報処理の面白い大会があると誘われる。優勝すると賞金2万円がもらえるとのことだった。

チーム名を決める

団体部門ではチーム名が必要である。
なお、団体部門に申し込みを行うと個人部門にも自動的にエントリーされる。

たいていのチームは学校名や部活名を使っていたのだが...

このざまである。
(検閲により削除)は顧問の先生の許可を得られなかったので、『  』で出場する。
なお、『  』は、小説「ノーゲーム・ノーライフ」(榎宮祐 著)の主人公の兄妹であり、作中では最強のビデオゲームプレーヤとされている。

対策

閑話休題
本番の問題はITパスポート試験基本情報技術者試験から出題されるということで、当該試験の教本を読んだり、過去問道場を利用した。
過去問道場では試験5回分くらいの基本情報技術者試験の過去問を解いた。
基本情報技術者過去問道場|基本情報技術者試験.com
また、チーム内で教えあいもした。
運営から配布された対策問題では、前日に80%程度の正答率であった。微妙なラインである。
申し込みが遅かったので、十分な対策ができたかといえば微妙であった。

本番当日

一時間前に先生から招集がかかり、説明や大会が行われるサーバーにアクセスできることを確認した。
その後、開始時刻まで、なぜか「天体のメソッド」の第一話の上映会が行われた。

本番

時間のかかりそうな計算問題やわからない問題を後回しにして、一通り問題を解き、後から残した問題を解きなおす。
10分程度時間を残して完了することができた。同点の場合、回答完了時刻の早い順に順位がつくので、問題を解く速度も大事である。
実際の基本情報技術者試験よりも、マネジメント・ストラテジ系の問題が多いように感じた。(気のせいかもしれない)

結果

個人部門は80点中74点で5位、団体部門は400点中303点で10位であった。

感想

予想外の出来だった。終了時に74点と表示されたときはびっくりした。
『  』を最強だけに1位にできなっかたのは少し残念であった。
申し込みをもっと早く行えば、余裕をもって対策ができたかもしれない。
来年こそは、後輩たちの力で『  』を一位にしていただきたい。

JOI予選参加記

かなり遅くなってしまいましたが、12月11日の情報オリンピック予選の振り返り記事を書いていきます。某部活のアドベントカレンダーもかねて...

 

問題文はこちらからどうぞ→

JOI 2016/2017 予選 問題文・採点用入出力・解説

 

問1 電子レンジ

焦らず丁寧に...。0度より高いか低いかで解の導出方法が異なることに注意。

//ヘッダー等は省略
int a, b, c, d, e;
signed main()
{
  cin >> a >> b >> c >> d >> e;

  if(a > 0){
    cout << e * (b - a) << endl;
  }
  else{
    cout << c * (-a) + d + e * b << endl;
  }
  
  return 0;
}

問2 ポイントカード

総和を求めてから、一番コストのかかるポイントカードを破棄すればよい。

//ヘッダー等は省略
int n, m;

int a[1010], b[1010];
int ans = 0, mx = 0;

signed main()
{
  cin >> n >> m;
  for(int i = 1; i <= m; i++){
    cin >> a[i] >> b[i];
  }

  for(int i = 1; i <= m; i++){
    if(a[i] < n){
      ans += n - a[i];
      mx = max(mx, n - a[i]);
    }
  }

  cout << ans - mx << endl;
  
  return 0;
}

問3 休憩スペース

全通り調べる。具体的にはi行j列目において、ベンチをそこが左端または上端となるようにおけるか、を全通り調べる。

//ヘッダー等は省略
int n, m, d;
char field[110][110];
int ans = 0;
signed main()
{
  cin >> n >> m >> d;

  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      cin >> field[i][j];
    }
  }

  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      
      if(j <= m - (d - 1)){
	bool flag = true;
	for(int k = 0; k < d; k++){
	  if(field[i][j + k] != '.'){
	    flag = false;
	  }
	}

	if(flag){
	  ans++;
	}
      }

      if(i <= n - (d - 1)){
	bool flag = true;
	for(int k = 0; k < d; k++){
	  if(field[i + k][j] != '.'){
	    flag = false;
	  }
	}

	if(flag){
	  ans++;
	}
      }
    }
  }

  cout << ans << endl;
  return 0;
}

少しバグらせてしまったのと、テストケースの表示がおかしかったのが災いして、少し時間を要してしまった。

問4 ぬいぐるみの整理

まさかの予選でのbitDP。過去に例を見ない問題構成で、かなり驚いた。

あらかじめ累積和をとっておき、任意の区間に任意のぬいぐるみが何個あるかをO(1)で求められるようにしておく。

連続してぬいぐるみを置くので、置き方はM!通り。

下からkビット目が1ならぬいぐるみkを置き終わっている、という記法*1を使うと、(これを「現在の状態」と呼ぶ)

dp[i]=現在の状態がiの時のぬいぐるみの交換回数の最小値

と表せる。「現在の状態」の通り数はビットの立ち方の通り数、すなわち2^M通りである。

あとは動的計画法なりメモ化再帰なり好きなようにやってください。計算量はO(M*2^M)。

問5 尾根

今年の問題は参加者を落としにかかってきているな...

愚直に各々のマスから幅優先探索を行うと、O(H^2 W^2)となってしまい、これだと20点しか得られない。

何度も何度も同じ経路をたどっているので、ロスが発生している。

ここで、番号の小さい順に幅優先探索を行い、その結果を覚えておき、次回以降そこに到達したときは探索を打ち切る、という手法を使えば、O(HW)で解を導ける。

どうやって覚えておくかというと、1か所に流れるときは流れ着くマスの番号、2か所以上の時は0とでもしておけばよい。

2か所以上に流れるマス(尾根)に到達できるマスは尾根と確定するので、いちいち流れ着くすべてのマスを覚えておく必要はない。1か所の場合は複数のルートから最終的に1つのマスにたどり着くという可能性があるため、覚えておく必要がある。*2

問6 ヘビのJOI君

「部屋iで自分の現在の状態がj、温度変化に対応できるようになるまでにあとk分」の状態にたどり着くまでの最短時間を求める問題。

部屋が同じでも、現在の状態や温度変化に対応できるようになるまでの残り時間が違えば、違う頂点として扱うのがミソ。頂点数は多く見積もっても10000*3*201通りしかない。

ダイクストラで実装すればよい。

//ヘッダー等は省略
int n, m, x;

int t[10010], a[20010], b[20010], d[20010];

vector<pair<int, int> > node[10010];

struct status
{
  int time, place, t, remain;
  status(int _time, int _place, int _t, int _remain)
  {
    time = _time, place = _place, t = _t, remain = _remain;
  }
  bool operator<(const status another)const{
    return time < another.time;
  }
  bool operator>(const status another)const{
    return time > another.time;
  }
};

priority_queue<status, vector<status>, greater<status> > pq;
bool visited[10010][3][210];
int fast[10010][3][210];

void dijkstra()
{
  for(int i = 1; i <= n; i++){
    for(int j = 0; j <= 2; j++){
      for(int k = 0; k <= x; k++){
	fast[i][j][k] = INF;
      }
    }
  }
  
  {
    status in(0, 1, 0, x);
    pq.push(in);
  }

  while(!pq.empty()){
    status now = pq.top();
    pq.pop();

    if(!visited[now.place][now.t][now.remain]){
      visited[now.place][now.t][now.remain] = true;
      fast[now.place][now.t][now.remain] = now.time;

      for(auto pt:node[now.place]){
	if(now.remain - pt.F <= 0){
	  status in(now.time + pt.F, pt.S, t[pt.S], t[pt.S] == 1 ? 0 : x);
	  pq.push(in);
	}
	else{
	  if(t[pt.S] == 1 || t[pt.S] == now.t){
	    status in(now.time + pt.F, pt.S, now.t, t[pt.S] == 1 ? now.remain - pt.F : x);
	    pq.push(in);
	  }
	}
      }
    }
  }
}

int main()
{
  scanf("%lld%lld%lld", &n, &m, &x);
  for(int i = 1; i <= n; i++){
    scanf("%lld", &t[i]);
  }
  for(int i = 1; i <= m; i++){
    scanf("%lld%lld%lld", &a[i], &b[i], &d[i]);
  }

  for(int i = 1; i <= m; i++){
    node[a[i]].PB(MP(d[i], b[i]));
    node[b[i]].PB(MP(d[i], a[i]));
  }

  dijkstra();

  int mn = INF;
  for(int j = 0; j <= 2; j++){
    for(int k = 0; k <= x; k++){
      mn = min(mn, fast[n][j][k]);
    }
  }

  printf("%lld\n", mn);
  return 0;
}

結果等

全完(600点)でした。

今回は、過去の問題と傾向がかなり違っていたと思います。

本選では昨年のようにDPで殺されることなく、春合宿に進みたいと思います。

まだまだ精進がんばるぞい!


問題のWrite-upを書くのはかなり久々なので文章が拙いような気がする...。気まぐれで修正かけるかもしれません。

*1:例えば、0b00001010なら、1と3を置き終わっている、と考える

*2:入力例2の15からは13と6を経由して最終的には1のみにたどり着く。