ABC115-D Christmasを救いたい
Christmas 聞け
かの有名な（？）ABC(AtCoder Beginner Contest)115-D Christmas。
全僕を苦しめた問題の一つです。
↓問題リンク
https://atcoder.jp/contests/abc115/tasks/abc115_d
その問題設定は「ダックスフンドのルンルンくんがintに収まらないほどのハンバーガーを食べる」という正気の沙汰ではないものです。
実際実験してみるとレベル1のハンバーガーはたったの5段（本当に 「たった」 か？）ですが制約上最大であるレベル $50$ はなんと $4503599627370493$ 段ものハンバーガーからなっています。ねずみ算怖すぎ。ありえねえ。
これだけでくそなぞなぞができそうです。
Q.レベル50のハンバーガーは4503599627370493段あるよ。これなーんだ？
A.そんなもの、あったらやばいだろ・・・
はい。
ところで、そんな問題ですが最近ようやくACすることができました。非常に嬉しかったです。
そこで自分なりの考察と解説をここにのこそうと思います。（この記事より優れた解説記事は多くあるので、それらを参考にした方がいいと思います。）
【ぱっと見の方針】
レベル $50$ のハンバーガー、やばいのでハンバーガーの層をしたから全て見ることはまず不可能です。
そこで以下のようなことを考えます。
右上のルンルンくん、かわいいですね。
非常に明瞭な絵なので解説は不要でしょう。（は？）
結局何が言いたいかというと、
レベル $N$ バーガーは、レベル $N-1$ バーガーを、
レベル $N-1$ バーガーは、レベル $N-2$ バーガーを、
・・・
レベル $2$ バーガーは、レベル $1$ バーガーを、
含んでいるということです。
よって、$X$ 段目までのパティの数を求めたいのに、位置が特定できない時は、今見ているレベルより下のレベルのバーガーに注目することで位置を絞り込むことができ、最終的には位置が特定でき、何枚パティを食べるかも特定することができる。ということになります。
ここまでくればあとは再帰なりで解くことができますね！ようやく光が見えました！（僕は再帰で解きましたが他の解き方もあるかもしれません。）
さて、本番はここからです。
前提として各レベルのバーガーの層の数、パティの数は事前に計算しているものとします。
この絵も非常にわかりやすいですね！（は？）
$(1),(2),(3),(4),(5)$ はそれぞれ下からX層目まで食べるときの、$X$ の値による場合分けを表しています。
それぞれ、以下のような状況です。
- (1) $X == 1$
- (2) $1 < X <$ (レベルN-1バーガーの層の数)$+2$
- (3) $X ==$ (レベルN-1バーガーの層の数)$+2$
- (4) (レベルN-1バーガーの層の数)$+2 < X < $(レベルNバーガーの層の数)
- (5) $X == $(レベルNバーガーの層の数)
なんとなくわかりやすくなった感がありますね。
この中で一発でパティの数を特定できるものは、$(1)と(3)と(5)$ です。
$(1)$ についてはレベル $0$ バーガーを見ている時ならば $1$ 枚パティを食べることができます。
それ以外では食べることができません。
$(3)$ についてはレベル $N－1$ バーガーに含まれるパティ $+1$ 枚を食べることができます。
$(5)$ についてはレベル $N$ バーガーに含まれるパティ全てを食べることができます。
これは以下の様に実装できます。
- //level.at(L)はレベルLバーガーの層の数
- //paty.at(L)はレベルLバーガーに含まれるパティの数
- if(L == 0){
- if(X == 1) ans++;
- return ans;
- }
- else if(1+level.at(L-1) == X){
- //真ん中のパティ一枚手前まで=レベルL-1バーガーのパティを全て取れる
- ans += paty.at(L-1);
- return ans;
- }
- else if(X == level.at(L-1)+2){
- //真ん中のパティまでちょうど取れる
- ans += paty.at(L-1)+1;
- return ans;
- }
- else if(X == level.at(L)){
- //レベルLバーガーのパティを全て食べられる
- ans += paty.at(L);
- return ans;
- }
さて、$(2)$ と $(4)$ の場合が少し大変です。
$(2)$ の場合から考えてみましょう。
- $(2) 1 < X < $(レベルN-1バーガーの層の数)$+2$
という条件を言い換えてみます。
$(2)$ の条件下において $X$ はレベル $N-1$ バーガーの層の数以下に収まります。
今見ているレベル $N$ バーガーの前半部分の層の数は $1+$ (レベルN-1バーガーの層の数)として表せるので、レベルを一つ下げて、さらに、$X$ を $X-1$ として再帰関数を呼べば、レベル $N-1$ バーガーを純粋に考えることができます。
これで $(2)$ の場合は考えることができました。
最後に $(4)$ の場合です。
- $(4)$ (レベルN-1バーガーの層の数)$+2 < X < $(レベルNバーガーの層の数)
(2)と同様に考えます。
Xは、今見ているレベル $N$ バーガーの前半部分を完全にカバーしています。よって、前半部分の、(レベル $N-1$ バーガーのパティの個数)+(真ん中の $1$ パティ)は確実に取ることができます。
後半部分の層の数は前半部分と同じく(レベル $N-1$ バーガーの層の数)$+1$ として表せます。よって、レベルを一つ下げて、さらに、$X$ を $X-$ (レベル $N-1$ バーガーの層の数)$-2$として再帰関数を呼べば、後半部分のレベル $N－1$ バーガーを純粋に考えることができます。
あとは実装です。$(2),(4)$ は以下の様に実装できます。
- if(1 < X && X < 1+level.at(L-1)){
- X--;
- dfs(X,L-1);
- }
- else if(X > level.at(L-1)+2 && X < level.at(L)){
- ans += paty.at(L-1)+1;
- X -= level.at(L-1)+2;
- dfs(X,L-1);
- }
くぅ～、疲れました！ｗ
これにてChristmas、ACです！
ACコード↓
https://atcoder.jp/contests/abc115/submissions/14204942
ありがとうございました。
緑コーダーになりました
ABC168にて、緑コーダーになりました！（いえーい！ドンドンパフパフ）
こう見ると灰色がとても長かったですね・・・。
茶色になってから本格的に精進を始めたのでそのお陰で茶色を割と早めに通過できたのかなぁと思います。（苦節のコンテスト参加35回・・・）
入緑したときのAC数とRated Point Sumです。
外出自粛期間にめちゃ精進頑張りました。
＜感想とか＞
直近3回のABCは緑が見えていた分、思った成果が出せなくて正直つらかったです。
今回のABCでもCとDでよくないムーブをしてしまい納得のいく形で緑になれなかったのは少し残念ですが、緑になれたのでなんでもヨシです！やったー！
＜精進とか＞
自分が精進する上で心がけていたこととしては、一つの問題に悩みすぎないということです。その問題を解くための知識・データ構造とかを知らない可能性もありますし、方針は立っている（計算量の考察も含めて）のに、実装ができないというのは、なんだかもどかしくないですか？僕はもどかしいです。なので僕は「考察はできているし解説見てヨシ！ｗ」のスタンスで問題を解いています。実際そういう時は解説・解説ブログを見ても割とすぐに理解して実装できる場合が多いです。
そして、最もおすすめしたい精進のお供として、E869120さん執筆の、
https://qiita.com/e869120/items/eb50fdaece12be418faa
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン
の中級編に書かれている、『分野別 初中級者が解くべき過去問精選100問』が非常におすすめです。AtCoderだけでなくJOI、AOJの問題も多く扱われています。分野別に基本問題から応用問題まで取り扱っており、取り組みやすいです。僕も100問中70問を解き、ある程度自信を付けました。↓進捗を管理すると、なんかいいですね。
さらにAtCoderの分野別の問題を解きたいという方には、けんちょんさん（@drken1215）の
https://qiita.com/drken/items/e77685614f3c6bf86f44
AtCoder版！蟻本（初級編）
がおすすめです。多くの問題が取り上げられており、とても良いです。（何様だよ）
それと、JOI過去問埋めもおすすめします。JOIは実装寄りの問題が多いです。
（難易度6,7が解けません・・・助けてください・・・）
＜学んだアルゴリズムとか＞
・学んだし使った
全探索
計算量改善（の努力）
ビット全探索
（高速な）素数判定法
（高速な）べき乗計算・nCr系の問題
累積和
・学んだけどコンテスト本番では使ったことがない
順列全探索（next_permutationとか）
二分探索
ナップサックDP
ダイクストラ法・ワーシャルフロイド法
Union-Find
圧縮
・学んだことがない、理解していない
区間DP、bitDP、等、DPについての理解が全体的に浅い
Segment Tree、BITとかの高度（個人的）なデータ構造
ゴリゴリにアルゴリズムや、データ構造を使うことはあまりありませんでした。（ABC E,Fとかになったらありそうではありますが、解いてないので、わかりません）
緑になれた最大の要因としては毎回コンテストに出ることと、復習を自分の納得できるレベルまでやる（僕の場合、水diffまでやるなど）
今後の目標ですが、高2になるまでに青色・JOI本選（なくならないでくれ）・PCK本選（やるかどうかわからないが）を達成したいです。
特にJOI本選、お前だけは何があっても達成してやるからな。
最後に、さんばかは、いいぞ。
ありがとうございました。
ABC162お疲れさまでした
ABC162お疲れ様でした
ジャッジが重かったですが僕は生きてます。それとジャッジ関連の仕様が変わっていて提出言語を間違えてCE出しましたが僕は元気です。（ペナにはならないため）
最近のコンテストめちゃくちゃ冷えていたので今回はどうなるかと思いましたが、初の4桁パフォを出し復活っぽくなりました やったね。
A問題
https://atcoder.jp/contests/abc162/tasks/abc162_a
色々やり方がありそうですが私は文字列でやりました。楽なので。
1:30 AC
B問題
https://atcoder.jp/contests/abc162/tasks/abc162_b
出ました！FizzBuzz！
といってもこれはFizzBuzzといえるかはよくわかりません（知らんけど）
N≤10^6なので全探索が間に合うのでそのままやりました。
具体的には、!(i%3 == 0 || i%5 == 0)だと数字を足します。
3:46 AC
C問題
https://atcoder.jp/contests/abc162/tasks/abc162_c
Σ って何ですか？？？？？？？？？？？？？
と言いながらサンプルを見て全てを理解gcd(a,gcd(b,c));をやるとOK
gcdをライブラリに持っていたので速解き（本当に解いたのか？）成功。
8:12 AC
D問題
https://atcoder.jp/contests/abc162/tasks/abc162_d
これ難しい。よく通した。えらい！（えへへ）
とりあえず考えたことは以下の通り
i,j,kの全列挙じゃんはい余裕～～～～
↓三重ループだとTLEなのはそれはそう。
i,jを二重ループで決めたらkもなんとなく求まりそうだな
↓
i,jを決めた状態でkを決めるのは結局三重ループなのでどうにかしてkを求めずに通り数を求めたい
↓
ぼく「累積和か！天才じゃん～～～」←これは罠で、解けるけどもっといい方法がある
↓
実装します。長いです。めんどくさいです。順位表を見ます。10000人突破！おめでとうAtCoder！それより（それよりじゃないが）Dの正解者は1700人くらい。
ぼく「今回もしかしてイケてる？？？？？やっと？？？？？精進の成果（これは偽で、あまり精進していない）が？？？？？報われる時が？？？？？来たわね？？？？？？」
↓
実装終わり
サンプル1の答えが合う！！！
ぼく「勝った！！！！！！」
脳内
↓
. -= ∧＿∧
-=と(`･ω･´)
-=/ と_ノ
-=_/／⌒ｿ ｼｭ
∧＿∧ =-
(`･ω･´)`つ=-
`つ \ =- ｼｭ
\,⌒＼\,,,_=-
サンプル2のACを確認！Submitヨシ！👈😸
心臓が飛びそうなくらいドキドキしていましたが勝ちを確信していました。
ジャッジ「WA」
？
？？？？
？？？？？？？？？
ぼく「嘘つけぇ！（迫真）」
割とすぐ気づけたので良かったですが、通り数合計だしN≤4000だしintで収まるわけがないんですね。
long long で提出
↓
「AC」
俺の勝ち！
45:20 AC 1ペナなので実際は+5min
もう僕を止められるものは何もありません。この調子でEも解いちゃうcar～🚙
とか言いながら考察します。わかりません。まあ？Fもあるし？Fも考察します。なんとなく方針が立ったので実装します。終了5分前で実装が終わります。
サンプルなんてどうせヨシ！
VSCodeくん「terminate called after throwing an instance of 'std::out_of_range'」
ぼく「どうしてヨシ！って言ったんですか？」
そのままバグが取れずにコンテスト終了。あぁ、今回も(E,Fは)ダメだったよ。
2505/10599 finish! Perf:1103
初の4桁パフォがでました！やったね！
パナソニックコンテスト感想
パナソニックプログラミングコンテストお疲れさまでした
【反省点】
・Bで1WA時点でコーナーケースわかったのに無駄におかわりWAしてしまった
・Cで式変形をやり遂げなくて闇を彷徨っていたこと
・Cで精度が足りないんだろうなぁとはわかりつつも同じようなコードを何回も提出していつのまにか4WA食らったこと
【感想】
注意力コンテストでした（Cまでしか解けてないけど）
【問題ごとに見ていく】
・A問題 K-th Term
https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_a
はい。コピペすると楽
・B問題 Bishop
https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_b
縦のHが奇数か偶数かで場合分けして、終わり！
↓
4 / 9 …WA
↓
ぼく「は？おい」 どうしてだ……！ あんなに慎重に確認したじゃないか……！！！
その時、僕の脳裏に電撃が走る！！！！
H == 1
せや！横一列の時は移動できへんからcout << 1 << endl;すればええんや！天才か？？？？？？？？？
↓
5 / 9…WA
↓
あほぼく「なんで？」（それはそう。W == 1に気づいていないのである！）
はい。2WAしました
・C問題 Sqrt Inequality
https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_c
ウゥワ問題文短ッ！！！！！！！！！！！！！！！！！！！！！！！！！
まずは√の計算は精度が怖いので式変形を試みる。
↓
2√ab < c − a − bで「うーん、無理！ｗ」と思い、断念（ア）
15桁のdoubleでsqrt()すればなんとか通るんじゃね？？？
↓
通りません（それは、そう）（C問題じゃないじゃん）
↓
精度をもっとよくする方法……（Google検索しながら悩む）
↓
オ？long double？そんなものが……やってみる→AC！！！
すでにCだけで4WAしてたぼく「ﾎ~~~~~~~~~~~~ﾝwwwwwwwwwww」
・Dは知らんのD
でもなんか解説見るとDFSで列挙してるっぽいので問題文の意味を理解すればいけそう……？
3完 4ペナ 101:27（ア） 2955 / 6553 かなしいね😢
TLに精進えぐい方がいらっしゃるので負けないように頑張りたいところ
日立コンAB感想とか
日立コンお疲れさまでした
【反省点】
・Aで3WAしたこと
・Aで3WAしたこと
・Aで誤読したこと
・Aで3WAしたこと
【感想】
…
……
……えっと……なにしてるんですか？？？？？？？？
おそらく速く解かなきゃという焦りがこんな悲劇（笑）を生んだのでしょうじゃねえよ1WA目で誤読に気づかなかったお前(自分)を決して許しはしない。
Aで事故ってなかったら15分2完とかだったので本当に悔しい。。。。
【問題解説的な】
まずはA問題。
https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_a
これは問題文を読む問題です。（自戒）
AtCoderReadingContestです。(知らんけど)
hitachi文字列というのは'hi'が一個以上繋がってできる文字列のことです。
一個でも含まれていたらでは、ありません。（ナ、ナンダッテー）
また、'hi'が繋がってないといけないので、Sの長さが奇数の時は問答無用でNoです。
- if (S.at(i) != 'h' || S.at(i + 1) != 'i') {
- cout << "No" << endl;
- return 0;
- }
"No"の処理はこのようにしました。return 0;とすることで、そこでプログラムの実行を終わらせることができるのが便利でいいですね。
8:56でAC,3WA。本当になにやってるの……😅
次にB問題。
https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_b
B問題にしては少し難しめに感じました。
[Step1:入力を頑張る]
[Step2:サンプルから、割引を使わなくてもいいことが分かるので、そこをどうするか考える]
Step2において、自分は、ansを答え出力用として、前半で割引を使うときを調べて、毎回minを取る→O(M)なのでO.K.
後半で割引を使わないときを調べる→AとBをそれぞれsortして昇順に並べることでA.at(0)+B.at(0)で割引なしの値段の最小値がわかる（割とすぐにこの解法に気づけたのはよかった）
前半と後半のでminを取る！→出来上がり
入力で配列は0からなのに順番は1≦i≦Aで与えられるの本当戸惑う。
16:07でAC,0WA。ナカナカヤルジャナイ
AB合わせて31:07-2完 2782/4349フィニッシュ。おい誤読ぶちころがしますわよ？
ｱｧ…どうかいかないで……(パフォーマンス)
C問題は知らんのC。はい。
お疲れさまでした！
次回：3/14のパナソニックコン2020頑張るぞ～
