JOIOJI
やばすぎる
解法(部分点)
とりあえずでやりたい…
vint J,O,Iに累積和をとっていきます。
といった感じですね
区間(t,s]のJの数はで求められるので
の箇所を求めてあげればよさそうです。
tとsを決めてあげてでできました
解放(天才)
の時に(t,s]のOとJの数が同じ…ふむ
こうじゃな(天才)これで独立に考えることができるようになった
vint JO,JIを定義します
という定義にします
この時、の時、長さがJOIが同じ数含まれている。
s,tを決め打ちするとになるので、天才になります
map<pint,vint>を定義してkeyはです。
mp[hoge].push_back(i)
をすべてのiについて行います。
同じKeyということはなのですべてのkeyのvalueをsortしてv[v.size()]-v[0]を行えば答えが出ます(すごい)。
累積和、最初に0をつけないとバグります(それはそう)
ABC176に出た
悲しき事
なんと3完でした。。。4分で、残りは全部椅子を温めていました…
記録
- Aを見る(簡単やな)
- Aを解く(upper_division(N,X)*T);
- Bを見る(簡単やな)
- 文字列に落として-'0'の和がいけるかどうか、多倍長持っておけばよかった…
- Cを見る(簡単やな)
- 今までのMax高さにそろえる、オーバーフローは、します
- Dを見る(まったくわからん)
- Eを見る(ボンバーマンじゃん)
- まあ各列、各行にある爆弾の最大値を足してそこの座標に爆弾があったら-1する、ってすれば行けそう。
- そこの座標に爆弾があったら、のあれムズイね…
- 10^6なのでy*10^7+xを配列に突っ込んでsortして二分探索すればあるかどうかが高速かつメモリを圧迫せずに行けそう。
- 各行、各列の最大値が多すぎる場合、要は斜めにブワァァァってこられるとTLEしそうなのでmaxが1ずつだったらifで分けとこ、最大値は1やな、←これがよくない
- 4WA!?!?ナンデ!?ナンデ!?
後記録
n=1の時は最大値1だけどそれ以外の斜めとかの時は最大値は2でした。。。
あとD愚直に01BFSすれば通るんですね…制約をちゃんと見よう
ベクトルと行列の積
これ
onlinejudge.u-aizu.ac.jp問題
の長さmの1次元配列と
みたいなn*mの2次元配列が渡される。
これの積Cを作ってね、という問題である。
解くわよ~~~
Σの意味わからん記法は読めないからとりあえず飛ばしていこう。とりあえずサンプルを見てみるか…
と
の積が
と…
解説
まあサンプルで考えます(楽なので)を横に倒して
にするわよ(配列が横のイメージがあるので横にしました)
B
A答えって並べてみると…
何か気づくことはないでしょうか?
各要素の掛け算の和になってるように、感じませんか?
例えばサンプルのAの1行目だけ取り出してみて、考えてみましょう。
あれ?A*Bじゃね?みたいな?わかりやすいようにA*Bを追加してみます
はい、他のも同様ですね、この問題の解き方は、Aの各列(縦)の要素とBの要素を掛け合わせたやつsの和です。
緑になったよ
やはり
色変記事は書くべきかな~っと…
色が変わりました!
うっしっし 緑になりました!
緑になるまでにやったこと
・Cが解けなさそうだからと思ってDに行く
・配列の添え字をよくチェックせずに変数のところに定数を入れる。(2WAだから違うと思ってた…)
緑になるまでにやらなかったこと
C
これから
芸人にならないように早く水色になります…
水色になった
色編記事を書いてなかったので書きます.
水色になりました(ヤッター)
参加回数が74回と水色の中ではかなり多いほうですが、こんなカスでも無限にやれば水になるという証明になりましたね。(???)
水色になるまでにやったこと
いろいろ(ゲームとか)
マイクラを始めたのは大きかったと思います。
あと早解き、これが多分1番大きいです。自慢ですがFAを1度とってます。
水色になるまでにしなかったこと
全部、正直もっといろんな知識を早くつけておくべきだったと思います。
水色になるまでに知っていたアルゴリズムとかデータ構造とか
書き出すと、「あれ?何も知らないな…」となってしまう…
水色になっても知らないこと
くそお世話になったもの
E%dさんの水コーダーになるまでの良問100を70くらい説いたときに水になりました。くそ力尽くのでお勧めです
AOJ/AtCoder-JOIでJOI埋めを行う。
AtCoder Virtual ContestならびにAtCoder Problemsのバーチャルコンテスト、自分のレートdiffで説いてないやつを詰めるといい練習になります。
終わり
次は青になります。
PCK2015のバチャをやった
前書き
多分本選行きました(いいえ)
記録
・1をやる、tRue君に6~を見てもらう
・1を解く、やるだけ
・2を解く、やるだけ
・3を解く、intの範囲で頑張る。
・5を先に解く、どの問題をどれだけ説いたかをやって後ろから累積和。
・4を解く、やるだけ
・9を解いてもらう。7を考える
・7解けなかったぞ~やってもらう間に8を考える。
・8これ簡単じゃね?(いいえ)全共通の範囲を求めればおk?
・8全然むずかった。範囲の中が2次関数的になってるので三分探索。
・6わからん、解いてもらう
・6といてもらう
合計578分、4ペナルティで9完
ボーダーわからず
MAO#忘備録1
MAO
Markov Algorithm Onlineの略です
Twitterとかでよく見かけるマルコフアルゴリズムってやつですね(多分)
mao.snuke.org
↑ここです。
Markov Algorithmとは
ここで使えるルールの種類は2つです(楽だね!)
X:Y…Xを見つけたらYに変える X::Y…Xを見つけたらYに変えてプログラムを終了するまた、複数のルールを作った場合、上のほうから優先されて実行されていきます。
rule1 rule2 rule3という風にしたとき、
while(true){ if(rule1){変換} else if(rule2){変換} else if(rule3){変換} else{break;} }といった感じになっていきます
問題を解いていく
0001
Hello,をWorld!に変換します
Hello,:World!
です。どっちのルールを使っても大丈夫です。
0002
sを文字列から消します。
どちらのルールもX,Yに空文字列を指定しても大丈夫です。
s:
これでOKです。sがなくなるまで繰り返します。
0003
先頭にsを付けます。
Xに空文字列を指定すると、先頭にYを追加します。
今回は、1度だけ実行をしたいのでルール2を使用します。
::s
0004
じゃんけんです。変えるのは一度だけ
R::P S::R P::S
0005
iの間にwを入れる。
i:iw
とすると、iwiwiwiwiwのように最後に一つできてしまい、さらにまだiがあるので、無限に繰り返してしまいます。(実際にはiwwwwww…となる)
結論から言うと
ii:iwi
です。
MAOはかなりの閃きげーなので難しいですね…