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っぽくて)楽しめた。

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

*2:virtual contest

続きを読む

AtCoder Beginner Contest 113

11/4(日) 21:00-22:40


日曜開催 && サーバ激重回

いつも通りD→C→B→A(で4完)

続きを読む

AtCoder埋め Oct.2018

10月の埋め。

10月23日

ABC 111 (A,B)

一応ABCのA,Bも埋めておく方針。普段はpythonだけど今日はsed/awkで。

A - AtCoder Beginner Contest 999 (100)

こういうのはsed

y/19/91/

https://beta.atcoder.jp/contests/abc111/submissions/3445722

B - AtCoder Beginner Contest 111 (200)

次はawk

{n=$1;for(i=111;i<=999;i+=111)if(n<=i){print i;exit}}

https://beta.atcoder.jp/contests/abc111/submissions/3445738

ARC 103 D - Robot Arms (600, 部分点300)

出場したけど部分点しか取れなかった問題。

1,2,4,8,...,2^k のアームだけ用意して上下左右に振ることで、[-2^{k+1}+1..2^{k+1}-1] の範囲の奇数であれば任意の(x+y,x-y)が合成できるのは皆さんが図解してくれてるとおりなんだけど
(偶数の場合、長さ1のアームを余分に用意してxかyを1つずらして始めればよい)
与えられた(x,y)からこの上下左右を割り出すところがパッと書けなくて苦労した。

(x+y,x-y)座標系において、長さkのアームは向きによって

  • R=k(1,1)
  • L=k(-1,-1)
  • U=k(1,-1)
  • D=k(-1,1)

になるので、これを足していくのだけれど、長い方のアームから使っていくのが良い。
長いアームから、(x+y,x-y)の象限によってR,D,L,Uに振り、振った分を(x+y,x-y)から差し引いてまた同様に象限によってR,D,L,Uに振り、ということを最短アームまで繰り返す。
(※x,yそれぞれ±1e9の範囲なので最長アームは2^29では足りないと気づくまでに2WA出した。long longにすればいいという問題ではなかった。これはintの範囲で解ける。)

→AC
https://arc103.contest.atcoder.jp/submissions/3452355


AGC 028 B - Removing Blocks (600)

最近出場したAGCの、飛ばしたB問題。

解説解法はシンプルなのでとりあえず実装してみて、答えが合うのは確認できた。
→AC https://agc028.contest.atcoder.jp/submissions/3452974
でもなんでこれでいいのかが腑に落ちてない。

  • 答え = Σj(j番目のブロックの重さがコストになる確率×j番目のブロックの重さ)×N!
  • j番目のブロックの重さがコストになる確率 = Σi(i番目のブロックを取り除く際にi番目とj番目が繋がっている確率)

そこまでは良いんだけど

  • i番目のブロックを取り除く際にi番目とj番目が繋がっている確率 = \frac{1}{|i-j|+1} ←ここ

|i-j|+1というのは、例えばi番目からj番目まで繋がったブロック(どちらが先だったとしても)の長さ。

http://betrue12.hateblo.jp/entry/2018/10/14/121018
これ読んだ

ああ

  • 例えば、N点のうちの適当な4点a,b,c,d(連続していなくてもよい)を選ぶ(というか決める)。そしてN点をランダムな順番に選んだとして、a,b,c,dのうちのaが最初に取られる確率は1/4である。

それは納得。

  • a,b,c,dが連続していたとして、aを取り除くことでdの重さがカウントされる確率というのは、a,b,c,dのうちaが最初に取られるケースの確率に等しい
    • a,b,c,dのa以外(b,c,d)が最初に取られるケースでは、aを取り除くことがdに波及しない
    • a,b,c,dが全部残っていて、aより左側(仮にλとしよう)が取られることで(a,b,cも含め)dの重さがカウントされるケースというのは当然あるが、これはλを取り除くことでdの重さがカウントされる確率、のときに計算するので今考えなくていい。考えたいのはあくまでも「aを取り除くことでdの重さがカウントされる確率」。

で、Σ_d(dの重さ×Σ_a(aを取り除くことでdの重さがカウントされる確率))、で計算自体は累積和を使ってO(N)、みたいな感じなのね。

納得。

AtCoderで青になるまでにやったこと/黄色になるためにやるべきこと

備忘録。
f:id:n4_t:20181019221646p:plain:w500

AtCoderで○○色になるまでにやったこと

  • ARCに1回参加

  • AGCに1回参加

  • AGCに1回参加

  • ABCに1回参加、だけでは足りなくて
  • AGCに1回参加

  • ARCに1回参加

AtCoderで○○色になるためにやるべきこと

【追記】
ガヴリール・ドロップアウト観ました。
ガヴ・タプが同級生になる二期はまだですか?

  • 生まれ変わる

  • 2回生まれ変わる