ABC-C第14弾

<img width="884" alt="result.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/7769928d-a36e-6fbe-7d81-a3c96ee6725e.png">




- [バチャ第14弾](https://not-522.appspot.com/contest/5333048082038784)





# ABC066 「[pushpush](https://beta.atcoder.jp/contests/abc066/tasks/arc077_a)」

## 考察と解法

- 毎回文字を追加して反転すると$O(N^2)$で間に合わない
- そこで、どんなふうに追加されていくかの図を描くと、「後ろに追加、前に追加」を繰り返していけばいいことが分かる。
- 最後に、操作回数が偶数回ならそのままの、奇数回なら反転した文字列を表示させる。



## [コード](https://beta.atcoder.jp/contests/abc066/submissions/2436074)

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

int main() {
   int n;
   cin >> n;
   deque<int> v;
   for (int i = 0; i < n; i++) {
      int a;
      cin >> a;
      if (i % 2 == 0) {
         v.push_back(a);
      } else {
         v.push_front(a);
      }
   }

   if (n&1) reverse(v.begin(), v.end());

   for (int i = 0; i < n-1; i++) {
      cout << v[i] << " ";
   }
   cout << v[n-1] << endl;


   return 0;
}
```



### めも

- C++の`deque`は`vector`とほとんど同じ機能で、使い方も大体同じ。
- `deque`は`vector`と違って先頭に要素を追加したりできるので便利
- めったに使わないから存在を忘れがち



# ABC067 「[Splitting Pile](https://beta.atcoder.jp/contests/abc067/tasks/arc078_a)」

## 考察と解法

- すぬけくんの得点は要素0から累積和をとっていったものになる。アライグマの得点は合計ーすぬけくんの得点となる。
- これを最小化するだけ



## [コード](https://beta.atcoder.jp/contests/abc067/submissions/2436102)

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

using ll = long long;

int n;
ll a[222222];

int main() {
   cin >> n;
   ll sum = 0;
   for (int i = 0; i < n; i++) {
      cin >> a[i];
      sum += a[i];
   }

   ll ans = 1e16;
   ll rui = 0; // すぬけ君の得点
   for (int i = 0; i < n-1; i++) {
      rui += a[i];
      ll b = sum - rui; // アライグマの得
      ans = min(ans, abs(rui - b));
   }

   cout << ans << endl;

   return 0;
}
```





# ABC068 「[Cat Snuke and a Voyage](https://beta.atcoder.jp/contests/abc068/tasks/arc079_a)」

## 解法

- 辺を張ってダイクストラ法をつかう
- 始点からNまでの距離が2ならOK



## [コード](https://beta.atcoder.jp/contests/abc068/submissions/2436167)

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

struct edge { int to, cost; };
typedef pair<int, int> P; // firstは最短距離、secondは頂点の番号

const int VV = 222222;
const int INF = 1e8;
int V, M;
vector<edge> G[VV];
int d[VV];

void dijkstra(int s) {
   // 最短距離firstが小さい順に取り出せるようにする
   priority_queue<P, vector<P>, greater<P>> que;
   fill(d, d + V, INF); // 距離全てをINFで初期化
   d[s] = 0; // スタート地点を0で初期化
   que.push(P(0, s)); // キューに初期位置のコスト、初期位置をpush

   while (que.size()) {
      P p = que.top(); que.pop(); // p: 今の{最短距離、頂点番号}
      int v = p.second; // 今の頂点番号
      if (d[v] < p.first) continue; // 今見ている頂点の歴代最小距離 < 今見ている頂点の最短距離
      for (int i = 0; i < G[v].size(); i++) { // 今の頂点に隣接する頂点を調べる
         edge e = G[v][i];
         if (d[e.to] > d[v] + e.cost) { // 遷移先の頂点の歴代最小距離 > 今の距離 + 遷移コスト
            d[e.to] = d[v] + e.cost; // 歴代最小距離の更新
            que.push(P(d[e.to], e.to)); // 更新した遷移先の頂点をキューに突っ込む
         }
      }
   }
}

int main() {
   cin >> V >> M;
   for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a--, b--;
      G[a].push_back({b, 1});
      G[b].push_back({a, 1});
   }

   dijkstra(0);

   if (d[V-1] == 2) {
      puts("POSSIBLE");
   } else {
      puts("IMPOSSIBLE");
   }

   return 0;
}
```



## 別解

- 1→X→Nという順をたどればいい。つまり、1とNを中継するXが分かればいい。なので、1からもNからも行ける島があれば`POSSIBLE`そうでなければ`IMPOSSIBLE`となる。
- これは配列とか連想配列で解ける

### [連想配列のコード](https://beta.atcoder.jp/contests/abc068/submissions/2436191)

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

int main() {
   int N, M;
   cin >> N >> M;
   map<int, int> mp;
   for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      if (a > b) swap(a, b);
      if (a == 1) mp[b]++;
      if (b == N) mp[a]++;
   }

   for (auto x : mp) {
      if (x.second >= 2) {
         puts("POSSIBLE");
         return 0;
      }
   }

   puts("IMPOSSIBLE");

   return 0;
}
```

- ちなみに、[配列のコード](https://beta.atcoder.jp/contests/abc068/submissions/2436208)



## 感想

- **中継点を考えるみたいな問題が結構多い気がするので大事な考え方なのかもしれない。**
- 中継点を求めるというより、一番簡単な方法を思いつくちから？



# ABC069 「[4-adjacent](https://beta.atcoder.jp/contests/abc069/tasks/arc080_a)」

## 考察

- 隣り合う数の積が4の倍数になる場合を考える。
- 積が4の倍数になる数は、もともと4の倍数の数の数以外に、2の倍数を2つ並べた時がある。
- 便宜上、4の倍数を4、4の倍数でない2の倍数を2、それ以外の数を1と呼ぶことにする。
- 4の倍数を有効に使うためには、1414みたいな並び方がいいと分かる。1144みたいにしたら条件を満たさなくなってしまう。
- 2を2つ並べると4の倍数になる。2を1212みたいに並べても意味がないため、2は連続して2222みたいに並べるのがいいと分かる。
- なので、最終的には222141414みたいな並び方にすればいいことが分かる。
- 2があるとちょっと考えにくいので、1と4のみの場合を考えてみる。
- ギリギリ大丈夫なケースを考えると、14141のように1の個数が4の個数より1つ多いときとなる。。つまり、1と4のみのとき、$1の個数 \leq 4の個数+1$ならYes、そうでなければNoとなる。
- 次に、2がある場合について考える。2はひとまとまりにして222214みたいに置く。
- すると、以下の画像のように最後の2が1つ余る。あまった2は、1と同じ役割となってしまう。つまり、数列中に2がある場合、それは1が余計に1つ増えたことを意味する。つまり、2222111みたいな数列は1111という数列に置き換えられる。よって1と4のみのときの式を少しいじって、$1の個数+1 \leq 4の個数+1$ならYes、そうでなければNoとなる。式を簡単にすると、$1の個数 \leq 4の個数$ならYes、そうでなければNoとなる。


<img width="186" alt="a.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/a864c7c7-448c-2bf5-f89f-36515309432d.png">




## 解法

- 数列中に2が無い場合
  - $1の個数+1 \leq 4の個数$ならYesそうでないならNoを出力する
- 数列中に2がある場合
  - $1の個数 \leq 4の個数$ならYes、そうでないならNoを出力する



## [コード](https://beta.atcoder.jp/contests/abc069/submissions/2436483)

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

int main() {
   int n;
   cin >> n;
   int four = 0, two = 0, one = 0;
   for (int i = 0; i < n; i++) {
      int a; cin >> a;
      if (a % 4 == 0) {
         four++;
      } else if (a % 2 == 0) {
         two++;
      } else {
         one++;
      }
   }

   if (two) {
      if (one <= four) {
         puts("Yes");
      } else {
         puts("No");
      }
   } else {
      if (one <= four+1) {
         puts("Yes");
      } else{
         puts("No");
      }
   }

   return 0;
}
```



## 感想

- 公式PDFには、「2が存在しない場合を考えます」って書いてあった。2が存在しない場合を考えると確かに楽だけど、普通に思いつかない。この思考は当たり前ですよ、みたいなのは傷付く...
- 今回は、2があると考えにくいからいったん取り除いて考えた。こんな感じに、**条件を簡単にして問題を単純にとらえる**みたいな考え方は大事な気がする。まあ、本番中に思いつくのは結構むずそうだけど...




# ABC070 「[Multiple Clocks](https://beta.atcoder.jp/contests/abc070/tasks/abc070_c)」

## 解法

- 最小公倍数を求めればいいだけというのはすぐにわかる。
- 計算方法は解説に書いてある



## [コード](https://beta.atcoder.jp/contests/abc070/submissions/2436296)

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

using ll = long long;
ll gcd(ll a, ll b) {
   if (b == 0) return a;
   return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
   return a / gcd(a, b) * b;
}

int main() {
   int n;
   cin >> n;
   ll ans = 1;
   for (int i = 0; i < n; i++) {
      ll t;
      cin >> t;
      ans = lcm(ans, t);
   }

   cout << ans << endl;

   return 0;
}
```



## 感想

- GCDとLCMの求め方をすっかり忘れてしまっていたのでググって調べた。