naoya_t@hatenablog

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

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

企業コン問題も300まではぷちぷち埋めてたけど、400〜700で70問ある…
地道に埋めていきましょう

f:id:n4_t:20181215132917p:plain
(700まで残り50問…)

12/11(火)

CODE FESTIVAL 2016 Final (Parallel)

C - Interpretation (400)

問題の制約を読めてなくて、全員が2次までで繋がってるかどうかを調べようとしていたけど
友達の友達はみな友達(友達の友達の友達も友達)って話なら
UnionFindでくっつけて終わり
→AC
https://beta.atcoder.jp/contests/cf16-final-open/submissions/3774104

解説読んだけど

UnionFindでは満点取れないみたいなこと言ってるけど
言語x人の記述は高々ΣK=1e5個しかないし、取れるよね

部分点解法が直接話すことができる人同士の間に辺を引く方式だから?
それも、ある言語lで繋がる人々{p}を全結合したグラフとか構築せずに、{p}の最初の人とそれ以降の人をUnionFindでくっつけていくだけでいいでしょ(なぜかLeetCodeで良く使う手)

満点解法の人と言語の二部グラフの場合、連結でない言語の検出をしないといけなくて面倒では?(ってまあ予め分かるか)

CODE FESTIVAL 2016 qual A

C - 次のアルファベット / Next Letter (400)

https://beta.atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualA_c

はい
(先頭からgreedyにローテートして'a'に変えていく
K回きっかりやらないといけないってのを見逃しててサンプル通らず
直して(最後の文字をK%26回動かすだけ)
サンプル通る前のやつを投げちゃってWA
直したやつを通してAC
https://beta.atcoder.jp/contests/code-festival-2016-quala/submissions/3774210

CODE FESTIVAL 2016 qual C

C - 二人のアルピニスト / Two Alpinists (400)

https://beta.atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_c

はい(左から、右からの最高値をもとに各地点の標高の範囲を求め(辻褄が合わなければ0)、剰余系で掛け算して答える)
AC
https://beta.atcoder.jp/contests/code-festival-2016-qualc/submissions/3774301

CODE FESTIVAL 2017 final

B - Palindrome-phobia (400)

cf17_final_b
https://beta.atcoder.jp/contests/cf17-final-open/tasks/cf17_final_b

はい(a,b,cそれぞれの出現数を昇順に並べた時 (k,k,k) (k,k,k+1) (k,k+1,k+1) のいずれかのパターンになっていればYES)
AC
https://beta.atcoder.jp/contests/cf17-final-open/submissions/3774351

SoundHound Inc. Programming Contest 2018 (春)

C - 広告 (400)

これ本番で落としたやつだ
隣接するセルを二部グラフにして(というか折り畳んで)どちらか多いサイド(を島の数だけやる?)
→WA
本番で書いたやつ(島ごとに市松模様)と同じやつしかAC取れてない
そりゃそうだ

解説読んだ

(この解説、コンテスト後に読んだ気がする)
二部グラフ作るところまではいい
どちらか多いサイド、というのが間違いだった。

この問題は「グリッドグラフでの最大独立集合のサイズを求めよ」という問題に言い換えられます。

// 最大独立集合 = 最大安定集合
そもそもなんで最大独立集合?というのは割と簡単で、独立集合の要素同士の間には辺が存在しないから、ある独立集合の全要素に広告を置いても大丈夫ということ。

いやそうなんだけど
だったら二部グラフの「どちらか多いサイド」と何が違う?

二部グラフの最大独立集合の大きさがなぜ (頂点数) - (最大マッチングのサイズ) で求まるのかという所。

これは、

最小頂点被覆(その頂点さえ全部押さえれば全てのパスが繋がっている) = 最大マッチングのサイズ

が言える(らしい)から。なぜ?

Kőnig's theoremというらしい。
けんちょん先生の解説

とにかくそういうことらしい。

で、最小頂点被覆集合をグラフから取り去れば残りの頂点は最大独立集合を成す、というのは分かる。(残りの頂点の間に辺があるとしたら、その辺のどちらかの端は最小頂点被覆集合に含まれていたはずなので)

というわけで、最大マッチングを求め、それが最小頂点被覆集合の大きさに等しいから、頂点数からそれを引いて最大独立集合のサイズ、すなわちこの問題における最大広告出展可能数を求めよう。

(UnionFindとかしなくてよくて、全部まとめて1つの二部グラフとして扱える。x+yが奇数か偶数かで左右に振り分ければよい)

→AC
https://beta.atcoder.jp/contests/soundhound2018/submissions/3775304

COLOCON -Colopl programming contest 2018-

C - すぬけそだて――ごはん――(400)

https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_c

カードは高々36枚(偶数18、奇数18)

  • 何も買わない,(1)
  • 偶数を1つだけ買う(18)
  • 奇数だけで買うパターン(2^{18}-1)
  • 偶数1つと奇数でパターン(18\cdot 2^{18}-1)

それぞれ、36までの素数(偶数チェックは抜いてるので全部で10個)で割り切れる数が(1つ使う偶数も含め)2つ以上あったらそのパターンはNG、のようにチェックする。19x10=190

18×2^18×190=896532480 (8.9e8)
ギリギリかな…

→AC (596ms)
https://beta.atcoder.jp/contests/colopl2018-qual/submissions/3775651

解説読んだ

大体同じ方針。3の倍数も分けて考えることでさらに計算量を減らしている。(18\cdot 2^{18}18\cdot 12\cdot 2^{12}にできるのでかなり速くなる)

最速コード読んだ

https://beta.atcoder.jp/contests/colopl2018-qual/submissions/1844490
(by tossyさん)
1msとな
DPだ(桁DPみたいなやつ)
可能なパターンは36以内の素数(11個)のon/offで2048通りに分類できて
AからBまで1つずつ、それを使った場合で更新していって
なので高々36×2048の二重ループで計算が済んでしまう。
なるほど!

================

12/12(水)

天下一プログラマーコンテスト2016予選B

B - 天下一魔力発電 (400)

はい(できるだけ右に行かずに済ませたいので、右から半分、というか可能な限り右はいじらない。左端で完結するように推移させる)
→AC
https://beta.atcoder.jp/contests/tenka1-2016-qualb/submissions/3779116


CODE FESTIVAL 2017 qual A

C - Palindromic Matrix (400)

はい(それぞれの文字の出現回数を数え、幅と高さがそれぞれ奇数か偶数かで場合分けして、4の倍数とか2の倍数とかのチェックをして)
→AC
https://beta.atcoder.jp/contests/code-festival-2017-quala/submissions/3779186

解説でやってることも同様なんだけど、これは通してみるまで不安系だ…

CODE FESTIVAL 2017 qual C

C - Inserting 'x' (400)

はい(xを全部抜いてpalindromeであることが必須条件(PASS1)。x以外の各文字の間にxがいくつずつあるか数えて、多い方に合わせる形でx入りpalindromeを構築する(PASS2)。)
→AC
https://beta.atcoder.jp/contests/code-festival-2017-qualc/submissions/3779232

解説では1passでやってた

DDCC2016予選

C - ロト2 (400)

  • Kを素因数分解する(以後、Kに含まれる素数だけを見ればいい)
  • a[i]を素因数分解(Kに含まれない素数は無視)し、a[i]の約数を列挙する
    • それぞれの約数がa_1〜a_Nで何回ずつ現れたか数えておく
  • K/a[i]が(上述の約数として)何回現れたかを答えに加算する
    • (i,j)も(j,i)も数えられているのであとで2で割ること
  • a[i]の自乗がKの倍数になってしまうケースも数えてしまっているのでそれを引く

→TLE
https://beta.atcoder.jp/contests/ddcc2016-qual/submissions/3780196
最悪ケースで間に合わない。D=約数の個数とするとO(ND)で、1e9までの数の約数の最大数は2000を超えたような気がする。
ちょっと工夫しないと。

  • Kの約数を全列挙する
  • a[i] = gcd(a[i], K)
    • これでKに含まれない素数はa[i]から排除できる。これでa[i]がすべてKの約数になる。
  • a[i] の出現回数を調べておく
  • 掛け合わせるとKの倍数になるようなKの2つの約数(u,v)を洗い出し、table[u] = Σ(vの出現回数) を求めておく
  • 各a[i]についてtable[a[i]]を調べて答えに足す
  • 自乗がKの倍数になる約数uについて、uの出現回数を答えから引く
  • 最後に答えを2で割る

→AC
https://beta.atcoder.jp/contests/ddcc2016-qual/submissions/3780265

解説解も同様。

Kの約数の個数d(K)は (今回の制約では)1344個で抑えられる

なるほど

第3回 ドワンゴからの挑戦状(2016) 予選

C - スキーリフトの相乗り (400)

はい(人数の多いグループから優先的に充填していく感じで)
→AC
https://beta.atcoder.jp/contests/dwacon2017-prelims/submissions/3780387

みんなのプロコン(2017)

C - 検索 (400)

はい(検索にかかってほしい単語とかかってほしくない単語に分離し、それぞれTrieを構築し、かかる側Trieの最短共通prefixを求め、それがかからない側Trieに何文字かかるか調べてそれに1を加えて最短共通prefixの先頭からその文字数だけ答える。かからない語がない場合は空文字列でよい。)
→AC
https://beta.atcoder.jp/contests/a-procon2017-qual/submissions/3780593

別にTrieを組むまでもなさそう。

第4回 ドワンゴからの挑戦状(2018) 本選(オープン)

A - アナログ時計 (400)

はい(整数演算で出来るように1/59*11秒を1単位として計算。面倒くさい)
→AC
https://beta.atcoder.jp/contests/dwacon2018-final-open/submissions/3780700

解説読んだ

実際に時計を回してシミュレーションしても 61*C1_MAX 回数程度のループに抑えられるので、考えるよりもシミュレーションで実装したほうが早い

それな


みんなのプロコン(2017) 本選オープン

A - YahooYahooYahoo (400)

うーん
ああ
DPで行けるか: dp[i文字読んだ後][yahooの何文字目]
遷移の洗い出しが面倒いけど
→AC
https://beta.atcoder.jp/contests/yahoo-procon2017-final-open/submissions/3780804

解説の
「適当に1周だけすると境界でおかしいことになりうる」「2周すればOK」ってのがよく分からない。

dp[L+1][5] の2番目の次元がいま"yahoo"のどこかを表すわけだけど、
https://kimiyuki.net/writeup/algo/atcoder/yahoo-procon-2017-final-a/
http://noimin.hatenablog.com/entry/2017/12/26/222949
要するに、どこからどこまでの5つを見るか考えるの面倒くさいから2周回せばいいということかな
(自分のやつはループではなく細かく手書きしてたから関係なかったけど、そういうのを精密に考える必要なんてなくて雑に2周回せばいいんだよという知見だ)


12/13(木)

COLOCON -Colopl programming contest 2018- Final(オープンコンテスト)

B - 異世界数式 (400)

はい(lexer/parser書いてASTを組み上げて中置で書き出した;面倒くさ)
→AC
https://beta.atcoder.jp/contests/colopl2018-final-open/submissions/3783376

解説読んだ。自分のは解説解法1で解いてたんだけど

詳細略
(解法2を使おう!)

これはウケる
元の文字列中の演算子を前置じゃなくてカンマの位置に出現させればいいだけの話だ

書き直してみた。これは簡単すぎて泣ける
→AC
https://beta.atcoder.jp/contests/colopl2018-final-open/submissions/3783422

codeFlyer (bitFlyer Programming Contest)オープンコンテスト

B - 交通費 (400)

  • min(|Xi-c|,d) を d-min(0,d-|Xi-c|) と書き換えて
  • dNから以下の2つの部分和を引く
    • [c-d, c) の範囲のXiについて Σmin(d-|c-Xi|)=k(d-c)-ΣXi
    • [c, c+d) の範囲のXiについて Σmin(d-|Xi-c|)=k(d+c)+ΣXi
  • kはXiの各区間の要素数。Σは累積和を取っておけばそれぞれO(1)
  • 2つの範囲は二分探索で求まるのでO(logN)

というわけでO(N+QlogN)で解くことができましたとさ
→AC
https://beta.atcoder.jp/contests/bitflyer2018-final-open/submissions/3783711

解説もほぼ同様

CODE THANKS FESTIVAL 2017 (Parallel)

E - Coin Authentication (400)

インタラクティブ問題。50袋のコインの真贋を10回以内のクエリで当てないといけない。
本物の偶奇を調べるのは出来そうなんだけど10回じゃ50枚も無理だろ
ていうか
なぜ10000枚も入ってる?
なぜ8,9,10,11,12の5種類?

例えば、1番を1枚、2番を100枚とか調べて、1番の重さが8、2番の重さが11だったら1108とかが返ってくるよね
重さは5種類だし、これ5進法みたいなことで出来るのかな
1,5,25,125,625,3125で
1a + 5b + 25c + 125d + 625e + 3125f
が返ってきて。枚数x8を引いたら綺麗に5進数で答え(-8)が出てくるのでは。
6個ずつやっても高々9回目ですべての重さが判明するので、重さ%2を返せば終わり。
→AC
https://beta.atcoder.jp/contests/code-thanks-festival-2017-open/submissions/3784005

解説も同様。

CODE THANKS FESTIVAL 2018 (Parallel)

E - Union

えっと
下からDP

  • 数字iがj個になる組み合わせが何通りか、のDP
    • 数字iが1個になる組み合わせの数を答えに追加
  • 雑に1024x1024ぐらい取ってて最大3e8のループ
    • 600ぐらいで十分なはずだし、可能性がなくなったら止めてもいい

→WA(1) : mod1e9+7忘れてた
→AC
https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3784396

解説も同様。


12/14(金)

SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open)

B - Neutralize (400)

とりあえずK個の合計が負になる部分を貪欲に切っちゃっていいのか?(その後その両サイドを広げていくような)
幅Kで切ってマイナスになるブロックの連続のうち一番低いところを食っていって、その左右を削る感じの実装をしてみた
→WA
最初の11件だけACで残り33件WA...

解説読んだ


DPで解けちゃうの…
そうか
0連続の末尾か否かで分けて

  • 0末尾[i]:max(非0末尾[i-K], 0末尾[i-1])
  • 非0末尾[i]:max(非0末尾[i-1], 0末尾[i-1])+b[i]


max(0末尾[N], 非0末尾[N])が答え、みたいな感じか
→AC
https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/submissions/3788844

(DPで簡単に解けるってところに考えが至らず悔しい)

12/15(土)

CODE THANKS FESTIVAL 2018(Parallel)

F - Coins on the tree (400)

// なんでサンプル2が-1なのか分からない…サンプル1より操作回数が1多いなら根に置けて1 3 2になるのでは?あ、そうかM=2だから(=コインが2枚しかないから)か

  • postorder traversalした順になる(*)
  • コストはそのノードの深さ(根を1とする)
  • M枚使う
  • コストの合計がKになる

でどう攻める?

  • v_1〜v_M の先頭に来るのが何になるかN=300通り試す?
  • コスト合計がKになる組み合わせが存在するか?

右から dp[N+1][M+1][K+1] みたいなDPを書いてみた
(位置n以降でm個使ってコストKになる手が存在するかをbitsetで)

左から1つずつ決めていく方式

サンプルケースが通ったので投げてみる

→RE(1)
あ、bitsetの長さをデバッグ用に短くしたままだった
100001とかにして
→WA(1)
サンプル以外で5ケースぐらいACが出てるけど残りはWA…(TLEは出てない)

解説読む前に上位解を見てみる

左から1つずつ決めていくというのはそれで良さそう。これでいいかをDFSで調べてる?
マジックナンバー"252521"(にっこにっこにー?)...

これもDFS…?

解説読んだ


そうか、postorder traversal順じゃなくて単に「深い順」だ…

深い順に並べ替えて
→WA
同じ深さなら番号順に行ける...
→WA

違うな
深いやつが必ずしも先に来ないといけないわけじゃない
深いやつの邪魔をしない限り浅いやつが先に来てもいい…
あああ
なるほど

  • 左から1つずつ決めていく(やってた)
  • 各位置について1〜Nまで試す(やってた)
  • 使った(もう使えない)木のノードを塗り潰す(なるほど)
  • まだ使えるノードの中で和が K-(これまでのコスト)-今使おうとしてるやつ, にできれば採用(それは分かるんだけどそこの計算量どう減らす?
    • n個の和がkになるやつがあるか = 小さい方からn個の和 ≦ k ≦ 大きい方からn個の和、が成り立てばいい(らしいんだけど証明できる?)
      • sortして累積和取ってみたいなことを(惰性で)したけど、別に累積和を全部取る必要はない
      • (バケツソート的に)何がいくつあるか数えておくことで O(NlogN) ではなく O(N) で出来るとな(確かに)

→AC
https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3790140

元のWA解が1000+ms,1GB近く(991MB)使ってたのに対し、これは53ms/256KBで済んでいる(O(N)にすればさらに速くなるか)

自分の解答はdfsではなくqueueを使ったbfsになってるけど、どうせ全部見る(O(N))のでそれはどちらでも良いか

とりあえず400点は全部埋まった〜