Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
RedCoderがTypeScriptで競技プログラミングに挑戦して挫折した話
Search
forcia_dev_pr
December 07, 2022
1
1.2k
RedCoderがTypeScriptで競技プログラミングに挑戦して挫折した話
Shinjuku.ts#1発表資料
forcia_dev_pr
December 07, 2022
Tweet
Share
More Decks by forcia_dev_pr
See All by forcia_dev_pr
第7回ゆるふわオンサイト解説
forcia_dev_pr
0
130
第6回ゆるふわオンサイト解説
forcia_dev_pr
0
170
よくわかるFORCIAのエンジニア旅行SaaSプロダクト開発編
forcia_dev_pr
0
490
よくわかるフォルシアのエンジニア 新卒採用編
forcia_dev_pr
0
2.7k
第5回ゆるふわオンサイト解説
forcia_dev_pr
0
110
よくわかるフォルシアのエンジニア 旅行プラットフォーム部編
forcia_dev_pr
0
4.7k
React hooks を気合で理解する
forcia_dev_pr
0
300
k8sマニフェストを Typescriptで管理したい― cdk8s+を導入してみました ―
forcia_dev_pr
0
300
第4回ゆるふわ競技プログラミングオンサイト解説
forcia_dev_pr
0
480
Featured
See All Featured
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
44
2.2k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
27
4.3k
Teambox: Starting and Learning
jrom
133
8.8k
Mobile First: as difficult as doing things right
swwweet
222
8.9k
A designer walks into a library…
pauljervisheath
204
24k
Code Reviewing Like a Champion
maltzj
520
39k
Building Your Own Lightsaber
phodgson
103
6.1k
Practical Orchestrator
shlominoach
186
10k
Six Lessons from altMBA
skipperchong
27
3.5k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.3k
What's in a price? How to price your products and services
michaelherold
243
12k
We Have a Design System, Now What?
morganepeng
50
7.2k
Transcript
Red Coder が TypeScript で競技プログラミン グに挑戦して挫折した話 浦上 真之 2022.11.15 @Shinjuku.ts
自己紹介 • 浦上 真之(Masayuki Urakami) ◦ Twitter: @tempura_cpp
• ソフトウェアエンジニア@フォルシア株式会社 ◦ Webアプリケーション開発(TypeScript, Node.js, React, Next.js, PostgreSQL など) • (元)競技プログラマ ◦ AtCoder で最高レート 2865 を達成(上位約0.3%) 2 あとでいい感じの 画像に置き換える
競技プログラミング • 複数の課題が与えられて、それを解くプログラムを作成する ◦ 試験時間内に正解した問題数や解答時間等で順位が決定する ◦ 「複雑な処理を正しく記述する」「計算時間のかかる処理を、数学的/情報科学的に効率よく 処理する」能力などを競う • AtCoder
◦ 国内最大の競技プログラミングコンテストサイト ◦ 様々な言語が使用可能 ▪ C, C++, Python, Java, Ruby, Rust, Haskell, … ▪ JavaScript(Node 12.16.1), TypeScript(3.8) も! 3
過去に最高レート2865を達成した競技プログラマが 業務で常用しているTypeScriptで挑戦すれば どんな問題でも簡単に解ける説 4
問題① (Atcoder Beginner Contest 277 B問題) 問題概要 2 文字の文字列がN個与えられるので以下の3つの条件をすべてみたすか (≒トランプの手札を表す文字列として適切か)判定せよ。
• それぞれ文字列の1文字目は H, D, C, S のいずれかである • それぞれ文字列の2文字目は A, 2, 3, …, 9, T, J, Q, K のいずれかである • 全ての文字列は相異なる 5
解答例① 6
問題② (競プロ典型90問 055) 問題概要 N 個の整数 A1, A2, ⋯, AN
と整数 P, Qが与えられる。 この中から 5 個を選ぶ方法のうち、これら 5 個の整数の積を P で割ると Q 余るような ものが何通りあるか求めよ。 制約 • 5 <= N <= 100 • 0 <= Ai <= 10^9 • 0 <= Q < P <= 10^9 実行制限時間 5 秒 7
解答例②(不正解) 8
何がダメ? • 整数を5個掛け算すると、最大で(10^9)^5 = 10^45 • JavaScript の MAX_SAFE_INTEGER(=
2^53 - 1) を大きく上回っているので整数を正確に表 現できないため間違った答えになってしまう • a[i1] * a[i2] % p * a[i3] % p * a[i4] % p * a[i5] % p のように毎回 余りを取れば最大値を 10^18 程度に抑えられるがそれでも 2^53 - 1 を上回ってしまう ◦ 64bit 整数型を扱える言語(C++, Java, Rust など)はこの方法で正解することが できる(問題の想定解もこの方法) 9
ならば BigInt だ! 10
TLE(実行時間制限超過) 11
TLE(実行時間制限超過) 12
過去に最高レート2865を達成した競技プログラマが 業務で常用しているTypeScriptで挑戦すれば どんな問題でも簡単に解ける説 13
立証ならず 14
ご清聴ありがとうございました 15
諦めない • 結局 ◦ number 型同士の計算のまま ◦ 計算過程で一度も2^53-1を上回ることなく ◦
x * y % p (x, y, p は 10^9 以下の正の整数)を計算 できればいいということ • やってやろうじゃないか! 16
式変形① • 各数値は 10^9 < 2^30 なので高々30bit • xを32bit整数型で表したときの上位12bitをa,
下位20bitをb として x = a * 2^20 + b (a<2^10, b< 2^20) と表す • 同様に y = c * 2^20 + d (c<2^10, d< 2^20) と表す 17
式変形② x * y % p = (a * 2^20
+ b) * (c * 2^20 + d) % p = { a * c * (2^40) + a * 2^20 * d + b * (c * 2^20 + d) } % p = {a * c * (2^40 % p) + a * 2^20 * d + b * (c * 2^20 + d) } % p 18
式変形② x * y % p = (a * 2^20
+ b) * (c * 2^20 + d) % p = { a * c * (2^40) + a * 2^20 * d + b * (c * 2^20 + d) } % p = {a * c * (2^40 % p) + a * 2^20 * d + b * (c * 2^20 + d) } % p • a * c * (2^40 % p) < 2^10 * 2^10 * 2^30 = 2^50 • a * 2^20 * d < 2^10 * 2^20 * 2*20 = 2^50 • b * (c * 2^20 + d) < 2^20 * 2^30 = 2^50 19
式変形② x * y % p = (a * 2^20
+ b) * (c * 2^20 + d) % p = { a * c * (2^40) + a * 2^20 * d + b * (c * 2^20 + d) } % p = {a * c * (2^40 % p) + a * 2^20 * d + b * (c * 2^20 + d) } % p • a * c * (2^40 % p) < 2^10 * 2^10 * 2^30 = 2^50 • a * 2^20 * d < 2^10 * 2^20 * 2*20 = 2^50 • b * (c * 2^20 + d) < 2^20 * 2^30 = 2^50 できたぁぁ!!!!!!!! 20
こんな関数を定義して 21
これでどうだ! 22
AC(正解) 23
過去に最高レート2865を達成した競技プログラマが 業務で常用しているTypeScriptで挑戦すれば どんな問題でも簡単に解ける説 24
立証ならず が 工夫次第で頑張れることもある 25
EOF