すいかの精進旅日記
問題まとめ！
やった問題を分野別にまとめていくところ！最近やった問題やふとやったなこれって思いついた問題をとりあえず添付する！
過去にやった問題や新たにやった問題もどんどん追記予定。解説は気が向けば書くかもしれないやつもあるかもだけど、とりまぽんぽんおいていきます。解説書いて欲しいやつがあったら言ってくれたら書くかもしれない！ただすいかレベル（緑下位ぐらい！）かつすいかクオリティなことは予めご了承ください、、、(๑>◡<๑)
私ぐらいのレベル帯の人はどんな問題をやってるのかな？とか、この分野の問題を解きたいな！って時に活用するといいかも？
ただ、分野別なので、ネタバレ注意！！
全探索
bit全探索、DFS
B - Addition and Multiplication
深さ優先探索（グラフより）
幅優先探索
Programming Problems and Competitions :: HackerRank
二分探索
Programming Problems and Competitions :: HackerRank
Programming Problems and Competitions :: HackerRank
三分探索
尺取り法
累積和
Programming Problems and Competitions :: HackerRank
いもす法
Programming Problems and Competitions :: HackerRank
動的計画法
最大値最小値（boolも含む）
Programming Problems and Competitions :: HackerRank
Programming Problems and Competitions :: HackerRank
数え上げ
桁DP
bitDP
区間分割DP
最短経路
グラフ問題各種
トポロジカルソート、強連結成分分解
XOR
N進数
No.915 Plus Or Multiple Operation - yukicoder
数学的問題（GCDや素因数分解など）
数学的問題（整数や確率期待値、その他）
D - いろはちゃんとマス目 / Iroha and a Grid
コンビネーション
すいか、AtCoderで遂に緑色になりました！！
やったー！！わーい！！(๑>◡<๑)
遂に入緑！！！！！！！
本記事では緑色になるまでにやったことや必要そうなこと、嬉しみを書いていこうと思います！よければお付き合いください！
緑色になるまでの期間や精進量
現在のレート推移はこんな感じです！
コンテスト初参加から１ヶ月半ちょいほどで茶色に、茶色になってから２ヶ月ほどで緑色になることができました！かなり順調に上がっていってるんじゃないかなーと思います（笑）
灰色時の初めの数回は茶色パフォ下位、4回目ぐらいから茶色上位〜緑パフォが出始めました。150ACぐらいして、C問題も徐々に埋まっていったぐらいで少しずつ本番でも力を発揮できるようになってきたと思います。無事6回目に、実質速解きコンテストで提出コードを間違えてペナルティが出るなどしましたが、何とか茶色になることができました。（次の回に0完太陽をして灰色に舞い戻ったのはまた別のお話）茶色になってからも茶色上位〜緑下位パフォが出続けていましたが、それ以上に伸びることは殆どなく、誤読や凡ミスも相まって中々思うようにパフォが伸びませんでした。普通にやらかし回もあって、茶色下位パフォも出したりしてました。ただ精進は続けていたおかげか、体感では失敗を感じても、パフォはそれなりに出ていました。
悪い意味でも良い意味でも緑下位パフォほどで安定させることができ、今回のレート爆上げにも繋げることができたんだと思います。╰(*´︶`*)╯♡
期間にすると意外にも２ヶ月かぁ、という感じですがかなり長く感じてました笑
（みんなレート上がるのはやいんだもん！！）
当然ですが、競プロ以外にもやらなきゃなこともあってあまり精進できない時などもありました。そういう時は、とりあえずStreakぐらいは繋げようとスマホからA問題を解いたり、電車の移動中を活用するなどしてました。ただまだまだ捻出できたと思いますし、他のやらなきゃなことにももっともっと取り組めたかなーと反省はしてます。（成長は感じるので、これからもっとがんばっていきますー！＞＜）
ちなみに、これが緑色達成時のAC状況などなどです。
茶色時にはC問題埋めに加えて、AGCのA問題や、D問題埋め、他にもこどふぉを若干埋めたりAOJもたまーにやってました。
精進レートも置いておきます。のんびりじわーっと上がっていってます。
緑になるためにやるべきこと！
やっぱり過去問かな！！って思います笑
ただ流石にこれじゃ終われないので、特に重要に感じたものを挙げると、CPSCOの問題や、AGC-Aの300点あたりは個人的にはかなり効果を感じられたかなって思います。CPSCOは当時では非常に学びが多かったです。AGC-Aは最近取り組んだのもあり、どちらかというと今までの総復習をしているような感覚になったのですが、それだけ重要な考え方や知識なんかが詰まってるように感じました。ABC-CやABC-Dはじわじわ効いてくる感じがしますね笑
あとは色んな人の記事とかも参考にするのも勿論大切ですね！（けんちょんさんとkry）
具体的な知識やテクニックなどについては、学んでも実際にコンテストでは使用機会がなかったものや活用できなかったものも多いので難しいのですが、とりあえずやったことを（全部とはいかないと思いますが）挙げておきます！
重要
- DFS（深さ優先探索）
- BFS（幅優先探索）
- bit全探索
- 累積和
- しゃくとり法
- いもす法
- GCDやLCM（最大公約数や最小公倍数）
- エストラテネスの篩、素因数分解、約数を求める
- 二分探索
- 基礎的な確率や期待値の知識
- 順列、組み合わせ（ライブラリ持っておくの超大事だと思います。）
- 文字の出現頻度を数えるテク
- modの基本的な性質
これから活用できそうなもの
- 基礎的なDP各種
- Union Find
- ワーシャルフロイド法
- ベルマンフォード法
- XOR
大体こんな感じかなと思います。意外と多かった。。。（？）
ソートの仕方や貪欲、後ろから見る、区間スケジューリングとかそういうのはちょっと書きづらかったので上記には記しませんでした。他にも決め打ちにぶたんやマンハッタン距離（45度回転）、Sparse Tableっぽいものも気持ち触りましたが、まだまだ使いこなせるものではなくて、緑になるにも流石に必要ないかなということで記していません。組み合わせのライブラリは使う機会の割に、ライブラリを作るのが大変だったりすると思うのでどなたかのを参考にすると良いと思います。（フェルマーの小定理や繰り返し２乗法を使うかも？）他にも、大変だと思いますが、Union Findも一度ライブラリを作ってしまうとUnion Findを使ってかなり簡単に解ける問題もあると思うので、お勧めです。
これにて終わり！
ここまで読んでくださり、ありがとうございました！！
おめでとう！という声も沢山いただいてとっても嬉しいです！！また、緑になれたのも記事を書いていて下さっていた方々や、私の質問に真摯になって付き合って下さった方々、その他でも大変励みになることは沢山ありました！
みなさんありがとうございます！(*≧∀≦*)
最後に自慢気に緑到達時のコンテストの順位表を貼っておきます！(๑>◡<๑)
PS:タイトルから名前の自己主張強いかなーとは思った（）
技術室奥プロコン#4day1_G問題_バラバラ掛け算〜すいかの精進旅日記〜
まったりトークコーナー
本番中はとっても苦戦しました！！
ただとっても勉強になって面白かったですし、解説ACもなんとかできたので記事に残しとこうかなーって気分で今書いてます(*'▽'*)
解説
editorial.pdf - Google ドライブ
和が一定，積の最大値はいくつ?|思考力を鍛える数学
わからない！解説が欲しい！って人は正直この辺り見れば十分です☆*:.｡. o(≧▽≦)o .｡.:*☆
解説のページと数学のサイトとってもわかりやすかったです！
（ありがとうございます！）
それでは、ほぼ余談みたいなレベルの解説になると思いますが、それでも良いよって方はお付き合い下さい！
1, 2, 3, 4, 5, 6, ...と和の形に分解してその積の値がどんな時に大きいかを確かめていくと、
1 = 1
2 = 1 + 1 = 2
3 = 1 + 1 + 1 = 1 + 2 = 3
4 = 1 + 1 + 1 + 1 = 1 + 3 = 2 + 2 = 4
5 = 1 + 4 = 2 + 3
6 = 2 + 3 + 1 = 2 + 2 + 2 = 3 + 3
7 = 1 + 6 = 1 + 3 + 3 = 2 + 2 + 3
赤色をつけた分解の仕方が最も積が大きくなっています。ここでなんとなーくわかるのが、２や３の形で分解した方がポイントは大きくなりそうってことですね。もう少し考察を進めて、２や３でどう分解した時が最も大きいかを考えると、６を分解した時に2 + 2 + 2 = 3 + 3の時、2^3 < 3^2となっているので、2の足し算が3つ続いているときは3+3に置き換えた方が良さそうです。ただし、7の時にそれを行うと、1 + 3 + 3と2 + 2 + 3では後者の方が大きくなってしまいます。これは3 + 1と 4を比べた時に後者の方が積が大きくなるからです。
あとは、6を3+3で分解した時が最も大きい数がわかったので、与えられた入力Nを6で割った余りごとに場合分けして求めていけば良いです。この辺については、詳しくてわかりやすくて素晴らしい解説が上記に記した解説PDFにあるのでそれを見てもらえれば良いかなと思います。
それをPythonで実装したものを記します。（ほぼ一緒ですが書き方表記は等若干違うところもあります。）
Q = int(input()) N_list = list(map(int, input().split())) mod = 10 ** 9 + 7 nums = [] for N in N_list: a = N % 6 if N <= 4: num = N elif a == 0: p = N // 3 num = pow(3, p, mod) elif a == 1: p = ((N - 1) // 3) - 1 num = pow(3, p, mod) * 4 elif a == 2: p = (N - 2) // 3 num = pow(3, p, mod) * 2 elif a == 3: p = N // 3 num = pow(3, p, mod) elif a == 4: p = ((N - 1) // 3) - 1 num = pow(3, p, mod) * 4 elif a == 5: p = (N - 2) // 3 num = pow(3, p, mod) * 2 nums.append(num % mod) print(*nums)
余りが3, 4, 5の時は、（ここでは3について）
elif a == 3: p = (N - 3) // 3 num = pow(3, p, mod) * 3
のように、a = 0, 1, 2の流れのまま書くこともできますが、上記のように書くと、余りが0の時と余りが3の時、余りが1の時と余りが4の時が同じ式になっていることがわかります。よって、実はその計算式は周期が3で考えることができるので、Nを3で割った余りで考えることもできます。そうするともう少しスッキリ書くことができて、次のようになります。
Q = int(input()) N_list = list(map(int, input().split())) mod = 10 ** 9 + 7 nums = [] for N in N_list: a = N % 3 if N <= 4: num = N elif a == 0: p = N // 3 num = pow(3, p, mod) elif a == 1: p = ((N - 1) // 3) - 1 num = pow(3, p, mod) * 4 elif a == 2: p = (N - 2) // 3 num = pow(3, p, mod) * 2 nums.append(num % mod) print(*nums)
AtCoder ABC051-D Candidates of No Shortest Paths 〜すいかの精進旅日記〜
まったりトークコーナー
これから400点問題を埋めていくことが増えていきそうなので、復習なども兼ねて備忘録としてブログを書くことにしました。
ただ備忘録って書いてる人は時々見かける気がするので、ちょっとカッコつけて旅日記っていう言葉を使ってみました。すぐ周りと違うことをしたがる凡人の極みですね。（？）
それから当方茶色なので、間違いなどがあれば優しく指摘してくれると嬉しいよ！！＞＜
（ただ参考にしてくださった方には本当に申し訳ないので、話半分ぐらいでみてくれるといいかもしれません！）
当然ネタバレなどを含むので、みたくない人は撤退を推奨です＞＜
問題
解法
はっきり言って、ほぼみなさま頼りだったので、参考になったサイトなどを掲載しておきます。
いつものごとくけんちょんさんも登場です。
とってもわかりやすかったです！！
自分の書いたコードも最終的にはけんちょんさんのコードをほぼ写経しました（）
ワーシャルフロイド法については以下のサイトにお世話になりました。とても参考になったので、ワーシャルフロイド法がまだ不安って人は是非みてみると良いと思います。
（みなさまありがとうございました！）
AtCoder Beginner Contest 073 解説放送 - YouTube
解説ACとかになると自分なりの言葉をある程度用意できても、中々まだ人の言葉を使ってる感覚にもなるので罪悪感もありますね。ただ、こう言った記事を書く以上なるべく自分の言葉で頑張っていこうと思います。（もしも頼り過ぎた言葉になってたらごめんなさい！）
それでは、あくまで備忘録で解説ってわけでもないので、簡潔にいきます。（ちょっとは誰かがこの問題で躓いた時に助けになれたらなって気持ちはあります。）
連結グラフなので連結グラフを考えます。（それはそう）
グラフなので、DFSやUnion Find木なども考えたくなりますが、木じゃないことや最短経路を考える、N <= 100という条件からダイクストラ法やワーシャルフロイド法を使いたいような気持ちになると多分きっと嬉しいです。
ここで「どの異なる２頂点間の、どの最短経路にも含まれない辺の数」を満たす条件を考えます。まず最短経路になる可能性のあるルートを考えると、直接頂点aから頂点bへ行くルートと、頂点aから頂点cなどへ行ってから頂点bへ行く迂回ルートがあります。この時頂点aからbへ直接行くルートが最短経路だった場合、当然辺abは最短経路に含まれます。しかし、迂回ルートが最短だとすると、辺abが最短経路ではなくなるのでこれが最短経路にも含まれない辺になることがわかりますね！（どちらとも最短経路のケースもあることに注意！）また、どの異なる２頂点間でも〜とありますが、頂点a-b間が最短じゃない時点で、他に最短で良いルートがあるということなので気にしなくても良いです。
あとは、ワーシャルフロイドなどで各頂点の最短距離を求めて、その最短距離よりも距離がある辺を調べていけば良さそうです。
そしてほぼ写経によって書き上げられたコードがこちらです！（ちなみにPythonです）
おまけ（すいかの失敗話）
実は、初めはワーシャルフロイドなんてすっかり忘れててDFSで取り組んでました。
以下がそのコードになります。初めはO(N^3)ぐらいで各点からのDFSをして、その距離をうまく保存更新（visitedをvisited[N][N][2]で持つとかを考えた）、比較して解法に書いた方法をすればいけそうと思ったのですが、いつの間にかO(N^2)でいけるやろみたいに思ってしまって謎のコードが完成しました。できた時にはダメだと思ったのですが、一応サンプルを通したところ何故か全部通ったので投げてみると5/30ぐらいは進んで少し面白かったです笑
50ACを経てAtCoderコンテストに初挑戦した！
憧れのAtCoderのコンテストに参加してきました！
いや、ほんとにドキドキの緊張しまくりで大変でした、、、
タイトルの通り、完全に予備知識なしで飛び入りで挑んだわけではありません。割とそこそこ準備して挑みました。（たぶん）
これから、参加した経緯ややったこと、結果とかとかあばうとに書いていこうと思います。是非お付き合いして閲覧数に貢献してください（そして、初めてブログを書いている私の自信をUPさせてください←）
目次：
コンテスト参加までの経緯とか！
プログラミングバリバリでつよつよな先輩に誘われたのがきっかけでした。
な状態ではあったんですが、プログラミング自体にはぼちぼち触ったことはある（レベル的にはif文、for文が使える（≠使いこなせる）。ほんの少し指先だけ深層学習にも触れてるという感じ）、楽しいや好きって感情も沸くし、興味もあるからやってみようかな？そんな感じでした。時期的には去年（2018年)の11月ぐらいでした。
そして、早速AtCoderのサイトに行き、登録。
これからがんばるぞー！（盛大なフラグ）
思い切り忙しい時期に登録したことや、単純にモチベの問題（早い）などにより早々にAtCoderを離れましたとさ、、、、、（）ただ、離れる前にいい感じに休みなどもあり10日ぐらいはがんばった（自己満足）。やったことは次の見出しで！
そして、今年の3月中旬～下旬（正確には一瞬だけ2月にも触れてる）に時間とモチベを再降臨させ、舞い戻ってきました！
修行の日々！←
具体的に言うと、AtCoder Problemsで50問ほど問題を解いてから挑みました。
↓が初参加したときの精進グラフ（？）です。
B問題とC問題を中心に解いていたことがわかりますね。（誰目線（））
ついでに、この時は50AC記念＋10000P＋10Days継続記念ということで、
私がめっちゃくちゃ嬉しかった！！！！
ということもわかりますね。（誰目ｒｙ）
↓↓これより暫く50ACの経緯！（思ったより余談なので飛ばしていいかも！）
さて、ようやく本題っぽいこと、、、の前に、そもそもなんで50ACしてからの参加だったんだ？って話です。別に何度でも出れるし、AtCoderは参加回数が少ないうちはレートが低めについてしまいます。準備をし過ぎても、あんまりメリットはないんじゃないかなと私自身も思います。冗長になっても仕方がない話なので、簡潔に言うと、
初参加ですっごくレートが伸びてたらめっちゃつよそう！かっこいい！すごいって言われたい！
これに尽きます（）
実際、ツイッターとかみているとそんな人が沢山いるようにみえて、憧れがありました。そういう人達は（恐らくですが）、元々数学のガチ勢（数オリとか出てた人）や他の競プロをやっていた人、仕事などでガッチガチにプログラムに触れていた人、そして、適性がとんでもない人（天才）、などだと思います。私はこれらにこれっぽっちもかすってすらいません。ただ、憧れはあったので、少しでもそういうに風に演じられたな～、すごいって言われたいな～という邪な想いがあったからです。
褒められるのがとっても好きなので！（褒めるのも好き！
あとちょっとのよくわからないプライドみたいなのもあったかも？？ただ、変にちょっとかっこつけようとし過ぎてた感があるのでなんとなく反省してます（苦笑）。というのも、この計画を少し甘く見てた節があるからです。もっともっとACとか決めてから参加できてれば良かったんですけど、コンテストに参加したい欲求に負けてしまいました（笑）。50ACは私的には及第点ではあったんですが、ちょっと微妙ですよね( ;∀;)。けれど場合によってはこういうプレイングもアリだと思うし、誰かやってカッコ良く決めてほしいなとも思います（笑）
（脱線し過ぎそうなのでこの話はこの辺で）
さて、本題っぽいことです！
前述した通り、要は初動で高パフォーマンスをとりたかったわけです。なので、コンテスト初参加までの約3週間ほど、私なりに精進（つよつよな人からみれば大袈裟かもしれませんが）した方法とその結果を示していこうと思います。どんなことをして、どうなったか、そんな風に参考になったらなあと（願いすぎ？）
私がやったことは大きく分けて2つです。
- けんちょんさんのQiitaを参考に問題を解いていった。
- AtCoder Problemsから新しい順に問題を解いていった。
まずは、けんちょんさんのQiitaでおべんきょしました！というか、二進も三進もわからない中、これ以上なく頼りになりました。
主に、AtCoder Bebinners Selectionの勧めや後半にはB問題を解くのに重要な典型問題がまとめています。
というわけで、まずはAtCoder Bebinners Selectionの問題から解き始めました。A~C問題まであり、C問題では計算量を考える必要がある問題や少し発想が必要な問題もありました。しかし、前提知識としてはif文やfor文が少しわかっていれば、解ける問題が多く、わからなくても、解説を見れば十分解ける。調べる苦労がまだ少ない分、始めたばかりのひとにとって、すごくとっつきやすく感じました。
ここで、競プロの形がなんとなくわかったなぁと思います。
それから後半にまとめられている問題（グリッド、累積和、数学的な問題など）を解き始めました。Minesweeperがラスボスぐらいにみえました。
状態をループする問題も非常に難しく感じましたが、なんとかやり切りました。
取り組み方については
- 2度取り組んだ
- わかった問題も解答を見てやり方が違ったらリトライ
- 解答通りの解き方でも気になった解き方を思いついたらやってみる
「2度取り組んだ」については、登録してやり始めた時（半年ほど前）にやったいたんですが、久しぶりに始めたときに殆ど忘却していたので、再度解いたため、偶然そうなりました。しかし、結果的に2度解いたことはとっても功を奏しているなと思います。基礎的な良問がそろっている（そもそもAtCoderの問題はどれも良問だとは思いますが！）ので、このおかげで土台がしっかりとできて、以前理解が進まなくなっていた問題もスムーズに考察できるようになっていたなと思います。
そして、こちらのほうもやりました。
動的計画法の手前ぐらいまでやりました。この辺りで得られた知識を箇条書きにしておきます。（けんちょんさんのQiitaを見てもらえばわかるとは思いますけど！）
知識としてはこれぐらいはついたと思います。
そして、C問題ぐらいまでの内容は抑えられただろう、、、と考えて、AtCoder Problemsから過去問を解き始めます、、、、
しかし、びっくりするぐらい解けませんでした( ;∀;)
B問題までは確かに解けました。しかし、C問題は全然でした、、、ぶっちゃけ、簡単な方なんだろうなという認識はあったものの、D問題のGrid Repaintingとかは自力ACできていたので、変な自信がついており、競プロの難しさを再認識しました、、、
ただ、C問題を10問ほど解いたあたりで慣れてきたなという感触がありました。自力ACも少しずつできるようになってきました。何故かといわれると、シンプルにやってきた問題の幅がまだまだだったんだなってことだと思います。ただ慣れるのが（私的に）早かったのは、けんちょんさんのまとめのおかげだなぁ、とまざまざと感じました（圧倒的感謝でも足りないぐらい感謝してます！）。
そうしてC問題レベルぐらいまでの知識と、少し慣れてきたあたりで実際のコンテストに挑みました！！（目標は3冠でした！）
ABC124に挑戦！
AtCoder Beginner Contest 124に参加しました！
正直ここまで書いてへとへとなので、かなり雑いかもしれません（想定の10倍ぐらい長くなった気がする。）
問題のリンクを貼っておくので問題の概要は省きます。
注意：特に問題の解説等はなくほぼ感想です。
A問題
コードを見てもらえばわかると思うのですが、かなり血迷いました。速攻ACしようと力みすぎて、全く考察し切れてなかったです。つらい（）6分ほどかかりました。
B問題
落ち着いて問題文通り、そのまま実装したつもりです。8-9分で書き終わり、1-2分をしっかりテストにあててACできました。A問題でのことをきっちり反省できていますね（）
C問題
こちらは最後の出力（18行目）を思いつくまでに混乱したりあれしたりで時間がかかりました。あれ？あれ？っていうくだりを何度やったかわかりません。逆にfor文内の発想まではすぐできて、ここまでかければあとはなんとかなりそう！という見切り発車だったんですが、上手くいったといえばそうだし、いなかったいえばそうだし、うーん。
40分ぐらいかかりました。
D問題
にゃーん
総評（嘘、感想）
3冠！！！！！うれぢいいいいいいいい！！！！！！！
けど、くやぢいいいいいいいいいいいい！！！！
というのも、3冠達成者が多く、かかった時間の関係で思ったよりもパフォが出てなかったです！コンテスト中、3冠した時点で、「今回C問題にしては簡単な気がしたし、思ったほどパフォ出てないかな？」とは思っていたものの、順位表をみたところ下から数えた方が早くて、マジで涙目（嬉し涙ならよかったのに、、、）になりそうでした、、、
大体こんな感じで第1回ブログは閉廷しようと思います。
本当に拙いところばっかりだったと思いますが、もし読んでくれた方がいたなら、
本当に本当にありがとうございました！！！！！！
それから最後に、忘れていたので自己紹介しておきます。すいかです！これからたまに気が向いたらまた投稿するかも！よろしくお願いします～！
結論：けんちょんさんはかわいい（）
