naoya_t@hatenablog

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

〈企業コン埋め〉500点問題篇2019

皆様改めてあけおめことよろです。
本ブログは競プロ参加記録や過去問精進記録をメインとしたいわゆるチラシノウラ的メモです。

引き続きAtCoderの過去問を埋めていきます。
企業コン500点から。

1/1(火)

CODE FESTIVAL 2018 Final (Parallel)

Three Letters (500)

初埋めのTough Journey(600)と同じコンテストの未埋めのD問題から。

文字列を個別にDPして、その文字列で未出の3文字略語が生えたら全体での略語カウンタを++
→TLE
https://atcoder.jp/contests/code-festival-2018-final-open/submissions/3909323
およ...計算は30000\times26^2だけどメモリ初期化に30000\times26^3かかっててアウトか

  • ループを簡略化(26文字 x 大文字or小文字 → 52+α)
  • bitsetでメモリ初期化を26^3から\displaystyle\frac{26^3}{64}に減らす
  • stringでの文字列比較をやめて整数3つの比較に

→AC

https://atcoder.jp/contests/code-festival-2018-final-open/submissions/3909475
倍速以上になった

解説読んだ

計算量減らす方法が書いてある(bitset使ってたw)


CODE FESTIVAL 2016 Grand Final (Parallel)

A - 1D Matching (500)

  • a,bそれぞれソートして、aのi番目とbのi番目を繋いで
  • \\ とか // とか。Xにはならない。
  • 前のと繋がってるかどうか…
  • 繋がってるやつは行き先を交換できる
  • (島の数)!の積

→WA

135, 468 とか考えてみると
繋がっていてもすべてに行けるわけではない
とすると
行き先がいくつあるかを数えていってその積、か
deque使えばO(N)で行けそう
→AC
https://atcoder.jp/contests/cf16-exhibition-final-open/submissions/3911732

解説読んだ

意味わからない


1/2(水)

DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦

(DDCC2017本戦)

B - GCDロボット (500)

すべてのgcd(Z,a[i])のLCMを計算するだけでは
→AC
https://atcoder.jp/contests/ddcc2017-final/submissions/3912039

解説読んだ

はい
素因数分解しておくとやりやすいみたいな話(それはそう)


第4回ドワンゴからの挑戦状 予選

C - Kill/Death (500)

  • n個を昇順になるようにk人に分ける分け方 (1000x1000通り)の表(表1)を用意しておく
    • ここはDPで
typedef long long ll;

const ll MOD=1000000007LL;
ll ADD(ll x, ll y) { return (x+y) % MOD; }

vector<vector<ll>> f;
void f_init(int nmax=1000, int kmax=1000) {
    f.resize(1+nmax);
    for (int n=0; n<=nmax; ++n) {
        f[n].resize(1+kmax);
        f[n][0] = (n == 0) ? 1 : 0;
        for (int k=1; k<=kmax; ++k) {
            f[n][k] = ADD(f[n][k-1], ((0 <= n-k) ? f[n-k][k] : 0));
        }
    }
}
  • 各チームについて
    • kill数の合計を求める
    • kill数ごとにグループ分けしておく
  • チームAの合計をチームBの(グループ分けした)人数に割り振るDP
    • ここで表1が活躍
  • チームBの合計をチームAの... も求めて
  • その積

→WA(1)

表1でmod 1e9+7してなくてオーバーフローしてる

直して
→AC
https://atcoder.jp/contests/dwacon2018-prelims/submissions/3913968

解説読んだ

同様
「分割数」ってのは何人にという制約がない場合のやつだよね(自分の実装でいうf[n][n]にあたるやつ)


CODE THANKS FESTIVAL 2017(Parallel)

F - Limited Xor Subset (500)

dp[0..131071] = 0
dp[0] = 1

for each ai:
for n=1..131071
dp[n] = dp[n XOR ai] = dp[n] + dp[n XOR ai]

return dp[K]
これは計算あうけどN=10^5ではTLE

a_iに存在しないビットは立てられないので

b = a1 | a2 | ... | an
if ((K&b) != K) return 0

立ってるビット数をBとして
B = __builtin_popcount(b)

Bビットまんべんなく\displaystyle \frac{1}{2^B}ずつ立つとしたら
(なぜまんべんなく立つかというと、立っているbitが交換可能な行き先がある場合半分そちらに移り、行き先がない場合変化しないから)
可能などの値もその2^N
2^(N-B) if N >= B

→WA
うーん

例えば5と10しかないのに3を作ることは出来ない

4 3
5
10
5
10

(TLE版ではちゃんと0になるけど横着版では1を出してくる)

これをどう考えればいいか
3が不可能であることをどう探知すればいい?
UnionFind...?
いや、TLEって言ってたのと同じ計算量が必要になる

カウントは置いといて
0からa_iのXORでたどり着けるかをbitsetで見て回るのはメモリは足りてもO(N^2)では…いや、既にa_iが立ってたら飛ばせるからもっと速いか
でbitsetの立ってるビットのカウントをcとすると
答えは\displaystyle\frac{2^N}{c}
→AC
https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/3915466

解説読んだ

(解説の解法1のインデックス間違ってる気がする)
自分のは想定解法と違う

解法1は…和>or>xorを利用してるのか。ソートして小さい順にやればxorで行ける上限は限られてるから全部回さなくてもいい、と。
解法2なんでmax(m)が446?
ああ
\displaystyle \sum_{i=1}^{N} a_i \le 10^5
という制約が効いてくるのか
結構な数の重複があることを利用できる、ということね
重複分の遷移については2^c倍(cは重複数)しながらやればいいからね

M種類の異なる正の整数があるとすると、その和は最小で\displaystyle 1+2+3+...+M=\frac{M(M+1)}{2}
これが\displaystyle\sum a_i \le 10^5以下になるはずなので
M(M+1)\le \sqrt{2\times 10^5}
これを解いてM\le 446
なるほどね
それなら余裕


自分のAC解が思ってたよりはるかに速かった(9msでこれは最速7msには及ばないもののかなり速い)のは、「既にa_iが立ってたら飛ばせる」というのが思ってたより効いてるからなのね。

この記事
trap.jp
によると、ガウスの消去法的に解く方法があるらしい。面白い。


CODE FESTIVAL 2016 Grand Final(Parallel)

B - Inscribed Bicycle (500)

純粋数学幾何学)ゲーでは
三角形の辺の長さをa,b,c (a\le b\le c)、2つの円の半径をrとする。
cを底辺としたときの高さをhとすると、三角形の高さは当然\displaystyle S=\frac{ch}{2}である。
また、2つの円は(互いに接した上で両方とも)最長の辺に接している(に違いない)ので
円とcとの2つの接点を(u,c-v=u+2r)とすると
三角形の面積はこれらの長さ(a,b,u,v,r,h)を使って
\displaystyle S=(\frac12ur+2r^2+\frac12vr)+(\frac12ar+\frac12br)+\frac122r(h-r)=\frac{r}{2}(u+2r+v+a+b+2h)
u,vがうまく消えて
\displaystyle S=\frac{r}{2}(a+b+c+2h)=r(\frac{a+b+c}{2}+h)=r(s+h)
面積Sはヘロンの公式(\displaystyle s=\frac{a+b+c}{2}としたとき\displaystyle S=\sqrt{s(s-a)(s-b)(s-c)}で求められるので、そこからまずhを求めて、最後の式に代入してrを求めることができる。

即ち

  • \displaystyle a_i=\sqrt{(x_{(i+1)mod3}-x_i)^2+(y_{(i+1)mod3}-y_i)^2}
    • c=max(a_i)になるようにa,b,cとする
  • \displaystyle s=\frac{a+b+c}{2}
  • \displaystyle S=\sqrt{s(s-a)(s-b)(s-c)}
  • \displaystyle h=\frac{2S}{c}
  • \displaystyle r=\frac{S}{s+h}
  • \displaystyle r=\frac{S}{s+\frac{2S}{c}}

絶対誤差または相対誤差が10^{-9}でなければならない

というのが心配だったけど(何の考えもなしにとりあえずdoubleで投げて)通った。
→AC
https://atcoder.jp/contests/cf16-exhibition-final-open/submissions/3916143

64bit double型の仮数52ビット*1(最初の1.は省略されている)で、有効桁数53桁として2^{-53}\sim 1.11\cdot 10^{-16}ぐらいなわけだけど
今回の計算で気になるのはsqrt()の所だけ?
(sqrt関数の誤差は0.5ulp未満であることがIEEE標準で求められているらしいのでそこは大丈夫では。√の中は\frac18の倍数、即ち2進数でぴたっと表現できる数だし)

解説読んだ

なるほど…
内接円(半径をrとする)を使って*2、内接円の中心方向に3辺をxだけ押し込んだ(元の三角形と相似の)三角形を考えると、\displaystyle\frac{r-x}{r}=1-\frac{x}{r}スケールになる。この三角形の内側(辺上も含む)はどこでも、元の三角形の内側に含まれる半径xの円の中心になれる。この(小さい方の)三角形の内側に2つの点を最大限遠くなるように取るとしたら当然最長辺(に対応する辺)の両端で、その距離は2xになるはず…
すると\displaystyle c(1-\frac{x}{r})=2xが成り立つのでrからxを求めればよくて
\displaystyle x=\frac{c}{2+\frac{c}{r}}
(分子と分母に\frac{S}{c}を掛けると自分が導いた式と同じになる)


CODE FESTIVAL 2017 Final (Parallel)

C - Time Gap (500)

51人いて2か所ずつあり得て…2^{51}って思うじゃん
24か所しかないんだよね
D_iの値としては0〜12の13通りしかない。
差を1以上にしたいのなら0と12については定員1名(2人以上いると差の最小は必ず0になる)。
0には既に高橋くんがいるので定員0名ともいえる。
1〜11については定員2名(D_i24-D_iに1人ずつ振ることで 0 を免れることができる)。
というわけで、考えないといけないのは「1〜11に1人いる場合にどちらに振るか」のみでこれは高々2^{11}=2048通りなので全探索で良いだろう。差を求めるのも愚直にやっても24×24の計算だし。
これは500点としては易しいのでは?
→WA(1)
はい愚直な計算ミスりました(同じのを2つくっつけて簡略化しようとしたんだけどくっつける前のほうを参照してた)
直して
→AC
https://atcoder.jp/contests/cf17-final-open/submissions/3916759

解説読んだ

同様
左右に振っていけば最善らしい。


1/3(木)

codeFlyer (bitFlyer Programming Contest)

C - 部分文字列と括弧 (500)

  • 高さごとに、前にそこに来たインデックスと、それが何連目かを保存しておく
    • 前に来た時より後にその高さ-1を訪れていればコンボ成立せず
  • あるコンボがn連とすると\frac{n(n+1)}{2}通りの括弧対応がある
  • のでその合計

→WA(1)
")(" で1を返してる…ああ、前に来たインデックスが1ずれてる(最初に高さ0を位置0に挿入するため)

直して
→AC
https://atcoder.jp/contests/bitflyer2018-final-open/submissions/3919225

解説読んだ

「p[i]より低いものがあるかどうかは、BITかsetで管理できる」と言っているけど
自分のやり方だとチェックしながら追加しているので不要(だしO(N)で出来る)。


CODE FESTIVAL 2016 Grand Final

C - Cheating Nim (500)

うーん
a_iが奇数だったら1減らしても最下位ビットにしか影響ないから楽そう(2回以上やるxorする意味がないし)。偶数の場合に面倒くさい、かな
偶数の場合の計算でどうしたら計算量を減らせるだろう
a_ia_i-1をxorに使う、というのは、b=a_i xor (a_i-1)として
a_iを1回、b_iを0回か1回xorするのと同義。

  • A=(a_iを全部xorしたもの)

として、Aに b_iをいくつxor使えば0になるかがこの問題の答えになる。
すこし問題がシンプルに…なってないか


-1っていう操作は一番下の立っているビットを崩してその下を1で埋める
ってことは
元の数とxorすると、一番下の立っているビットを含めたその下を1で埋めた値になる
a_i=100100ならb_i=a_i xor (a_i-1)=000111
ビット操作の中でもなかなか使いこなせていない例の性質だ
とすると

b_i には2進数で1,11,111,1111,11111,... のような数しか来ない

これをxorしてAを作るのは簡単そう
Aの立っているbitに対応するb_iが存在するときにAの立っているbit数を答えればいい?(出来ないなら-1
→WA

あ。
(サンプルはそれでいいだろうけど)上位ビットからb_iを使いながら使った回数を返すべき。(使うb_iがないなら-1
→AC
https://atcoder.jp/contests/cf16-exhibition-final-open/submissions/3920055

*1:仮数=mantissaと思ってたんだけど仮数をmantissaと呼ぶのは好ましくないとする意見もありsignificandと呼んだほうが良いらしい。see also:https://ja.wikipedia.org/wiki/%E4%BB%AE%E6%95%B0

*2:内接円の半径をrとすると当然\displaystyle S=\frac12r(a+b+c)=rsが成り立つので\displaystyle r=\frac{S}{s}である。