naoya_t@hatenablog

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

〈ARC埋め〉C問題集中アタック (093 - 075)

ARCの不参加回のC問題をスナック感覚で。
(とりあえず093から075まで遡った)

「問題文をさっと見て方針が立ったら次へ」ってのをやろうと思ったんだけど何かACぷちぷちしたい気分だったので(どうせ1問あたり数分だし)コードを書いて提出するところまでやった。
(ARCのC問題は早解き種目なので「すばやく書くにはどうしたらいいか」考えながら)

6月7日

ARC 093 C - Traveling Plan (300)

https://beta.atcoder.jp/contests/arc093/tasks/arc093_a
スポットiをスキップする場合、全スポットを訪れた場合の距離 + (abs(A[i+1] - A[i-1]) - (abs[A[i+1]-A[i]) + abs(A[i]-A[i-1])) を計算すればいい。番号が前後する地点の距離を計算しておくと便利。
→AC
https://beta.atcoder.jp/contests/arc093/submissions/2630202

ARC 092 C - 2D Plane 2N Points (400)

https://beta.atcoder.jp/contests/arc092/tasks/arc092_a
二部マッチングするだけでは
→WA(1)
https://beta.atcoder.jp/contests/arc092/submissions/2630244
あ、if (i==j) continue;とか入れてた…赤と青は別々だった
そこ消して
→AC
https://beta.atcoder.jp/contests/arc092/submissions/2630258

解説より

(二部グラフの最大マッチング問題としても考えることができる)というのはそうとして、
青(右上に来るべき存在)を一番左(xが小さい)から見ていって
その左下にある中で一番上(yが大きい)の赤いやつと組んでいく、というアルゴリズムの説明があった。これはこれで納得しておきたい。
・一番上(y最大)の赤と、それより下(yの小さい)赤があってそれぞれ今見ている青より左にあってどちらもその青とペアにできるとしたら、どちらを後に残しておくのが良いか、という問題。後で見る青は今見ている青より右にあるわけだから、前の青より左にあるなら後の青より左にあるのは当然で、x条件は満たしている。後の青のほうが上なら無条件にどちらともペアリングできるから問題ない。後野青のほうが下にある場合、できるだけ下にある赤を残しておいてあげたほうがペアリングできる可能性が高い。というわけで、ペアリング可能な赤の中で上から取っていくのが最適。(なるほど)

ARC 091 C - Flip,Flip, and Flip...... (300)

https://beta.atcoder.jp/contests/arc091/tasks/arc091_a
1x1から10x10ぐらいまでシミュレーションしてみて
abs(N-2)*abs(M-2) 、但しlong longになりうるので注意。
abs()はintを返すのでN,Mをllにしても意味がなく、abs()の結果をキャストすること。
→AC
https://beta.atcoder.jp/contests/arc091/submissions/2630368

ARC 089 C - Traveling (300)

https://beta.atcoder.jp/contests/arc089/tasks/arc089_a
次の地点までのマンハッタン距離を測って、時間内に行けなければその時点でNo、時間内にたどり着いても残り回数が奇数なら(とどまれないので)No
→AC
https://beta.atcoder.jp/contests/arc089/submissions/2630574

ARC 088 C - Multiple Gift (300)

https://beta.atcoder.jp/contests/arc088/tasks/arc088_a
YをX未満になるまで2で割っていける回数を数えるだけ
→AC
https://beta.atcoder.jp/contests/arc088/submissions/2630582

ARC 087 C - Good Sequences (300)

https://beta.atcoder.jp/contests/arc087/tasks/arc087_a
数値ごとに集計して、ある数値xがx個以上あった場合はその余りを、x個未満なら全てを取り除く
→AC
https://beta.atcoder.jp/contests/arc087/submissions/2630593

ARC 086 C - Not so Diverse (300)

https://beta.atcoder.jp/contests/arc086/tasks/arc086_a
レアな順に貪欲に書き換え。合計がlong longになる可能性があるので注意。
→AC
https://beta.atcoder.jp/contests/arc086/submissions/2630628

解説より

「できるだけ少ない数のボールの整数を書き換える」というのは,「できるだけ多くのボールの整数を,変更しないま まにしておく」というのと同じ

ARC 083 C - Sugar Water (300)

https://beta.atcoder.jp/contests/arc083/tasks/arc083_a
投入可能な水と砂糖の質量として可能な数を列挙して、それぞれの総当たり(の中でビーカーに収まりかつ溶け残らないもの)で一番濃度の高い組み合わせを答える
→AC
https://beta.atcoder.jp/contests/arc083/submissions/2630772

ARC 081 C - Make a Rectangle (300)

https://beta.atcoder.jp/contests/arc081/tasks/arc081_a
長さごとに集計して、2本以上あるやつを長い順に2組(あればその積、なければ0)
→WA
https://beta.atcoder.jp/contests/arc081/submissions/2631423
ああ
4本あったらそれ2組取れるじゃん
直して
→AC
https://beta.atcoder.jp/contests/arc081/submissions/2631432

ARC 080 C - 4-adjacent (400)

  • 4の倍数
  • それ以外の2の倍数(偶数)
  • 奇数

・偶数は偶数同士で並べる必要がある
・奇数は4で挟むか、4と隣接した両端になら置ける
・両端を奇数に使ってしまうと偶数を繋げない

→AC
https://beta.atcoder.jp/contests/arc080/submissions/2631777
あっけないな

ARC 079 C - Cat Snuke and a Voyage (300)

1からの船の行き先とNへの船の行き先のintersectionが空でないか
→RE1つ出た…
https://beta.atcoder.jp/contests/arc079/submissions/2631807

vector a(N), b(N) とか言ってるわ
Mだろ
直して
→AC
https://beta.atcoder.jp/contests/arc079/submissions/2631817

解説より

vectorの配列を1本用意して
中継点となりうる島(2〜N-1)について、1からの船があればtrue
Nへの船がtrueの島にあればPOSSIBLE

ARC 078 C - Splitting Pile (300)

累積和を取っておいて
i=[0..N-1)の範囲で、そこまでの和(x)とその後の和(y)を毎回O(1)で得ながらabs(x-y)の最小値を探る
→AC
https://beta.atcoder.jp/contests/arc078/submissions/2631844

ARC 075 C - Bugged (300)

DP
→2つWA...
https://beta.atcoder.jp/contests/arc075/submissions/2631893
あ、昇順にスキャンしてた
これじゃあ同じ問題のスコアを何度も足してしまう
修正して
→AC
https://beta.atcoder.jp/contests/arc075/submissions/2631902

解説より

DPするのは「オーバーキル」ってevima先生が書いててウケる
「正攻法」は、合計を出して、それが10の倍数でなければそれ、10の倍数なら10の倍数でない中で最小のやつを引いたのが(あれば)答え、なければ0