keidaroo’s diary

底辺系競プロer

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

です。
がんばります!

ABC-4 D マーブルポイント

解法

DPですね、枝狩り全探索でもできますが、コードを書くのが面倒です。(枝狩りは10^6ぐらいではいけそう)

ポイント1

この状況、ありえなくね?って思ってもとりあえずDPにぶちこむ!!

→もし状況自体がありえなくても、それが最適解になる可能性もありえないのであればDPにぶちこめる!!
 

ポイント2

簡単なDPから考える!!

ミドリムシ君の練習を見ているとこれをしていて、難しいDPから簡単なDPに落とし込めるなあ、と

ポイント3

順序だっているものは省略できる!!

今回の場合は色で順序付けできます、それをつかって合計数で省略をしましょう

サプリメント解説(ABC17-D)

DPの尺取りをやったことがなかったため、難しく感じました。forDPじゃないと解けないDP多すぎませんか。
あと高橋君、サプリメント10^5個飲むのは飲みすぎ。

解説

部分点解法

部分点解法は明らかにDPです。ここでは満点解法につなげるためにもらうDPを書きます
dp[i]=a(i=何個目の薬か、a=i個目の薬を選ぶとき、その前の薬から考えて何通りの選び方があるか)

dp[i]=(dp[i-1]+~dp[i-k])(i-kは同じ味の薬がでない最大の範囲)

こんな感じでもらうDPが書けます。
しかし、遷移の計算量含めるとO(N^2)となり、間に合いません。

満点解法

f:id:keidaroo:20171215234541j:plain
この画像の通り、同じ区間を何度も計算するのは無駄となります。
このようなときに使えるアルゴリズムには「尺取り法」と「累積和(いもす法)」というのがあります。
尺取り法→

www.slideshare.net

累積和→
累積和手法 - sataniC++

今回は尺取法を使います。

尺取法はその時その時で前にある値を削り、新たに新しい値を追加することで成り立ちます。
iを更新していくごとに、そのiの前でどれだけの範囲をかぶることなく選べるかというのを考えると、尺取法のような形になるのがわかります。
なので、
for(n個目までの薬){
while(かぶっている間は){
i個目の時に適応できない薬は合計から減らす
}
配列にi個目の時の選び方の通りを保存
i+1個目の合計にはi個目の合計が含まれるので、合計を二倍する
}
というようになります。

Fractionの別解について

別解とか言ってますが、この解法の人も結構いて安心しました。

joisc2008.contest.atcoder.jp
この問題、想定解だとファレイ数列というのですが、僕はその解法ではなかったので雑に解説します。

注目するべき点

k<=200000

これで、0からkまでループさせればいいということがわかりますね。
ここからは発想です、そのまま解を載せます

1/nから1/2までsetにいれる

i/a<(i+1)/aは自明なので、i/aが消去されれば(i+1)/aをsetにいれる

これだけでなんとかなります。
あとは、i+1とaの最大公約数が1出ないといけない、とかありますが、そこら辺は実装して気づくと思います。
時間に非常に焦っていたので、残念ながら雑になりました。申し訳ないです。

25個の整数の反省文。

自力で解けなかったので反省しています。この問題で使ったテクについてメモします。
間違っていたら教えてね!
あとこれは解説じゃないです。

大小関係が定まっているかつDPの問題は小さい方から見てけ!

これはもちろん思いつきました。ただ使えませんでした。

使ったテク2

bitDPは制約から判断しろ

これももちろん出来ました。ただこれも使えませんでした。
xi,j≠0 を満たす整数組 (i,j)(1≦i≦5,1≦j≦5) は 5 個以上存在する。
これで一発でbitDPとわかるだろ、20といえばbitDP

使ったテク3

bitにおいて、forループで計算されたあとたされることはない

これは初めて気づきました。
これはどういうことかというと、
dp[101(2)]+=dp[100(2)]で、101はもうすでに計算されて二度とforループが回ってこない、ということはないということです。
それはそうだけれども、まあいいでしょ、僕は驚いたので。

使ったテク4

座標をbitDPで保存する

うん、これは驚いた。
テク1を使うことによって、何が省略されるか、を考えるべき。

使ったテク5

適さないものを除外

適したものを足すより適さないものを足すほうが簡単にかけることがあります。

ぼくがやるべきこと

綺麗にノートにまとめる

整理しないとだめだってn回言ってる

2009年春合宿 ビンゴ

この問題、非常に難しく感じた上に、解説の需要がありそうなので書きます。
日本語が下手なので、twitterで質問してください。

問題

JOI 2008-2009 予選 問題6

問題概要は省略させていただきます(わからない人はその前に考えましょう)

解説

ポイント1

ビンゴの表は一列の数列に表せる!

これはほとんどの人が分かったと思います。左の列より右の列のほうが大きいかつ同じ列で昇順になっているので、それはそうですね。

ポイント2

これはDP!w

これもまた暫く考えていると予想はついてくるのではないでしょうか。ついてきますね。

ポイント3

とりあえずDPの構想を練ってみる!

この解説の続きを見る前に自分でDPを組み立ててみましょう。これ無理じゃん!wって気づいたらこの解説を見てください(もうDPの構想を練った人は続きを読もう)

DPの構想(仮)

必要な情報を考えてみます。
場所(何個目の整数か)//max50
今まで使った中で最大の値(要するに一個前の値)//max2000
今までの合計//3000
残念ながら、これだと50*2000*3000=3*10^8個の配列(メモリ)が必要になります。もちろん通りません。
ここでforDPでしかできない裏ワザ的な何かを使います。

使うと思った値を、使わずに済ませる→ループの順番を工夫して、その値を使わなくても自明な状態にする

ここで使わずに済ませる、自明にできる値は、予想がつくとは思いますが、今まで使った中での最大の値です。
最大の値が果たす役目は2つあります。
1.一個後の値を超えなければいけない。
2.制約で決められた値を超してはならない←これがなければ再帰でできます。
この役目2つを果たすためには、使う値を1からmまで順番に組み立てればいいです。そうすれば、3を組み立てたあとにそれより小さい1が来ること(これは例です)はなくなります。

最初のfor文で1からmまでループさせよう!

これで解決です。こうすれば、最大の値を考慮する必要があります。

もうこの先は、普通のDPです。頑張ってください!

No need

ブログもNo needでしょうが自分のために書いているので許して><

問題
D: No Need - AtCoder Beginner Contest 056 | AtCoder

解答
Submission #1631478 - AtCoder Beginner Contest 056 | AtCoder

この問題、難しかった。
嘘解法ばかり思いついて、自分には少し早すぎたのではないか、と思っています。(自分の忍耐力で何とかAC出来て嬉しい)

解説

まず、kより小さい状態からkより大きくなる、という遷移が起こっている状態を考えます。(ギリギリ集合、と呼ばせていただきます)
この時、制約とかを見るとわかる通り、何を使ったか、という情報は記憶することが不可能なことが分かります。
なので、それを使わない方法を探しました。
→既に使った数も、まだ使っていない数も同じようになる共通の性質を探しました。
ここでギリギリ集合を入れ替えることを考えます。
ギリギリ集合を入れ替えるとき、ギリギリ集合の中のどのような数を抜いてもkより小さくなることが前提となります。
このためには、大きいものから順に選んでいけば、ギリギリ集合を作ることが可能となります。
ギリギリ集合の最も小さい数をメモり、それより大きい数は入れ替えることができるため、必要な数となります。このとき、ギリギリ集合の中にもともと含まれていた数は最小値以上の物だけなので、これが共通点となり、成り立ちます。

まとめると

DPでギリギリ集合を作る(逆順ソートして)
ギリギリ集合の最小値をメモり、更新していく。
それより小さいものは、必要ない数字なので、countしておく。

分かりにくくてすみません(自分のことしか考えていない人の例