naoya_t@hatenablog

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

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

D問題埋め(随時更新)

6月10日

ARC 093 D - Grid Components (500)

ARC 093 Eが解けたので093 Dもやってみる。
白い島がA個、黒い島がB個になるような任意のグリッドを描く問題。
なんか陰陽の点の数を変えればいいだけじゃないかな
f:id:n4_t:20180610194032p:plain
幅は100決め打ちで
行数はA,Bそれぞれを50で割ったceilingで

→WA(1) 13'31''
https://beta.atcoder.jp/contests/arc093/submissions/2643079

出力したグリッドがちゃんとA個の白島+B個の黒島になっているかチェックするプログラムを書いてみたら
なってないじゃん


出力してる行数と最初のh,wが合ってない(ra,rbをrb,rbにしてる)
1文字直して
→AC 33'56''
https://beta.atcoder.jp/contests/arc093/submissions/2643163

(解説見たら全く同じ解き方だった)

6月11日

ARC 092 D - Two Sequences (500)

約1ポモドーロ(27分)考えたけど解けなかったので解説を見る

答えを1ビットずつ求めていく、というのは当然そうだと思うのだけれど
a_i + b_j のkビット目(最下位を0ビット目とする)が 1 になる、ということは、
a_i + b_j[1\cdot 2^k, 2\cdot 2^k), [3\cdot 2^k, 4\cdot 2^k), ... といった区間にあるということで、bの配列の中にそういう数がいくつあるかは lower_boundとかでO(logN)で求められる、さらに、それより上のビットは無視できるので、ビットは上から見ていって、要らなくなったところはmodで切り捨てて進むことで探索が各ビットにつき[0,1), [2,3)の2回ずつで済む。
b[] のmodを取った後に再度ソートが必要なことに注意。(上位ビットが消えるから順番が変わる)
→AC
https://beta.atcoder.jp/contests/arc092/submissions/2655105

解説にあった「愚直解法をSIMDで書いたら3秒切れるかも」説、kimiyukiさんのエントリで紹介されていた2つの実装とも2.9秒台だった。凄い…(けど本当ギリギリで、実戦で使うのは憚られる技法だなあ。MMで使えたら地味に効きそうだ)

ARC 091 D - Remainder Reminder (400)

・bを1〜Nまで全部見ていく
・可能なaの数を求めて足していく。bで割った余りがK以上、ってことはbはKより大きいし、余りは[K..b-1]の範囲。商の最大値qmax=floor(N/b)で、q:[0..qMax-1]のときは[K..b-1]すべて(※K=0のときa=0を含んでしまうのでそれは除外)、q=qMaxのときはN-qmax*bの余りから(K-1)を引いた分。
→AC 20'07''
https://beta.atcoder.jp/contests/arc091/submissions/2656495

解説より

DEGwer先生の解説ではaのほうを0からNまで動かしてるね
(a,bのどちらから攻めてもO(N)で行けるってことか)

ARC 089 D - Checker (500)

・2Kx2K の枠を考える
・(x_i,y_i)をそれぞれ mod 2Kでその枠に押し込める
・白は(+K,0)なり(0,+K)シフトして黒に変えてしまう
・KxKの正方形で(嘘。斜めに接したKxKの正方形2つで)できるだけ多くの黒をすくいたい
・二次元いもすして +imos[left-1][top-1] -imos[left-1][bottom] -imos[right][top-1] +imos[right][bottom] みたいに正方形内の黒を数える。(上下、左右が繋がってるので適宜分割)。斜めに接したもう1つの正方形についても同様に。いもすクエリはO(1)。
・ってのを2Kx2K箇所総当たりしてもO(K^2)だし間に合うっしょ
→AC 60'04''
https://beta.atcoder.jp/contests/arc089/submissions/2656793
方針思いついたのは良かったんだけど計算が合うまで(てか斜めに接したもう1つの正方形を調べ忘れててサンプルケースすら数が合わずに)ちょっと時間かかりすぎた

解説より

(もっと賢い方法があるのかなと思って期待しながら)解説読んだけど結局同じ事やってた…

6月12日

ARC 088 D - Wide Flip (500)

最初全然思いつかなくて

文字列sの長さをLとする
・幅Lのflipが使える場合→「全部0」か「全部1」のみに対応できる
・幅L-1のflipも使える場合→端の1を消せる
・幅L-2のflipも使える場合→両端の1を消せる(これは幅L-1の段階で可能)、端の11を消せる(ので端の1を消せるのと組み合わせて端の01(左)/10(右)も消せる
・…
・両端から見ていって、左から(あるいは右から)k番目に1が出現するとしたらL-kのflipが必要ということか。
・sと、sを全て0/1反転したものとでこれを試して良い(=大きい)ほう

→WA(1) 23'22
Lが偶数のとき余分に調べていて、00001111で3を返していた。あと全反転スタートを調べてなかった。
直して
→AC 33'55
https://beta.atcoder.jp/contests/arc088/submissions/2661273

解説より

解説よく分からなかったんだけど
max(k,n-k)の最小値、というのは端から見ていって1が最初に出る(というか隣りと異なる)位置kというよりL-kの方の、中央に一番近いやつってことね

ARC 087 D - FT Robot (500)

(便宜上x正軸方向を東、y軸正方向を北とする)
・最初は東限定だけど、その後のターンでx軸方向に進む時は東西どちらでもよい。
・y軸方向の動きは南北どちらでもよい。
・sを左から読んで行って、Tの切れ目までにいくつずつ進むかを東西方向、南北方向別々にリストアップして、その合計で(x,y)になる可能性があるか調べる
・最初の東限定に注意。(その長さだけxから引いてしまえばいい)
→WA(1) 12'01
テストケース1つだけWAであと全部AC
見落としてるコーナーケースがあるな
https://beta.atcoder.jp/contests/arc087/submissions/2661286

"F" のときに1,0にたどり着けない
(Tがないと東限定でいくつ進んだか記録されないじゃん)
直して
→AC 15'53
https://beta.atcoder.jp/contests/arc087/submissions/2661288
途中、ソートしてるけど意味なかった

解説より

その合計で(x,y)になる可能性があるか調べる、のところのDP (O(N^2))、自分のやつはsetで回してるからO(N^2logN)か。


6月16日

ARC 086 D - Non-decreasing (600)

うーんうーん
左から…右から…平均が正か負か…最大値が…

・絶対値が一番大きいやつを全部(それ自身以外は除いていい)に足したら全部同じ側に寄るよね(N-α手 - 同じ負号ならやらなくていいからもっと少なくできるけど面倒なのでやってない)
・全部0なら終わり
・全部非負なら…左から右へ、a[i+1] += a[i] を連鎖していく。非負のものに非負を足すから、必ずa[i] ≦ a[i+1] になる
・全部非正なら…右から左へ
これで高々N-1手なので、合計しても2Nを下回る。
→AC 24'49
https://beta.atcoder.jp/contests/arc086/submissions/2673761

ARC 085 D - ABS (500)

これは出場回だから見たことがある…(確か、全部取るか1つ残すかしかない、みたいな)
自分で1ポモドーロ考えたけど納得できなくて
とりあえずコード書いてAC取ったけどなんでこれが正しいのか分からない。

https://beta.atcoder.jp/contests/arc085/submissions/2673910
毎回のことだけれど、こういう最大化 vs 最小化問題をどう詰めていったら良いんだろう。

解説より

・N=1の場合はXが全部(というか1つ)取るから|a_1 - W|
・N≧2の場合:
 ・Xが全部取ると…|a_N - W|
 ・1つ残すと…|a_{N-1}-a_N|
 ・2つ残すと…Yが1つ取った場合と2つ取った場合の大きい方だから max(|a_{N-2}-a_N|, |a_{N-1}-a_N|)、これは上限がXが1つ残したときのスコアなのでXにとって2つ残す意味はない。
 ・3つ残すと…max(|a_{N-3}-a_N|, |a_{N-2}-a_N|, |a_{N-1}-a_{N}|)
要するに、2つ以上残した場合 Y は |a_{N-1}-a_N| よりスコアが小さくなる手を取る可能性があるが、それよりスコアが大きくなることはありえない。Xにとって2つ以上残す意味はない。
そういうことか。(この問題については完全に理解した)

ARC 083 D - Restoring Road Network (500)

・ワーシャルフロイドを回してみて、より短い経路が見つかるなら-1
・全てのi<jな(i,j)の組を長さでpriority_queueに入れて、短い順に、その道(i,j)+隣接する道(i,k)ないし(j,k)の合計が直行路と同じ長さなら直行路のほうを捨てる
・残った道の長さの合計
→AC 25'47
https://beta.atcoder.jp/contests/arc083/submissions/2674099

解説より

WFのとこまでは良いとして
辺(i,j)を残すべきかどうかは a(i,j)==a(i,k)+a(k,j) になるような中継点kが存在するかしないかで分かる、と。(やってることは同じなんだけどそう考えたほうがシンプルかも)

6月17日

ARC 081 D - Coloring Dominoes (400)

グラフの色塗り分け…とか思って難しく考えすぎてた
けど
ドミノの形状が1x2と2x1しかないので、幅2の空間では1つが塞いでいるか2つ並んでいるかのどちらかで、

  • いちばん端:1つなら3色から1つ選ぶから3C1x1!=3通り、2つなら3色から2つ選ぶのと並び順で3C2x2!=6通り
  • あとは左から
    • 1つ→1つ:残りの2色から1つ選ぶから2C1x1!=2通り
    • 1つ→2つ:残りの2色と並び順で2C2x2!=2通り
    • 2つ→1つ:残りの1色から1つ選ぶから1C1x1!=1通り
    • 2つ→2つ:全6通りから2つ同じものと片方共通なものを除いて3通り

→AC 34'07
https://beta.atcoder.jp/contests/arc081/submissions/2691743

解説解も同様

ARC 080 D - Grid Coloring (400)

ロンゴロンゴ文字方式(左から右に進んで行って次の行は右から左に、と折り返しながら塗る)*1
→AC 11'11
https://beta.atcoder.jp/contests/arc080/submissions/2691767

解説解も同様

ARC 079 D - Decrease (Contestant ver.) (600)

  • 幅(N)を50に固定しても大丈夫そう。a[]の中の順序はどうでもよさそう。
  • 「a_iが全て49(=N-1)」になるのをゴールとする
  • Kを50で割ったときの商と余りを q, r とすると(50q+r=K)
    • 50手で全てを-1できるので、まずはa_i全てを+qインクリメント(=50q手で-qできる状態)
    • 残りrを頑張る。1手につき1つだけN伸ばしその他を-1するのをr手やる。すなわち、N本のうちr個については N+(r-1) インクリメントし、残りは r デクリメントする。

(そこは1手ずつシミュレーションしても高々49回だからそこまで考えてまとめて計算する必要もなかった)
→AC 28'47
https://beta.atcoder.jp/contests/arc079/submissions/2691843

解説解も同様(最後1手ずつシミュレーション)

ARC 078 D - Fennec VS. Snuke (400)

これは木なので、ノード1とノードNを繋ぐpathは取り合いになるがそれ以外は片方からしかリーチできない。(届かないノードは必ず相手ノードの向こう側にあるので、距離で言えば相手からの距離のほうが必ず小さい)
というわけで、各ノードについて、ノード1からの距離、ノードNからの距離をそれぞれ調べて、ノード1からの方が近い(あるいは等距離)ならFennecが取れるノード、それ以外はSnukeが取れるノードになる。
個数を比べてFennec≧SnukeならFennecの勝ち
→WA(1) 17'03'
https://beta.atcoder.jp/contests/arc078/submissions/2691904

同数の場合は後手も打てるから先手が負けるんだ
そこだけ修正して(Fennec>SnukeならFennecの勝ち)
→AC 18'32''+penalty
https://beta.atcoder.jp/contests/arc078/submissions/2691910

解説解も同様



ARC 075 D - Widespread (400)

k回で全部倒せるか調べる方法:
d = A-B とすると(問題制約よりd>0)
kB以下のものは倒せている。kBを超えるものについては dで割ったceiling回だけ必要で、その総和がk以内なら全部倒せる。
あとは二分探索で。long longが必要。
→AC 12'10'
https://beta.atcoder.jp/contests/arc075/submissions/2695353

解説解も同様

ARC 074 D - 3N Numbers (500)

  • 切れ目となる可能性となるのはN+1箇所で
    • 「前半」になるのは先頭N個〜2N個の範囲でのベストNの合計
    • 「後半」になるのは末尾N個〜2N個の範囲でのワーストNの合計

それぞれをpriority_queueを使いながら計算しておいて、N+1箇所それぞれについて前半と後半の差を求め、最大値を返す
→AC 16'11
https://beta.atcoder.jp/contests/arc074/submissions/2695437

解説解も同様

ARC 073 D - Simple Knapsack (400)

  • N≦100であること、それぞれの重さが[w0,w0+3]の範囲であることに着目
  • dp[個数][(重さ-w0)の合計] = 最大価値
  • 個数0〜Nそれぞれについてdpの結果を見る。W-(w0×個数)の範囲内の最大価値はいくつか。
  • 個数0〜Nすべてに渡る最大値が答え

→AC 29'52
https://beta.atcoder.jp/contests/arc073/submissions/2695614

解説より

  • 物の重さは高々4種類。各重さについてそれぞれ何個選ぶか。
    • その重さの中で価値の高いものから選ぶ
  • 4種類がN/4個ずつだったとして (N/4+1)^4通りとかそんな程度なので全探索できるよ

https://beta.atcoder.jp/contests/arc073/submissions/2695661

200AC超えてた
f:id:n4_t:20180618004936p:plain

*1:牛耕式(boustrophedon)というらしい。cf. 牛耕式 - Wikipedia