ABC176参戦記

atcoder.jp

はじめに

2020年8月22日21:00からABC176に出場しました。

結果は14分43秒　3完で9496人中4400位、パフォーマンスは705でレーティングは4下がって745でした。

A問題

A問題は単位時間(T)あたりに焼けるたこ焼きの数(X)、焼くたこ焼きの数(N)が与えられて所用時間を出力する問題です。

換言するとN/Xを切り上げてTを乗じた答えを出力する問題ですが、この切り上げの処理が初心者にはもたつくところです。

割り算の切り上げは（N+X-1)／Xで求めるのが定石ですがぱっとでてこず、割り切れたらそのまま、割り切れない場合は１を足す、という処理で対応しました。

#include "bits/stdc++.h"
using namespace std;
 
int main() {
	int N, X, T,A;
	A = 0;
	cin >> N >> X >> T;
	if ((N%X) == 0) {
		A++;
	}
	cout << (N/ X+1-A)*T << endl; 
	return 0;
}

回答時間4分22秒はちょっともたつきすぎで、せめて2分以内に回答したかった。

B問題

B問題は大きな数が９で割り切れるかどうかを判定する問題です。

10e200000という天文学的な数字が対象なので整数型のまま処理することはできず、文字列で受けるのはすぐ思いつきました。

比較的スムーズにできましたが丁寧にテストケースをあたって回答時間は4分50秒。

C問題

数列を広義単調増加にするための必要数の最小値を求める問題です。

よく見かけるパターンの問題です。

これまでの最大値を保持しながら、新たな要素が最大値よりも小さい場合、差を加算していく、大きい場合、最大値を更新する、というシンプルなアルゴリズムで書きました。

タイプミスなどで少し時間をロスして回答時間5分31秒。

D問題

一見して考察と実装に時間がかかりそうだったので飛ばしました。

E問題

H*Wのグリッドにおいた爆弾を爆発させる問題です。起爆装置と同じ行、同じ列にある爆弾を爆発させることができ、爆発させることができる爆弾の数を最大化したときの最大値を出力します。

問題自体は簡単に意味がとれましたが、HもWも最大3*10e5という巨大な数であるところがE問題です。

最初の方針

最初の実装は二重ループに全グリッド全探索を考え、TLEしないよう枝狩り（行が０の場合は飛ばす）をする方針で臨みましたが、TLEがとれません。

https://atcoder.jp/contests/abc176/submissions/16136646

次の方針

もう少し考えたところ、行での最大値と列での最大値を足せばよいことに気づきました。

意外に簡単だったなと思ってテストケースを試したら間違うケースがあります。起爆装置を置いたところに爆弾がある場合、行と列で二重に数えてしまうので１を引く必要があることに気づきました。

真の課題

この問題はこの部分の処理が真の課題でした。

爆弾の座標を保持し、出力を最大化する起爆装置の座標（複数あり得る）のすべてに爆弾がある場合は出力からー１する、いずれかに爆弾がない場合はそのまま出力する、という方針にしました。

爆弾の座標の保持を二次配列でシンプルにやろうとすると９００億になりさすがにメモリが足りません。
あとでfindで検索することを考えてはじめてsetに手を出しました。

出力を最大化する起爆装置の座標の方は、行と列それぞれvectorで候補を持ち、二重ループで順次判定していく方針にしました。

しかしバグがとりきれず時間内にかけませんでした。

#include <bits/stdc++.h>
using namespace std;

int main(){
   int  H,W,M;
   cin>>H>>W>>M;
   int AH[300100]={};
   int AW[300100]={};
   int ans=0;
   int h,w;
  set<pair<int,int>>s;
    for(int i=0;i<M;i++){
        cin>>h>>w;
        AH[h]++;
        AW[w]++;
      s.insert({h,w});    
    }
  vector<int>hp;
  vector<int>wp;
  int maxh=0;
  int maxw=0;
  for(int i=1;i<=M;i++){
    if(AH[i]>=maxh){
      maxh=AH[i];
    }
  }
  for(int i=i;i<=M;i++){　//MまでではなくHまで見なければダメ　以下も同様
    if(AH[i]==maxh){
      hp.push_back(i);
    }
  }
  
  for(int i=1;i<=M;i++){
    if(AW[i]>=maxw){
      maxw=AW[i];
    }
  }  
  for(int i=i;i<=M;i++){
    if(AW[i]==maxw){
      wp.push_back(i);
    }
  }
  ans=maxh+maxw;


  int flag=1;
  for(auto i=hp.begin(); i !=hp.end();i++){
    for(auto j=wp.begin();j != wp.end();j++){
      if(s.find({*i,*j})!=s.end()) flag=0;
    }
  }
  
  if(flag){
    cout<<ans<<endl;
  }
  else{
    cout<<ans-1<<endl;
  }
  return 0;
}

コンテスト終了後のトライ

バグとりに手間取りながらもなんとかAC。

https://atcoder.jp/contests/abc176/submissions/16159983

反省と次回に向けて

緑手前で停滞していますが主観的には一歩づつ前に進んでいるつもりです。

今回のコンテストでEを解ききれなかったのはデータ構造の使い方に習熟していなかったことが主な原因なので、まだ慣れていないsetなどのデータ構造の使い方に習熟するよう精進を重ねたいと思います。

また簡単な知識をすぐに引き出して使えるようにする力も足りてません。

A～Cを解きなおすのにかかった時間が9分35秒。まだまだ時間がかかってますが、5分ほど短縮できています。
本番でこのくらいの時間で解ければパフォ894ぐらい。

これまでは早解きをあまり意識してきませんでしたが、もう少し意識したいと思います。

まだまだ足りないところ、改善できるところがたくさんあることを実感しています。
そして改善できるところがあるうちは停滞ではない、と感じています。

くさらず、あせらず、たゆまず、更に精進を重ねていきます。