AtCoderにWebエンジニアが取り組む様子
koheiyamayama今は灰色なので、茶色を目指して頑張る。
そのためにAtCoder Problemsというサイトで片っ端から灰色の問題を解いていく。
また、茶色を目指すので、茶色の中でも簡単そうな問題にも挑戦していこうと思う。
koheiyamayama茶色になるために問題を解くだけではなく、アルゴリズムの実装と実装の検討を付けられるようにならないとダメそう。
abc258のC問題は愚直に実装したらTLEだった。これはアルゴリズムというわけでないが、アルゴリズム的な発想(？)が必要な気がした。
こういう発想力を養いつつ、計算量の見込みがパッと建てられると良さそう。
koheiyamayamaまずは灰色問題を素早く解くことができる状態を目指す。
その上で茶色問題に挑戦できると茶色に素早くなれるのかな？しらんけど。
koheiyamayama最近の問題を見ていると、C問題ぐらいまでは茶色diffになっている。
現在の内部レーティング(補正されていないレーティング)がこの値の人がコンテストでその問題を見たら50%の確率で解けると考えられる値です。
ratingxxx点の人が50%で解けるってことらしい。ということはC,D問題を常に解くことができれば茶色になれそう。
緑はD,Eを常に解くことができるとなれそう。だが、Eからは緑より上の難易度の問題もあるので、結構たいへんそうだなぁ。
koheiyamayama茶色になるための第一ステップとして
- A,B問題を10分弱で解く
- C,D問題を90分で解く
というのが必要そう。
この2つができると確実に茶色になれそう。
そのためにA,B問題を10分以内に解けるように頑張る必要がある。
今はB問題に30分ぐらい掛かってしまう。これにはいくつか要因がありそう。
- 解法を実装できない
- 解法が間違っており、実装してから気づいてしまう
- 解法が湧かない
これらにどう対処するかが求められる。
CとDは計算量の見込みを立てたり、問題を愚直に解くだけでなく発想力だったり、アルゴリズム力が必要そう。まぁ何にせよまだ先の話。
koheiyamayama今日はC問題でdiff560ぐらいの問題が解けた。
diff600ぐらいまでならそこまでアルゴリズム的な発想力は必要ないのか？
koheiyamayamadiff635で累積和というアルゴリズムを使った問題が出てきた。↑はそんなことなさそうだった。
これをそのまま解こうとすると、ループの中に2つのループがある感じになってしまう。Nが10**5だったので、解けなそうだと判断した。
判断結果は正しかったが、そこから解法を思いつくことはできなかった、、、。
koheiyamayama累積和は数学アルゴリズムの本に載っているっぽい。
やはり、今持っているアルゴリズム本を読んでいくのが良いのかなぁと思った。
koheiyamayamaABC069までの灰色茶色はたぶん全部解いた。ABCも毎週参加する。
ABCに7回参加したけど、ようやくRating100超えたところ。今までも思ったけど、
- ABを早く解く
- CDが解ける
状態にならないと茶色にはなれなそうだなと思う。
問題は解きつつ、けんちょんさんが書いた鹿本を読み始めてみる。数学とアルゴリズム本は自分にとっては少し難しい(というより、数学的、アルゴリズム的な文章があると読みづらい)ので、茶色を目指す人向きそうな鹿本を読むことにした。
少しづつABの回答率は上がっているし、時間も早くなっている。C問題はまだコンテスト中に解けたことはないけど、少しづつ解法が想像できるようになってきたし、練習では解けることが増えている。
この調子でスローペースだけど地道に続けることにする。
koheiyamayama鹿本読んでるけど、文字列の章を読んでるとC++便利そうだなーと思った。
Rustは文字列をどう持つかかなり悩ましい。
- Chars
- String
- &str
の3択があり、どれも変換するのはだるい。
が、C++であればその辺苦労せずにできそうなので、素晴らしいなぁと思った。
koheiyamayama文字列はCharsかStringでだいたいことが足りる。
koheiyamayama同じ難易度でも全探索とバケット / 連想配列の問題だと後者のほうが圧倒的に解ける。
全探索は半々ぐらいの解説ACと自力AC、最後の2問は諦めてしまった。
全探索、何が難しいのか言語化して対策する必要を強く感じる。なぜなら、噂によると全探索はDPぐらいしょっちゅう出るっぽくて、これが解けないと茶色にすら至れないだろうから。
koheiyamayama区間分割・連長圧縮の問題も苦手かも。
結構解くのに時間がかかるし、https://atcoder.jp/contests/abc116/tasks/abc116_c が全く解けなかった。写経ACしてしまった。
もうちょいこの分野の問題を解いてから苦手なところを言語化したい。
koheiyamayamaRustで結果出している人
koheiyamayama私は数学が本当にできない。ここでいう数学とは高校数学までのことを言う。大学でやるような数学なんて見たこともない。
どのくらい苦手だったかと言うと、高校2年生のときに受けた進研模試(中堅都立高校ではこの模試を毎年?受ける高校が多い)の数学は白紙で出した。
なぜ白紙かと言うと、本当に1問も解くことができなかったからだ。
今思えば、本当に後悔しているが、これから先のエンジニア人生で数学を避け続けたら絶対に後悔するので、それなりに気合を入れてちょっとずつ数学に取り組んでいる。
その中でタイトルにある問題解決のための「アルゴリズム✕数学」が基礎からしっかり身につくという本を読んだ。
結論から言うと、数学模試を白紙で出すような人間には少し難しい。
このような人間はまず中学数学ぐらいから数学が苦手である。少なくとも私はそうだった。
都立高校の共通入試でだいたい60点代後半だった記憶がある。周りの私立受験(March付属校や進学校)している友達は90点以下を取ったことないと言っていた。
この本は数学とアルゴリズムの関係性を整理する目的が強い気がしており、数学白紙人間に数学を叩き込むための本ではない。
つまり、私はちょっと対象読者から外れている気がした。
特に対数関数や組み合わせ、順列、数列、行列、微積分辺りがアルゴリズム周りでよく紹介されている気がするが、その辺りの知識が一切ないので、あっさりした説明だと頭の中が「？？zaqqwsxedcrfvtgb[]]]_@:/p;.olllllll？？」という感じになってしまう。
なので、まずはマセマのはじめからはじめる数学という本を読み始めた。
これは高校生でやる数学を本当に最小限かつわかりやすく説明している。
数学白紙人間でもなんとか理解できた。ちょこちょこ分からないところはYoutubeで講義を見たり、弟からパクった高校数学の教科書を読んだりして補うことにした。
ちなみに、チャート式もやったが、あれは問題集なので解説が少ないし、アルゴリズム✕数学本を理解するには過剰だと思う。
もちろん、大学に行きたい人にはもってこいなのだろう。しらんけど。
マセマをやり直してから3,4ヶ月ほど間が空いてしまって、結構忘れていることが多いが、もう一度読み返してみた。
なんとなく一回目読んだ時よりも苦手意識が減っているし、理解が進むように感じる。
完璧に理解しようと思うと、もう一回マセマをやり直したいところだが、マセマをやったおかげで1回目より理解が進む。やってよかった。
koheiyamayamaやっぱり数学をこれで理解するのは私には無理そう。
マセマが一番わかりやすいし、この本と同じぐらいの内容になっている。
koheiyamayama分からんけど、この本の難易度3がギリギリ茶diffかな？と思った。
この本とこちらを読めば、茶色は行けるのでは？
koheiyamayamaこの本は数学とアルゴリズムの結びつきを紹介する本で、その点はまじですごい良いってことに気づいた。
数学のところはあぁそういうのマセマでやったなーと思いつつ、アルゴリズムの理解を深めていくという進め方が自分には合っていそう。
koheiyamayamaそもそも数学とアルゴリズムを同時に学ぶのは私には大変すぎると思った。
数学とアルゴリズム的な数学(？)、数学とアルゴリズム、アルゴリズムという分類があるように思える。この本は数学とアルゴリズムを紹介している。私の中ではアルゴリズム的な数学が全く無いので、しんどいのかもしれない。
アルゴリズム的な数学とは、、数学の文章問題に近い気がする。数学の学習しているときも式を整理する系の、いわゆる計算問題のほうができるが、そうじゃない問題はしんどかった。
koheiyamayamaABC258に挑戦した。これが私の初めてのコンテストだ。
結果、A問題が解けた。あまりいい解法じゃなかったし、Ruby使ってしまった(本当はRustで解きたかった)ので、残念。
B問題は解法が全く浮かばず、C問題はTLEでそっから解法が思いつかず。
公式のYoutubeを見た。
B問題とC問題で共通して分からなかったのは「nで割ってあげれば良い」というところ。
なぜnで割るといい感じになるのかさっぱり分からない。
C問題の解法の発想は理解できたし、B問題もイメージは付くのだが、nで割るというのがどうしても分からない。
トーラスの場合には必要となる処理っぽい？ので、その辺りの考えを身に着けたい。
koheiyamayamanで割ってその余りを使うという考えが分からない。
koheiyamayama今日の1題
このくらいのレベルだと一瞬で解法が思い浮かぶ。それが良い解法なのかはさておき。
koheiyamayamaローカルだとコンパイル通るが、AtCoderだと通らない現象が起きたが、無事にACした。
が、ループで解いていて、あんまり良い解法じゃない気がするので、他の解法を見てみる。
見た感じ入力で3つの整数をu8の配列で受け取り、ソートする。ソートした配列と5,5,7の要素を持ったvectorを比較することで答えを得ている。
koheiyamayama今日のもう1題
今日の1題はdiffcultyが89。これは254。
koheiyamayamaかなりいい解法、他の人の回答と同じようにかつシンプルに解けた。
最初は解法は似たようなことを思いついたが、実装イメージが全く違かった。
いったん入力をもとに元の図を出力する実装をしたら、これ2Hだから2回出力するだけで事足りるのでは？と気づいた。
解法を思いつくことと、実装イメージが湧くこと、実装できることには差があるなと感じた。
koheiyamayama今日の1題
最初に型をusizeにしていて、overflowした。isizeにすることで解決した。
引き算する時は気をつけないといけない。
本番じゃなくてよかった。
koheiyamayama今日のもう1題
1つ目の解法を思いついてから5~10分後に解法が間違っていることに気づき、第2の解法を思いつき、修正完了するまでに10~20分弱かかった。合計30分弱は掛かった。
これくらいなら3分ぐらいで解けるようにならないと厳しそう。
koheiyamayamaさらにもう1題
これも今日のもう1題と同じぐらいの難易度っぽい。
正しい解法はすぐに思いついたし、実装できそうだったが、もっといいやり方があるんじゃないか？と思って途中で違う解法を考え始めた。それが良くなかった。
ちなみに、他の人の回答を見ると
- HashMapを使った解法
- 文字をcharとして扱い工夫する解法
の2つがある。
この文字をcharとして扱う解法は結構頻出な気がするので、マスターしたい。
koheiyamayama今日の1問
これはすぐにできた。
koheiyamayamaちょっとよくわからないRustの挙動?に悩まされた & overflowしてしまいそれに戸惑ったが今まで一番はやくB問題が解けた。
koheiyamayama他の人の回答も概ね同じ。
10**9 + 7を定数としている人が多かった。確かにpowの使い方調べるよりも定数で置いたほうが遥かに早い。
koheiyamayama茶色問題にチャレンジしてみる。
koheiyamayamaSとCのパーツからSccという文字列をいくつ作れるか。
c2つからsを作れる。
つまり、Sccを作るには
- S一つとc2つ
- c4つ
の2パターンある。
例えば、Sが100個、Cが200個あった時はSccは100個できる。
Sが100,Cが204の場合は100 + 1
つまり、Sの個数2 =< Cの個数がある場合は、Sの個数 * 2 + (Cの個数 - (Sの個数 * 2 )) / 4
Sの個数2 =< Cの個数がない場合は、Sの個数 * (Cの個数/2)
って思った。
koheiyamayama若干式が違くてデバッグした。
Sの個数2 =< Cの個数がある場合は、Sの個数 * 2 + (Cの個数 - (Sの個数 * 2 )) / 4
Sの個数2 =< Cの個数がある場合は、Sの個数 + (Cの個数 - (Sの個数 * 2 )) / 4
Sの個数2 =< Cの個数がない場合は、Sの個数 * (Cの個数/2)
Sの個数2 =< Cの個数がない場合は、Cの個数/2
が正しかった。
koheiyamayama解説見た感じ、ほぼ理想的な解法っぽいので、良かった。
koheiyamayama今日の1問。
見た瞬間に解法が思いついたが、問題文を読み違えてしまい、足し算、引き算、掛け算、割り算 だと思ってしまった。割り算はする必要がなかった、、、。
koheiyamayama今日のもう1問
4,50分も掛かってしまった、、、。
なにかいい方法がないか考えてたが、思いつかず力ずくで解く方法に切り替えるまでが長かったし、力ずくの方法を実装するのも結構時間が掛かった。
結局力ずくの解法と同じことをスマートに解いている人が多い。
HashSetを使っており、HashSetにintersectionメソッドがある。HashSetならば要素の重複を省けるし、intersectionもあるしで一石二鳥だったなと思った。
いつかHashSetを使って解き直してみよう。
koheiyamayama
累積和というアルゴリズムが必要らしい。
解けなかった、、、。
koheiyamayamamath-and-algorithm014
すげー時間掛かった。大まかな解法はすぐに思いついたし、正しかったが、それをプログラムにするのにとても時間がかかってしまった。結局答えを見たし、、、。
koheiyamayama計算量の話は流し読みしてどうしてそのアルゴリズムが良いのか？そのアルゴリズムをどうやって応用するのかを考えたい。
だし、力づくで解いたら計算量が足りなくなるような問題が解けないからこれを読んでいるのであって、解けるならこの本を読む必要はない。頑張ろう。
koheiyamayama
今日の3問。
一問目は結構たいへんだった、、、。論理構造は分かっているが、プログラムに起こすのが大変だった。
二問目は一問目を再帰関数にリファクタしてから、着手することで簡単にできた。
三問目はa,b,cと整数があるときにlcm(lcm(a, b), c)となることに気づいて、プログラムを組んだが1回目でsubmitがコケた。データ制約を読むと10 ** 18となっており、usize(u64)を超えていることに気づき、u128に変更したら通った。ただ、3つ以上の整数のlcmの求め方がどうしてこれなのかは分からなかった、、、。2つの整数のlcmの求め方は二章に書いてあったことを思い出して、それを読んで思い出した。
koheiyamayama最大公約数と最小公倍数の求め方、関係について学べた。役に立つのかはわかんけど。
koheiyamayama
abc259参加した。
AとBが解けた。やったぜ。
B問題はsin/cos使ってゴニョゴニョすれば解けそうなことが分かったけど、細かい式は分からなかったので、ぐぐったら出てきた、、、。それを真似して解いた。
早く解ければ解けるほど順位に影響があるらしいので、何も見ないでスラスラ解けるほうが良いが、まぁそんなこと気にする必要ない段階だと思うので、気にしないことにした。
が、B問題でなんか分からんが , を答えに入れていて、かなりの時間ロスした。これがかなりしんどかった。
これがなければC問題を考える時間ができたのだが、、、残念。
koheiyamayamaRustのHashMapの扱い方が大変。
koheiyamayamaC問題はこちらを参考にさせていただいた。
ラングレス圧縮法と条件式を思いつけるか実装できるかの勝負だった。
どちらもできなかった、、、。
koheiyamayama
どうやって高校数学の問題に落とし込むのか？が課題になりそう。
これを見たときに組み合わせの問題だと気づけるか？っていう、、。
上の問題とだいたい同じ。
本に書いてある xC2 = x(x-1)/2の式変形が最初は分からなかったが、自力で理解できたので良かった。
参考にした。
全探索の問題が解けないと茶色は遠いので練習したいところだ、、、。
koheiyamayamaさすがにすぐにできる。
解説見てやっとできた。
ラングレス圧縮法みたいな解き方なのかなと思った。
文字列、数列内で特定の要素がどのくらい出現しているかカウントし、O(N**2)掛かるところをO(N)にするために圧縮する。圧縮するための計算量もO(N)なので、この圧縮 + 判定はO(2N)で終わる(？)的な？
abc259だかでもこの手法が出てた。タイムリー。
koheiyamayama
そこそこすぐにできた。期待値の線形性の問題。
期待値の総和と総和の期待値は一致する。
koheiyamayama
すぐできた。
解説読んで考え方はちょっと合ってたけど、そこから進めなかった。
解説はいまいち理解できない。
koheiyamayamaシグマとかその辺りがいまいち分かってない。
あと、具体例までは理解できるし、似たようなことを考えてたけど、Nとか使いだしてから何言っているのかさっぱりわからなくなった。
koheiyamayamaabc260参加した。
AB解けた。Cは再帰関数で解けることは分かったが、実装できず、、、、。
再帰関数の考え方、難しい。
AとBは想定解法だった。
Bは得点が同じ場合はindexの小さい方を優先するという条件を実装するのがRustでめんどくさかった。
やっぱりRustめんどくさいなーと思った。
koheiyamayamaCは再帰関数と動的計画法で解けるらしい。
再帰関数は数学とアルゴリズムの本でやったので、もっと練習したい。
動的計画法はそろそろ出てくるので、さっさと読みたい。
この辺りはよく出ると思うので、よーく練習したい。
koheiyamayama
koheiyamayama初めての動的計画法
動的計画法はこの本によると「小さい問題の結果を利用して解くアルゴリズム」のことらしいが、この問題でよく理解できた。
特定の足場に至るまでの最小コストを一つずつ計算することで最終的に特定の足場にたどり着くための最小コストを計算できる。
koheiyamayama
組み合わせの問題も解ける。
koheiyamayama
解けた。
が、よくある間違いとしてindexと問題文の添字(この問題なら何番目の商品、とか)がごちゃごちゃになり、実装ミスがある。
これは注意しないといけない、、、、。
koheiyamayama
解いた。
難しい。
二次元の動的計画法の場合、二次元表を書いていくこと、実際にどういう二次元配列が作られているかを確かめながら進めると最初は良さそう。
koheiyamayama
動的計画法、難しい。二次元配列になってから全然解けない。これは二次元配列じゃなくて2つの配列を使うやり方だった、、、。
koheiyamayama本読んでからか、明日からか、これやってみる。
koheiyamayamadp contest一問目。
これは本でも使われていた問題。先週にやったので、細かい解法は覚えてなかったけど、なんとなーく覚えてた部分がある。
koheiyamayamadp contest二問目。
全然解けなくてイライラする。
結局こちらの記事のRust版を写経することになった。
koheiyamayamaABC261参加した。
最近信長の野望 新生が出てしまったので、サボっていたが、いったん天下に泰平をもたらしたので、再開する。
AB完、C無念。
Cも考え方にそこまで大きな違いはなかったが、おそらくcloneとinsertがサイズが大きなればなるほど遅くなってしまい、TLEとなってしまった、、、。無念、、、、。絶対に解けたはずなので、もっとRustでグレー問題の練習したほうが良さそう。
だが、いったんはDPコンテストの問題を解いてみる。なぜなら、DPできたらかっこよさそうだから。
koheiyamayamaabc042~abc047のAB問題を解いた。
ほとんどの問題は半分が灰色、半分が茶色みたいな感じだった。
ABC042とABC047のB問題がなかなか解けなかった。。。
特にABC047は座標を扱った問題であまり解いたことがないので、かなり苦戦した。
そもそも042から047までで座標問題はたぶんない?ので、仕方ない。
文字列、数字をゴニョゴニョする茶色問題はそこそこ解けるようになってきた。
この調子で茶色問題ぐらいまでを目処に練習を続ける。
灰色は結構早く解けるようになってきた。
koheiyamayama
解いた。
解説見た。
区間の数を求めると良いと一言書かれていたし、たしかにその通りだけど、どうして区間の数を求めると良いと分かるんだ、、、？
実装は適当だったけど、まぁ良しとしたい。
が、周りはもっときれいに書けているので、精進しないとなぁ、、、
koheiyamayama
解いた。
回答に書いたけど、けんちょんさんの実装を参考にして解いた。
全探索で総和を求める問題だったのに、、、。これくらいは解けるようになりたい。
koheiyamayama解けたけど、コードがきれい、シンプルじゃないとバグが起こりやすくてコンテスト中に時間が取られてしまう。なので、その辺り精進したほうが良い。
で、どうしてきれいに書けないのか？と考えてみると、問題の読み取り方が違うんだと思う。
本当に問題文を再現しようとしてプログラムを書くのと、問題文はこう書いてあるからこうやって考えることで楽に実装できる、みたいな考え方が自分と他の人とのdiffな気がする。
koheiyamayama初めて茶色diff750近くの問題がすぐに解けた。これ、精選10問の問題で紹介されていたやつとほぼ同じだった気がする。
koheiyamayamaabc262の前に灰色と茶色の問題を解いた。
052と053のab, abc合計5問を解いた。
abc053cが茶色diff745だった。このレーティングの問題、少しづつ解けるようになっている気がする？？分からんけど。二回ミスったので、素直に喜べないが、、、。
koheiyamayamaあとA問題で痛恨のミスをした。未満と以下の読み違いが起きた。これはしんどい。気をつけないとだめ。
koheiyamayamaabc262に参加した。
A問題でまず意味分からんエラーになってイライラした。
B問題は無向単純グラフの意味が分からなすぎて最初飛ばした。
C問題は全探索だと解けないのはわかりつつ実装してTLEとなった。
B問題に戻って問題を理解できたので考え始めた。解き初めてこれなら解けそうと思ったが、実装できずタイムアップ。
感想として、ABC05xぐらいから比べると、BCの問題のレベルが上ってるような気がする、、、。
あと、Rust難しい。所有権周りでプリントデバッグできないときがあるのが辛い。
正直イライラしすぎて今日はもう何もしたくない、、、。
koheiyamayama灰色でも図形が絡む問題は特に解けないことに気づいた。
abc056bも灰色だけど、解くのに時間が掛かった。実装に時間が掛かったし、他の灰色と比較してパッと解法が思いついたわけじゃない。
図形問題にどう立ち向かうかが茶色を目指す上で一つ課題なのかもしれない。
koheiyamayama
この問題とか昔のatcoderでdiff434、これに1時間近く掛かってしまった。遅くても10分とかで解けるようになりたい。
この問題で躓いたのは
- 距離を出力する問題だと勘違いしていたこと
- 距離を求めて最小の距離となるチェックポイントをどうやって出力するかの実装にめちゃくちゃ時間がかかったこと
がある。後者が致命的に悪い。
atcoder、解ける時は楽しいけど、解けないときはめちゃくちゃイライラしてしまう、、、。
koheiyamayama正しい解法を思いつくまで、それを実装するまでに5分ずつぐらい掛かった。
合計3~5分ぐらいで解けないダメそう。知らんけど。
koheiyamayama
解法を思いつけなかった。
各文字列にどのアルファベットがどのくらい出現するかカウントし、それらの最小値を取る。
具体的には
- 文字列
- abcdeeedf
- addeadef
- aaaaaaccccbbf
みたいな場合は
- a: 1, b: 1, c: 1, d: 2, e: 3, f: 1
- a: 2, b: 0, c: 0, d: 3, e: 2, f: 1
- a: 6, b: 2, c: 4, d: 0, e:0, f: 1
みたいな感じでカウントする。
これの各配列のアルファベットの最小値を使うと答えが出せる。
つまり、a: 1, b: 1, f:1 の配列を算出して、これを使うと答えが出せる。
解法は解説を読んで分かった。
そして実装も大変だった。
まず、最初はHashMapを使ったパターンを思いついたが、毎回思うけど、RustのHashMapは扱いが難しすぎる。
さらには今回だとVectorのHashMapを用意する必要があるので、これまた大変だった。
ここで実装を諦めてRustの実装例を探した。その結果 https://scrapbox.io/yu2ta7ka/AtCoder_ABC_058_C_-%E6%80%AA%E6%96%87%E6%9B%B8(300_%E7%82%B9) が良さげだった。
競技プログラミングのコードで嫌いなこととして、文字を数字として扱うことがある。あんまりわかりやすいと思えないので、嫌いなわけだが、この問題では文字を数字として扱うことで便利に進められるのは間違いなかったので、このやり方に慣れる必要があるなと感じた。
基本的に文字通り実装すればいいみたいに言いたそうな解説は腹立たしいことこの上ない。
koheiyamayama一発で解けはしたが、u128で扱えない数字をどう扱うか経験がなかったので、無駄に悩んでしまった。
一発目の実装は無駄に長いコードを書いてしまい、30分以上時間が掛かった。
二発目の実装は3分で実装できた。まじでRustやめようか悩む。Rubyなら数分で解けそうだけど、Rustで数十分掛かること多い。
koheiyamayama次に、A%B, 2A%B, 3A%B, ... という数列を考えます。なお A%B は A を
B で割ったあまりを表します。
ここで、(k + B)A%B = (kA + BA)%B = kA%B に注目すると、この数
列は周期的で、最初の B 個の要素を繰り返す数列になっていることがわかり
ます。
どうやったらこの発想に至るのか分からない、、、。
この数列は周期的であることにどうやって気づくの？
koheiyamayamaちょっと自信なかったがACした。https://atcoder.jp/contests/abc060/tasks/arc073_a
解法は割と早めに思いつきそれがあたった。ただ、想定解法ではなかった。
が、実装でだいぶ時間が取られた。
配列の使い方があんまりうまくないなー。
koheiyamayamaどうやったらこの発想に至るのか分からない、、、。
この数列は周期的であることにどうやって気づくの？
最初のサンプルにたいしてとりあえず手を動かすと分かりそう。
7 % 4 = 3
14 % 4 = 2
3+2 = 5、、、これはもしかして？ってなりそう。
改めて問題見た時にそう思えた。
競技プログラミングのコードで嫌いなこととして、文字を数字として扱うことがある。あんまりわかりやすいと思えないので、嫌いなわけだが、この問題では文字を数字として扱うことで便利に進められるのは間違いなかったので、このやり方に慣れる必要があるなと感じた。
だいぶ慣れてきた。
何なら出現するCharをカウントするときはこのやり方がどんな場面でも都合が良さそう。
koheiyamayama
マイナスの数値をusizeで受け取るとRuntime Errorになる。
koheiyamayama問題文の理解がしづらかったけど、解法はすぐに思いつき、実装もすぐにできた。素晴らしい。
koheiyamayama
最初の解法を思いつきサンプルケースはすぐに通ったが、WAとなりそこから苦戦した。
最初の解法は合計値から数列の中で最も小さい値を引いていき、合計値が10の倍数じゃない場合はそれが答えになるのでは？というもの。
が、計算過程で10の倍数であるがなかろうが最終的な結果が10の倍数でないことには関係がないので、だめだった。
ただ、合計値から値を引くという発想がすぐに出たのは良かった。
想定解法は合計値が10の倍数である場合、数列の中に10の倍数じゃない数値がある場合はその中から最小の値を引く、10の倍数しか無いなら0になる。
合計値が10の倍数じゃない場合はそのままそれが答えになる。
というものだった。
koheiyamayama
幽遊白書見て3,4日サボった。
この問題、最小を計算するときの考え方が違った。
最小を出すためには
一人以上3199以下のレーティングがいるかどうかで計算方法が変わる。
いる場合は3199以下のレーティングの人数が最小値となる。なぜなら、3200以上の人はすでに選択されている色を選ぶことが最小値となるから。
いない場合、つまり全員が3200以上の場合は(起業したほうが良い)、1となる。誰か一人が適当な色を選び、他の人がその一色を選ぶのが最小となるから。
最小計算で考えが悪かった。
koheiyamayamaこういう灰色問題、ややこしくなってきて大変。
x軸を書いて何がどうなるのか考えながらやると良いかも？
koheiyamayama
解説見た。
解法は思ってたとおり愚直に遷移するだけだったが、実装がうまくできなかった。
koheiyamayama
解法は割と早めに思いついた。
が、実装がめんどくさい。
10_000の階乗Rustだとoverflowしてしまって簡単にできない。これがめちゃくちゃだるい。
Rubyみたいに型がゆるい言語だったらすぐに解けそう。
だけどまぁC++の実装とかも似たような感じになっているし、こういうもんって思うしか無い。
koheiyamayamaふと思ったけど、毎週コンテストに決まった時間に出るのは良いこともあるけど、あんまり向いてないし、競技性や労働性を持ったことが好きじゃないなと改めて思った。
koheiyamayama
出た。
AB解けた。
AでCEとREが出てめちゃくちゃ萎えた。
CEはおそらくrustcのバージョンが違うから起きたんだと思う。今までも違うことは知ってたけど、問題になったことなかったので気にしてなかった。これを機に合わせる。
REはベクタのサイズを一つ小さく設定したから起きてしまった。これはまじでもったいない。これからベクタ作る時はstd::usize::MAXとかキャパシティ持たせてやろうかと思った。しないけど。
Bは単純にベクタを遡るだけで、LinkedListみたいなやつを実装すればよかった。
解法を思いつくのに時間が掛かった。問題文が最初の方は全然理解できず、、、。
理解してから解法を思いつくまではすぐだったが、実装が無駄に複雑になってしまいだめだった。
諦めて信長の野望でもしようと思ったけど、どうしても納得行かず、ちょっと休憩してから再実装したらシンプルな実装ができてまじで良かった。
やはり問題文が理解できない時は図に書くしか無いなぁと感じた。
C問題はRubyならArray#combinationメソッドを使えば1分で解けそう。やはりRubyは偉大。Pythonでもできるっぽいけど、Pythonはやったことない。そろそろ教養としてチュートリアルぐらいはやったほうが良いのかもしれない。
Rustで解くとなると、10重のループを書く方法がパッと思いつくし、計算量的にも問題がなさそうに見える。
が、時間がなかったので諦めて信長の野望を始めた。無念。
灰色茶色がなかなか解けないけどあと過去問が600問ぐらいありそうなので、地道に解きつつ茶色を目指したい。
koheiyamayamarustcのバージョンを合わせたいけど、1.42.0をインストールしてからcargo competeのセットアップができないので、諦めた。
環境構築 is とてもダルい。
koheiyamayama
abc066解いてた。
C問題は全探索すると間に合わなそうだったので、解法を探した。
結果、いい感じの解法を見つけられたので、それを実装した。
かなり時間かかってしまったけど、ipadにメモ取りながらどう並び替えられるか考えたら思いつけた。
嬉しい。
koheiyamayamaただ想定解法とはだいぶ違くてかなりよく分からん解法になってしまった。
想定解法はAiの値を数列Bに先頭末尾に交互に入れていくということだった。
C++ではdequeというデータ構造?がありこれを使う方法が紹介されていた。
RustだとDeqVecというデータ構造があり、これを使うと配列から先頭pop, 末尾popが行える。
普通にVec#popとremoveがあるので、同じことができるが、DeqVecの先頭popはめちゃ早い。これこそアルゴリズムとデータ構造を理解してれば解説で分かりそう。
ただ、想定解法だろうが自分で思いついた解法だろうが、解法を思いつきそれを実装するスピードが大事。今回はDeqVecがあるぞ！っていうのが分かっていると(先頭と末尾を交互に操作する構造がある)ってことが頭の片隅にあれば、もっと早く解法を思いつけたかもしれない。
数学とアルゴリズムの本の5章に遇奇に着目するっていうのはこういう問題のことなのかもなと思った。
koheiyamayama
abc067、なんか相性が良かったのか分からんけど、abcがスラスラと解けた。
特にC問題は配列を上手く使ったり、無駄に計算をせずにxとyを求めることができることにすぐに気づき、一発でACした。
茶色diff700(もう少し緑diff)の問題を一発で、しかもスラスラと解けたのは初めてなので、とても嬉しい。
koheiyamayama
この問題、解けたけど、解説読んだ感じだともっと簡単に実装できる。
解き方としては全探索だったけど、解説だと2 ** x < 100の値である1,2,4,8,16,32,64の7種類のどれかが答えになるとあり、渡されたN以下の中で最も大きいものが答えとなる。
例えば99が渡されたら64が答えになる。
思ったけど、これってどうして1が答えになるんだ？？？？
0が絶対に2で割り切れるから、、、？
koheiyamayama
解説AC。
解説頭良すぎる。当然だけど。
だいたい解法の方向性は合っていたけど、どうしてもN**2になってしまった。
それを回避するために解説の考え方を参考に実装し直した。
もともとの考え方はMに着目する考え方だった。
つまり、Nに到着するMiを探し、Miの出発地点に到着するMiを探す、みたいな考え方だった。
それを実装したのが最初にTLEした提出。
解説ACしたのは、Nに着目した考え方。つまり、1 -> Ni -> Nという道順があるかどうかをNiに着目して解いていた。
島iに到達する道があるか かつ 島Nに到達する道があるかを求めることで、答えを出せる。
ふぁぁぁぁぁぁぁ。天才か、、、、。
koheiyamayama@satouMIMIMI
はじめまして、私の雑なメモに書いてある疑問点に返信いただきありがとうございます。
こちらの問題で入力が1のときに出力が1となるのはどうしてだろう？という疑問でした。
satouMIMIMIさんが書いた内容だと、入力が1の時は出力0になると思うのですが、認識違いますか？
koheiyamayamaありがとうございます。
今、よくよく問題文を読み直して理解できましたm(__)m
教えていただきありがとうございます！
koheiyamayama
らしい。LeetCodeもそのうち見てみたい。
koheiyamayama
便利そう。
koheiyamayama
こんな感じで使うらしい。
koheiyamayama見た感じサイトの使い勝手は圧倒的にLeetCodeのほうが良さそう。
問題の検索ができるのは良い。
- 自分が解いた問題
- 問題の特徴
- 難易度
- etc
AtCoderは基本的にどれもできない。
koheiyamayamaLeetCodeのうーんって思ったのは
- 英語力大丈夫かな、、、という不安
- UIがごちゃごちゃしており、なんかわかりづらそう
ぐらい。
koheiyamayamaあと、解説ACしたのか、自力でACしたのかとかACにも色々あるからそのへん管理できるようになったら良いなぁとふと思った。
koheiyamayama
abc264出た。
AB解けた。Cは解けなかった。
Bはむちゃくちゃ無理やり解いた。
マス目をベクタで表現して、あとは座標を指定するだけにして解いた。
思いっきりハードコーディング。クソみたいな解き方してしまった。
しかも、一回REとなった。やってしまった。
解説を読むと、この問題は(r,c)マスは中央のマスからの距離が奇数の場合に黒、偶数の場合に白、みたいになるらしい。また、この中央マスからあるマスの距離をチェス盤距離というらしい。知らんかった。
なので、このチェス盤距離を計算すればすぐに出せる。
Cは解説読んだ感じだとbit全探索とやらを使うらしい。名前は知ってたけど、使ったことがない。
これを機に調べてみると良さそう。
解説読んでも記号が多すぎるし、C++はよく分からんすぎてパッと理解できないが、6回ループ回している辺り、そんな頓珍漢な考え方じゃなかったんじゃないか？っていう気がした。
そのうち復習する。
koheiyamayamaABC069Cについて
まず、気づいたことで正しかったのは
問題文の条件は奇数の隣に来る数字は4の倍数でなければならないと読み替えられること、4の倍数、偶数、奇数などをカウントし、それらの大小で答えを出せること。
が、細かいところで条件を整理できずに解説を読むことになった。
解説を読んで理解したが、4の倍数外の偶数の扱い方、どうしてその発想ができるんだ、、、？っていう気持ち。
こういう発想は数学とアルゴリズム本の5章を読むと良いのかぁ、、、。
koheiyamayama鹿本メモ
koheiyamayama初っ端から「割り算を使いこなすだけでこれだけの問題が解けるのか、、」と衝撃を受けた。
こういう「これを使うとこういう問題が解ける」っていうまとめは大事だなぁと思った。
koheiyamayamafor文を使うことで解けるような問題も多い(for文の中で引き算して0以下になったらbreakするみたいな感じで)ので、そういう風に解いていることが多かった気がするが、ちょっと見直したいと思った。
koheiyamayama典型90の033を解いているときに思ったけど、自分の問題への考え方は
- いくつか具体例を並べる
- 計算する
- 共通点を見つける
- その共通点を言語化する
- 正しそうかいくつかの具体例を並べる
- 正しうなら実装する
っていう感じなんだけど、どうしても漏れが出る。ここで数学とアルゴリズム本にも載っていた背理法みたいな証明技法が役に立つのかな？と思った。どうなんだろう、、、？
koheiyamayamaあと、上記の手順だとやっぱり時間が掛かる。証明技法を使って一発で共通点が正しそうであれば、実装に踏み切れるとだいぶ早く実装完了できて、AC狙えそう。
koheiyamayama典型90 033解けなかった、、、。
解説ACするか悩んだけど、もうちょっと解けそうだし、鹿本を読み終わったらもう1回チャレンジするかもしれない。
koheiyamayamaって思ったけど、https://www.creativ.xyz/atcoder-yellow-596/ に解説読みましょうって書いてあったから読む。もう2時間ぐらい考えたけど、あと一歩が出ないし、、。
koheiyamayama
~ツイッターでは難易度4ってなってるけど、AtCoderでは難易度2となっている。どっちだろう？？~
勘違いだった。
あと、この問題のコーナーケースってどういう意味なんだろう？
(H, W) = (1, 8)がコーナーケースなのは分かるけど、これって2*2の領域をそもそも形成できない場合の仕様が記載されていないから、どうするべきかわからないような、、、？
答えの上界と下界を考える方法が紹介されている。
これは作問者の著者にも紹介があるので、それについてメモした上で問題を考えてみる。
条件を満しつつ最も最適な答えを出すやり方を考える、みたいな感じ。
この問題で考えると、常に(i*j)が奇数のところを光らせるのが最適解を導くことになる。
#.#.#.
......
#.#.#.
なので、HWの中にどれだけijが奇数となるマスが存在するか計算すると答えが出せる。
それを計算するためには(H+1)/2 * (W+1)/2となる。
また、コーナーケース(H or W = 1の場合)を考えて答えを出す。
が、H+1とW+1の発想、どこから出てくるんだろう、、、。どうしてこれが必要なのかは分かったけど、、、。
koheiyamayama
難しい問題じゃないけど、Rubyしかやったことないときの俺だったらnを文字列として操作して最終的に整数にするみたいな手順で解いただろうけど、今は*1000して+200すればええやんっていう発想ができるから進化したなぁと感じる。
koheiyamayamaこれ、ややこしい解法を思いついてしまい、なんかACできなかった。
公式解説などを見てACした。
悔しい。
テストケースは網羅的だろうということは分かったが、自分の実装が良くなかったっぽい。
公式解説ではa~bの要素数が2K以上かどうか判断して、trueの場合はaからa+kまで、b-k+1からbまで出力する。falseの場合はaからbまで出力する。
というもの。これは理解できる。要するにfalseの場合にtrueの手順で出力すると重複する数字が出てしまう。なので、こうしている。
最初自分で考えた時はHashSetに値をinsertしていけば良いのでは？(重複を省きたいから)と思ったけど、だめだった。条件はもっとシンプルにできた。
koheiyamayamaRust(に限らないけど)の小数の扱い方がめんどくさいから、横着した実装したらWAになったので、ちゃんと実装した。
これは答えは最大でも1_000なので、1から1000をループして問題通りに実装すればおっけー。
koheiyamayama
aからbまでの数字を文字列にしてreverseして比較して解いた。
これ以外に方法あるのか？と思ったけど、五桁だから、1桁目と5桁目、2桁目と3桁目が同じであれば回分数であると言える。
このx桁目を割り算で求める方法、素晴らしいのだけど、rust-analyzerがすごい長ったらしい型を付ける(linterのせいではないのだが、、)のが気になる。
koheiyamayama
問題文を読み違えた。
K進法表記のA, Bと書いてあり、A,Bは105以下とあった。
A,BはK進法表記の数字であり、10進法表記じゃない。
A,Bを10進法に直した値が105以下ということらしい。
くそややこしい。腹が立つ日本語だと感じた。
で、そう勘違いしたせいで10**5まで、つまり10_000まで対応できればOKだと思っていた。そういう制約のある関数を書いてしまって11000011010011110とかいうテストケースに対応できなかった。
n進法の値を10進法に直すにはm桁目にn**m-1を掛けていき、それらの合計すると答えが出る。
具体的には1011という2進法がある場合、1 * 1 + 1 * 2 + 0 * 4 + 1 * 8 = 11となる。
一桁目: 1 * 2 ** 1-1 = 1
二桁目: 1 * 2 ** 2-1 = 2
三桁目: 0 * 2 ** 3-1 = 0
四桁目: 1 * 2 ** 4-1 = 8
合計: 1 + 1 + 0 + 8 = 11
てな感じ。
koheiyamayama
この問題、めちゃ簡単やなと思ったけど、一発目waだった。
この手の間違い、ちょこちょこある。
どういう間違いかと言うと、デフォルトでcount = 1とするか、count = 0とするか、みたいな間違い。
入力をlengthがnの配列の時に、配列に含まれないがカウントを1つ進めないといけない時に、count = 0として、分岐の後に加算すると最後の一つの要素が計算されずにwaとなる。
しかも、こういうのはたいていsampleケースだと気づけないので、waとなる。
くぅぅぅぅぅぅ。
koheiyamayama前々からRubyやPython3なら便利メソッドを使うことで解けるなーと思っていたけど、それを使って解いても本質的にアルゴリズムとデータ構造を学べない気がした(そんなことない場合もたくさんありそうだけど、余すところなく楽しみたい)ので、まぁRustでC++と同じぐらいの便利具合(?)で頑張ろうと思った。知らんけど。
koheiyamayama
初めてコンテスト中にC問題解けたけど、B問題が解けなかった。
A問題を解くのに20,30分も掛かってしまったし、一回WA出してしまった。原因は計算式にsampleしか通らない値をハードコードしたままだったこと。ふぁああああああああああああああああああ。悲しい。
時間は足らなかったけど、ABC3問解けただろうなっていう感じがする。
23:07分にB問題が解けた。それまでにWAも多かったけど、3完したことないので、それができたらよく寝れそうだったなぁと思った。
A問題で20,30分ぐらい掛かったのが本当に悔やまれる。わからない問題はiPadで問題を噛み砕くことを反射的にやれないとコンテストは厳しいなと思った。
koheiyamayamaB問題はボーナスを全探索で求めようとしてTLEを食らったこと、条件式を間違えてWAだったことがしんどかった。
解説見てボーナスの受け取り方を工夫することでいい感じにできるっていうのが確かになぁと思った。
じゃなくても、ボーナスを含めない移動経路を算出し、その後にその移動経路にボーナスを含めた場合を計算し直すっていう感じでもできそうだなと思った。
koheiyamayama
これむずかった。というより、medianという言葉にめちゃくちゃ囚われた感じがする。
それはさておき https://blog.hamayanhamayan.com/entry/2019/06/30/100033 がわかりやすかった。
koheiyamayama
逆にこれは簡単だった。
なんかの問題と考え方は似ている。
入力値をsortしておき、先頭から順にループする。こうすると、h[i]~h[i+k-1]が探索するべき区間であり、この区間内においてh[i]が最小、h[i+k-1]が最大である。
よってh[i+k-1] - h[i]をすることでこの区間のdiffを求めて、あとはmin関数で今までのループで求めた値の中で最小のdiffを求める。
最終的に算出したdiffが答えとなる。
koheiyamayamaかなり簡単だった。
diff360だったけど、すぐに解けた。
やっぱり問題との相性もあるし、仕事の後のほうがよく解ける気がする、、、？
koheiyamayama
うぉぉぉぉぉぉぉぉぉぉぉぉぉぉぉぉ！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
初めてdiff873の問題解けた。2時間ぐらい掛かった気がするけど。
でも、一発ACで通せたし、計算量的にも通るはずっていう確信もあったので、素晴らしい。くそ嬉しい。ふぁああああああああああああああああああああああああああああああああ。
koheiyamayamaAtCoderのことをTwitterにつぶやくと、関連ツイートでよくAtCoderやってる人たちのツイートが回ってくる。たいてい素晴らしい成績を残している。まじでこの世には青色以上しかいない気持ちになる。
koheiyamayama
B問題。時間掛かったし、3, 4回WAだったが、、、そんなに難しい問題ではない。
3つの条件を表せばよくて、2つ目の条件の表し方に応じて、3つめの条件の実装が多少変わりそう。
問題が掛かったのはcharをu8として扱ったところでコケたっぽい。最終的にcharの大文字小文字の判定するメソッドがあったので、それを使った。
koheiyamayamau8とcharの関係性を知っているとめちゃくちゃ便利だなと感じる。
koheiyamayamacharの対応
'a'が97
'z'が122
'A'が65
'Z'が90
koheiyamayama文字列の最後の問題。
diffが497で茶色diffだった。
時計は24時を回っており、今日も睡眠時間が削られることを覚悟したが、、、3分?ぐらいで解けた。
嬉しい。
koheiyamayama本では二重ループと書いてあるが、3重ループで解けた。
ユーザ解説も3重ループだから、まぁいいか。
koheiyamayamakoheiyamayama地味に実装が難しいと感じた。
この手のCharsとCharsを比較する問題は結構ABでは頻出だなーと感じる。
koheiyamayama昔は「XXX使ってこんなことできるんか！！すごい！！」で満足できたが、今は世界中のエンジニアにとってのXXXの開発に関わりたい。
だから、アルゴリズムを勉強したいし、数学を勉強するし、ネットワークを学ぶ。これらが全ての基礎であり、世界中で使われるXXXは基礎的なことを抑えた上で作られていると感じるから。
基礎的なことを抑えてそれを自在に実装できる人が俺はかっこいいと思う。
koheiyamayama全然解けない。
二次元盤面で二次元配列をイテレートする時にi, jがx,yのどっちに対応するのかわからなくなってくる。
koheiyamayamaまず、H,W,X,Yの関係がごちゃごちゃになる。
二次元平面の世界だとHとY、WとXが対応しているように感じるが、これが逆になっている。
プログラムを書く時にこの対応が狂うと違うプログラムになるので、上記の対応になるように変数を作ったほうがいい。
koheiyamayama二次元平面を特定のx,y座標を軸に上、右、下、左方向へマスを探索するのができなかった。
が、なんとか解けた。
koheiyamayama
参加した。ABは解けたが、Bはなんか適当に計算してたらこれじゃね？っていうのを見つけて適当に解けた。
Cは図形問題で図形問題はもう解けないものは解けない(高校までの簡単な数学がわかれば解けそうだが、わからないし、それをプログラミングするのはだるい)ので、仕方ない。
D問題はDPっぽいなーと思ったが、まぁまだD問題解けなくても仕方ないや！っていう気持ちで諦めた。
まぁ安定してAB解けるようになったし、ちゃんとCDを解けるようになれば茶色行けるんじゃね？知らんけど。
とりあえず、BとCの振り返りをする。
koheiyamayamaこの手の問題(2次元平面上で隣接するマスの種類に応じてカウントする問題)は解いた時にやってやったぜ感があって好き。
koheiyamayama
これも同じような問題だが、
- 入力値を書き換えていく
- 下から上へ探索しないと正解にならない
というのに最初から気づけなかった。が、実装中にすぐに気づくことができて、対応も素早くできたので、良かった。
rangeに対するrevメソッドが便利すぎる。
二次元平面を下から上へ探索する時には重宝しそう。
koheiyamayama
解けなかった。解説ACした。
べき乗をどうやっていい感じに全探索するのかイマイチ分からなかった。
が、解説を読んでなんとなく分かった。
要するにloop / whileを使う感じになる。
解説をRust実装するとこんな感じになった。
let mut ans = 1;
for i in 2..=x {
// 以下のコードが何をやっているか
// まず、i**2を求める
// i**2がx以下の場合は答えになりうるので、探索をする
// 探索時にそれまでの答えと比較して最も大きい数を答えとする
// x=10の時
// i=2の時には以下の順で計算をする
// tmp = 2**2 = 4
// 1回目のループ
// ans = max(4, 1)
// tmp = 4 * 2 = 8
// 2回目のループ
// ans = max(8, 4)
// tmp = 8 * 2 = 16
// ここでループが終わり、i = 3の計算をする
// tmp = 3 ** 3;
// 1回目のループ
// ans = max(9, 8)
// tmp = 9 * 3
// これでループが終わる
// これ以降はループが回ることはない 4**4はx以上
let mut tmp = i * i;
while tmp <= x {
ans = tmp.max(ans);
tmp *= i;
}
}
解説ACした。
10**9の数を5つまとめて掛け算するとバグることが分かった。
しかも、REじゃなくてWAとなる。
主題であった計算量の方は100C5が大した数じゃないことは分かっていた。
が、usizeを超える数を扱う時に気をつける必要があるのはなかなか気づけ無い。
koheiyamayamaあと、どうしてREじゃないんだ？っていう疑問が強い。正直、よく分からない。
koheiyamayama
これも https://zenn.dev/link/comments/6be9e87f133ecb と似たようなミスした。
10**9を掛け算する時はまじで気をつけないとだめ。
考え方としてはA,Bで使う枚数が決まるとCで使い枚数が決まる。よってAとBに関するループを回せば答えを求めることができる。
この提出は行けるんじゃね？って思ったけどだめだった。
おそらくNが10^9近い値かつAとBが小さい値の時にめちゃくちゃループが回る、理論上は10^8^2ぐらいの計算回数になりそうなので、その時にダメそう。
koheiyamayama
koheiyamayama10**8ぐらいから厳しくなるっぽいので、やっぱりそうだと思う。
koheiyamayama
これのほぼ写経になってしまった。
この問題について考える。
方針としては
- scからdigitsを埋める
- digitsを埋める際に条件を満たすことを担保する
- sc内で二回以上指定された桁がある かつ 二回目以降の指定した数がそれまでと異なる場合は-1を出力する
- digitsが条件を満たすか担保する
- nが2以上の場合、先頭が指定されていない時は先頭に1を追加する
- nが2以上の場合、先頭が指定されているが0の場合は-1
- digitsを出力する
- n桁目以降は最小値として0を取りうるので、指定されていない場合は0を出力する
みたいな考え方。
最初に考えたやり方と大枠は同じだが細部が全然思いつけなかった。
特に - sc内で二回以上指定された桁がある かつ 二回目以降の指定した数がそれまでと異なる場合は-1を出力する の考え方が抜けていた。
サンプルからもとにこんな感じの条件があるのは分かっていたが、うまく日本語にできてなかった。もっとうまく日本語にできていれば実装できたと思う。
koheiyamayamaこれも解説写経になってしまった。
これは答えととなる数値、つまりみかんを選ぶことができる個数は、みかんの重さが最小値1gなので、1~1000 * 1000までの数値となる。
この数値をループして条件を満たす最小と最大の数値が答えとなる。
条件はAN<=1000*W<=BNらしい。
AN, BNはみかんN個選んだときの重さである。
例えば、Aが120, Bが150の時に4つのみかんを選ぶと480g, 600gとなる。
要するにみかんをN個選んだときに合計g数は480g~600gがありえる。
つまり、みかんを4つ選んだ時は480g~600gまで自由にみかんを選択できる。
なので、上記の条件が成立する。
koheiyamayama
この類型を覚えておくと良さそう。
koheiyamayama
ABC267参加した。
ABともに何回かWAを出した。
AのWAはまじでポンコツ。出力内容を間違えていた。
BのWAは何回か気づけなかった。問題は条件を満たす2つの列の間に1つ以上の条件を満たさない列がある場合、Yesと出力するというものだったが、1つ以上じゃなくて1つだと思っていた。なので、最初はtrue, false, trueとなっている場合にYesと出力していた。もったいない。
CはACできなかった。
ただ、解説読んだ感じだとそこまで見当外れなことは考えてなくて、
- 事前に数列からいい感じに計算しておく
- 計算した結果から最大値を出力する
という流れだろうとは思っていて、それは合ってそうだった。
が、細かいところが全然考えつけなかったし、パッと解説読んだ感じだと全然分からない。
明日、解説動画でも見る。
koheiyamayama
公式の解説読んでもいまいち分からなかったが、上記解説で理解した。
ABピザ2つを買った個数が0,1,2,...の時にA, Bを買う枚数が決まる。なので、ABピザ2つ買った個数でループすると良い。
この何でループするのか？を考えるのが全探索の難しいところな気がする。
koheiyamayama
この辺りの解説はだいたい同じことを言っているが、以下が全く理解できない。
部分的なことはわかったので、全体的なことを考える
a,b,ca,b,cという3つの数を考慮した場合、条件を満たすのは以下のいずれかが当てはまる時である
(a%K,b%K,c%K)=(0,0,0)(a%K,b%K,c%K)=(0,0,0)
(a%K,b%K,c%K)=(K2,K2,K2)(a%K,b%K,c%K)=(K2,K2,K2)
AtCoderやってる人は全員、この辺の定理?整数の性質?みたいなのを暗記しているのか？？？？？
そんなのどこで習うんだよ、、、、。
koheiyamayama
難しい。
最初、バケットを使ったけど、全然関係なかった。
解法は本に書いてあるけど、
- 文字列をソートする
a. アナグラムであればソートされた文字列はおなじになる - 文字列をキー、countを値としてHashMapを作る
a. 与えられた文字列の中に同じアナグラムがいくつかあるかカウントする - 2で作ったHashMapを使ってキーごとに組み合わせを計算し、合算する
っていう流れだった。
言われてみればたしかになと思う反面、思いつけねぇ、、、っていう気持ち。
koheiyamayama
この提出の最後の方のループの回し方、綺麗だなと思った。
この問題は
- 出現したボールに書かれた数をグループごとにカウントする
- カウントでソートする
- 少ない方から数えて、ボールの種類 - K分のカウントの合計が答えになる
という問題だった。
俺はvaluesとsliceの展開を使って解いたけど、この提出は最後の工程をループで解けている。この提出のほうがif式が少なくて綺麗。
koheiyamayama
あまりいい解き方じゃなさそう。
2回sortしており、それが遅い原因になっていそう。
他の解き方を見たがいまいちわからんかった。
koheiyamayama
一回WA出した。
そのあとすぐに3回以上出現する数がある場合にどうなるのか？ということに気づき、そのケースが漏れていることが分かった。
それの修正もすぐにできたが、用意したテストケースが間違っており、手元でACしなかった。
koheiyamayama数学とアルゴリズム本の著者が数学解説のスライドを作った。俺でも理解できるかわからないけど、読んでみたい。
koheiyamayama
解説ACした。
要するに
- 組み合わせは(n-1)+(n-2)+(n-3)...をnが0になるまで行った結果である
- これは自分で気づいた
- 2,1,3,4,1,5みたいな数列がある時、1までに作れる組合わは1通り、3までは2通りと増えていく
- これも気づいていた
- 問題の条件である(i,j)のときAi != Ajであることを満たす組み合わせを計算するためには3までで作れる2通りのうちに無効な組み合わせが存在するか確かめると良い
- 解説で分かった
- 例えば、5つ目の1を考えると、これまででできる組み合わせの数は4通り、そのうち1が一つ含まれているので、3通りが有効な組み合わせとなる。これを素早く計算するためにはMapを使い、5つ目の1が出るまでにどんな数字がいくつ出たか数えておくと良い。
koheiyamayama完全にひらめいた。
koheiyamayama
youtubeの解説を見た。
解説と全く同じ考えだったが、実装がよく分からない。
を読んだ。
けんちょんさんの実装はわかりやすい。
実装もなんとなく理解できたが、また解ける気はしない。
この問題、めちゃくちゃ難しい。
koheiyamayama
この回答、めちゃくちゃわかりやすい。
今回も考え方はそんな間違ってないんだが、実装ができなかった。
この回答は
- 増加してるタイミングから減少するタイミングを数える(逆もしかり)
という考え方。
考え方自体は理解できるし、似たようなことやってたが、俺は数列をシミュレートしようとして実装ができなかった。カス。
koheiyamayamaちょくだいさんがWAになったときのテクニックを紹介している。
koheiyamayama累積和問題として二次元平面のグラフが与えられる場合とマスが与えられる場合でちょっとシミュレーション方法が違う。
グラフをマス目で安直に考えると正しい答えを出せない。
以下の問題を対比すると、A09はマス目、B09はグラフで問題が与えられてる。
若干シミュレーション方法が違うはず。
koheiyamayama累積和、1回はREを出してしまう。辛い。
koheiyamayamaRust(に限らないが)ビット演算を使って解く問題は基本的に難しく感じる。
何を言っているのか分からない。
2進数とかは分かるんだが、ビット演算を使うことで、どうして問題を解けるのかイメージできない。
koheiyamayama割り算難しい。