らての精進日記

修行をします

競技プログラミングだけではダメだと感じた話

スペック

  • atcoderなど 赤
  • TOEIC700 speaking/writing 無
  • 開発経験 ほぼなし
  • B4

本題

就職 or 院進 で迷っていたのですが,諸々の理由で就職したいと考え,atcoder jobsで5社応募しました.

某社1

「弊社への関心があまり高くないように思われます」と言われて祈られた.すみませんでした.

F社

普通に落ちた.すみませんでした.

某社2

某社3

よくみたらインターンの応募だった
間違えましたと言えなかったのでインターンの面接受けたらインターン落ちた
すみませんでした.

F社

開発経験無し が響いたのか コミュ力の低さが問題視されたのか わからんけどスカスカの面接で祈られた
もう少しお話したかったな

お気持ち

競技プログラミング以外の能力をもっと磨かないと厳しいなと感じました.
atcoder jobsで応募したらすぐにレスポンスが帰って来てとてもすごいなと感じました.atcoderさん,素敵なサービスをありがとう.

codechef:PSUM

問題を解く過程で考えたことを書くよ

題意

Contest Page | CodeChef


N個の宝がある
i番目の宝の重さはciで、価値はviである
重さSまで許容するナップザックがある

ナップザックに収まるような(重さの合計がSを越えないように)宝の選び方すべてについて、(価値の合計)^Kを計算して、その総和を求めてください mod 998244353

N,S<=100
K<=100
ci<=100
vi<=10^9

考え方

前からdpしていくイメージで考える

今、[1,i-1]の中からいくつか選んで、その価値の総和がvであるとする。そして、v^Kが求まっているとする

このとき、(v+vi)^Kを計算できると嬉しい(i番目の宝を追加したときの価値^K)
二項展開すると、(v+vi)^K=Σbinom(K,k)v^k vi^(K-k)
あ、exponential generating functionの積が計算できればいいじゃん
→modが998244353 勝ちました


負けました
www.codechef.com


上記の解法について詳しく書くと、
dp[i][j][k]:=宝を[1,i]から選んで、重さの総和がjとなるようなすべての選び方についての、価値^kの総和
と定義すると、二項展開の式から、
dp[i][j][k]=dp[i-1][j][k]+ Σ[l=0,...,k] binom(k,l)dp[i-1][j-ci][l]*vi^(k-l)
という漸化式が生えて、これはO(NSK^2)で計算できる
ここで、漸化式をよく見るとexponential generating functionの積を計算するような形になっている gg




上記をさらに詳しく説明すると、
2つの数列{ai},{bj}があったときに、新たな数列
{ck} (ck=Σ[l=0,...,k] binom(k,l) ai*b
数式を普通に打ち込んだら読みにくいだろ やめました

JAG夏合宿2019参加記

参加しました

day1

担当した問題と、印象に残った問題について書きます
C:
やりまーす

D:
法が互いに素でないような連立合同式を解けばいい
ライブラリの使い方が分からなくてチーム全員大慌てでしたが、冷静になると、ベズーの等式を考えて拡張ユークリッドの互除法でささっと求解できるようなスマート人間になるべき


F:
これすごいですね 感動です

G:
こういう問題楽しいですね
明らかにdpなのはわかって、dpを成立させるために必要な状態の持ち方を考えていきます

H:
writer許さね~~~~~~~という気持ちになるんですが、こういう問題を堅実に実装できるようにならないとダメだな(気づき)

I:
ゾンビを基準とした相対位置・相対速度を考えるとかなり見通しがよい
人間について二分探索することにすると、普通にCHTになって終わり
しかしライブラリの仕様が分からず大幅にタイムロスした グッと睨むと蟻本ベースだとわかるので直線の追加の方向が理解できて終わり

上記のlogが2つの解法でギリギリ通ったんですが、並列二分探索すればCHTは線形のものを使用できてlogが減ります これが想定なのかな

J:
うん
ぽてちくんがフローを使う嘘を考えたんだけど、反省して議論してたら二部マッチングでよいとわかり、写経したフローが生きる 不死鳥 


K:
どう見ても2D Convolutionで、破滅

2D Convolutionがまともに解けるのは知っていたが、知識がないと無理だと思ってまともに考察しなかった 反省

wikipediaとか見てると、2Dの離散フーリエ変換を行列で表してみたらうれしい性質がある(2Dの離散フーリエ変換は、各行を離散フーリエ変換してから各列を離散フーリエ変換すればよい)ことがわかって、知見でした  

HIR180先生に、直接的に1D Convolutionに落とす方法を教えてもらって、嬉しい

総評:
時間かければ確実に解けるレベルの問題に時間をかけてしまっているところがある

ギア上げて素早く処理していきたいね 

day2

writer側です。いかがでしたか?僕が書いた問題を当ててみてください。一問も書いてません ぽてちくんごめんなさい

B:
こんなん無理だろ
C:
最小費用流に落ちるのはまあわかる(実はそこまで正当性をはっきり理解できていないが)

貪欲はよくわからん

F:
そういえばいまだに一般マッチング書いたことありません 理解もしてないし 詰んだ

G:
これかなり難しいと思うけどな でもsigmaroonはあっさり通している なぜ

H:
形式的冪級数で解けます(ホントかな??)


まあ愚直dpしてみるとかなり分かりやすい形になって、エスパーするなり組み合わせ的にイメージするなりdp配列を多項式で表現してみたりすると二項係数が出てくると思う

見た目は威圧的だけど考察はやりやすいと思うな

I:
これ絶対やりたくねえな アレルギーが出ます

J:
まあある程度分かりやすい式にはなって、計算方法が問題になる
ダブリングしながら多項式補間する方法普通に素敵だとおもった

総評:
ぽてちすごい

酒は飲んでも飲まれるな
人に迷惑をかけるな
酒を飲むな

やむなくさんごめん(いなかったけど)(他に謝るべき人いるだろ)

day3

C:
頭が悪いので貪欲に確信を持てない 実装も怖い よくわからないことはぽてちにやらせよう

D:
iとi xor Xはどちらか片方しか使ってはダメで、ここから2-SATが芽生える
3^nでダメなペアを列挙できるのはまあ難しくなくて、本当に難しいのは、なぜか2-SATをUFでやり始めたこと(無向辺ではありませんが??)

2-SATではSCCを用いるという事実を唐突に思い出して、焦りました

E:
なんかぽてちとreewが頑張ってたな 

F:

こういう問題見ると頭止まっちゃう 存在意義なし 赤コーダーとは

G:
英語が読めなさ過ぎて、"On the i-th operation, flip a fair coin"を読んだときに、木の頂点にコインが置いてある問題だと思っちゃって一生読解が進まなくなったな(どうして?)

みんなEやってたから邪魔しづらかったんだけど、勇気を出してぽてちに英語読んでもらえばよかったな 

問題自体は面白いと思います(題意が分かれば解けてたと思う(負け惜しみ))

H:
UFをマージすれば解けるけどなあ~~(思考停止)
UFをマージすれば解けるじゃん(天地開闢)(国士無双)

残り15でPCが開いたので書いたけどダメだった 主人公ではないので


I:
解けぬ
解説みても解けない

J:
なんかreewとぽてちが通したな なんで

総評:
だめ

おわりに

競技プログラミングをやりましょう

日記 20190316

卒業した

3/15に卒業式でした 朝まで飲んでから家に帰って寝て起きてバイトに行きました 3/16終わり。

ポエム

"みんなやってることをやらないこと" "周りと波長が合わないこと"をかっこいいと思っていた。
わざわざ学校をさぼって、学校の真横にあるパン屋で確率統計の本を読んでいる自分に酔っていた。
卒論提出が近いのに研究室に行かずに家でゲームやってる自分に満足していた。
いつの間にか自分しか見えなくなっていたと思う。周りに大切な人がたくさんいたのにね。大変お世話になりまさした!!やるな笑笑

2019/5/6追記:ポエム書くな

フォートナイトについて

やっぱりミドルセンシじゃないとエイムが合わないな 無理にローセンシでやってたけど戻したらまともになった

ポエム

時間経つの早くてびっくりする もっと毎日大切にしたい

趣味とか

競技プログラミングをちゃんとやろうと思います フォートナイトも楽しいけどね
新しい趣味を探しつつ、昔の趣味も大切にしたいな 
そういえばルービックキューブとか全然やってないな 

星見純那について

すき