ＡＢＣ１９７参戦記

はじめに

2021年3月27日21:00-22:40 ABC197に参戦しました。
結果は89分42秒3完ノーペナ 3316位／7885人中でパフォーマンス736、レーティングは前回862から12下がって850でした。

A問題

３文字の文字列の１番目を３番目に移す問題です。
あまりうまい方法を思いつかずs[1],s[2],s[0]の順に出力しました。
2分05秒。

B問題

B - Visibility

H*Wのグリッドに障害物が置かれていて(x,y)から見通せるマスの数を数える問題。
よくあるパターンで素直に実装。サンプルを試して8分27秒通算10分32秒はまずまず。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;

char c[110][110];
int main(){
  int h,w,x,y;
  cin>>h>>w>>x>>y;
  x--;
  y--;
  string s;
  rep(i,h){
    cin>>s;
    rep(j,w){
      c[i][j]=s.at(j);
    }
  }
  int ans=0;
  for(int j=y;j>=0;j--){
    if(c[x][j]=='.') ans++;
    if(c[x][j]=='#') break;  
  }
  for(int j=y+1;j<w;j++){
    if(c[x][j]=='.') ans++;
    if(c[x][j]=='#') break;  
  }  
  for(int j=x;j>=0;j--){
    if(c[j][y]=='.') ans++;
    if(c[j][y]=='#') break;  
  }
  for(int j=x+1;j<w;j++){
    if(c[j][y]=='.') ans++;
    if(c[j][y]=='#') break;  
  }      
  cout<<ans-1<<endl;
  return 0;
}

C問題

C - ORXOR

長さ２０までの数列Aを１つ以上の区間に分け，各区間のビットORの全ての値のXORの最小値を求める問題です。
未だにビットOR、XORの演算に慣れていない上、数え上げの方法をすぐに思いつけず、いったん飛ばしてD問題に進みました。D問題で詰まって戻ってきて解き切りました。

数え上げはN-1個の仕切りをbit全探索で試す方法でよさそうです。
仕切りがでてくるまでbitOR演算で各区間の値を計算し，仕切りがでてきたらvectorにストックしておいて，最後にすべてのXORを出し，最小値を更新していく方針でときました。

ビット演算に慣れていないこともあり，バグ取りに手間がかかりましたが，なんとか解ききれてほっとしました。

79分10秒　通算89分42秒　20分ぐらいD問題を考えていたので実質60分くらいでした。

提出コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;
ll a[20];
int main(){
  int n;
  cin>>n;
  rep(i,n) cin>>a[i];  
  ll maxans=10000000007;
  ll tempans=0;
  ll totalans;
  for(int i=0;i<(1 << (n-1));i++){
    vector<ll>vec;
    tempans=a[0];
    for(int j=0;j<(n-1);j++){
      if(i & (1<<j)){
        //cout<<i<<" "<<j<<" "<<tempans<<"%"<<endl;
        vec.push_back(tempans);
        tempans=a[j+1];
        //cout<<tempans<<"#"<<endl;
      }
      else{
        tempans=(tempans|a[j+1]);
      } 
    }
    //tempans=(tempans|a[n-1]);
    vec.push_back(tempans);
    //cout<<vec.size()<<" "<<tempans<<endl;
    totalans=vec[0];
    for(int k=1;k<vec.size();k++){
      //cout<<vec[k]<<"#"<<endl;
      totalans=(totalans^vec[k]);
    }
    //cout<<totalans<<endl;
    maxans=min(maxans,totalans);
  }
  cout<<maxans<<endl;
  return 0;
}

D問題

幾何問題です。久しぶりの印象。
図形的なイメージはできましたが解き切ることができませんでした。

時間内に思いつけなかったのは中心点から回転させる，というところです。
これが思いつけば，回転行列をつかって解くことに思い至れたと思います。

コンテストが終わった後で回転行列についてぐぐって解くことができました。

親子競プロ

今回は親子そろって冷えましたが息子は４完でこのところ負け続けてます。
どこかで一矢報いたいなと思っています。

おわりに

３連続で冷えてしまいましたが，冷えた回にこそ成長のカギがあると思います。
今回の問題も４完は手のとどくところにあるように感じました。
多少時間がかかるかも知れませんが今の努力を継続すれば水色になれるはずです。
引き続きがんばります。

ARC115参戦記

はじめに

2021年3月21日20:00～22:00に開催されたARC115に参戦しました。
結果は121:43のB１完で1890位／2592人中、パフォーマンス562でレーティングは前回890から-28の862になりました。

前日のABCに続けての茶パフォでだいぶ冷えましたが、多少冷えても茶落ちしないのは心の平穏に寄与しています。
反省の多い回でした。

A問題

A - Two Choices

解けませんでした。
愚直解で当然のTLE。えいやっで出すのはいい加減に辞めようと思います。
答えが違う問題が奇数個ある場合→正解の数の偶奇　まで思い至りませんでした。
Ｏ（N^２）がダメなのでO（Ｎ）解法を捜すしかなく、０１の列なので偶奇は見やすいところです。
実装が簡単な問題だけに悔しいところですが、いい勉強になりました。

B問題

B - Plus Matrix

A問題に相当長時間つぎ込んだ上でのＢ問題。
実装がやや重たいだけの問題ですがコードがぐちゃぐちゃになり時間がかかりました。
それでも解ききれてよかった。途中、０完の悪夢も頭をよぎりました。

私の恥ずかしいコード

https://atcoder.jp/contests/arc115/submissions/21147534?lang=ja

C問題

C - ℕ Coloring

これはよく見れば素因数の数の行列になります。
落ち着いてやれば解けたなと思います。
ちょっと悔しいですがこれが今の実力か。

復習しました

　素因数の数だけでは不十分で約数のAiより大きな数とするようDP的に更新していく必要がありました。
細かな実装の工夫も必要でしたが解けない問題ではなかったと思います。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;

int k[100010];
int main(){
  int n,temp;
  cin>>n;
  vector<int>vec;
  k[1]=1;
  rep(i,n){
    temp=i+1;
    if(temp==1){
      vec.push_back(temp);
      continue;
    }
    for(int j=1;j*j<=temp;j++){
      if(temp%j==0){
        k[temp]=max(k[temp],k[j]+1);
        if(j !=1){
          k[temp]=max(k[temp],k[temp/j]+1);
        }
      }
    }
    vec.push_back(k[temp]);
  }
  for(int i=0;i<vec.size();i++){
    if(i !=0) cout<<" ";
    cout<<vec[i];
  }
  cout<<endl;
  return 0;
}

親子競プロ

父親が１完で冷えている間に息子は前日に続く青パフォで爆上げしています。
この調子でもう１戦すると水色になるレベルでちょっと離されました。
諦めずにもう１度追い抜けたらいいなと思います。

ABC196参戦記

はじめに

2021年3月20日21:00-22:40に開催されたABC196に参加しました。
結果は44分59秒ABC3完で3695位／8630人中、パフォーマンス731でレーティングは前回907から-17の890となりました。

A問題

Ａ問題は簡単な算数問題。
a<=x<=b , c<=y<=d となるようx,yを選ぶときx-yの最大値を求めます。
xがより大きく、yがより小さくなるようにとればいいのでb-cを出力します。
間違えやすい問題なので丁寧にサンプルを試して2:1０で提出。まずまず。

B問題

整数または小数が与えられ小数点以下を切り捨てて出力する問題です。
入力の上限が10^100と大きいので文字列で受けて小数点がでるまでそのまま出力する方針でAC。
2:44で提出。通算4:54とここまでもいい感じ。

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

int main(){
  string s;
  cin>>s;
  int len=s.size();
  int flag=-1;
  rep(i,len){
    if(s.at(i)=='.'){
      cout<<endl;
      return 0;
    }
    cout<<s.at(i);
  }
  cout<<endl;
  return 0;
}

C問題

今回の失敗はC問題でした。
問題は10^12以下の数nが入力され、n以下の数で①偶数桁　かつ　②前半と後半が文字列として等しい ものを出力する問題です。この②を回文になっているものと誤読して、だいぶ時間を溶かしてしまいました。細かいバグとりにも手間取って提出に痛恨の40分05秒。通算44分59秒となりだいぶ遅れました。

提出コードに無駄にひっくり返す関数を書いた跡が残ってます。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;

int rev(ll x){
  string s=to_string(x);
  //cout<<s<<endl;
  reverse(s.begin(),s.end());
  //cout<<s<<endl;
  ll r=0;
  int n=s.length();
  rep(i,n){
    r*=10;
    r+=s.at(i)-'0';
  }
  //cout<<r<<endl;
  return r;
} 

int main(){
  vector<ll>vec;
  ll m;
  for(int i=1;i<=999999;i++){
    //if(i%10==0) continue;
    ll j=i;
    m=10;
    if(i>=10) m=100;
    if(i>=100) m=1000;
    if(i>=1000) m=10000;
    if(i>=10000) m=100000;
    if(i>=100000) m=1000000;
    vec.push_back(i*m+j);
  }
  sort(vec.begin(),vec.end());
  ll n;
  cin>>n;
  if(n<=10){
    cout<<0<<endl;
    return 0;
  }
  //cout<<vec.size()<<endl;
  rep(i,vec.size()){
    if(n<vec[i]){
      cout<<i<<endl;
      return 0;
    }
  }
  cout<<vec.size()<<endl;
  return 0;
}

D問題

解けませんでした。
翌日解説AC。
次は同じようなのがきたら解けると思います。

E問題

時間中にトライしましたが解ききれませんでした。
解説もまだしっかり理解できておらず、後日復習します。

ABC195(パナソニックプログラミングコンテスト）参戦記

はじめに

2021年3月13日21:00-22:40に開催されたABC195(パナソニックプログラミングコンテスト）に参戦しました。
結果は43分38秒ACDの３完で2202位/7679人中、パフォ―マスは1014でレーティングが前回894から+13の907となりhighestを更新しました。

A問題

A問題らしいA問題。HがMの倍数かどうかを判定します。
丁寧にサンプルも確認して1分48秒で提出。

B問題

時間内に解けませんでした。
全探索だろうとあたりはついたのですが，難しく考えすぎてしまったかも知れません。
10分近く悩んで見切りをつけてC問題に進みましたが飛ばして正解でした。

あとで戻ってきて更に30分ほど考察しましたが正答に至らず。
コンテスト終了後、解説をみてなるほどでした。

C問題

1～10^15以下の数までを３ケタ毎にコンマ区切りで書いた場合にコンマの総数を求める問題。
大きい方から順に足していく解法がすぐに見えました。
通算18分42秒。

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

int main(){
  ll n;
  cin>>n;
  ll ans=0;
  if(n==1000000000000000){
    ans+=5;
    n--;
  }
  if(n>=1000000000000){
    ans+=(n-999999999999)*4;
    n=999999999999;
  }
  if(n>=1000000000){
    ans+=(n-999999999)*3;
    n=999999999;
  }  
  if(n>=1000000){
    ans+=(n-999999)*2;
    n=999999;
  }
  if(n>=1000){
    ans+=(n-999);
  }  
  cout<<ans<<endl;
}

D問題

D - Shipping Center

箱に荷物を入れていく問題。
クエリでｌ～rまでの箱が使えない場合があります。
貪欲法で、価値が最大の荷物を入れられるもっとも小さい使っていない箱に入れる、でよさそうです。

クエリで出てくる使えない箱は、大きさ０にすることで表現しました。
使った箱の大きさも０にします。
もとの箱の大きさを配列xでもち，クエリ毎にyにコピーして使います。
ちょっと時間はかかりましたが破綻なく実装し切れてよかったです。
通算43分38秒。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;

//int v[50];
//int w[50];
int x[50];
int y[50];//クエリ作業用
int main(){
  int n,m,q;
  cin>>n>>m>>q;
  vector<P>vec;
  rep(i,n){
    int w,v;
    cin>>w>>v;
    vec.push_back({v,w});
  }
  sort(vec.begin(),vec.end());
  /*for(auto e:vec){
    cout<<e.first<<" "<<e.second<<endl;
  }*/

  rep(i,m) cin>>x[i];
  int ans=0;
  //クエリ
  rep(i,q){
    ans=0;
    int l,r;
    cin>>l>>r;
    l--;
    r--;
    for(int j=0;j<m;j++){
      if(l<=j && j<=r){
        y[j]=0;
      }
      else{
        y[j]=x[j];
      }
    }
    sort(y,y+m);
    for(int k=n-1;k>=0;k--){
      for(int l=0;l<m;l++){
        if(vec[k].second<=y[l]){
          ans+=vec[k].first;
          y[l]=0;
          break;
        }
      }
    }
    cout<<ans<<endl; 
  }
}
    

E問題

10分ほど考えましたが解法を思いつきませんでした。
７の倍数は末尾の数字を消してその２倍を消した数から引いた数も７の倍数、みたいなのをぐぐって見つけましたがどう使っていいのかもわからず。

一つ上に行くにはこのレベルをきちっと解けるようにならないとダメだと思います。

終わりに

今回はB問題が解けなかったのが悔しかったですが，B問題が解けていてもパフォーマンスの差はわずかでした。
Dが解けたのは最近取り組んでいるcodeforcesでの精進による実装力強化の成果だと思います。

幸い停滞していたレートも緩やかに上昇を始めています。
水色を視野に入れて、基礎を固めつつ、Ｅ問題以降が解けるような力をつけていきたいと思います。

ABC194参戦記 2021/3/6

はじめに

2021年3月6日21:00-22:40に開催されたABC194に参戦しました。
結果は82:20 4完 3WA 2333位/ 7892人中　パフォーマンス1003でレーティングは882から+12の894となりhighestを更新しました。

A問題

A - I Scream

無脂乳固形分と乳脂肪分が与えられ乳固形分と乳脂肪分の割合により分類されるアイスクリーム類の分類をする問題です。

誤読しやすい問題ですがサンプルをちゃんと試せばＯＫ。
Ａ問題としては難しめの印象でした。

4分25秒。

B問題

B - Job Assignment

２つの仕事を誰にさせると最短でできるかを求める問題。

同じ人がやる場合には２つの仕事にかかる時間の合計時間がかかり(Ａi+Ｂi）、別の人がやる場合には、それぞれの人がかかる時間の長い方（max(Ai,Bj)）がかかります。

少し悩みましたがＮが１０００以下なので全探索でやるのがあっさりです。
同じ人が担当する場合と別の人が担当する場合で計算式を変えて最小時間を更新するようにします。

これもＢ問題としては難し目に感じました。

7分36秒　通算12分01秒

提出コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
  int n;
  cin>>n;
  int a[n];
  int b[n];
  rep(i,n){
    cin>>a[i]>>b[i];
  }
  int mintemp=200000;
  rep(i,n) rep(j,n){
    if(i != j){
      mintemp=min(mintemp,max(a[i],b[j]));
    }
    else{
      mintemp=min(mintemp,a[i]+b[j]);
    }
  }
  cout<<mintemp<<endl; 
  return 0;
}

C問題

C - Squared Error

長さＮの数列Ａの各要素同士の差の二乗の和を求める問題です。
Ｎが最大3×10^5なのでＯ（Ｎ^２）ではTLEしそうです。

サンプルを見ながら式変形を考えました。
(A-B)^2=A^2+B^2-2*AB
なので，前の部分は各要素の二乗で計算できます。

後ろの部分は更に式変形すると　ある要素にその要素以外の要素の和を掛けたもの　の和を２倍すればよいことに気づきました。
これを前の部分から引きます。

すぐに解法が見えてしめしめとおもっていましたが，実装するとサンプルが合わなくて悩みました。

いろいろ考えても全然合わないので，血迷って１回TLE必至の愚直実装を提出しましたが当然TLEに。

あらためてＮ＝５のサンプルを手計算と比較しながら見直して間違いに気づきました。
前半部分をＮ＝３のサンプルから二乗の和の２倍と計算していたのが間違いでした。Ｎ－１倍すれば合います。

かなりもたつきましたがむしろ解ききれてよかったという気持ちの方が大きかったです。

32分14秒　通算44分15秒 1WA

提出コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
  int n;
  cin>>n;
  ll a[n];
  ll sum=0;
  rep(i,n){
    cin>>a[i];
    sum+=a[i];
  }
  ll ans=0;
  rep(i,n){
    ans+=(a[i]*a[i]);
  }
  ans*=(n-1);
  rep(i,n){
    ans-=(a[i]*(sum-a[i]));
  }
  cout<<ans<<endl;
  return 0;
}

D問題

D - Journey

頂点１にいる高橋君がN個の頂点にランダムに辺を張っていく場合にグラフが連結になるのに必要な操作回数の期待値を求める問題です。

この手の問題は見た目は怖いけどシンプルな問題が多く怖がらずにやろうと思いました。

最初はサンプルから計算式を考えましたがなかなか合わずにWA2連発。
ぐぐってガチャをコンプするのに必要な回数の期待値を発見してクリアーしました。
最初頂点１にいるので１引くのがポイント。

23分05秒 2WA　通算67分20秒 3WA

提出コード

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

int main(){
  int n;
  cin>>n;
  double ans=0;
  for(int i=1;i<=n;i++){
    ans+=(double)(1.0)/i;
  }
  ans*=(double)n; 
  cout<<setprecision(18)<<ans-1<<endl;
  return 0;
}

E問題

E - Mex Min

RANGE MEX MIN QUERY問題。

区間MEX問題。
こないだ齧ったセグ木に乗せて解くことを考えましたが解ききれず。
最小値ではなくMEX MINを返すにはどうしたらよいのかを思いつきませんでした。
最小値で記念提出。

いろいろな解法が考えられそうなのでじっくり考えてみます。

Dまでをもっと短い時間で解き切ることも課題だなと思いました。

感想など

いろいろ足りない部分にも気づきましたが力を出せた回となりhighestを更新できました。
実力相応の問題の精進に取り組んでいる成果を感じています。

この先に進むにはＥ問題レベルにしっかり向き合える力が必要なことを感じました。
焦ることなく一歩づつ進みたいと思います。

Codeforces 1490C

Problem - 1490C - Codeforces

Codeforcesの問題で手元環境での出力と提出結果が違ってどうしてもWAがとれないので後日の検討のためアップしておきます。

提出コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cube[10010];

int main(){
  map<long,long>mp;
  for(long long i=1;i<=10000;i++){
    cube[i]=i*i*i;
    mp[cube[i]]++;
  }
  int t;
  cin>>t;
  ll temp=0;
  string ans;
  for(int i=0;i<t;i++){
    cin>>temp;
    ans="NO";
    for(int k=1;k<=10000;k++){
      if(cube[k]>temp) break;
      if(mp[temp-cube[k]]>0){
        ans="YES";
        break;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) 参戦記

atcoder.jp

はじめに

2021年2月20日21:00-22:40に開催されたSOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) に参戦しました。

結果は29:25 3完 WAなし 4369位/8699人中でパフォーマンス654、レーティングは前回892から21下がって871になりました。

Contest Result - AtCoder

A問題

100の倍数に切り上げる問題です。
入力に100のMODをとり，100から引いて出力しました。
サンプルも確認し1分23秒で提出。

B問題

文字列が小文字・大文字の順でできているかを判定する問題。
このあたりの処理には余裕がでてきましたが丁寧にサンプルもためして提出します。
4分02秒、通算5分25秒。

C問題

難しかったというか、難しく考えすぎました。
問題自体はシンプルで実装もそんなに重たくないのですが、関数部分を丁寧に試しながら書いていて時間がかかりました。時間がかかったのは、計算量がすっと読めずに不安に感じていたのも一因だと思います。

24分　通算29分25秒で提出。

提出コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int temp;

int gf(int x){
  if(x==0) return 0;
  vector<int>g2;
  while(x){
    temp=x%10;
    g2.push_back(temp);
    x/=10;
  }
  int len=g2.size();
  sort(g2.begin(),g2.end(),greater<int>());
  int ans=0;
  //cout<<len<<endl;
  for(int i=0;i<len;i++){
    ans*=10;
    ans+=g2.at(i);
  }
  return ans;
}

int gs(int x){
  if(x==0) return 0;
  vector<int>g1;
  while(x){
    temp=x%10;
    g1.push_back(temp);
    x/=10;
  }
  int len=g1.size();
  sort(g1.begin(),g1.end());
  int ans=0;
  for(int i=0;i<len;i++){
    ans*=10;
    if(i==0 && g1.at(i)==0) continue;
    ans+=g1.at(i);
  }
  return ans;
}

int f(int x){
  return gf(x)-gs(x);
}

int main() {
  int n,k;
  cin>>n>>k;
  for(int i=0;i<k;i++){
    n=f(n);
  }
  cout<<n<<endl; 
  return 0;
}

D問題

難しかったです。
愚直に実装して２ケースでTLEになり、原因をつかみきれずに詰まりました。
あとでいろいろ試すと桁数の小さいところでTLEしていることがわかりました。
二分探索は頭をよぎりましたが本番中に実装するところまでいかず。
終了後に解説ＡＣしました。

解説で学んだこと。

・　二分探索に使う変数を(l)left,(r)rightとかでなくAC,WA,WJにするのはわかりやすくていいなと思いました。
・　文字列中の文字を順に操作する際の範囲for文　for(char c:x) 　はすっと使えるようになりたいと思いました。
・　未だにif文　else文の書き方がしっかり身についていません。必要以上に{}を多用して行が増えて読みにくいコードになってるのでシンプルに書けるよういちどしっかり押さえておきたいと思いました。
・　オーバーフローの判定は悩ましいですが解説でもだいぶ悩んでおられたので理屈をしっかり押さえるのは難しいところだと理解しました。とりあえず確実な方法をストックしておきたいと思いました。

E問題

ダイクストラで解く方法は思いつきましたが３変数を収納するデータ構造を書けないところで詰まりました。
structの使い方とか独学でやってると入門書などでも丁寧に解説されたものがあまりなくて（特にアルゴリズム本などは、そのあたりは当然に理解していることが前提の説明が多いように思います）しっかり理解できないままに来ています。これもどこかでしっかり押さえておかないと、と思いました。

終わりに

今回は冷えましたが多少冷えても茶に落ちないのは精神的に余裕があります。まずは緑安定をしっかり確保したいと思います。

パフォ654がいつのまにかだいぶ失敗したな、できなかったな、というレベルに感じられるようになったのも進歩です。

Ｄ問題、Ｅ問題いずれも実力のちょっと上にある感じで解けませんでした。
全体に参加者のレベルが高くなっていることを感じますが、５完できれば最低でも水パフォは確保できるのであり、水色が決して手の届かないところにはないことを再確認しました。

道は平たんではなく課題もたくさんありますが、道のりが見えてきた気がします。
更に考えながら精進していきたいと思います。

なお、今回は、DropBoxにおいていたライブラリが壊れて自宅環境からアクセスできないというアクシデントがありました。古いアプリを使ったデータベースだったので、これを機会に、シンプルな形に整理することを考えたいと思います。