PERVERSE ワンページプレゼン
adventar.org
21日目です！！22日になったので書き始めます（すみません）
私はPERVERSEというパズルゲームをリリースに向けて開発しています！
このアドベントカレンダーでは、このゲームをなるべくシンプルにどんなものか伝えます！（自分の頭の整理のためなのですが）
ワンページプレゼン
ある日、ペンタくん（仮）は植物に水をあげていました。
すると芽から出てきたのは花でもなく、タワー！
タワーが上に伸びると同時に、大事な仲間も連れて行かれました！
ぺんたくんはパズルを解き、ふうせんをつかって上にのぼることで仲間を助けに行きます！！！
パズル本体は中央の2つのキューブを動かし、円のゴールに持っていくゲームです！
ただ、灰色のキューブは色付きのキューブの反対方向に動くという性質があります。
例えばここでオレンジのキューブを上に動かすと、
このように動きます。
ゲームの説明は以上です！なんとなくわかってもらえるとありがたい！！
細かい仕様とか考えていること
ここから先はこれまでPERVERSEを遊んでいただいた方向けになってしまうのですが、細かい仕様変更などについてまとめます
1. マップの難易度は下げます
2. クリア後の追加時間はクリアしていくにつれ、短くします
3. 手数を表示します
4. メインプレーヤーのアニメーションとかも選べるようにしたいです。モーション教えてください。
5. 対戦モードはなくなります。ランキングは引き続きつけます
6. ZENモード（時間制限などがないモード）をつけます。
7. 課金をどこかでつけます（広告はあんまりいれたくない！けれどどうしよう！）
というわけで、完全な自分語りになってしまいましたが、どうぞご期待ください！（ハードルを上げることによって自分を追い込むテク）
ABC107 Median of Median
感想
精進不足だなあと（解説読んでも3時間はバグなおしにかかった）
解説
転倒数を求め始めるところまでは公式解説を参照
https://img.atcoder.jp/arc101/editorial.pdf
僕は二分探索で
決めた数より小さい値が半分以下のものをlowerにするというのを繰り返しました。
その結果
https://beta.atcoder.jp/contests/abc107/submissions/3104934
見事にWAしました
原因
単純に頭がわるい、っていうのはおいておいて、
累積和の気持ちに！！！なれなかった！！！
転倒数を数えて足すだけだと実は足りなくて、この場合累積和は[0]の和から始まっていて、imos[0]!=0であるため、l=始めの時をかんがえていませんでした
（どういうことかというと、70行目に+(imos[i]<0)を加えてあげるべきということです）
もうひとつ間違っていて、v[i]
なのでl==rのときは累積和上ではimos[r]-imos[r-1]になるんですね！！たさなくていい！！！
頭の悪さは仕方ないので、事前にメモした後に解くこと、累積和の気持ちになることを意識してがんばります！！！
SRM608 div1 easy MysticAndCandies
概要
n個の箱にキャンディが合計でC個入っている
また、各箱にはlow[i]~high[i]個キャンディが入っている
今X個最低でとりたい。必ずX個以上取れるような箱の選び方の最小値（箱を何個選ぶか）はなんでしょう？？！
解法
まずこれは貪欲だが、一つの貪欲ではなくて２つの貪欲が存在する
1. 選んだ箱のlowの総数がX以上
2. max(0,C - （すべての箱のhighのSum - 選んだ箱のi個目までのhighのSum))>=X
のうちどちらかである。
両方同時に成り立つことはあり得なくて、なぜかというと
1と2以外のときは自分の選んでいない箱が中途半端にキャンディが入っているときであって、それはむしろ自分にとって甘えなので「すべての場合において成り立つ」とはとうてい言えないからだ。
余談ですが
これDPでもできませんか？
DP[何個選択しないか][何個目についてみているか]
というようにし、再帰DPの外に選択していないやつのmaxの総和、選択した奴のminの総和ってやればできそうかな、とは思いましたが萎えたので残念ながら実装していません。すみません。
コード
#include <bits/stdc++.h> #define REP(i, n) for (signed long long i = 0; i < (n); i++) using namespace std; class MysticAndCandies { public: int minBoxes(int C, int X, vector<int> low, vector<int> high) { int highsum = accumulate(high.begin(), high.end(), 0); int himos = 0, limos = 0; sort(high.begin(), high.end(), greater<int>()); sort(low.begin(), low.end(), greater<int>()); REP(i, low.size()) { himos += high[i], limos += low[i]; if (limos >= X || C - highsum + himos >= X) return i + 1; } } };
SRM 605 div1 easy AlienAndHamburgers
ひえ〜〜めっちゃ失敗した
概要
とある宇宙人は地球を滅ぼす前にハンバーガーを食べたいと思った。
N 個のハンバーガーがある。各ハンバーガーは二つの属性 type と taste をもち、それぞれ整数値で表される。
これらのハンバーガーのうち、いくつかを選んで食べる。（食べた種類の数 × taste の合計）が最大となるように食べたときの、この値を求めよ。
失敗談
DPをしようとおもった
DP案1
dp[何個目についてみるか][何種類とったか] = 合計のtaste
今思うと自分頭悪すぎ..
これだと最終的に何種類とったかわからない、そうすると2種類とって100っていうのと、3種類とって99だと2*100<3*99なのに100>99なので2種類しか取っていない100が採用される。
「何種類とったか」が関係するのではなくて、「最終的に何種類とったか」が関係する、、ので、、
DP案2
「何種類とったか」が関係するのではなくて、「最終的に何種類とったか」が関係する、、ので、、
- > せやな、dp[何個目についてみるか][何種類とったか] = 合計のtaste * 合計のtypesにしたろ
今思うと自分頭わるすぎ,,,(n回目）
なぜかというと[何個目についてみているか]以降のtasteの最大値じゃあ、何種類とったほうがいいかというのは判断できない
例)
i個目までに
1000のtaste
i個目以降では
2種類とって-100
3種類とって-200
の時に-100*2>-200*3だが、i個目までの合計を考えると
990*2<980*3
になる、、
教訓: i個目以前の結果が関連づいてくるDPは書いてはいけない（書くとしたら必ずdpの添字に追加する必要がある）
最終的に
i種類とるとき、tasteが最大値を取るときに最大になる！ｗと気づき、4時間かけてようやくソートして貪欲した、、頭悪い、、
見るとSugarDragon5君などが余裕でACしていて人生つらい気持ちになった
sugardragon5.hatenadiary.com
#include <bits/stdc++.h> #define pb push_back #define REP(i, n) for (signed long long i = 0; i < (n); i++) #define MOD 998244353 #define INF 93193111451418101 #define bitcnt(a) (ll) __builtin_popcount((a)) #define lb(a, b) lower_bound((a).begin(), (a).end(), (b)) #define ub(a, b) upper_bound((a).begin(), (a).end(), (b)) using namespace std; typedef long long ll; typedef pair<ll, ll> P; bool positive[101]; ll maxTaste[103], tasteSum[103]; P dp[51][51]; set<ll> vis; vector<ll> num; class AlienAndHamburgers { public: int getNumber(vector<int> type, vector<int> taste) { REP(i, 101) { maxTaste[i] = -INF; } REP(i, (signed)type.size()) { vis.insert(type[i]); if (taste[i] > 0) { positive[type[i]] = true; tasteSum[type[i]] += taste[i]; } maxTaste[type[i]] = max(maxTaste[type[i]], (ll)taste[i]); } for (auto &a : vis) { if (positive[a]) { num.pb(tasteSum[a]); } else { num.pb(maxTaste[a]); } } sort(num.begin(), num.end(), greater<ll>()); ll ret = 0, im = 0; REP(i, (signed)num.size()) { im += num[i]; ret = max(ret, im * (i + 1)); } return ret; } };
srm 604 div1 easy
解説ACしたのでメモ
a^nはa進数として考える、そうしたらあとは自明に下の桁からシミュレーションしていけばとける。
この太字にしたところの考え方は大きな知見！！
#include <bits/stdc++.h> #define pb push_back #define REP(i, n) for (signed long long i = 0; i < (n); i++) #define MOD 998244353 #define INF 93193111451418101 #define bitcnt(a) (ll) __builtin_popcount((a)) #define lb(a, b) lower_bound((a).begin(), (a).end(), (b)) #define ub(a, b) upper_bound((a).begin(), (a).end(), (b)) using namespace std; typedef long long ll; typedef pair<ll, ll> P; class PowerOfThree { public: string ableToGet(int x, int y) { x = abs(x); y = abs(y); while (x + y != 0) { if ((x % 3 == 0 && y % 3 == 0) || (x % 3 && y % 3)) { return "Impossible"; } int *calc = &y; if (x % 3) calc = &x; if (*calc % 3 == 1) (*calc)--; else (*calc)++; x /= 3, y /= 3; } return "Possible"; } }; int main() { ll x = 10; ll *a = &x; cout << *a << endl; a++; cout << *a << endl; cout << *a << endl; }
SRM601 div1 easy WinterAndPresentのメモ
解法
Xを予め決めておく
その後に要素の数だけループさせて、りんごについてだけ見た時に最小で何個、最大で何個とれるか調べる
最小をminとして、最大をmaxとおくと、
minとmaxの間の数個とれない、ということが起き得ないことは自明（そのためのmin,max)
Xをどんどん増やしていき、そのたびにans+=max-min+1をすればいい
メモ
Xを決め打ちしたときに、りんごだけについて見ればもう一方は自動的に決まると気づいてほしい
解説ACしてしまった
条件的にわからない！ってなったら愚直解をさがす
Atcoderで青になるまでにやったこと
keidaroo - AtCoderです、こんにちは。
私事ですが、この前青コーダーになることができました。
やったね！！
というわけで、「青コーダーになるまでにやったこと」という感じのブログを書いて！！と約0名ほどから要望を頂いたのでそれに応える形で書きました！！
灰色から茶色へ
やるべきこと
- AtcoderのA問題、B問題を新しいものから解いていく(AtCoder Problemsがおすすめ！)
- わからなかったら「提出一覧→すべての提出」から他の人がACしたコードを見て、理解して、自分で書く！！
- 入力の方法を覚える！！
- AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiitaを読む！
これで多少のプログラミングスキルに入力方法がわかれば茶色にはなれます。
コンテストには出ようね！！(あと早解きをしよう！！）
あとおすすめはAGCです。そこまで早解きできなくてもA問題を解くだけで結構パフォもらえます。
ひらめき系コンテストなのでABCに比べてプログラミングスキルを問われないです！！
プログラミング完璧に理解してるけれど茶色になれない。。って人へ
キツい言い方をしますが、そういう人は自分がプログラミングを完璧に理解できていないということを自覚したほうがいいと思います（競技プログラミングにプログラミング完璧に理解することは求められていないとかいうつっこみきそう、まさにその通りです。）
茶色から緑色へ
AB問題早解きに、C問題たまにとける！
ってなると緑になれます。
緑色から水色へ
僕はこのパートで精進方法をミスった感じがします。
僕個人の考えですが、水色になるには発想の良さ、よりもプログラミングコンテストへの慣れが必要だと思います。要はC問題を早解きできるようになればいいと思います。
（C問題早解きでD問題はたまにとけるようにはなります）
やるべきこと
- C問題を解きまくる（30分考えてわからなかったら解答みて、コードは自分で考えてかいて）
- コンテストにでて、なれる
C問題を爆ときしてから1ヶ月ほどたったあたりから成長をはじめました。精進をしてから結果が反映される時間、人によりけりだと思います（すぐに反映する人はすごいと思う）
水色から青へ
特に1500になってから苦労した記憶があります。。
後悔してるところを公開（はい爆笑）します！！
やるべきこと
- ABC-Dをうめる
- ABC-Dを早解きできるように為る
これだけで1500行くと思います、ここからです
やるべきこと
- NoSubをしない
- 常に「できる」という気持ちをもつ！！
NoSubをしないについて
NoSubをすると、
もう駄目だ！ｗあきらめ！ｗTLのみなさんプロすぎ！ｗ
で終わってしまう危険性がかなり高いです。僕もそうで、モチベ続かないです。
なので、Nosubを絶対にしない、それかコンテストに出ない、のどちらかを選ぶ気持ちで行きましょう。
最後に
青になった瞬間水色に落ちました！ありがとうございました！
