ARC034備忘録初めてのARC

はじめに
A問題
B問題(解けなかったので簡単な振り返り)
まとめ

はじめに

バイト疲れのため最初の1時間寝てました、なのでギリギリに書いたコードになります……という言い訳を書いておきます。

A問題

※提出したコードは上記のリンクから辿れます。

先ほどの事情により急いで書いた為少々汚い部分があったので説明の為比較的綺麗なコードに直しました。


       #include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int main() {
  int n, a, b, c, d;
  cin >> n >> a >> b >> c >> d;
  char s[n];
  // Aがゴールのパターン、Bがゴールのパターン
  bool flag = true;

  for (int i = 1; i <= n; i++) {
    cin >> s[i];

    //岩が二連続のパターン
    if (i >= a && i <= max(c, d)) {
      if (s[i] == '#' && s[i] == s[i - 1]) flag = false;
    }
  }

  // c>dならb動かしてa動かして終わり
  if (d < c) {
    for (int i = b; i <= d; i++) {

      //途中に3つ空きがあればtrue、無ければ追い越せないのでfalse
       if (s[i]==s[i + 1] && s[i]==s[i - 1] && s[i]=='.' ) {
         flag=true; break;
       }else{
         flag=false;
       }
  }

  if (flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}

まず、範囲内に岩が二連続である場合は強制的に失敗です。これは入力時に確認できるのでさっさとやっちゃいましょう。

そして、Aの到着地点よりBの到着地点が後ならこれもBを先にゴールさせてAをその後にゴールさせれば良いので終わります。

ここまでは多分良いとして、おそらくつまづくのは追い越しのパターン、つまりD < Cですね。まずは図にして考えます。

a---------b------d---------c (-は岩(#)か道(.)のどちらか)

岩が二連続のパターンは既に判定しているので、調べる範囲はb~dの間であることがわかります。

どういった場合に追い越せなくなるかということを考えると、常に2マス先までBと岩で埋まっている時になります。……逆に言えば、一瞬でもそうじゃない状態があるかどうかを判定すればOKです。

..#...#..#..#..#..#『A B .』#.....#...#..#.

そこで、AとBを動かして考えましょう。注目するのは『』の部分。

こんな感じに、隣接するスペース、B、その次の地面……というスペースが存在する事が追い越せる条件になるので、3連続の空きマスがあるかどうかを判定してみればOKです。

B問題

ABC

説明簡略化のため、解説通りにBCをDに置き換えて説明します。

まず,AAAAAAAADみたいなパターンだとAの数だけ変換されます。

次に、AAAADAAADAD……というパターンですが、太文字の部分に注目しましょう。この部分は、DAAAAとなってAの数だけカウントされます。

その操作後には、DAAAAAADADとなるので、二つ目のDは一つ目の『AAAAD』と『AAAD』のAの数の合計が操作回数になります。

つまり、ある一つのDに対しては、その前のAの数を数えればそのDに関わる全ての操作回数になります。あとはこの和を求めていきましょう。

ただし、ここで注意すべきこととして例えば20万文字中にAが10万個、Dが5万個(元がBCなので)の場合50000*100000 > 2*10^9(おおよそint型の範囲)　を超えてしまうので、答えの値はlongなど大きい範囲の数値を扱えるものにしておいてください。

まとめ

寝坊という盛大なガバについては言及しません。

とりあえず、競プロを初めて2ヶ月……C++の文法をあまり知らない状態から400点問題が普通に解けるようになったのは嬉しいです。

この前日の企業コンテストでまさかの500点問題……B問題の文を勘違いしてミスり、さらにCの高校数学（後半の条件で?マーク）、D問題には実装についてはまだあまり詳しくない木構造が出て虐殺されたばかりだったので、反動で嬉しくなって更新しました。

今回のB問題も解説を見てある程度まで大体理解できるようになったので、実力はついたと思いたいです……実装力は無いですが。ですので競プロ界隈の巷では有名なプログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (通称:螺旋本)を購入しました。

Atcoderで滝のように浴びるにしても知識が足りずにどうしようも無い物も多く、どうすべきか迷ってたのですが、そもそも基礎が足りて無いのでしばらくはAOJのコースリスト埋めに走るかもしれません。有名なqiita記事のAtcoder版蟻本初級編でもやろうと思ったのですが（超おすすめ記事です）蟻本が図書館から借りたものなので現在家に無いのです、悲しい。

前の記事でAtcoder頑張るって書いた気がするのにAOJに浮気してますがまあそれはいつものことです、うん（同じ競プロなのでセーフ）

ARC034備忘録 初めてのARC

はじめに

A問題

B問題

まとめ

ARC034備忘録初めてのARC