naoya_t@hatenablog

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

〈企業コン埋め〉Tenka1 Programmer Contest

埋めたはずの100点200点で埋まっていない問題が生えていたので見てみたら先月10/27のTenka1 Programmer Beginner Contestの問題だったので(pythonで)さくっと埋めた後、せっかくなので同時開催のTenka1 Programmer Contest*1を本番と同じ100分間で取り組んでみた(いわゆるバチャコン*2)。

C,D通して2完、55:31で243位相当(パフォ1860前後なので多分+10ぐらい上がる?)
そんなに嫌な問題じゃなくて(普通のARCっぽくて)楽しめた。

C - Align (400)

とりまソートする
前半と後半に分けてgreedyにギザギザするのがいいのかな?
いや、各区間の使われる回数に注目すると

規則性あるような? [2,[4,[6,[8,[...],8],6],4],2]みたいな感じ?一番多い部分のどちらか(奇数ならそれ)が-1する感じで。折り畳んでるだけだからまあ当然っちゃ当然だった。区間が偶数ならいい方を取ればいい。
(時間かかっちゃったな)
→AC (33:32)
https://beta.atcoder.jp/contests/tenka1-2018/submissions/3590178

解説読んだ

ぎざぎざにするのが当然よくて(小<大>小<大>... か 大>小<大>小<… のいずれかのパターン)
そうすると、例えば 小<大>小<大>… だと、
(p2-p1) + (p2-p3) + (p4-p3) + (p4-p5) + ... = 2(p2+p4+..) - 2(p3+...) - p1 - ..
みたいに足すだけの数と引くだけの数に分かれるので、大きい数を足すだけの方に、小さい数を引くだけの方に貪欲に振ればいい。(大小大小/小大小大は両方試せばよい)
なるほど。

D - Crossing (500)

問題読んだ時、(1,2)(2,3)(3,1)みたいにすればNいくつでも行けるのでは?と思ったけど
サンプルのN=4でNoって言ってる…
あれ?
そうか、(1,2)(2,3)(3,4)(4,1) だと、対角線で取った(1,3)と(2,4)が共通項を持たない。
てことは、ああ、完全グラフになるやつだけYesなのか
頂点がn個だと辺がn(n-1)/2本。N=n(n-1)/2 になるような整数nがあるときだけYes。
具体的に数字をどう割り振るかはi,j (i<j) の二重ループで簡単に振っていけそう。

これはCより簡単に思えた。
→AC (55:31)
https://beta.atcoder.jp/contests/tenka1-2018/submissions/3590264

解説読んだ

各集合のサイズは (他の集合との交わりの個数に等しく) k − 1 になります。

はい
f:id:n4_t:20181112223557p:plain:w320
↑解説PDFのこの図が素晴らしかった(すべての点で2本のみがクロスしている)

E - Equilateral (700)

  • 300x300なので、点の数は最大90000(=9e4)。
  • マンハッタン距離は1〜600まで取りうる。

いろいろループを考えてたけど時間内に収まりそうにない。

マンハッタン距離な空間で正三角形みたいなのがいくつあるかって事だけど、
3つの点の相互間のマンハッタン距離がすべて等しいときの性質について考えていた。

3点 (x0,y0), (x1,y1), (x2, y2) の相互間の距離は

|x1-x0|+|y1-y0|
|x2-x0|+|y2-y0|
|x2-x1|+|y2-y1|

で、x軸上の3つの距離の最長の1つは残り2つの和に等しく、y軸上の3つの距離についても同様である。
(x0≦x1≦x2 という位置関係にあるとしたら |x2-x0| = |x2-x1| + |x1-x0| である)

あるいは、x0≦x1≦x2, y0≦y1≦y2 として、(x0, yi) (x1, yj) (x2, yk) のような3点の取り方は3!=6通りあるが
3点間相互の距離がすべて等しくなる組み合わせは限定される。
(x1-x0)+|yj-yi| = (x2-x0)+|yk-yi| = (x2-x1)+|yk-yj|

x1-x0=a, x2-x1=b, y1-y0=c, y2-y1=d とおくと
a+|yj-yi| = b+|yk-yi| = (a+b)+|yk-yj|

  • i,j,k=0,1,2なら a+c=b+d = a+b+c+d、これはa=b=c=d=0でないと成り立たないのでNG
  • i,j,k=0,2,1なら a+c+d=b+c=a+b+d これはb=c=a+dのときに成り立つ。
  • ...

成り立つ時に3点のうち2点は斜め45度の線上に乗るっぽい。
(45度の位置関係にある2点を総ざらいして…というか斜め線でスキャンして)調べていくにしても全部見て回る時間ないのでは?

この辺りまで考えて時間切れ。

解説読んだ

3点のうち2点が斜め45度の線上に乗る、というのは自分の考察でも出てきてた
2点が固定されているとき、残りの1点の位置は?というと、固定した2点から縦横に伸ばした線の交点(2つある)を挟んで、固定した2点を結ぶ線分をミラーリングした線分上ならどこでも良い。(交点を原点としたとき原点から3つの各点への距離はどれも等しい)

それは分かるんだけど計算量的にどうなの?

あ、
最初の2点の固定が90000C2 (=O(N^4)) じゃなくて(1200本ぐらいの斜めスキャン線について)高々300C2でいいからO(N^3)なのね
それで
ミラーリングした線分上に乗ってる個数はどこからどこまでなので累積和で…斜めスキャン線上の累積和を取る必要があるけど…まさかのO(1)で、合計でO(N^3) なわけか
// N=max(H,W) ね

でも重複カウントどうやって排除するんだ?(線分の端点については直角三角形になるから二回ずつカウントされてしまうよね)
ってまあその数を数えておけばいいか

(あとで実装してみよう…)

実装してみた
  • 縦横比で場合分けするの面倒い → transposeしてどちらかに直せば考える手間が省ける
  • 斜めにスキャンするの面倒い(開始条件・終了条件きわどい)→ ±45度回転したものを用意してしまえばいい。何もないところはどうせ何もないので問題ない
  • 二回ずつカウントされる端点について → それがいくつあるか数えて2で割って答えから引けばいい

→AC
https://beta.atcoder.jp/contests/tenka1-2018/submissions/3595348
一発で通って嬉しい

あと

  • /と\、その上と下、で4通りあるんだけど、semiexpさんのコードを見たら入力を最初に45度回転して、それを90度ずつ回しながら(rot)4回(solve)やってた。両端じゃなくて片方だけ足してる。なるほど。(自分の場合は混乱するので二回ずつカウントされる端点を数えて2で割る作戦は有効)

縦横2倍の大きさのキャンバスに入力を45度回転したものを最初に作っておいてそれを処理する、というのは定石のようだ。

F - Circular (900)

開いてない

*1:企業コンなのにレーティング変動あり、で少し惹かれたけれど出なかった回。

*2:virtual contest