naoya_t@hatenablog

いわゆるチラシノウラであります

〈AGC埋め〉A問題集中アタック (AGC022 - 001)

AGCのほうも不参加回を埋めていきたい。

自分のレベルでは練習のためにやるべきはC(3問目)なんだけど、エンジンがなかなかかからないのでAの早解き練習でお茶を濁す

(6/13 0:42am completed)

6月9日

AGC 022 A - Diverse Word (300)

next_permutationで…だけじゃ駄目か。
・長さが25までなら一番若い未使用文字をpush_backしたやつ
・長さ26ならnext_permutationして、0なら-1を返す。そうでなければ元の文字列と照合し、前と異なる最初の文字まで拾ってその後ろを切り捨てたやつ
→AC 8'35
https://beta.atcoder.jp/contests/agc022/submissions/2638592

解説より

解説の説明、next_permutationの原理みたいな話だよね。(前に一度自分で書いてみたことがあったけどもうすっかり忘れている)

AGC 021 A - Digit Sum 2 (300)

・「上からk-1桁目までそのままで、k桁目を-1してその後を9999にしたやつ」を桁数分見てその最大値。k桁目が0のところは飛ばす。
→AC 10'07
https://beta.atcoder.jp/contests/agc021/submissions/2638622

AGC 020 A - Move and Win

・敵に背を向けたら負ける
・AとBの間の最後の1駒を取ったほうが勝つ。間にスペースがなければ取れなくて先手必敗。
・Drawなんてない
→AC 6'06
https://beta.atcoder.jp/contests/agc020/submissions/2638642

6月10日

AGC 016 A - Shrinking (300)

最終的にどの文字に落ち着くか、a〜zの26通りそれぞれを仮定して、その文字かそれ以外かに収束させていく
毎回引数を参照渡ししていたせいで、前より短くなった(&前の文字に収束させようとした)文字列に対して処理をしていて答えが合わない!というバグと闘ってた.

→AC 14'21''
https://beta.atcoder.jp/contests/agc016/submissions/2643381

AGC 015 A - A+...+B Problem (200)

A>Bな入力があるのは問題として気持ち悪いな
まあサンプルケースを見て忖度して
→AC 4'59''
https://beta.atcoder.jp/contests/agc015/submissions/2643427

AGC 014 A - Cookie Exchanges (300)

シミュレーション
・a,b,cのどれかが奇数になったらそこまでの回数を表示して終わり
・a=b=cになったら-1を表示して終わり
→AC 7'53''
https://beta.atcoder.jp/contests/agc014/submissions/2643484

解説より

解説解も愚直なシミュレーションだけど、max(a,b,c) - min(a,b,c)が毎回半分ずつになっていくから、高々log_2 M回の操作で収束するという話。多分大丈夫でしょと思ってやったけど、そういうのがパッと浮かぶと安心感がある。

6月12日

AGC A埋め

AGC 001 A - BBQ Easy (200)

長い順に2本ずつペアを作って、ペアの中で2番目に長いやつ(あるいは長い順リストで偶数番目に来るやつ)の合計。
サンプルケースで数あわないなあと思ってたら問題ちゃんと読んでなかった(N本じゃなくて2N本だった)
直して
→AC 4'29
https://beta.atcoder.jp/contests/agc001/submissions/2660202

AGC 002 A - Range Product (200)

どちらかが0、または a<0<b → Zero
0<a<b → Positive
a<b<0 → (b-a+1)が奇数ならNegative,偶数ならPositive
→AC 6'38
https://beta.atcoder.jp/contests/agc002/submissions/2660257
取りこぼしがないか慎重に考えすぎた

AGC 003 A - Wanna go back home (200)

・NとSのどちらかだけが存在する
・EとWのどちらかだけが存在する
というケースでNo
それ以外はYes
→AC 3'57
https://beta.atcoder.jp/contests/agc003/submissions/2660306

AGC 004 A - Divide a Cuboid (200)

A,B,Cどれか1つでも偶数があれば0
なければAB,BC,CAの最小値
→WA(2) 3'22
ああ、せっかくsolve()の中でlong longで計算した値をintで返してるわ
(なぜそういうミスを防ぐためにテンプレで ll solve() としてるのにintに書き直した)
→AC 7'13''+penalty(2)
https://beta.atcoder.jp/contests/agc004/submissions/2660388

AGC 005 A - STring (300)

頭から見て行って、Sが来たら+1,Tが来たら-1、みたいな事してって、負の状態でTが来たら(それより前にSはないので)カウント++(した後±0リセット)、みたいに数えればよいのでは?
あれ、サンプルあわないぞ…もうちょいちゃんとやらないと駄目か
まずRLEで圧縮して…後ろからペアを詰めていくか
いやSTSTST...とか10万文字来たらTLEしないかそれ…双方向リストとかしないと駄目?
...
いや待てよ、最初のコード、取りこぼすTの数しか見てないし。Sも同数残るはずだから2倍にして返せば合うのでは
それだ
→AC 12'19
https://beta.atcoder.jp/contests/agc005/submissions/2660476

解説より

ああースタックに積めばいいだけじゃん

AGC 006 A - Prefix and Suffix (200)

sのsuffix と tのprefix が最長何文字マッチするか総当たり
で(2N - 何文字マッチしたか)が答え。
計算あわないあわないと思ってたら、マッチした文字数じゃなくてマッチしたかどうかのフラグ(0 or 1)を引いてた…
→AC 6'19
https://beta.atcoder.jp/contests/agc006/submissions/2660530


AGC 007 A - Shik and Stone (200)

右か下にしか進めないなら、必ず(H-1)+(W-1)手で右下に到達する。
最大でも(8-1)+(8-1)=14手。
そのうち(W-1)=7手が右に進む手なので、14C7通りのパターンを(next_permutationで)作ってシミュレーションしてしまえ
→WA(1) 12'59
あー、入力をH行じゃなくてW行読んでた
直して
→AC 15'55
https://beta.atcoder.jp/contests/agc007/submissions/2660620

解法より

「問題文および a で与えられる情報と整合するような駒の動き方が存在する。」という制約があるので、単に # の数を数えてそれが H+W-1個かで判定できる、とな。(そりゃ200点問題だわ)


AGC 008 A - Simple Calculator (300)

{x, y, 0, -x, -y} の5地点を考えて、相互間が一発で行ける場合の手数を与えてワーシャルフロイドした
→AC 17'05
https://beta.atcoder.jp/contests/agc008/submissions/2660720

解説より

正規表現でいうと B?A*B? みたいなパターンに限定できる、のか
とすると4パターン試せばいいだけだ
(最初そう思ったんだけど0近傍とか反例がありそうな気がして怖かったけど、なるほど、操作の中のBBは消えるし、残った単独のBでAに挟まれてるもの(ABA)はBと同義だし、挟まれてない(=両端の)Bしか残らない)

AGC 009 A - Multiple Array (300)

後ろから足してく
それまでにいくつ足したか記憶していればaを毎回書き換える必要はない
→AC 4'29
https://beta.atcoder.jp/contests/agc009/submissions/2660788

AGC 010 A - Addition (300)

奇数の個数が奇数個あったらアウト
→AC 3'34
https://beta.atcoder.jp/contests/agc010/submissions/2660814

解説より

合計が偶数かどうかで判定できる(そりゃそうだw)

AGC 011 A - Airport Bus (300)

T[] をソートしてシミュレーションするだけだよね
なんかごちゃごちゃになって無駄に時間かかったけど
→AC 20'04
https://beta.atcoder.jp/contests/agc011/submissions/2660897


AGC 012 A - AtCoder Group Contest (300)

上位2N人で、ペアを作ってそれぞれの小さい方を取る感じの
(ソートして上位2N人でAGC001Aをやる感じ)
→AC 5'23
https://beta.atcoder.jp/contests/agc012/submissions/2660922

AGC 013 A - Sorted Arrays (300)

先頭から見ていって、そこまでの(単調非減少|単調非増加|非減少非増加)の3種類の続きかを判定しながら伸ばしていく or 切るをやっていくだけ
→AC 4'46
https://beta.atcoder.jp/contests/agc013/submissions/2660941