読者です 読者をやめる 読者になる 読者になる

はむこの勉強記録

http://bit.ly/2ktf20t の写し

TopCoder SRM 699 Div1 Medium FromToDivisible

docs.google.com なんかこう、始めからパッと高速なコードがかけるというのが大事な感じがする。 全然コーディングイディオムが足りないなあ。 でも解答一回も見ないでMedが通せたのは良いこと。

TopCoder SRM 601 Div1 Easy WinterAndPresents

docs.google.com めんどい(吐血) sumを数式できちんと書くとなんか答えが生えた。 こんなん本番で無理やろ、と思ってたら、制限が100万なので普通にXについて全探索できるやん…

TopCoder SRM 678 Div1 Easy ANewHope

docs.google.com 全然わからない… 考察ゲーですね、と言って終わるにはちょっとひどすぎると思うので、情報的に(探索的に)できる方法はないんですかね?? いろはちゃんにいつか教えてもらったのだけど、よくわからなかった上、ツイ消ししてるっぽくてアク…

TopCoder SRM 539 Div2 Hard CaptureFish

docs.google.com 始め、アスタリスクを潰せば自由度25bitやん!とかしてた。馬鹿だった。 あと、OXOとXOXがOKなので、OXもOKだと思っていたが、浅はかだった。

TopCoder SRM 539 Div2 Medium Over9000Rocks

docs.google.com 絶対にBatch Testはやりましょう(575)

TopCoder SRM 539 Div2 Easy PlatypusPaternity

docs.google.com 競技プログラミングは英語のテストではありません。

TopCoder SRM 628 Div2 Hard InvariantSets

docs.google.com Functional GraphでのDPするのに、SCCして逆辺張ってゴニョゴニョしたのが馬鹿すぎる…

TopCoder SRM 628 Div2 Medium BracketExpressions

docs.google.com

TopCoder SRM 628 Div2 Easy BishopMove

docs.google.com

TopCoder SRM 631 Div1 Easy TaroJiroGrid

docs.google.com 出力の上限を使った解法、面白い。

TopCoder SRM 627 Div1 Easy HappyLetterDiv1

docs.google.com 流石にこれは…

TopCoder SRM 709 Div1 Medium SoftMatch

docs.google.com Aho Corasick+bitDP解。 普通の(想定解の)DP解は全然わからないので、後で復習したい。 DPの勉強方法ってどうすればいいんだろうなあ。自分で考えるより、解答がきちんとあるものを写経したほうがまだ筋がいい気がする。

TopCoder SRM 696 Div1 Easy Gperm

docs.google.com 塗りはがすタイプの問題。 困ったら逆から見てみるみたいなの、とても自然な発想方法なんだけど、なかなか出てこない。逆像的に見るというか、なんと言うか。 以下の問題も、塗りはがす発想を使っている点で似ている。 docs.google.com

TopCoder SRM 695 Div1 Easy BearPasswordLexic

docs.google.com

TopCoder SRM 614 Div1 Easy MinimumSquare

docs.google.com 座圧を上手くサボる方法が面白かった。

TopCoder SRM 698 Div1 Easy RepeatString

docs.google.com 配るDPは、集めるものと違って全部のDP領域を走査する必要があるというのと、 配る先のメモリがあるかどうかわからないのは面倒なので、DPテーブルを大きめに確保しておくほうが良い。 編集距離くらい自分で編み出したい…。 DPに慣れるため…

TopCoder SRM 665 Div1 Easy LuckySum

docs.google.com 配る桁DP、苦手の塊。

Codeforces #398 Div2 C - Garland

docs.google.com DFSやDPなどは、部分問題のマージが本質。 このような問題の場合、求めたい状態と遷移をしっかりと言語化することが極めて重要。 DFSの場合には、頂点にデータが載っているので、頂点にどのような情報を載せるかを検討して、実装可能性を吟…

Codeforces #402 Div2 E - Bitwise Formula

docs.google.com ループを回しきらないバグ、やっかいすぎる。 これくらいの実装問題になってくると、もはや早解きのために雑に変数を定義するより、コメントをきちんと書いたりテスト駆動的にやったりするほうがパフォーマンスがでるなあ。 日本に帰ってき…

Codeforces #402 Div2 A - Pupils Redistribution

docs.google.com

Codeforces #402 Div2 D - String Game

docs.google.com

Codeforces #402 Div2 C - Pupils Redistribution

docs.google.com

Codeforces #402 Div2 B - Weird Rounding

docs.google.com

MUJIN プログラミングチャレンジ Programming Challenge 2017 : B - Row to Column(部分点)

docs.google.com 部分点解法。この程度のプログラムをバグらせるとか本当に何なんだ。 相変わらずBFSを再帰で実装しようとするし…

Codeforces #401 Div2 C - Alyona and Spreadsheet

docs.google.com BもCもしゃくとり法で、しゃくとり法コンテストだった。 勉強になった。

Codeforces #401 Div2 B. Game of Credit Cards

docs.google.com どうやってしゃくとり法を思いつくのだろう…

Codeforces #400 Div2 C - Molly's Chemicals

docs.google.com 類題として、Leetcode 512 Contiguous Arrayがある。 docs.google.com 区間和数え上げは、折れ線を値域から見るみたいなのが定石っぽい。 モノイドのreductionでも値域からみても良さそう。

Codeforces #400 Div2 B - Sherlock and his girlfriend

docs.google.com ちゃんと論理式レベルで考察しましょう。

TopCoder SRM 699 Div1 Easy OthersXor

docs.google.com XORのためになる問題。

TopCoder SRM 709 Div1 Easy Xscoregame

docs.google.com 勉強になった。

TOEIC 第217回

前回、TOEICなんてセンター試験くらいのテストだろうと思って、いい加減に受けたら810点しか取れなかった。 今回は、895点取れた。Listening 470pt Reading 425pt。 ということで、英語の勉強は1分もしていないが、今回は全力で準備した。 具体的には、以下…

Leetcode 517. Super Washing Machines

docs.google.com

Leetcode 525. Contiguous Array

docs.google.com

Leetcode 526. Beautiful Arrangement

docs.google.com 枝刈り全探索は強いですね。

Leetcode 520. Detect Capital

docs.google.com

「これがわからなかったから解けなかった…」みたいな情報まとめ(Topcoder SRM Easy 600番台)

Topcoder SRM Easyを100ACしたので、Topcoder SRM 600番台で勉強したことをまとめます。 僕の解説リストから、特に勉強したこと、新しい発想方法だけ抽出します。 docs.google.com 目次 目次 二分探索と全探索の順序は、全探索→二分探索のほうが枝刈りできて…

TopCoder SRM 635 Div1 Easy SimilarRatingGraph

docs.google.com

TopCoder SRM 639 Div1 Easy Egalitarianism3

docs.google.com Topcoder SRM Div.1 Easy 100AC目!!

TopCoder SRM 639 Div1 Easy AliceGame

docs.google.com {1, 3, …, 2n+1}でxを作るには、 「引いた結果が2か負でなければ、上から引いていく」という貪欲で構築できるが、知るかという感じ。 どう証明するんだこれ…

TopCoder SRM 648 Div1 Easy OkonomiyakiParty

docs.google.com System> hamko has submitted the 250-point problem for 169.47 points DPがそれなりに早く解けるのは嬉しい。

TopCoder SRM 648 Div1 Easy TheConsecutiveIntegersDivOne

docs.google.com 典型&典型という感じ

TopCoder SRM 648 Div1 Easy AB

docs.google.com 部屋に移動できなくてSystem Testができない…

TopCoder SRM 649 Div1 Easy Decipherability

docs.google.com

TopCoder SRM 632 Div1 Easy PotentialArithmeticSequence

docs.google.com md5 vectorハッシュを使った、O(n3)全探索解。普通の全探索ではO(n4)のはず。ソースコードがめっちゃ長い(551 lines)。 System> hamko has submitted the 300-point problem for 215.47 points それなりのスピードでデバッグもほぼせずに…

TopCoder SRM 642 Div1 Easy WaitingForBus

docs.google.com

ダイクストラと非負整数辺BFSなどめっちゃ色々試した TopCoder SRM 612 Div1 Easy EmoticonsDiv1

docs.google.com みんなやさしい。ありがとうございます。 @ryo_wk https://t.co/DuGkFZernY こういう事だと思います(適当に書いたのでどっかバグってるかも)。 01-bfs のように差分だけを持つパターンも https://t.co/qPVbeuzkgE— koyumeishi (@koyumeish…

TopCoder SRM 612 Div1 Easy EmoticonsDiv1

docs.google.com 4WA。コスト付きの操作の最小回数ってどうするのがいいんだろうなあ…はっこれが所謂ダイクストラか!!

TopCoder SRM 628 Div1 Easy DivisorsPower

docs.google.com

TopCoder SRM 611 Div1 Easy LCMSet.cpp

docs.google.com 1WA、解答見た。

TopCoder SRM 652 Div1 Easy ThePermutationGame

docs.google.com System> hamko has submitted the 250-point problem for 246.55 points なんやこれ