AtCoder ABC282

またも3完。2回連続5完は夢だったのか？

 

A - Generalized ABC

B - Let's Get a Perfect Score

C - String Delimiter

B問題で凡ミスしてC問題ACまで13分。

 

D - Make Bipartite 2

  1. 二部グラフでググって、Union-Findを使った実装を取ってくる
  2. 木のルートとサイズのmapを作る
  3. mapのサイズが2なら、B*W-Mが答え。
  4. これでAC27、WE20
  5. 木のサイズを64bitに変更でAC29、WE18
  6. 後のWE18はassert()でチェックするに木が4より多い。どういうことだ？

解説を読んでも、木が4より多い（二部グラフが2より多い）問題で答えが0にならない理由がわからなかったが、

おそらく二部グラフA、B、Cがあって、AとBをつなぎ、AB、Cという状態でも問題の条件が満たされる。

 

ちなみに、解説にある式で二部グラフが1つの場合

N(N-1)/2 - B(B-1)/2 - W(W-1)/2 - M

は、上記のB*W-Mと一致する（W=N-Bなので）。

しかし二部グラフが1より多い場合に計算するなら、解説の方の式でないと式を求めることが非常に困難。

 

E - Choose Two and Eat One

  1. i, jに対するA_i^A_j+A_j^A_i (mod M)はatcoder/modintを用いてあらかじめtable[509][509]に求めておく。
  2. その中から、条件を満たしつつ和が最大になるようにN-1個を選ぶ。

2の条件を満たしつつの部分を全探索すると500!でもちろん間に合わない。

DPかと思ったが、解説を読むと最大全域木だった。

 

 

AtCoder ABC301

またも3完。緑に上がった。

 

A - Count Down

B - Sandwich Number

C - Circular Playlist

今回も簡単だった。Bluetoothキーボードの不調がなければ3問10分は余裕で切っていたであろう。問題の難易度に差がありすぎでは。

 

D - Max Multiple

N = K = D = 100
なので三次元探索、DPなのは予想がついていたが、すぐには思いつかず、
あと一歩のE問題に時間を取られて、解けず。

 

本番後に30分程考えて、とりあえず二次元のDPを実装するもAC10、TLE19。

・N, Dのループ

・vector<pair<int, long long>>で手数と最大値を保持

 

結局、解説が三次元のDPなのを確認し、DPを考えてAC。
到達できないところ
    -1で初期化しておいて、-1であれば使わない
    A_iの総和より多きい-10^9*109で初期化しておいて、max()の作用で落としていく
のどちらでもACできる。
負の大きい数で初期化する方法は計算中には条件分岐しなくて便利だが、
最後はできない場合-1を表示しなければならないので、負の数なら-1を表示するという条件分岐が必要。

 

E - Least Elements

M個の数のうち、小さいK個を入れておくs_smallと、大きいM-K個を入れておくs_bigを用意し、
古いA_iをどちらかから消去し、新しいA_M+iをどちらかにつっこんでいく。セット間で移動も起きる。

・値に重複があるのでsetではなくmultisetを使用し、erase(値）ではなくerase(イテレータ)で一つだけ消去する必要がある。

・Nループの中でlog(最大M)の操作（erase(), insert()）を行うので、O(N log(M))

 

本番中は、AC20、TLE1で一時間どはまり。

K = 1やM = K = 1でmutlisetが空になった時の処理を加えて、やっとAC。

 

AtCoder ABC300

3完。敗北すぎる。かろうじて緑パフォーマンスで、レーティングは茶色のまま。

 

A - Pawn on a Grid

B - Inverse Prefix Sum

C - Extra Character

簡単すぎて合わせて10分以内。このことがDでの油断を誘うことに。

 

D - Factorial and Multiple

結局解けなかった。

  1. 素因数と個数をmapにつっこむ
  2. 各素因数に対して、個数が消費される値を計算。7が3個なら、7 14 21なので21。
  3. その中で一番大きい値がN

で組んだがACの方が少ない。解説見る前に明日すっきりした頭でもう一度考えよう。

 

E - Crystal Switches

苦手なmod問題のためスキップ。atcoderlib modintの使い方を早く覚えなければ。

【競プロライブラリ】mint(modint)で学ぶC++ - Qiita

「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita

  • 多倍長整数を素で扱えない言語（C++とか）に対する不公平さをなくすため。
  • 998244353に10^9に近い素数という以上の意味はないようだ。
  • 足し算、掛け算などは後からmodでも、式の途中でmodでも結果が変わらない。
  • 引き算はマイナスをプラスに直す処理が必要。
  • 割り算だけややこしい。逆元を求める。逆元の存在が、pとmが互いに素なこととあるので、このために素数を指定しているもよう。
  • 足し算等なら自分で書けばいいが、割り算が面倒なのでatcoderlib modintを使うべき。
  • modint998244353などが容易されていてべんり。

 

F - Pay or Receive

解説を読んだが、かなり近いところまで迫ってはいた。

考察

  • N, M, Q ~ 10^5。ダイクストラと違って負のコストが扱え、閉路が検出できる（と鉄則本で復習した）Bellman-FordはO(NM)×クエリー数Qなので全然無理そう。Warshall-FloydもO(N^3)なので全然無理。
  • Union-Find（DSU）でつながっていない判定はできる。root()がO(logN)なので計算量的にもこれっぽい。
  • 閉ループは0なら問題。0以外ならどちか回りで必ずinf。

ここに、graph[N+1][]とdist[N+1]で探索を加えればよかったのか。

あとlong long int の上限に近いINFはlong long int INF = 2LL << 60;とLLが必要。

 

 

AtCoder ABC278

今回のABC278では5完を取れた。勉強の成果を感じる。

 

ABC278

A - Shift

単純実装問題。

 

B - Misjudge the Time

入力時刻から＋1440分まで紛らわしい時刻があるか探索。

 

C - FF

  1. T=1の場合、pair(A,B)をmapにinsert
  2. T=2の場合、pair(A,B)をmapからerase
  3. T=3の場合、mapからpair(A,B)とpair(B,A)をfindして両方あれば、Yes。それ以外はNo。

 

D - All Assign Point Add

vector<int>(N)に値を保持し、クエリを処理して行くとTLE。各処理を以下のように言い換える。まず、map<int, int> mに初期値を持っておく。

  1. x_qの値をallに保持。mに空mapを代入。
  2. m[i_q] += x_q
  3. all+m[i_q]を出力

 

E - Grid Filling

単純にH-h * W-w * H * Wの4重ループで探索すると当然TLE。問題文から、H * W * N = 300 * 300 * 300は可能そうなので、最初に数字ごとにこの領域をカバーされちゃうと画面から消えますよという領域を計算しておき（O(HW)）、その後H-h * W-w * Nの3重ループで探索。

 

緑パフォーマンス（1100）出たので一安心。レーティングはまだ灰色。

 

AtCoder ABC278 に向けた練習

ABC277でAB2完という惨敗を喫したので、ABC278に向けた練習（2022/11/19（土）より前の話）

 

大槻兼資「アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門 単行本」 – 2022/8/1

の中級編の問題をやってみる。

 

ABC085C - Otoshidama

ABC085B - Kagami Mochi

は以下でも取り上げられていたのですでに終了済み。

qiita.com

ABC137C - Green Bin

アナグラム問題。文字列s1をソートしたものと文字列s2をソートしたものが一致すればアナグラム。mapで重複を数え、その組み合わせの数n(n+1)/2を出力。

 

PAST1F F - DoubleCamelCase Sort

PAST問題に行くには、AtCoder公式より

https://kenkoooo.com/atcoder/#/table

のPASTタブを見たほうが早い。

 

単純実装問題。一つの文字列から切り出してソートする。文字列を識別するのが先頭と末尾が大文字なことなので、その条件で切り出し、小文字に変換してソート、先頭と末尾を大文字に戻して出力。

 

PAST3E E - Sprinklers

単純実装問題。グラフをvector<vector<int>> graph(N+1);で保持して、クエリを処理していく。

 

ABC122 C - GeT AC

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


int main() {
  int N, Q;
  string s;
  cin >> N >> Q >> s;
  vector<int> v(N);
  int cnt = 0;
  for(int i = 1; i < N; i++){
    if(s[i-1] == 'A' && s[i] == 'C'){
      cnt++;
    }
    v[i] = cnt;
  }
  for(int i = 0; i < Q; i++){
    int L, R;
    cin >> L >> R;
    cout << v[R-1] - v[L-1] << endl;
  }
}

でACだったが、本の解説と累積和の取り方がずれている気がする。

 

AGC024 A - Fairness

AtCoder Grand Contest (AGC)でもAは結構簡単なのか。AGCの問題も、AtCoder ProblemsからAGCタブを選ぶのが早い。

高橋君の値をA、中橋君の値をBとしたときに、偶奇でA-BかB-Aを出力するだけ。答えの絶対値が10^18を超える場合Unfairを出力せよとあるが、そんな場合はない。

パリティ問題と呼ばれている。

ABC086 C - Traveling

ACした記憶があって、AtCoder ProblemsではACになっているが、AtCoderにはない。そんな不思議なお話。

マンハッタン移動の問題。パリティ問題らしい。時間の差分、xの差分、yの差分で、時間が間に合ってかつ時間と距離のパリティが一致すれば移動可能というもの。時間の差分、距離の差分で探索しても間に合ってACだった。

ABC125 D - Flipping Signs

言い換え問題と呼ばれている。問題を如何に簡単な問題に言い換えるかが非常に重要なことが本の5.9で解説されている。競技プログラミングにかなり重要な要素だと思う。

偶数個のマイナスは消せるのですべてプラスになり、マイナスが奇数個の場合に絶対値が最小になる数のみにマイナスをつけて、和を取る問題に帰着できる。

 

AGC030 A - Poisonous Cookies

ペアリングの例題（p. 232）。

算数問題。毒入りの美味しいクッキーC枚中、何枚食べれるかをcとすると、最後に毒入りのクッキーを食べて不調のまま終わってもよいから、cはA+B+1かCの小さい方。よって答えはB+c。

diverta 2019 Programming Contest C C - AB Substrings

AtCoder ProgramsのARC-Likeタブの、DIVERTA2019（DIVERTA2019-2じゃない方）。

 

算数問題。初サブミットで48問中46ACから、WAを抜け出せなかった私に以下の解説が響く。

少し考えただけでも大変複雑な問題であることがわかります。なるべく多くの"AB"が生成されるように考えたつもりでも、考え抜けがあるかもしれません。このような問題への1つのアプローチとしては、いろんな場合を試してみて、もっともらしい答えが見出せたらそれをコーディングして提出することが考えられます。場当たり的に説いたとしても、何度もWA判定を受けながら試行錯誤して最終的にACがとれるかもしれません。しかし、確実に一発でACをとりたいならば、「上界を見積もる」という方法が有効です。

 

この本は素晴らしい本だ。

大槻兼資「アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門 単行本」 – 2022/8/1

 

 

AtCoder ABC277 (2)

本番で解けなかった問題を解いてみる。

atcoder.jp

D問題（44分）
  1. カードの数字はmod Mした数字とみなす（M=20なら21は1と同じ）→そもそも数字はMより小さい
  2. 連続した数値のカードを塊とする（3 4 5 5 6と7 7 8は別の塊）
  3. それぞれの塊の合計値を求める。合計値が最大の塊を除いたカードの合計値が答え。
  4. ただし、M=20の時19と0は連続できることに注意。

で解ける。1は勘違いで、M以上の数字が書かれていると上の方法で解けない（M=20の場合に35から16につながったり、合計値を求める時に数値がmod Mしていると変になる）。

E問題（40分）
  1. あるノードでスイッチを押すことは、そのノードで表世界と裏世界を移動することに相当する
  2. a=1の場合には表世界のグラフでつながる。
  3. a=0の場合には裏世界のグラフでつながる。
  4. 表と裏と言っているが、表のノード番号＋Nを裏のノード番号にするなどで大丈夫

と考えて問題変換すると、

  1. a=1の場合、uとvはコスト1の枝でつながっている。
  2. a=0の場合、u+Nとv+Nはコスト1の枝でつながっている。
  3. スイッチがuにあれば、uとu+Nはコスト0の枝でつながっている。

グラフの最短経路問題（1からN）として解ける。

C++ダイクストラで検索し、priority_queueを使った関数を拝借して解く。

今後の改善点

  • 自前でグラフ理論のライブラリを用意。
  • priority_queueの使い方。
  • struct edge{int to; int cost;};を簡単に初期化する方法→edge e{3, 5}。コンストラクタ書かなくてもedge e(3, 5)も動くみたい。

 

AtCoder ABC277

当面の目標

  1. 競技プログラミングに復帰する
  2. AtCoder Beginner Contest を半年続ける
  3. ブログに感想を書く

久々に競技プログラミングに復帰しようと思い、ABC 277に参加した。結果は2問。CのTLEがどうしても消えず、ABのみ。なかなかの惨敗である。

atcoder.jp

A問題、B問題

事前準備として、ABは何問か解いており、BはAより一段難易度が上がったように感じ最初中々解けずにいたが、実はそんなに難しくないということに気づいてから連続でぱぱっと解けるようになった。本番でも二つで10分はかかっていない。

 

C問題

梯子の数N=10^5と、階数A,B=10^9がある

  1. 梯子は両方向に移動できる
  2. 1階からどこにも行けないパターンもある

ぐらいの注意点でWAは消えた。

  1. 最初は再帰で探索→TLE
  2. メモ化（一度探索したところは探索しない）→TLE
  3. 再帰を諦め、バブルソートのようにNの二重ループで、梯子の両側の階から行ける最大の階を更新していく方式に。（階、最大の階）にmapのfindを使っているので、N^2 log(N)ぐらい？→TLE
  4. 階数は疎（スパース）なので、最大2Nの連続した整数に変換できる。（階、最大の階）の保持と検索にvectorとO(1)を使えるので、N^2→TLE

ここで心折れる。ABCへの参加は初めてだが、C問題からすでに計算量を考えてアルゴリズムを組まないと行けないのか？C++なのに。次回までにこれのC問題もやって感触をつかまなければ。

qiita.com