swift-developers-japan

https://twitter.com/koher/status/1313500039206047751

昨晩AtCoderに登録して初めて競プロの問題に挑戦してみたんだけど、最近開催されたらしいAtCoder Regular Contest 104の問題に取り組んでみたら、問題B（↓）で大苦戦して1時間以上かかってしまった・・・。競プロむずい。 https://t.co/ldefCXxFbj

2:35 AM

AtCoder Beginners Selectionという初心者向け問題集があったのでやってみた。とりあえずABCの問題Cまでは解けそう。一問ミスっててWAを連発してしまったけど・・・。今のところSwiftでAtCoderも特に問題なさそう。

leetcodeとちがってArgmentを取るところからかかないといけないんですね

3:01 AM

こっちのほうがやりやすい

https://twitter.com/koher/status/1314015159732457474 なるほどｗ

https://developer.apple.com/documentation/foundation/nsdecimalmaxsize

次回 #swiftzoomin の内容決定しました。みんなで AtCoder に登録して、 Swift で AtCoder の過去問に挑戦します！ Swift で競技プログラミングに興味がある方は是非ご参加下さい。参加希望者の人数に合わせて枠は調整します。 https://t.co/tCcrS7nZHl

1

ただ、 Swift Zoomin' のために AtCoder を始めたというよりも（そうではあるのですが）、前から Swift で競プロに興味があって、それを Swift Zoomin' に持ってきたという感じです

前からそんなイメージでしたｗ Swift で競プロぼくも気になっていてleetcodeはちょくちょくやっていますね

僕は leetcode も AtCoder もやったことなくて、今週初めて競プロに手を出しました。

7:59 AM

これはなかなかおもしろいゲームですね。

ｗｗｗｗｗたしかにこれはゲームっちゃゲームか

ゲームにしか見えませんでした

なんか「競プロ」っていう一種の競技種目のように見てました

8:01 AM

あーでも、競技種目 == ゲームか

そうですね。あまり境目がないイメージです。

8:01 AM

遊びで競技をやる人もいるし、本気で勝負する人もいるし。

今日は初めて↓のABCのD問題に挑戦してみましたが、結構難しかったです。 https://atcoder.jp/contests/abc138/tasks/abc138_d

D - Ki

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

↓当たり前とはいえ、要素数が限られてるなら Set 使うよりも Array を使った方が速かったです。 Set だと 375 ms 、 Array だと 354 ms 。 Set 版: https://atcoder.jp/contests/hhkb2020/submissions/17324446 Array 版: https://atcoder.jp/contests/hhkb2020/submissions/17324417

昨日・今日でコンテスト初参加してみました。今のところ Swift で不利を感じることはなかったです。 ARC 107: https://atcoder.jp/contests/arc107/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=koher ABC 181: https://atcoder.jp/contests/abc181/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=koher

2:11 PM

強いて言えば、 Python みたいにデフォルトで Big Integer が使えると若干楽になりそうなケースがあるくらい？

Pythonってそうなのかと思って調べたら桁数に制限がないんですね！

2:24 PM

BigInt的なものが必要な問題はどれくらいの桁数が必要なんですか？

最終的には 64 bit に収まるように余りを計算させられるんですが、

2:27 PM

その場合、途中の計算をすべて % つけないといけなくて面倒で、

2:27 PM

Python だったら最後に % つけとけば良いみたいな問題がありました。

2:28 PM

ただ、基本的には Python だろうと % つけて都度計算しとかないととんでもない桁数になる問題が多いので

2:28 PM

ほとんどの場合は変わらないと思います。

2:29 PM

↓これとか。 https://atcoder.jp/contests/arc107/tasks/arc107_a

A - Simple Math

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

なるほど。まあPythonがいろいろ入ってて便利そうというのはわかります。

1 ≤ A, B, C ≤ 10^9 で、積の和を計算するので、とてもじゃないけど 64 bit じゃ収まらないです。

2:31 PM

Python で % 前の値を出力させてみたら↓でした。 1858445835049782285757026664950217712384527500000000

2:32 PM

ただ、この程度で収まるのは例外的なので、基本的には Python でも都度 % の計算が必要になります。なので、あまり変わらないかなと。

Pythonはメモリがあればこの桁数を普通に使えるのか。

Swift も標準ライブラリで BigInt が使えれば同じことができるんですが・・・。

2:34 PM

Python は↓を計算させてみると楽しいですよ。 2 ** (2 ** (2 ** (2 ** 2)))

すごいすごい

2:39 PM

Pythonすごいなあ

Swift でも Decimal で同じことできるかと思ったんですが、 pow の第 2 引数に Decimal を渡せないのでダメでした・・・。

Decimalは意外と桁数制限がすぐに来なかったかな。あれはNSDecimalNumberだけかな？

2:42 PM

SwiftCryptoあたりにないかなと思ったけど無かった https://github.com/apple/swift-crypto/blob/afe4c9b5f65b612a2bd4b1cb5ac70eb5841f278e/Sources/Crypto/ASN1/Basic%20ASN1%20Types/ArraySliceBigint.swift

apple/swift-crypto

Open-source implementation of a substantial portion of the API of Apple CryptoKit suitable for use on Linux platforms. - apple/swift-crypto

そうなんですか？使ったことないので知見がないです

なくはないけど思ってたのと違う

BigInt ↓これはあるんですが https://github.com/dankogai/swift-pons

dankogai/swift-pons

Protocol-Oriented Number System in Pure Swift. Contribute to dankogai/swift-pons development by creating an account on GitHub.

2:44 PM

AtCoder ではライブラリを入れられないのでそのままじゃ使えないです

2:44 PM

Gives a precision of at least 38 decimal digits, 128 binary positions.

2:45 PM

普通に使うには十分な桁数だけどさっきの用途には足りなさそう。

結構少ないんですね。

2:48 PM

コピペ用 BigInt 作るか・・・。

https://github.com/mkrd/Swift-BigInt ワンソースファイルのBitInt

mkrd/Swift-BigInt

A lightweight, Multiple Precision Arithmetic Library for Swift! - mkrd/Swift-BigInt

長っｗ

2:50 PM

コード長512KBiまでの制限があるけど、さすがにそれは大丈夫かな・・・。

Doubleの部分はいらないから1000行は減らせるかな。。。

まあでも、 AtCoder に限れば BigInt 必要と感じたことはないんですよね。

2:54 PM

あー、でも微妙にオーバーフローで実行時エラーになることはあるから、そういうのは Python や Ruby だと強そうですね。

2:54 PM

実行時エラーでもたしか 5 分のペナルティを受けるはず？

2:54 PM

あ、ちがった。 -Ounchecked だから実行時エラーにならないのか。

2:55 PM

単に Wrong Answer になるだけですね・・・。

2:56 PM

BigInt よりも ModInt を作りました。こっちで計算しておけば常に % で余りとってくれるので問題ないです。 BigInt では無理な桁数も扱ってくれるし。 https://github.com/koher/swift-atcoder-support/blob/main/Sources/AtCoderSupport/ModInt.swift

koher/swift-atcoder-support

Contribute to koher/swift-atcoder-support development by creating an account on GitHub.

998244353 この値はなんですか？なんか競技プログラミングではよく出てくる値みたいですけど。

素数で余りを計算させるのが定番みたいです。

3:14 PM

コピペ前提なので、問題によって modulus を書き換えて使うという荒業ですｗ

ということは競技プログラミングでよく使われる値、ということなんですね。

3:14 PM

おもしろい

1000000007 とかもよく使われるみたいです。

3:15 PM

まあ、たまたま一致とかがなくて、オーバーフロー気にせずに計算できるならなんでもいいんだと思います。

そうそう 10の9乗+7というのも見ました。

負の数の場合、 Swift の % だと結果が負になってしまうので、そこのケアも ModInt でやってます。

3:16 PM

最初は %+ とか %- とか作ろうかと思ったんですが、型にしました。

3:17 PM

でも型考えるの地味に面倒なので、 %+ とかの方が用途に合ってるかもしれません。

競技プログラミング、おもしろそうですね。

おもしろいですよ。ぜひ @Kishikawa Katsumi さんも！

3:29 PM

登録自体は 2, 3 分で終わりますし、登録が終わった後に初心者が練習で挑戦すべき過去問集↓があって、過去問だけど実際にコードを提出してクリアできるか試せます。テストを通すコードを書いてる感覚。 https://atcoder.jp/contests/abs/tasks

Tasks - AtCoder Beginners Selection

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

3:31 PM

2 秒の制限時間があるので、工夫しないと制限時間オーバー（ TLE ）になる問題（↓とか）もあって、制限時間クリアできたらうれしいです。 https://atcoder.jp/contests/abc180/tasks/abc180_c

C - Cream puff

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

3:31 PM

僕もまだ競プロ歴 1 ヶ月未満なので是非一緒に挑戦しましょう〜。

今日の ARC は Swift で C 問題まで解けたの二人だけでした

2:30 PM

Go は 8 人、 Rust は 42 人。

便利ツールだ https://qiita.com/hotpepsi/items/c9bea1500d38a3f6d4c9

Xcodeで競技プログラミング - Qiita

これはCompetitive Programming (1) Advent Calendar 2020の8日目の記事です。 AtCoder Tools for Xcode SwiftでAtCoderを楽しむ方が増えてきたので、k...

はやい! ありがとうございます

今日21時からBeginner Contestあります。初めてコンテストに参加するにはちょうど良いかと。 https://atcoder.jp/contests/abc185

AtCoder Beginner Contest 185 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

これ見て行けると思って突撃したら見事に動作しないコードを生成してほぼ丸々書き直しました

https://twitter.com/koher/status/1352765051568943105?s=21

Swift競プロ部 (2021/02/06 22:40〜)

嘘です。仕様通り動くコードを書くだけでも難しいです。動くコードを書くのは簡単とか言ってる人はぬるいコードしか書いてないのでは？僕はこの前これ https://t.co/0CXJ7J8Ux7 を仕様通り動かすことすらできませんでした。 https://t.co/bm0D2KvlSk

1

書き直したってことは通ったってことですか？すごい！

11:35 AM

↑今日の Swift Zoomin' で問題解けて暇な人向けに使う予定だったので、別の問題用意しないと・・・。

やばい、直前で予定に影響を与えてしまった

1

この問題は解を与える式と実装の距離が遠く感じましたね

昨日の ABC 190 の E 問題で必要だった巡回セールスマン問題の Swift 実装です。なお、昨日の問題では最後にスタート地点に戻る必要がなかったので 5 行目の右辺を 0 にする必要があります。 https://github.com/koher/swift-atcoder-support/blob/main/Sources/AtCoderSupport/TSP.swift#L5

今日は出ようかなと考えています

1

今日の22:40からの「Swift競プロ部」では音声チャットチャンネルの kyoprobu を使いますが、テキストチャットが必要な場合（コードやリンクを貼るとか）はこちらのチャンネルを使おうと思います。 https://connpass.com/event/202305/

# Swift競プロ部 Swift で AtCoder Beginner Contest 191 （以下、 ABC 191 ）に挑戦し、コンテスト終了後にわいわい語り合います。会場は Discord の swift-developers-japan サーバーの音声チャンネル

kyoprobu です。

ABC 191 は個人戦です。コンテスト中に他人とコミュニケーションを取ることはできません。本イベントはコンテスト終了後に開催します。 # Swift と競プロ競技プログラミングにおける Swift 使用人口は多くありません。だからこそ、 Swift 競プロerで集まってわい...

1

待機

2問は解きたい･･････

1

ぐえー

1:41 PM

3問目悔しい

2完でした、くやしい

おなじく２完・・！

なかーまもう少し時間があれば3完できたかも…（かなり回りくどいやり方ですが）

1:49 PM

A https://atcoder.jp/contests/abc191/submissions/19959446

Submission #19959446 - AtCoder Beginner Contest 191

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

1:49 PM

B https://atcoder.jp/contests/abc191/submissions/19966044

Submission #19966044 - AtCoder Beginner Contest 191

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

1:50 PM

Aは print(D < V * T || V * S < D ? "Yes" : "No") で算出しました

A はprint(!(v*t...v*s).contains(d) ? "Yes" : "No") にしてみました！

かしはらさん消えている範囲をrangeで示すの、わかりやすいですね…！

1

1:54 PM

! を付けることで消えていないときに "Yes" を出しているのですね

1:55 PM

Bは print(aa.filter { $0 != X } .map { String($0) } .joined(separator: " ")) で算出しました

1:56 PM

mapの中身以外はこひーさんと同じ書き方だ

自己交叉のない多角形の意味がわからなくてググりました

意味を知らなくてもいいかなぁと思い、わからないまま進めましたｗ

tardigrade さんと同じだ

hotpepsiさんつよすぎるんですよね…笑

おおお

2:11 PM

なるほど＞辺の数から角の数

あそっか四角形は辺が4つ

2:15 PM

ちなみに他の人の説明を聞いても全然ついていけないｗ

テストケースに凹の例ほしかったですね

例が1つだけなの厳しい

https://atcoder.jp/contests/abc191/editorial/612

Editorial - AtCoder Beginner Contest 191

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

自己交叉の意味、Wikipediaを見てもわからないｗ https://ja.wikipedia.org/wiki/%E4%BA%A4%E5%8F%89%E7%90%86%E8%AB%96#%E8%87%AA%E5%B7%B1%E4%BA%A4%E5%8F%89

%E4%BA%A4%E5%8F%89%E7%90%86%E8%AB%96

私もそれを読んで「わからなくていいや」となりましたw

ですよねｗ

2:23 PM

どういうことなんだってばよ…

2:24 PM

私も3x3で考えてパターン多すぎて終わりました

2:27 PM

これの意味がわからん

2:33 PM

D以降は考えてすらいないので抜けますm( )m

# が 1or3 のだと角になる。の説明書いてみました

1

31415939325

だいたい円周率っぽくなるんですね

kashihararara

# が 1or3 のだと角になる。の説明書いてみました

おおおおおおお理解できました、ありがとうございますm( )m

自分もそろそろ音声チャット抜けます

おつかれさまでした！

私も失礼します！おつかれさまでしたー！

E以降は着手できていないのでこの辺りで失礼します

お疲れ様でした

私も失礼します、色々勉強になりました

iPad の Swift Playgrounds でやる場合、User Modules にこういう readLine() を定義しておくとコードの変更なしでテストできるのでそうやってました。

// Paste a sample input here var stdinString: [String] = """ 42782.4720 31949.0192 99999.99 <- ここに標準入力の内容を貼り付ける """.split(separator: "\n").map(String.init).reversed() public func readLine() -> String? { stdinString.popLast() }

https://discord.com/channels/291054398077927425/763427634179735592/785524649504145428

FYI: https://kato-hiro.github.io/AtCoderClans/cli

AtCoder Clans

【非公式】AtCoderがもっと楽しくなるリンク集です。有志による非公式サービス・ツール・ライブラリ・記事などをまとめています。

oj 対応状況: https://github.com/online-judge-tools/api-client (edited)

online-judge-tools/api-client

API client to develop tools for competitive programming - online-judge-tools/api-client

https://atcoder.jp/contests/abc191

AtCoder Beginner Contest 191 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

ありがとうございました〜

hとw逆なので30分ぐらいハマってた･･････

giginet

hとw逆なので30分ぐらいハマってた･･････

あるあるですね

D問題WAが4個残ってましたが、10^4倍して無事ACなりましたー！浮動小数点厄介ですね... 満足...

1

https://twitter.com/yuuboku/status/1358361869782716419

遊牧家族/yuuboku (@yuuboku)

AtCoderの何角形問題についてです

Retweets

151

Likes

524

1

今日も3完でした！Cでつまらないミスをしてしまい、時間がかかってしまいました

1

僕はDまではスムーズに行ったんですが、Eが前にやった https://atcoder.jp/contests/abc186/tasks/abc186_e の変化形だなとわかって、前の問題すら理解してなかったので半分途中から諦めてました。 (edited)

E - Throne

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

1

Swiftで提出されたコードを見てると、意外とみんな 2... でループするってやってないですね。 @swift-5.2.5 let n = 10000000000 var aa: Set<Int> = [] for a in 2... { if a * a > n { break } aa.insert(a) } print(aa.sorted().last!) (edited)

100000 (edited)

ついに入茶しましたー！ https://twitter.com/the_uhooi/status/1370735412163997697?s=20

ウホーイ (@the_uhooi)

AtCoder を始めて約 4 ヶ月、ついに入茶…！本当に嬉しい

https://t.co/P9LOv8WnG3

4

2:16 PM

今日知ったんですが、毎回, 解説放送が youtube で流れてるんですねパナソニックプログラミングコンテスト（AtCoder Beginner Contest 195） - YouTube https://www.youtube.com/watch?v=k2fzO_U7RnA

AtCoder Live

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）

2:17 PM

みかんが怖くなりました

知っていましたが、文字の解説だけで満足して1回も見たことなかったですｗ

なるほどｗ

2:20 PM

今日は文字の解説だけでは理解できなかったので閲覧中〜

その場合はよさそうですね、自分は解説読んでわからなかったら諦めていたので、動画も見てみようかな…ｗ

（ちなみにB問題がC問題より難しくて解説見てますｗ）

わかりますｗ Cのほうが簡単でしたｗ

良い取材 https://www.youtube.com/watch?v=WGNQrH0AV2k

テレ東NEWS

未経験者のアナタもハマる？競技プログラミング「AtCoder」って何だ？【理系通信】（2021年3月19日）

1

1:47 AM

そんな競技プログラミングのコンテストに、プログラミングのド素人・橋本ディレクターが挑戦。

さりげなく３完してるのすごいｗ

uhooi

わかりますｗ Cのほうが簡単でしたｗ

これ、僕も B パスして D までやってから B に戻りました。実際 difficulty も B は 483 で C は 265 になってますね

https://kenkoooo.com/atcoder#/list/

1

koher

これ、僕も B パスして D までやってから B に戻りました。実際 difficulty も B は 483 で C は 265 になってますね

https://kenkoooo.com/atcoder#/list/

おおっこんなサイトが！

毎週コンテスト後は、今日の問題の難易度はどれくらいだったんだろうと楽しみに待機してます

1

レッドコーダーの方の記事

https://engineer-lab.findy-code.io/redcoder

findy-lab

現役高校生が、AtCoderでレッドコーダーになるまでにやってきたこと。プログラミング上達の秘訣を全て教えます - Findy Eng...

こんにちは、はじめまして。筑波大学附属駒場高等学校 3 年生（今年 4 月から東京大学に入学予定）の米田優峻（@e869120）と申します。私は競技プログラミング（競プロ）が趣味で、AtCoder・情報オリンピック・パソコン甲子園などの大会に出場しています。2021 年 3 月時点で、AtCoder では赤色（レッドコーダー）です。また、国際情報オリンピックの 2018 年／2019 年／2020 年大会で金メダルを獲得しています。*1 とはいえ、決して簡単にこの記録を手に入れられたわけではありません。何度も挫折と失敗を経験しながら自分のスキルを磨いた結果、競プロを始めてから 3 年後にはレッ…

今週のabcは日曜開催だった https://atcoder.jp/contests/abc198 (edited)

AtCoder Beginner Contest 198 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

お、ABCないなぁと思ってたら生えたんですね。

昨日か今日、生えたみたいですねぇ

↓

kyoprobuでやってます。ABC出た方他にもいらっしゃればご自由にどうぞ。 https://twitter.com/koher/status/1390973068940431376 (edited)

https://github.com/apple/swift-evolution/blob/main/proposals/0225-binaryinteger-iseven-isodd-ismultiple.md

@koogawa @the_uhooi 今日のABC出ます？終了後Discordのボイチャで振り返りどうですか？

apple/swift-evolution

This maintains proposals for changes and user-visible enhancements to the Swift Programming Language. - apple/swift-evolution

2:25 PM

numbers.filter(\.isEven)

@takakengo

@swift-5.4.3 extension Int { var isEven: Bool { isMultiple(of: 2) } } print([2, 3, 5].filter(\.isEven))

[2]

@swift-5.4.3

let n = 5 var sumToCount: [Int: Int] = [:] for i in 1 ... n { for j in 1 ... n { for k in 1 ... n { let sum = i + j + k sumToCount[sum, default: 0] += 1 } } } for sum in sumToCount.keys.sorted() { print(sum, sumToCount[sum]!) }

3 1 4 3 5 6 6 10 7 15 8 18 9 19 10 18 11 15 12 10 13 6 14 3 15 1

let n = readInt1() let aa = readIntN() var aToCount: [Int: Int] = [:] for a in aa { aToCount[a % 200, default: 0] += 1 } var ans = 0 for count in aToCount.values { ans += count * (count - 1) / 2 } print(ans)

2:43 PM

https://github.com/apple/swift-evolution/blob/main/proposals/0165-dict.md

apple/swift-evolution

This maintains proposals for changes and user-visible enhancements to the Swift Programming Language. - apple/swift-evolution

2:44 PM

@swift-5.4.3 var a = true a.toggle() print(a)

false

@takakengo https://heart-of-swift.github.io/value-semantics/how-to-use-value-types

Swift が値型中心の言語になれた理由とその使い方

“Heart of Swift” は、 Swift の Heart である Value Semantics と Protocol-oriented Programming を軸に、 Swift という言語のコンセプトを説明するオンライン書籍です。

聞く専門でしたが、私も失礼いたします。勉強になりました♪

1

ほんと便利。 https://twitter.com/koher/status/1406249867924541446

koher (@koher)

AtCoderやってるとSwiftの dictionary[key, default: 0] += 1 みたいなのめっちゃよく使うな。 https://t.co/8Ot10eRyDG

2:01 PM

2回に1回は使ってる気がする。

2

dictionary[optional: index] みたいなのよく使う

3:31 PM

(実世界で)

誰か #毎日アルゴ式を Swift で解いてくれる人いないかな

https://twitter.com/algo_method/status/1427602147525361675?s=19

D - Sum of Maximum Weights

【#アルゴ式新企画開始！】本日から新企画「#毎日アルゴ式」を開始します！毎日1題、様々な分野のコンテンツの練習問題を基礎から順番に公開する、というものです。初回のテーマは「動的計画法」です！動的計画法の導入はこちらから読むことができます→ https://t.co/XNT49VsH2f (続きます)

2:34 PM

ウホーイはとりあえずできるところまでは解いて GitHub に上げていくつもりです

https://twitter.com/the_uhooi/status/1427625425010823191?s=19

ウホーイ🔴 (@the_uhooi)

動的計画法を知らないけど解いてみた N <= 1_000 だからこれで AC 取れる気がする…？ https://t.co/7Y9Jgcxkmc #アルゴ式 #毎日アルゴ式

2:35 PM

アルゴ式が Swift に対応していないから、つよい人が解いてその解答と照らし合わせたいw

行列の計算に落とせばO(logN)ぐらいで解けるんじゃ無いかな？という気がします

2:58 PM

上の解法はO(N)かな？

やってみました。 https://gist.github.com/koher/00bd76c909ff149d31d631676f1bcc48

1

3:04 PM

最初普通にループで解いたけど出題者の意図を組んで DP でも解いてみました。

3:06 PM

1個目はほぼウホーイさんと同じになりました。

[A0,A1]×[[X,Y],[Z,W]]=[A1,A2]となる行列XYZWを求める。この時、mod100は最終項の下2桁を取れば良いので無視する。A2=A0+A1のとき、行列は[[0,1],[1,1]]なので、答えは([A0,A1]×[[0,1],[1,1]]^N)[0]%100となる。計算量はO(logN) (edited)

1

3:07 PM

ザッと方針書いてみた↑ネタバレなので伏せてます

tarunon

ザッと方針書いてみた↑ネタバレなので伏せてます

N/2回2x2行列の掛け算を繰り返さないといけないのでO(N)じゃないでしょうか？

正確には4logNですがまあ

ああそうか

3:16 PM

log N か

3:16 PM

N乗はlogNでできるから

X^Y=(X^(Y/2))^2なので

3:17 PM

動的計画法だったんですね、問題を壊してしまいました

これ、 O(logN) じゃないと TLE になる問題にしたら結構おもしろそう。普段競プロやってる人でも結構解けない気がする。

初見で動的計画法な問題を行列計算に落とし込むのは、割と常套手段な予感もしますが、どうなんでしょうね、私は競プロガチ勢ではないからわからない

AtCoder で普段僕が解いてるレベルの問題（ 500 点問題くらいまで）では見たことがないです。もっと上位になるとわかりません＆去年の11月からのコンテストで僕が出たものに限りますが。 (edited)

なるほど、そんな感じなんですね

この、行列式の解法もめちゃくちゃテクい方法で更に計算量を圧縮する(4logNの4の部分について)みたいなのもあったと思うんですけど、ちょっと覚えてない

3:29 PM

10×10行列とかだと結構効いてくる

AtCoderで行列計算見たことないですねー。結構分野が偏ってるのかな。他に見たことがないのは SortedSet を使う問題。

3:32 PM

逆に、これまで見たことのなかったいくつかのデータ構造（ Union Find とか Priority Queue とか）やアルゴリズム（ワーシャルフロイドとかベルマンフォードとか）は結構頻出ですね。

3:32 PM

特に Union Find は初回コンテストから使ったし、これまで何度も使ってる。

3:33 PM

上記がライブラリとしてある前提で、 AtCoder の解答はコードとしてはかなり短めのものが多いです。

3:35 PM

先週末1時間以上考えてわからなかった↓とか、解説見て書いたら実質13行でした。 https://atcoder.jp/contests/abc214/tasks/abc214_d

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

TLEにならないだけで、スコア上位の人は普通に使ってるテクニックだったりする、というのは有り得るかな

制約を見て TLE にならない最も簡単な解法を選ぶことが多いですね。 O(log N) の解法が存在しても O(N) で簡単に解けるなら大体はそれを選びます。 (edited)

3:50 PM

逆に O(log N) が想定解なのに Swift が結構速いから O(N) でも通っちゃったみたいなのはあります。昔ウホーイさんがそれで二分探索の問題を線形探索で突破してました。 (edited)

1

ひどいw

uhooi

誰か #毎日アルゴ式を Swift で解いてくれる人いないかな

https://twitter.com/algo_method/status/1427602147525361675?s=19

私も解いてみました実行結果を試せないのがもどかしい

https://gist.github.com/koogawa/4a2de9795dc0a045dfe066fd47b867cb

https://algo-method.com/tasks/302

https://algo-method.com/tasks/302. GitHub Gist: instantly share code, notes, and snippets.

1

みなさんありがとうございますー！ウホーイはアルゴリズムの知識なしで解いているので、いろいろ勉強になります

koogawa

私も解いてみました実行結果を試せないのがもどかしい

https://gist.github.com/koogawa/4a2de9795dc0a045dfe066fd47b867cb

私と同じ解き方ですね！毎日21:00に次の問題と前の解答が公開されるようですが、今回は「動的計画法（dp）」というアルゴリズムがテーマなので、我々の解答は出題者の意図とは違うようですw ↑でこひーさんがdpの解法をgistに上げてくださっています！（まだちゃんと理解していない）

uhooi

私と同じ解き方ですね！毎日21:00に次の問題と前の解答が公開されるようですが、今回は「動的計画法（dp）」というアルゴリズムがテーマなので、我々の解答は出題者の意図とは違うようですw ↑でこひーさんがdpの解法をgistに上げてくださっています！（まだちゃんと理解していない）

なるほどｗ koher さんの解法、みてみます！

1

koogawa started a thread. 8/18/2021 12:47 AM

tarunon

[A0,A1]×[[X,Y],[Z,W]]=[A1,A2]となる行列XYZWを求める。この時、mod100は最終項の下2桁を取れば良いので無視する。A2=A0+A1のとき、行列は[[0,1],[1,1]]なので、答えは([A0,A1]×[[0,1],[1,1]]^N)[0]%100となる。計算量はO(logN) (edited)

これ対角化すれば行列の累乗計算いらないですね。 pow((1-sqrt(5))/2, N) が出てきますがこれって計算量どうなるんですっけ

おー

https://ja.wolframalpha.com/input/?i=%7B%7B0%2C+1%7D%2C+%7B1%2C+1%7D%7D%E3%82%92%E5%AF%BE%E8%A7%92%E5%8C%96%E3%81%99%E3%82%8B wolfram alphaまじ便利だ……

powはO(logN)ですね

5:02 AM

行列が数値に変わっただけなんだけど

なら変わらないですね。

sqrt(5)が浮動小数なのがちょっと気になりますね

定数のsqrtはコンパイラが計算してくれます

5:20 AM

そういう意味じゃなかった

@swift-5.4.3

import Foundation func original(n: Int, x: Int, y: Int) -> Int { var (n, x, y) = (n, x, y) for _ in 2 ..< n { let t = (x + y) % 100 x = y y = t } return y } struct Mat { var m11: Double var m12: Double var m21: Double var m22: Double init(_ m11: Double, _ m12: Double, _ m21: Double, _ m22: Double) { self.m11 = m11 self.m12 = m12 self.m21 = m21 self.m22 = m22 } static func * (lhs: Mat, rhs: Mat) -> Mat { Mat( lhs.m11*rhs.m11 + lhs.m12*rhs.m21, lhs.m11*rhs.m12 + lhs.m12*rhs.m22, lhs.m21*rhs.m11 + lhs.m22*rhs.m21, lhs.m21*rhs.m12 + lhs.m22*rhs.m22 ) } } func mat(n: Int, x: Int, y: Int) -> Double { let S = Mat( -(1+sqrt(5))/2, -(1-sqrt(5))/2, 1, 1 ) let Jn = Mat( pow((1-sqrt(5))/2, Double(n-2)), 0, 0, pow((1+sqrt(5))/2, Double(n-2)) ) let St = Mat( -1 / sqrt(5), (5-sqrt(5)) / 10, 1 / sqrt(5), (5+sqrt(5)) / 10 ) let m = S * Jn * St let num = Double(x) * m.m12 + Double(y) * m.m22 return num - floor(num/100)*100 } print(original(n: 60, x: 2, y: 3), mat(n: 60, x: 2, y: 3)) print(original(n: 80, x: 2, y: 3), mat(n: 80, x: 2, y: 3))

81 81.00830078125 91 64.0

誤差対策は必要そう

今日の問題 https://algo-method.com/tasks/303

すぐ諦めちゃいました！！！

解いてみました！動的計画法できてるかな https://gist.github.com/koogawa/79cd302dc86947cbf750d63c52dcb87d

https://algo-method.com/tasks/303

https://algo-method.com/tasks/303. GitHub Gist: instantly share code, notes, and snippets.

1

おお、なんかそれっぽいです…

昨日の koher さんの解法を真似してみました

すごい…

ちなみに、これを copy して Xcode にそのまま貼り付けると

1:43 PM

let aa = readLine()!.split(separator:" ").map { Int(String($0))! }

1:43 PM

で配列に分解できない

むむっ最後Stringなくして Int($0)! でもダメですか？

1:46 PM

let aa = readLine()!.split(separator: " ").map { Int($0)! }

1:47 PM

もしくは文字コードの問題？

Int($0) でもだめでした！

1:48 PM

aa を出力すると [] になります

1:48 PM

文字コードの問題かもしれないですねー

数字かスペースが全角になってるとか？w

貼り付けたあと、自分で return しないといけないのも気になる

最近覚えたDPテーブルで解いてみました。 https://gist.github.com/koher/00bd76c909ff149d31d631676f1bcc48#file-303-swift (edited)

1

11:40 PM

うまくペーストできないの気になりますよね。 VS Code に貼ってからコピペしなおすとうまくいきました。コンテストじゃないからいいですが、コンテストでこれだと辛いですね。

おぉっ　たしかにVS Code に貼ってからコピペしなおしたらうまくいきました

自分も解いてみました！ https://twitter.com/the_uhooi/status/1428146859294425088

ウホーイ🔴 (@the_uhooi)

初めての動的計画法間違っているかも…？ https://t.co/ei6fGDeira #毎日アルゴ式

1

12:12 AM

こひーさんとほぼ同じですね（なお dp テーブルの意味はわからないｗ）配列って要素数がわかっているなら、 append() するより init(repeating:count:) で最初に確保するほうがパフォーマンスがいいのでしょうか？

12:13 AM

あと私は dp.last! で強制アンラップしていますが、 dp[N - 1] でインデックスを使えば ! は不要ですね、、

12:18 AM

文字コードの件、報告してみました↓

動的計画法 1-2 について Xcode（Mac でしか動作しない IDE）のコンソールに入力例をコピペするとエラーになります。VSCode に貼ってからコピペし直すとうまくいくようなので、文字コードなどの問題かもしれません。 また、入力例を貼り付けたあとに自分で Enter キーを押下しないといけないのも地味に手間です。AtCoder では自動で Return まで入力されたので、同じ仕様だと嬉しいです。

1

uhooi

こひーさんとほぼ同じですね（なお dp テーブルの意味はわからないｗ）配列って要素数がわかっているなら、 append() するより init(repeating:count:) で最初に確保するほうがパフォーマンスがいいのでしょうか？

DP テーブルは↓で説明されています。少し前にテーブル作らないと TLE になる問題があって覚えました。なお、僕はこの記事の最初の 2, 3 個くらいまでしか読めてません。 https://qiita.com/drken/items/a5e6fe22863b7992efdb

典型的な DP (動的計画法) のパターンを整理 Part 1 ～ナップサック DP 編～ - Qiita

はじめに --- DP は役に立つはじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「DP が好きな人」と呼ば...

1

uhooi

こひーさんとほぼ同じですね（なお dp テーブルの意味はわからないｗ）配列って要素数がわかっているなら、 append() するより init(repeating:count:) で最初に確保するほうがパフォーマンスがいいのでしょうか？

パフォーマンスは若干良くなりますが、結局 O(N) なのでどちらでも良いと思います。ただ、 DP テーブルが 2 次元になるケースなどでは最初から確保しておかないといけないので、 1 次元でも確保しちゃえばいいかなくらいの気持ちでした。最初に確保しようとすると初期値が必要になるのが若干気持ち悪いかもしれませんね。

1

uhooi

あと私は dp.last! で強制アンラップしていますが、 dp[N - 1] でインデックスを使えば ! は不要ですね、、

! 不要ですが、 Array に [i] でアクセスするのは ! 使ってるのと同じ（ ! の nil も [i] の範囲外も Logic Failure ）なので、どちらが良いかと言われると微妙ですね。

1

Arrayは内部的に持てる要素数が決まっていてappendで場所が足りなくなったら場所を確保しなおすようになってます。この場所を確保しなおすのが重い処理なので単純にappendして行くだけだと遅くなります。予めArray#reserveCapacity(_:)で場所を確保しておけば問題ないです。

masakihori

Arrayは内部的に持てる要素数が決まっていてappendで場所が足りなくなったら場所を確保しなおすようになってます。この場所を確保しなおすのが重い処理なので単純にappendして行くだけだと遅くなります。予めArray#reserveCapacity(_:)で場所を確保しておけば問題ないです。

append でのバッファの確保は倍々に行われるので、バッファの allocate およびコピーの計算量がその長さに比例するとした場合、最終的に N 要素分の領域を確保するための計算量は reserveCapacity してもしなくても O(N) になります。もちろんそれでも reserveCapacity した方が定数倍速いんですが、競プロの問題は定数倍が原因で TLE になることは稀であり、成績を残すには速く解くことが重要なので、このようなケースでは reserveCapacity はほぼ必要ないと考えています。

https://github.com/apple/swift/blob/7123d2614b5f222d03b3762cb110d27a9dd98e24/stdlib/public/core/ArrayShared.swift#L163 ↑2倍にするところ

swift/ArrayShared.swift at 7123d2614b5f222d03b3762cb110d27a9dd98e24...

The Swift Programming Language. Contribute to apple/swift development by creating an account on GitHub.

2

本日の問題 https://algo-method.com/tasks/304

1:38 PM

（これ atcoder チャンネルでやっていいのかな…？）

競技プログラミング専用のチャンネルを新たに作るか、もしくはこのチャンネル名を競技プログラミングっぽく変更するか

1:41 PM

とかですかねー

atcoderだけで話題占有してるわけではないので後者で良さそう

1:45 PM

名前は変えなくても大きな問題は無いかなと思いますが、気になるなら治して良いと思います

私も今のチャンネル名のままで特に気になりません

自分も気になりませんが、AtCoderの話がしたい人の邪魔にならないかと思い…

AtCoderの話をしたい人が

を表明しない限り大丈夫です

はい！メンツほぼ変わらないので大丈夫そうですねw

2

意見じゃなくて単なる質問なんですけど競技プログラミングを表す英語ってあるんですか？

2:12 PM

あるかどうかでいうとそりゃあるか。同じくらいシンプルな訳語ってなんでしょう？

competitive programingって見たことあるけど直訳かもしんない

https://en.wikipedia.org/wiki/Competitive_programming

2:13 PM

あってそう

competitive、なるほど。

competitiveん？ってなるぐらいなら日本語で競プロとかでもいいですけどね

あ、日本語でチャンネル名ってことですね。

他に日本語のチャンネルがないと気持ち的に作りづらいですよね

2:23 PM

Kyoproとか

competitive programmingは普通に言うと思う。この業界で。

2:23 PM

日本語チャンネル、そういえばそんなのもあった。

kyoproとかでもいいかも。

2:45 PM

競技プログラミングは、東京大学競技プログラミング同好会2007年春台湾合宿から始まります。それまで、プログラミングコンテストは開催されてきましたが、競技プログラミングの名前が使われたのはこの合宿がはじめてで、このとき一つのジャンルが生み出されたのです。

https://nuc.hatenadiary.org/entry/2021/03/31

nuc

Twitter で医師を拾ってきて Google のソフトウェアエンジニアにするだけの簡単なお仕事 - 白のカピバラの逆極限 S.14...

はじめに「【転職エントリ】Googleに入社します｜Lillian｜note」という、医師から未経験で Google のソフトウェアエンジニアになった記事があります。 note.com 私は、この記事に出てくる「とある元 Google のソフトウェアエンジニア」で、面接の対策を立てました。記事が出た当初から大反響で、私もそれなりの反応を見まして、いろいろと誤解されているなあ、と思う一方、アドバイザーはあくまでもアドバイザーだから、アドバイザーとして知りえた情報については、口をつぐむべきだと思っていました。ただ、あまりにも誤解されており、悪影響が大きく、犠牲者も多くなってきたと思ったので、…

1

2:46 PM

これが史実かはわからないけど、あまり英語にする意味のない言葉かも？

2:48 PM

↓ではcompetitive programming使われてた。 https://en.wikipedia.org/wiki/Topcoder (edited)

Topcoder

Topcoder (formerly TopCoder) is a crowdsourcing company with an open global community of designers, developers, data scientists, and competitive programmers. Topcoder pays community members for their work on the projects and sells community services to corporate, mid-size, and small-business clients. Topcoder also organizes the annual Topcoder O...

2:48 PM

いや、competitive programmerか。

2:49 PM

あ、competitive programmingも出てきてるな。

名前は僕は atcoder のままでも変更になってもどちらでもいいです。

3:15 PM

DPについて、semisagi先生の教え。 https://twitter.com/semisagi/status/1428373622305873925

https://twitter.com/semisagi/status/1428373886970699779

動的計画法、探索するパターンが多すぎるときにパターンを減らす手法だと思っていて、具体的には区別しなくてもいいものを同一視するとパターンが減るっていうので大体説明できると思う

1

3:15 PM

https://atcoder.jp/contests/apg4b/tasks/APG4b_b

階段を登る例だと段数が同じになるような登り方を同一視して、ナップサック問題では同じ重さになる選び方を同一視して、行列積問題ではi番目からj番目までの積を求める方法を同一視している

1

3:20 PM

@koogawa @uhooi

1つのテーマについて、何パターンか解いていくと理解が深まりますねぇそれ思います！かなりいい練習になります…！

僕は未チャレンジですが、似たような感じで↓が評判良かったようなのでいいかもです。これなら AtCoder なので実行して試すこともできますし。 https://atcoder.jp/contests/typical90

競プロ典型 90 問 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

1

3:22 PM

みんなでやる楽しさもあるので、今のが終わったらここで1日目からみんなで始めてもいいかも？

koher

みんなでやる楽しさもあるので、今のが終わったらここで1日目からみんなで始めてもいいかも？

典型90問、気になりつつもまったく手を付けられていないので、ぜひみんなでやりたいです！！！

uhooi

典型90問、気になりつつもまったく手を付けられていないので、ぜひみんなでやりたいです！！！

今のが終わったら（いつになるかわかりませんが

）参加者を募ってやってみましょー！

1

今日から問題と解説が同時に公開されるようですね https://algo-method.com/tasks/305

1

2:14 PM

今日は見様見真似でcppで解いてみました https://algo-method.com/submissions/28697

1

2:15 PM

他の人の回答までリアルタイムで見れちゃうんですね https://algo-method.com/tasks/305/submissions

uhooi started a thread. 8/21/2021 3:33 AM

今回は動的計画法 1-2の応用っぽい動的計画法 1-5 https://algo-method.com/tasks/306

今日の問題 https://algo-method.com/tasks/323

今日の問題 https://algo-method.com/tasks/324 二次元になってきた

今日の問題 https://algo-method.com/tasks/325

1

koogawa さん、気づいたら C++ マスターしてそうｗ

cin >> cout << hoge << endl; みたいな書き方にもだんだん慣れてきましたｗ

これ何してるかよくわかっていませんｗ

カスタム演算子ですね。

let N = Int(readLine()!)! を cpp で書くと int N; cin >> N;

1:33 PM

みたいな雰囲気かな

1:34 PM

↑のように変換しながら解いてます

std::scanf std::printf 派もいるみたいです（こっちのほうが正統？） (edited)

printとString interpolationをその演算子を定義して割り当ててる、みたいな。

なるほど、 cin → c-input, cout → c-output みたいな略かな

cout が count みたいでややこしい！

思いますｗ

swift の print(hoge) は cout << hoge << endl

endl はなんやねんｗ

↑これだけ抑えておけば、勢いでなんとかなる！

uhooi

endl はなんやねんｗ

末尾改行ですね

1

character in/outかな。endlessはend lineかな。

1

おおーありがとうございます！なんの略かわかると覚えやすいんですよね

endl を end にすると改行しないバージョンかなーと予想して実行してみたんですが、エラーになりました

まあ慣れですけど今どきのセンスではないですね。普及したから許されるやつだと思います。

Apple 系のいいところは略語が少ないところです悪いところは略さないから長くなり過ぎるところです

わかります！

1:40 PM

componentsSeparatedByString とか、普通に英文として読める

stringByAddingPercentEncodingWithAllowedCharacters: とかも > 長いの

長いけど、何をするメソッドなのかわかりやすいですよね

(edited)

1

あ、ちなみにendlが改行なので、改行したくない場合はendlを書かなければいいです。 cout << なにか << なにかで終わる

左から処理していく感じですかね？一番右に endl を書くと末尾改行（Swift の print のデフォルト）になるっぽいですね

int main() { cout << "Hello" << "World!"; return 0; }

1:53 PM

HelloWorld!

1:53 PM

おおっ　なるほど！

わかりやすい！

B - 1.01.出力とコメント

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

int main() { cout << "Hello" << "World!" << endl << "hahaha"; return 0; }

HelloWorld! hahaha

endl を間に挟むこともできる！便利！

C++で文字列を出力するには cout（しーあうと）を使います

しーあうと！

読めんｗ cOut みたいに O を大文字にしてほしいｗ

あ、swift-developers-japan なのにc++ の話をしてしまっているｗ

2:01 PM

スレを作りますか

1

2:01 PM

C++の話題

これ、運営者に言えば Swift 足してもらえる可能性ないでしょうか？ Docker コンテナで動かしてるとして、 Docker Hub のどのイメージ使って、どんなコマンドでコンパイルして、どうやって実行するかという情報さえあれば結構簡単に追加できると思うんですが・・・。 (edited)

8:02 PM

https://twitter.com/algo_method に言えばいいのかな？

プログラミングや情報科学をコツコツ積み立てて学習できるサービス #アルゴ式の公式アカウントです。毎日21時に情報科学の教育的な練習問題を公開中です。現在ベータ版です

代表 → @sak_algo コンテンツ → @sak_algo + @drken1215 デザイン → @yukino_works

Tweets

137

Followers

1706

koher

これ、運営者に言えば Swift 足してもらえる可能性ないでしょうか？ Docker コンテナで動かしてるとして、 Docker Hub のどのイメージ使って、どんなコマンドでコンパイルして、どうやって実行するかという情報さえあれば結構簡単に追加できると思うんですが・・・。 (edited)

私は前にお問合せフォームからSwiftの追加を依頼しました！あとkoogawaさん宛に↓のリプも来ています https://twitter.com/algo_method/status/1428369065316216839?s=19 とはいえたくさんの人から要望すると追加されやすくなりそうなので、ありですね…！笑

@koogawa 本当ですね

のちほどコメントにて訂正させてください。ご指摘ありがとうございます！ (Swift の追加は現在開発班で検討中のため、もうしばらくお待ちいただけると幸いです。いつも問題を解いてくださりありがとうございます

)

uhooi

私は前にお問合せフォームからSwiftの追加を依頼しました！あとkoogawaさん宛に↓のリプも来ています https://twitter.com/algo_method/status/1428369065316216839?s=19 とはいえたくさんの人から要望すると追加されやすくなりそうなので、ありですね…！笑

そうだったんですね！僕もリプしておきました。

3

Swift だけに迅速な対応

https://twitter.com/semisagi/status/1430463417949704198?s=19

https://algo-method.com/submissions/36511

アルゴ式、swiftサポートしてくれたらしい。 https://t.co/EXRopvjtWh

5

直近のコード全部提出してみたら、全部1ケースだけコンパイルエラーで泣いてます

me too ですｗなんかおかしい気がしますね

10:04 AM

確認してくださるそうです https://twitter.com/sak_algo/status/1430470601383108609?s=20

sak (@sak_algo)

@the_uhooi え、これ確認します

2

今日の問題 https://algo-method.com/tasks/41

提出結果をみたところ、動的計画法1-2などでREになっているものは、Nに対してのRangeの範囲が原因のような気がしますね。

5:44 PM

Fatal error: Range requires lowerBound <= upperBound

5:44 PM

CEのほうはちょっとわかりませんが…。

strmikan

提出結果をみたところ、動的計画法1-2などでREになっているものは、Nに対してのRangeの範囲が原因のような気がしますね。

これは思いました、後ほど修正します、、

もしかしてCE問題でSwift一旦取り下げられてしまった？

koher

もしかしてCE問題でSwift一旦取り下げられてしまった？

そのようですね、、

1

アルゴ式、提出できるようになってます！

4

サーバーエラーを叩き出してしまったｗ

2

4:05 AM

CE の代わりに IE が出るようになっただけで、解決されていないですね、、泣

4:07 AM

実行時間と使用メモリがカンストしてるっぽいおま環ではないよね…？

ある意味 TLE や MLE ？

動いてるよ？

4:27 AM

そしたらワイのコードが悪そうですね

ありそうなのはループの終了条件がおかしくて無限ループ化してる

4:38 AM

ループ内でメモリを確保してる

4:39 AM

メモリのquotaでout

4:39 AM

ですかね

業務後にいろいろ見てみます、、

https://twitter.com/sak_algo/status/1430775265009885185?s=19

sak (@sak_algo)

@the_uhooi 返信遅くなりました、とりあえずの結論が出たのでのちほどアルゴ式公式からアナウンスします

‍♂️

6:17 AM

Swift について公式アナウンスがあるようです

2

今 Swift で解いたら全部動きましたー！

5

本日の問題 https://twitter.com/algo_method/status/1430862600095649793?s=19

https://twitter.com/algo_method/status/1430867791628804100

【 #毎日アルゴ式】本日 (8/26) の練習問題はこちらです！最適化問題ではない課題に動的計画法でアプローチする問題となっています。是非挑戦してみてください！ https://t.co/HODwhncSTt ※ 解説が公開されるまでの解法などの言及は自由に行っていただいて構いません

#アルゴ式

コードテンプレートめっちゃ便利

12:26 PM

AtCoder Beginner Contest 216 - AtCoder

【機能追加】問題を解く時にはじめに表示されるテンプレートを編集する「コードテンプレート機能」が追加されました！ユーザーページからオリジナルのコードテンプレートを作成することができます

#アルゴ式

2

本日の問題 https://algo-method.com/tasks/333

2

今週の abc は日曜開催！ https://atcoder.jp/contests/abc216

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

2:58 PM

（いつも土曜か日曜で迷う）

本日の問題 https://algo-method.com/tasks/334

3

本日の問題 https://algo-method.com/tasks/335

1

急いでシャワー浴びて ABC に備える

本日のABC https://atcoder.jp/contests/abc216

AtCoder Beginner Contest 216 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

本日の問題 https://algo-method.com/tasks/336

本日の問題 https://algo-method.com/tasks/337

1

メモ化について最高にわかりやすい記事があったので共有 https://twitter.com/the_uhooi/status/1432724849466781702?s=19

ウホーイ🔴 (@the_uhooi)

Hirobe さんの記事や登壇のわかりやすさは異常 https://t.co/OoWaVgvMEG 「メモ化」と「動的計画法」って同じ意味なのかな？再帰関数にしないほうが読みやすくなりそうだけど、それは好みかな？

せみさぎさんが競プロ用のスニペットを公開してくださっている https://twitter.com/semisagi/status/1432652106805039107?s=19

スニペットのファイル名を書き換えるプログラムを書き終えたのでgithubに競プロ用のスニペットが置けるようになった。https://t.co/bF9qstfGK2

3:57 PM

考察用のリポジトリまで…！ https://twitter.com/semisagi/status/1432733084160385028?s=19 内容は難しくてわからないけど、、笑

https://twitter.com/i/spaces/1lPKqXMlkgZxb

競プロの考察中に気づいたことを残すためのリポジトリを作った。https://t.co/VEjFjoKB8e

本日の問題 https://algo-method.com/tasks/341

これはw https://twitter.com/kiri8128/status/1433052028226334720?s=21

きり (@kiri8128)

ABC ヌーヴォー

ABC212: 非常に高いレベル（橙上位 Diff） ABC213: 50 回に 1 回のレベル（ABC 史上 4 回目の赤 Diff） ABC214: 歴史にないほどのレベル（ABC 史上最高 Diff 更新） ABC215: 過去最高と言われた前回に迫るレベル ABC216: 過去最高レベルと言われた前回・前々回を超えるレベル

2

2:01 PM

↓のH問題のdiffと見比べるとおもしろいです。 https://kenkoooo.com/atcoder/#/table/

８問になってからのdiff、こんなことになっていたんですね・・！

多分問題が難しいだけじゃなくて、100分で8問もあるから解きづらいというのも影響してるかと思います。

今日の問題 https://algo-method.com/tasks/342

今日の問題 https://algo-method.com/tasks/350

12:37 PM

ワイワイやってます

koogawa started a thread. 9/3/2021 1:11 PM

自分用メモ print("row: \(row), column: \(column), dp: \(dp)")

今日の問題 https://algo-method.com/tasks/352

11:44 AM

そして今日の abc https://atcoder.jp/contests/abc217

AtCoder Beginner Contest 217 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

https://twitter.com/algo_method/status/1434486474712371200

Q1-2. お菓子 (1) | アルゴ式(beta)

【 #毎日アルゴ式】本日 (9/5) の練習問題はこちらです！いよいよ動的計画法シリーズ最後の問題です。今までの練習問題のエッセンスを凝縮した良問となっているので是非挑戦してみてください！ https://t.co/84gc5hfPd2 ※ 問題への言及は自由に行っていただいてかまいません

#アルゴ式

12:07 PM

リンク切れてる

1

12:07 PM

アルゴ式さんには連絡済みです

koogawa started a thread. 9/5/2021 12:21 PM

今日の問題 https://algo-method.com/tasks/359

今日の問題 https://algo-method.com/tasks/362

今日の問題 https://algo-method.com/tasks/360

Q1-3. コイン問題 | アルゴ式(beta)

結局「貪欲法」がなんなのか… なんとなくは理解できたけど、うまく言語化できないな https://twitter.com/the_uhooi/status/1435593242179870721?s=20

ウホーイ🟡 (@the_uhooi)

ふむふむ「動的計画法」と同じく、特定のアルゴリズムというよりは考え方って感じなのかな「とにかく大きい数でぶん殴る」くらいのイメージ？ｗ --- 「貪欲法とは」を勉強中... https://t.co/inmP6FvIAj #アルゴ式

来た

https://github.com/apple/swift-algorithms/releases/tag/1.0.0

Release Swift Algorithms 1.0.0 · apple/swift-algorithms

Swift Algorithms is now source stable! Changes Most sequence and collection types have been renamed, following a more consistent naming structure: The Lazy prefix was dropped. Either a Sequence o...

uhooi

来た

https://github.com/apple/swift-algorithms/releases/tag/1.0.0

これが AtCoder で使えるようになったらうれしいですよね。 Python とかなんでライブラリ入ってるんだろうと思って前回の Language Update を見直してたら、ライブラリのカラム（ J ）に記載がありますね。次回アップデート時には Numerics と Algorithms は入れたいですね。 https://docs.google.com/spreadsheets/d/1PmsqufkF3wjKN6g1L0STS80yP4a6u-VdGiEv5uOHe0M

AtCoder 2019/7 Language Update

シート1 https://docs.google.com/spreadsheets/d/1X5Yk5PiGx-Otm1JaHpQQzQhEIPj8trofLTkphKX43s0/edit#gid=0 70,Judge Server Information,↓右クリックして「セルの編集履歴」を参照することができます,←複数です,←複数の場合はファイル　変更履歴変更履...

koher

これが AtCoder で使えるようになったらうれしいですよね。 Python とかなんでライブラリ入ってるんだろうと思って前回の Language Update を見直してたら、ライブラリのカラム（ J ）に記載がありますね。次回アップデート時には Numerics と Algorithms は入れたいですね。 https://docs.google.com/spreadsheets/d/1PmsqufkF3wjKN6g1L0STS80yP4a6u-VdGiEv5uOHe0M

おおっこのようなスプレッドシートが…！入れたいです…！

Collectionsも入れたらいいんじゃない

1

今日の問題 https://algo-method.com/tasks/361

Q1-4. 荷物と箱 | アルゴ式(beta)

1

今日知ったんですが、テストデータ　ダウンロードできるんですね！！

3

今日の問題 https://algo-method.com/tasks/364

Q1-5. お菓子 (2) | アルゴ式(beta)

ヤバイ。iOSDCの収録で何日かパスしたら、最近全然ついていけてない・・・。

2

今日の問題 https://algo-method.com/tasks/365

Q1-6. 巡回セールスマン問題 (貪欲法) | アルゴ式(beta)

今日の問題（まだ昨日の問題も取りかかれてないけど） https://algo-method.com/tasks/363

Q1-7. 区間スケジューリング問題 | アルゴ式(beta)

2

今日の問題はリンク切れのようです（連絡済み） https://twitter.com/algo_method/status/1437385578694299654

Q2-4. 小さい数の個数 | アルゴ式(beta)

【 #毎日アルゴ式】本日 (9/12) の練習問題はこちらです！今週は「二分探索」がテーマです。初回は雰囲気を掴むために値を順番に代入しても解ける問題となっています。是非挑戦してみてください！ https://t.co/XxuwZKUJZn ※ 問題への言及は自由に行っていただいてかまいません

#アルゴ式

1

koogawa started a thread. 9/13/2021 12:32 PM

今日の問題 https://algo-method.com/tasks/367

Q2-2. 貯金 | アルゴ式(beta)

2

今日の問題 https://algo-method.com/tasks/370

Q2-3. 最小の添字 | アルゴ式(beta)

3

今日の問題 https://algo-method.com/tasks/382

3

今日の問題 https://algo-method.com/tasks/381

Q2-5. 和がK以上のペア | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/399

Q2-6. 重さは何番目？ | アルゴ式(beta)

https://twitter.com/sak_algo/status/1439223090462871555

sak (@sak_algo)

え、もしかしてDアルゴ式見ながら解いた人結構おる？？？なんか部分和問題のページのアクセスめっちゃあってんけど

2

1

今日の問題 https://algo-method.com/tasks/366

Q2-7. 貯金 (2) | アルゴ式(beta)

2

koogawa started a thread. 9/19/2021 12:25 PM

今日の問題 https://algo-method.com/tasks/369

Q2-8. ひもを切る | アルゴ式(beta)

今週のabcは土曜日ではなく日曜開催 https://twitter.com/atcoder/status/1439980784673116167

AtCoder (@atcoder)

【コンテスト開催のお知らせ】コンテスト時間: 2021-09-26(日) 21:00 ~ 2021-09-26(日) 22:40 (100分) AtCoder Beginner Contest 220 https://t.co/1jre4NMqbX

4

今日の問題 https://algo-method.com/tasks/406

Q2-9. 九九の表 (1) | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/407

Q2-10. 九九の表 (2) | アルゴ式(beta)

今日の問題。タイトルがエモい https://algo-method.com/tasks/411

Q3-1. 友達 | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/412

今日の問題 https://algo-method.com/tasks/413

Q3-3. 友達の友達 | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/415

Q3-4. 箱の中の箱 (1) | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/414

Q3-5. 頂点を塗る | アルゴ式(beta)

今日のモン愛 https://algo-method.com/tasks/416

Q3-6. 箱の中の箱 (2) | アルゴ式(beta)

やべぇ追いつけなくなってる…

今日の問題 https://algo-method.com/tasks/418

Q3-7. スモール・ワールド | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/424

Q3-8. 迷路 | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/422

Q4-1. 1 + 2 + … + N (再帰) | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/426

Q4-2. A + (A+1) + … + B (再帰) | アルゴ式(beta)

なんだろ。。！ https://twitter.com/algo_method/status/1444541154054197251?s=21

Q4-3. フィボナッチ数列 (再帰-1) | アルゴ式(beta)

本日21:00頃にこれからの運営に関わる大切なお知らせを公開します。よろしくお願いいたします

2

今日の問題 https://algo-method.com/tasks/425

uhooi started a thread. 10/3/2021 12:29 PM

今日の問題 https://algo-method.com/tasks/423

Q4-4. フィボナッチ数列 (再帰-2) | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/427

Q4-5. 部分和問題 (再帰 1) | アルゴ式(beta)

今日の問題です https://algo-method.com/tasks/438

Q4-6. 部分和問題 (再帰-2) | アルゴ式(beta)

今日の問題はこちら https://algo-method.com/tasks/428

Q4-7. 数を選ぶ (1) | アルゴ式(beta)

本日の練習問題です https://algo-method.com/tasks/430

Q4-8. 数を選ぶ (2) | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/429

Q4-9. 昇順数 | アルゴ式(beta)

11:33 AM

そして今日のABC https://atcoder.jp/contests/abc222

Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） -...

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder お疲れ様でした！

2:11 PM

次回は日曜開催のようですコンテスト時間: 2021-10-17(日) 21:00 ~ 2021-10-17(日) 22:40 (100分) https://atcoder.jp/contests/abc223

AtCoder Beginner Contest 223 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

今日の問題 https://algo-method.com/tasks/439

Q5-1. バブルソート | アルゴ式(beta)

今日の問題です https://algo-method.com/tasks/440

Q5-2. 単純選択法 | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/441

Q5-3. 挿入ソート | アルゴ式(beta)

今日の問題！ https://algo-method.com/tasks/442

Q5-4. クイックソート | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/443

Q5-5. 乱択クイックソート | アルゴ式(beta)

今日の問題 https://algo-method.com/tasks/444

マージソート | アルゴ式(beta)

今日の問題です https://algo-method.com/tasks/518

ヒープソートの準備 | アルゴ式(beta)

今日の問題はこちら => https://algo-method.com/tasks/524

ヒープソート | アルゴ式(beta)

今日の問題はこちら https://algo-method.com/tasks/447

バケットソート | アルゴ式(beta)

ここ最近まったく手を付けられていない、、

12:06 PM

今日初めてメモ化でライブラリのパフォーマンスを改善してみました！ただもっといい方法がある気がしています。 https://github.com/Kyome22/LegoArtFilter/pull/2

Improve performance by uhooi · Pull Request #2 · Kyome22/LegoArtFil...

概要 LegoColor(r:g:b:) の処理に時間がかかるため、rgb の値をキーとしてキャッシュするようにした。私のアイコンを StudType: Round ・ Max Stud: 128 で試したところ、処理時間が約 1/33 になった。同じ色を使っている画像ほど処理が速くなる。逆にほぼ異なる色だと、キャッシュを捜査する分だけ処理が遅くなるが、具体的な時間は計測していない。 ...

4

高速化いいですね！個人的に懸念点としてはメモリ使用量くらいでしょうか（全ピクセルで色が全部異なる場合とか）

空間計算量ってやつですね確かに…どうなんでしょう… 全ピクセルで色が異なる画像が欲しいｗ

このへんですかね https://imgur.com/a/O9OyA

1

こういうの、キャッシュのヒット率見て悪ければ途中で打ち切る、みたいなのって有効に働くもんなんですかね

なるほど、今だと単に memo[rbg] でキャッシュのディクショナリにアクセスしていますが、 memo の要素を 1 つずつ取り出し、ヒット率が悪くなれば打ち切る、ということですねヒット率のしきい値をきれいに求められれば有効そう…？

何％hitしたらオリジナルより早くなるか、が閾値ですね

1:03 PM

ダミーの画像作って計測しましょう！w

Swift に標準でないかな、、、、、

log5 さんが貼ってくれた画像で試したところ、Before と After で処理時間がほぼ変わりませんでした。なのでヒット率を算出するまではやらなくてよさそうですｗ

1

Dictの探索が正しくO(1)で動いてることが予測できて良い題材ですね

あ、そういやディクショナリの検索って O(1) なんでしたっけそしたらまったく問題ないですねｗ

多分大丈夫だとは思いますが、メモリへの負荷も問題なかった感じでした？

計測していませんが、おそらく大丈夫だと思います、、おそらく、、、

1

このケースだと memo はメソッドが呼び出される度に使い捨ててるので、空間計算量のオーダーも変わってないですし特に問題なさそうですね（超巨大な画像で、メモリを数倍使ったらアウトとかいう状況でなければ）。

1

今日の問題はこちら https://algo-method.com/tasks/525

行きがけ順 | アルゴ式(beta)

今日の問題はこちら https://algo-method.com/tasks/529

頂点の深さ | アルゴ式(beta)

今日の問題です https://algo-method.com/tasks/528

木の高さ | アルゴ式(beta)

今日の問題はこちら https://algo-method.com/tasks/434

子孫の個数 | アルゴ式(beta)

そういえば昨日の問題がまだでした https://algo-method.com/tasks/536

デッドロック | アルゴ式(beta)

strmikan started a thread. 10/24/2021 2:04 PM

本日の問題です！https://algo-method.com/tasks/558

連結成分の最小値 | アルゴ式(beta)

今日の問題はこちら https://algo-method.com/tasks/559

Union-Find | アルゴ式(beta)

今日の問題です -> https://algo-method.com/tasks/560

グループ分け問題 | アルゴ式(beta)

今日の問題はこちら https://algo-method.com/tasks/566

for文とシグマ計算 (1) | アルゴ式(beta)

UnionFindに関する問題も増えていたので、スレッド立てておきます https://algo-method.com/tasks/561

粘土の重さ | アルゴ式(beta)

1

今日の問題はこちら https://twitter.com/algo_method/status/1454040327925473288