keidaroo’s diary

底辺系競プロer

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個以上取れるような箱の選び方の最小値(箱を何個選ぶか)はなんでしょう??!

解法

まずこれは貪欲だが、一つの貪欲ではなくて2つの貪欲が存在する

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が最大値を取るときに最大になる!wと気づき、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です、こんにちは。

私事ですが、この前Twitter上の皆様、そして✝資産✝の源である家族(これはジョークです、青に上がれたときに一緒に喜んでくれて嬉しかったです。)のお陰で青コーダーになることができました。
やったね!!

というわけで、「青コーダーになるまでにやったこと」という感じのブログを書いて!!と約0名ほどから要望を頂いたのでそれに応える形で書きました!!

灰色から茶色へ

「初めてのプログラミングとして競技プログラミングをやった」というタイプの人はここでつまずくと思います。
僕もその一人です。
そのようなタイプの人がやるべきことは以下のとおりです。

やるべきこと

これで多少のプログラミングスキルに入力方法がわかれば茶色にはなれます。
コンテストには出ようね!!(あと早解きをしよう!!)

あとおすすめはAGCです。そこまで早解きできなくてもA問題を解くだけで結構パフォもらえます。
ひらめき系コンテストなのでABCに比べてプログラミングスキルを問われないです!!

プログラミング完璧に理解してるけれど茶色になれない。。って人へ

キツい言い方をしますが、そういう人は自分がプログラミングを完璧に理解できていないということを自覚したほうがいいと思います(競技プログラミングにプログラミング完璧に理解することは求められていないとかいうつっこみきそう、まさにその通りです。)

茶色から緑色へ

AB問題早解きに、C問題たまにとける!

ってなると緑になれます。ミドリムシくん(2年後輩でそろそろ黄色いきそうな子)にはなれません。残念。

やるべきこと
  • Atcoder ABをガンガン解く。とにかく解く。解きまくる。解き終わったらCも解き始めてもいいかも
  • AGCで爆上げを狙う。
  • 早解きをしようと心がまえる。

AGCほんと大事。

このぐらいからプログラミングスキルだけでは対処できなくなると考えています。
一部の人たちは「業務プログラミングやってて青とか黄色とかになれない人はプログラマを名乗れない」とか言ってる人がいますが、それは単なるイキリかネタかだと捉えているのでまあ無視してください(業務プログラマでないので何も言えないやが)

緑色から水色へ

僕はこのパートで精進方法をミスった感じがします。
僕個人の考えですが、水色になるには発想の良さ、よりもプログラミングコンテストへの慣れが必要だと思います。要はC問題を早解きできるようになればいいと思います。
(C問題早解きでD問題はたまにとけるようにはなります)

やるべきこと
  • C問題を解きまくる(30分考えてわからなかったら解答みて、コードは自分で考えてかいて)
  • コンテストにでて、なれる

C問題を爆ときしてから1ヶ月ほどたったあたりから成長をはじめました。精進をしてから結果が反映される時間、人によりけりだと思います(すぐに反映する人はすごいと思う)

水色から青へ

特に1500になってから苦労した記憶があります。。
後悔してるところを公開(はい爆笑)します!!

やるべきこと
  • ABC-Dをうめる
  • ABC-Dを早解きできるように為る

これだけで1500行くと思います、ここからです

やるべきこと
  • NoSubをしない
  • 常に「できる」という気持ちをもつ!!
NoSubをしないについて

NoSubをすると、
もう駄目だ!wあきらめ!wTLのみなさんプロすぎ!w
で終わってしまう危険性がかなり高いです。僕もそうで、モチベ続かないです。

なので、Nosubを絶対にしない、それかコンテストに出ない、のどちらかを選ぶ気持ちで行きましょう。

常にできるという気持ちを持つ、について

例えばE問題でも、コンテスト後に解説を見ると、「これ自分でもできた。。」っていうのが結構あったりします。。
ただ、ここで「もうできない!w」ってなると結局伸びないので、できるという気持ちを持ちましょう!!

恥ずかしいですが僕はコンテスト前に「できるぞおお」とか独り言していたりします。恥ずかしいですね。内緒にしておいてください。

最後に

内容がないよう(爆笑)な記事になってしまい、申し訳ないのですがこの中からなんとか内容を作り出してくれる方がいれば有難いです!!
精進方法は人によりけりだとも思うので、いろいろ試して競プロlifeを一緒に楽しみましょう!

railsメモ

こんにちは
一ヶ月ほど前(かな?)からrailsをやり始めたので、テストも終わったことだしメモを書きます
f:id:keidaroo:20180218154448p:plain

とりあえず一ヶ月間触った感想

すごい便利だなあと思いました、作業を省けるところはrailsがやってくれるし、うれしかったですが、なるべく基礎から学びたかったのでscaffoldとかはつかいませんでした
あと楽しいです、フロントも組み立てる必要があるのですが(webアプリなので)それに比べたら圧倒的に楽しいです。

ファイル構造について

今まで使ったのは
/app

  • /assets
  • /controllers
  • /views

/config

  • /routes.rb

/db
です(インデントの付け方がわからず見難くて申し訳ないです)

assetsについて

ここには画像やJSやCSSをおきます。
CSSとかどこにおいてもいいじゃん」とか思っていましたが、本番環境では通用しないようです。(こわいね)
ちなみにこの辺のディレクトリは
/assets/stylesheetsとかでいけます。

controllerについて

ここで大体の処理を書きます。
今のところの印象ですが、だいたい関数に書くイメージがあります
できること(いままでやったこと)

  • 一般的な処理(ふつーのプログラミングをrubyで書ける)
  • 値の受け取り(今まで使ったのは、例えば/user/0とあったら0を読み込むとか、formから値を受け取るとか)
  • 移動(リンクの移動、htmlの描画)

ですね、大体ここが大事です。
要は、ここでRubyが書けるよ★ガンバルビィ(ここで例の黒澤ルビィの画像が入る)

formについて

formは割と躓くところが多かったのでメモします

formの関数的なもの
  • = form_for @user, :url => {:controller => 'user_show', :action => 'update'} do |f|

(controllerのほうで@user=User.newとしてuserを宣言していることが前提です)
これは、@userという変数にいれ、(@というのはグローバル変数だよってこと)、controllerはuser_showっていうもの、アクションは適当な名前(多分処理後の関数名のほうがいいのかな?)にし、for i in 0..5 |f|のような感じでfにいろいろ動作させるとうまくいくよ、的な感覚で行っています(雑ですみません(実は深くまでは理解していない)
これが終わると、postといって受け取った値を渡す作業に入ります。routes.rbでpost 'user_show/update'=>'user_show#update'のようにしましょう(中身の名前は変えてください)

views

ここでhtml書けます。
htmlも、Rubyの場合はhtml.erbとかいってscssのhtml版のruby(つまりhtmlだけどruby書ける)みたいなのがあります
railsで初めてhtmlというニセプログラミング言語に触れたのですが、なんか吐き気しかしません。
無駄なところ多いし、無駄な割には可読性ないし、最悪です。
twitterにいる方からのおすすめでhamlを使い始めて、今はそれで落ち着いてます()

routes.rb

ここでリンクと処理の組み立てができます。
例:/user/0ってやったら0がidのuserを表示的な
あと先ほどお伝えしたようにpostなど値の受け渡しができます

db

データベースの処理は大抵ここでかきます、passwordとかの暗号化もBCrypt先輩のお力によってできたのですが、

いつか暗号化も自分で実装したい!!w

です。
がんばります!