ABC175で冷えたこと

はじめに

みなさんこんにちは。
ABC175で緑化するつもりで色変記事のドラフトまで準備して臨んだのにみごとに冷えたchacoderです。

勝ちに不思議の勝ちあり、負けに不思議の負けなし（甲子夜話）といいます。
失敗の背景には必ずその原因があるので、冷えた回こそしっかり振り返りたいと思います。

コンテスト経過

コンテスト経過

成績表

３完６ペナで８８１２人中の５１７５位、パフォーマンスは５１８でした。
前回レートから２４さがって７４９になりました。

コンテスト中の感想

A問題

A問題はA問題にしては少し大変だなと思いました。
２種類３文字の組み合わせで高々８通りなのでさっさと手を動かして全部書き出す方針でのぞみました。

途中でちょっと工夫する気になり３日の場合、２日の場合、０の場合を書いて残りを１にする、という方針に切り替えましたが、何も考えずにそのまま実装した方がかえって早かったかも知れません。

最初は、３日のうち何日降ったかという問題と誤読しており、テストケースでWAを出して連続して雨が降る日を聞かれているのに気づきました。

AB問題あたりでつまらないミスをしてペナルティをはやすことがよくあったので、しっかり確認して提出しました。

提出タイム４分５６秒。

#include <bits/stdc++.h>
using namespace std;
 
int main(){
  string S;
  cin>>S;
  if(S=="RRR"){
    cout<<3<<endl;
    return 0;
  }
  if(S=="RRS"||S=="SRR"){
    cout<<2<<endl;
    return 0;
  }
  if(S=="SSS"){
    cout<<0<<endl;
    return 0;
  }
  cout<<1<<endl;
  return 0;
}

B問題

B問題は見覚えある問題です。

ｎ本の棒の長さが与えられ、つくれる三角形の組み合わせの数を求める問題です。
蟻本のウォーミングアップ問題に類題があります。

ループを回すときに起点を１つづつ増やすのがコツです。

三角形をつくる条件はある辺の長さが他の２辺の和より短いこと、この問題特有の条件として等しい辺を持たないこと、の２つのケースはカウント処理をする前にcontinueして飛ばします。

  int cnt=0;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      for(int k=j+1;k<n;k++){
        if(A[i]==A[j]||A[j]==A[k]||A[i]==A[k])continue;
        if(A[i]+A[j]<=A[k]||A[i]+A[k]<=A[j]||A[j]+A[k]<=A[i])continue;
        //cout<<i+1<<" "<<j+1<<" "<<k+1<<endl;
        cnt++;
      }
    }
  }

この問題もB問題としては難しめかと思いましたが、最近のABCではこのレベルの問題はみんなすらすら解いてくるように思います。

最初、比較を配列の要素でするのを添え字のまま比較してしまって少しもたつきました。
上のコードの中のcoutデバッグはそれを発見したときのものです。

//cout<<i+1<<" "<<j+1<<" "<<k+1<<endl;

これもテストケースを全部確認して提出。

提出タイム１５分５０秒。

B問題で１１分近く使ってますが、前述のもたつきで５分近くロスしており、丁寧にやっても、もう少し短縮できたと思います。

C問題

C - Walking Takahashi

数直線の上をうごく問題です。

問題文自体はわかりやすく、動きのイメージもすぐつかめました。
最終的な座標の絶対値の最小を聞かれているので正の場合と負の場合をしっかり分けて考えなければ、と思いました。
算数問題のカテゴリーだと思います。

解説や強い人のコードをみると、最初の入力を受けた時点で絶対値(abs）をとって正にして処理しており、なるほどと思いました。
これも一つの定石なのでしょう。

方針は、まずK回の操作で原点に達するかどうかを確認し、達しない場合は、K回分近づいた位置の絶対値を出力、達する場合は、その後は原点をまたぐ距離Dの２つの座標を繰り返す反復横跳びになるので、（原点までの距離をDでわった数）とＫの偶奇の比較でいずれかの座標を出力することにしました。

この方針で正しかったのですが、実装してみるとなかなかWAがとれずWAを重ねてしまいました。

１時間以上悩んでようやくわかったのは、負の数を割った余りが負になる、ということです。
偶奇の比較をするのに（原点までの距離をDでわった数）の剰余ー１とＫの剰余１を違う数と判定してＷＡになっていました。

この手の分岐のときは省力化のためelseのときには評価文を置かずに書く（else if((X/D)%2!=K%2としない）ことが多いのですが、しっかりelse の場合も評価を入れておけばすぐにエラーに気づけたと思います。

提出時間９６分０５秒と終了間際でした。

最後に気づいたからまだ傷は浅かったのですが、気づかないまま終わっていたら更に冷えてました（２完１５分５０秒の推定パフォは４０９　Ｃが遅すぎたため思ったほど低くもない）。

はまらずにスムーズに書けたとすれば４０分ぐらいまでには出せたと思うのでＤ問題以下に１時間残すことができたと思います。

Ｄ問題

Ｄ問題はＣ問題でバグりまくっているときに問題文を読みました。ぱっと方針を思いついたらＣ問題を棄ててとりくもうと思ってましたが、複雑そうなので解決間近と思っていたＣを解き切ることにかけました。

Ε問題

コンテスト終了後、TLでE問題が簡単という噂を目にして解いてみました。
１時間ほどかかりましたがほぼ自力で解くことができました。

初めてAGCで解けた問題と同じようなDP処理でした。

A - Range Flip Find Route

１行中に３つまで、というところで今何個まで持っているかという数を保持しながらDPを組みました。

コードテストでは通ったのにジャッジでランタイムエラーになるのがわからず、TLでつぶやいてみたところ、巨大な配列を宣言するときはグローバルにおくとよい、というアドバイスをいただきACできました。

冷えにこそ成長の糧あり

竹は節があるから強いのだといいます。
失敗やスランプで冷えたときにこそ、実力をつける機会だと思います。

あなたがたの会った試練はみな人の知らないものではありません。神は真実な方ですから、あなたがたを耐えられないほどの試練に会わせることはなさいません。むしろ、耐えられるように、試練とともに脱出の道も備えてくださいます。（コリント人への手紙 第一 10章13節)

最後までお読みいただきありがとうございました。