ABC 073 参加記録(一週遅れ)
ABC073 Only
いや、最近ずっと考察してて書く暇がないのでまとめて書くよ((((
いつもは撤退して、書いてるんですがねぇ
A問題:September 9
string で受けて S[0]=='9' || S[1]=='9'
B問題:Theater
被らないらしいので、
全クエリに関して
r-l+1を足し算。終わり
C問題:Write and Erase
sortします。
if(A[i]!=A[i+1])のときに偶数なら左っ側が偶数なら消える
奇数ならans++
C問題:joisino's travel
ワーシャルフロイド法を用いると全部の距離が求められますね。
でその後はNextPermutationで全探索!
間に合いますね。
おまけレート
なんかやる気ありませんでした(当時)
ARC082 参加記録
ARC 082
いやぁ、何とかレート単調減少から復帰しました。
今まで書いてなかったのはそういうことです。
C:Together
これ、私の解法想定解ではないと思います。
- Aの各要素の個数を取る(配列を10^5個用意した())
- で、3~Nまで 全部尺取っぽく回すといい感じになる(は?)
- いわゆる全探索
D:Derangement
- A[i]==i+1になるものを探す
- 見つかったらインクリメントする
- 連続してそれが起こる回数を記録する。
- その回数が0以外で2で割ってたあまりが0になったときはデクリメントして辻褄を合わせる
- 終わり。
- (雑ですいません)
おまけ
951(+2) Perf.975
もうレートあがんねーな
JOI 11th('11/'12) - 4 パスタ
解説記事ではないd嘘です。
Nafmoです。Twitterを見ていただいてる方はわかるように、
私は現在、動的計画法を始めとした、競プロっぽい問題が全く解けません。
この問題は動的計画法で えい ってすれば解ける問題なんですが、なんせかけません。
Twitterは流れるし...うーんって考えた結果ここにメモっとこうかなっという発想になりました。
本当に何もわからない()
が、通っちゃいました(追記)
あ、ここで補足なんですが、私がDPといったときは動的計画法を指します。
メモ化再帰で書くDPはメモ化再帰、ループで書くDPはループDPなどと記すことが多いという注意書きをね。
メモ化再帰用関数の名前をDP、メモ用変数をdp...などと書く事が多いです。
問題概要。
- パスタのメニュー、3種類を選びながら食べる
- N日目まで食べたとする。何通り?
- ただし、3日連続同じメニューの場合を除く。
めっちゃ簡単そう。に見えるじゃん?
できません。
私の考察。
- はじめにDP(x,y)=(x日目にyを食べたときの通り数)としました。
- 詰みました。(何もできなかったので)
(eiyaさんが考察ツリーを作って突破していました...) - で、考えを改め引数を増やしました。
- DP(x,y,z)=(x日目にyをとり,x-1日目にzを取ったときの通り数)としてみました。
- dp[x][y][z]=dp[x-1][z][i(1~3)]の和(ただしy==z==iの時を除く)
その日食べれないものを指定していた場合は0を返す
1日目は食べれるものを指定していた場合は1を、それ以外は0を返す - というような感じになるように目指して、実装をはじめました。
書き上げましたが、思っている通りにかけてる気がしないですね...
状況遷移も怪しい動きをしているんですよね...
1通りしかないところ3通りとカウントしてるし
あ、見えたぞ(遅い。)
1日目の処理がおかしい。
あ、通ったwwwwwww
ここの差、0日目を1 2 3選ぶってことをカウントしていた模様。
それをif文で外しました
通っちゃったんだけど?
できました。(落ちねぇ....)
チラシの裏
どーでもいいことを書いていく記事1
#CombNaf なんですが、次3月にしようと思ってたんですが、「冬は?ねぇ…冬は?」と言われたので12/24も候補に上がってきてるんですね…
— CombNaf@固定アンケ (@Nafmo2) July 24, 2017
ここでアンケート。次回いつがいいですかね…?
とりあえずこんなアンケートやってたんだけどね
どっちも開催しろって言われて、嬉しくもあるし辛くもあるんだよね。
まぁ一応。思いついたこと書きなぐっときます。
晒しとく意味は無いんですが、忘れないように?
続きを読む