JOIOJI

やばすぎる

atcoder.jp

解法(部分点)

とりあえずO(N^{2})でやりたい…
vint J,O,Iに累積和をとっていきます。
J_i=J_{i-1}+S_i=='J'?1:0といった感じですね
区間(t,s]のJの数はJ_s-J_tで求められるので
J_s-J_t=O_s-O_t=I_s-I_t
の箇所を求めてあげればよさそうです。
tとsを決めてあげてO(N^{2})でできました

解放(天才)

J_s-J_t=O_s-O_tの時に(t,s]のOとJの数が同じ…ふむ
J_s-O_s=J_t-O_tこうじゃな(天才)これで独立に考えることができるようになった
vint JO,JIを定義します
JO_i=J_i-O_i,JI_i=J_i-I_iという定義にします
この時、JO_s=JO_t,JI_s=JI_tの時、長さmax(s,t)-min(s,t)がJOIが同じ数含まれている。
s,tを決め打ちするとO(N^{2})になるので、天才になります
map<pint,vint>を定義してkeyは(JO_i,JI_i)です。

mp[hoge].push_back(i)

をすべてのiについて行います。
同じKeyということはJO_s=JO_t,JI_s=JI_tなのですべてのkeyのvalueをsortしてv[v.size()]-v[0]を行えば答えが出ます(すごい)。
累積和、最初に0をつけないとバグります(それはそう)

ABC176に出た

AtCoder

悲しき事

なんと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すれば通るんですね…制約をちゃんと見よう

ベクトルと行列の積

AOJ

これ

onlinejudge.u-aizu.ac.jp

問題



B=\begin{pmatrix}
b_1\\
b_2\\
b_3\\
b_4\\
\vdots\\
b_m
\end{pmatrix}
の長さmの1次元配列と


A=\begin{pmatrix}
A_{11} & A_{12} & \cdots &A_{1m}\\
A_{21} & A_{22} & \cdots &A_{2m}\\
A_{31} & A_{32} & \cdots &A_{3m}\\
\vdots & \vdots & \vdots  & \vdots\\
A_{n1} & A_{n2} & \cdots &A_{nm}\\
\end{pmatrix}
みたいなn*mの2次元配列が渡される。

これの積Cを作ってね、という問題である。

解くわよ～～～

Σの意味わからん記法は読めないからとりあえず飛ばしていこう。

とりあえずサンプルを見てみるか…



B=\begin{pmatrix}
1\\
2\\
3\\
0\\
\end{pmatrix}
と


A=\begin{pmatrix}
1 & 2 & 0 & 1 \\
0 & 3 & 0 & 1\\
4 & 1 & 1 & 0\\
\end{pmatrix}
の積が


C=\begin{pmatrix}
5\\
6\\
9\\
\end{pmatrix}
と…

解説

まあサンプルで考えます(楽なので)



B=\begin{pmatrix}
1\\
2\\
3\\
0\\
\end{pmatrix}
を横に倒して


B=\begin{pmatrix}
1&2&3&0
\end{pmatrix}
にするわよ(配列が横のイメージがあるので横にしました)

B

A答えって並べてみると…



\begin{pmatrix}
1&2&3&0
\end{pmatrix}\\
\begin{pmatrix}
1 & 2 & 0 & 1 \\
0 & 3 & 0 & 1\\
4 & 1 & 1 & 0\\
\end{pmatrix}
\begin{pmatrix}
5\\
6\\
9\\
\end{pmatrix}
何か気づくことはないでしょうか？

各要素の掛け算の和になってるように、感じませんか?

例えばサンプルのAの1行目だけ取り出してみて、考えてみましょう。




\begin{pmatrix}
1&2&3&0
\end{pmatrix}\\
\begin{pmatrix}
1 & 2 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
5\\
\end{pmatrix}
あれ?A*Bじゃね?みたいな?わかりやすいようにA*Bを追加してみます



\begin{pmatrix}
1&2&3&0
\end{pmatrix}\\
\begin{pmatrix}
1 & 2 & 0 & 1
\end{pmatrix}\\
\begin{pmatrix}
1 & 4 & 0 & 0
\end{pmatrix}
\begin{pmatrix}
5\\
\end{pmatrix}
はい、他のも同様ですね、この問題の解き方は、Aの各列(縦)の要素とBの要素を掛け合わせたやつsの和です。

緑になったよ

やはり

色変記事は書くべきかな～っと…

色が変わりました！

うっしっしf:id:SaSaKi:20200817222311p:plain 緑になりました！

緑になるまでにやったこと

・Cが解けなさそうだからと思ってDに行く
・配列の添え字をよくチェックせずに変数のところに定数を入れる。(2WAだから違うと思ってた…)

緑になるまでにやらなかったこと

C

これから

芸人にならないように早く水色になります…

水色になった

AtCoder

色編記事を書いてなかったので書きます.

水色になりました(ﾔｯﾀｰ)f:id:SaSaKi:20200812002252p:plain 参加回数が74回と水色の中ではかなり多いほうですが、こんなカスでも無限にやれば水になるという証明になりましたね。(???)

水色になるまでにやったこと

いろいろ(ゲームとか)
マイクラを始めたのは大きかったと思います。
あと早解き、これが多分1番大きいです。自慢ですがFAを1度とってます。

水色になるまでにしなかったこと

全部、正直もっといろんな知識を早くつけておくべきだったと思います。

水色になるまでに知っていたアルゴリズムとかデータ構造とか

  • Union-Find
  • DP(ナップサック、bit、区間とか)
  • BFS,DFS
  • 文字列操作
  • BIT(Binary Indexed Tree)
  • 貪欲
  • 二分探索、累積和、Warshall_floydなど…
    書き出すと、「あれ?何も知らないな…」となってしまう…

    水色になっても知らないこと

  • SegTree(BIT以外)
  • FFT
  • Dijkstra(マジ?)
  • 最小全域木とかの木をいじくるやつ

    くそお世話になったもの

    E%dさんの水コーダーになるまでの良問100を70くらい説いたときに水になりました。くそ力尽くのでお勧めです
    AOJ/AtCoder-JOIでJOI埋めを行う。
    AtCoder Virtual ContestならびにAtCoder Problemsのバーチャルコンテスト、自分のレートdiffで説いてないやつを詰めるといい練習になります。

    終わり

    次は青になります。

    • PCK2015のバチャをやった

    PCK

    前書き

    多分本選行きました(いいえ)

    記録

    ・1をやる、tRue君に6~を見てもらう
    ・1を解く、やるだけ
    ・2を解く、やるだけ
    ・3を解く、intの範囲で頑張る。
    ・5を先に解く、どの問題をどれだけ説いたかをやって後ろから累積和。
    ・4を解く、やるだけ
    ・9を解いてもらう。7を考える
    ・7解けなかったぞ～やってもらう間に8を考える。
    ・8これ簡単じゃね?(いいえ)全共通の範囲を求めればおk?
    ・8全然むずかった。範囲の中が2次関数的になってるので三分探索。
    ・6わからん、解いてもらう
    ・6といてもらう

    f:id:SaSaKi:20200718170741p:plain

    合計578分、4ペナルティで9完

    ボーダーわからず

    MAO#忘備録1

    MAO

    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

    f:id:SaSaKi:20200513161547g:plain です。
    MAOはかなりの閃きげーなので難しいですね…