競プロっておいしいの?(仮)

ARC082 参加記録

ARC 082

いやぁ、何とかレート単調減少から復帰しました。

今まで書いてなかったのはそういうことです。

C:Together

これ、私の解法想定解ではないと思います。

  1. Aの各要素の個数を取る(配列を10^5個用意した())
  2. で、3~Nまで 全部尺取っぽく回すといい感じになる(は?)
  3. いわゆる全探索
  4. Submission #1558834

D:Derangement

  1. A[i]==i+1になるものを探す
  2. 見つかったらインクリメントする
  3. 連続してそれが起こる回数を記録する。
  4. その回数が0以外で2で割ってたあまりが0になったときはデクリメントして辻褄を合わせる
  5. 終わり。
  6. (雑ですいません)
  7. Submission #1561673

おまけ

951(+2) Perf.975

もうレートあがんねーな

CombNaf2

懲りずに企画やるみたいです。

あ、どうも、Nafmoです。

 CombNaf2決まっちゃいました。告知と中身概要など必要なこと書きます。

待たせたな!!!(待ってない)

続きを読む

JOI 11th('11/'12) - 4 パスタ

解説記事ではないd嘘です。

Nafmoです。Twitterを見ていただいてる方はわかるように、

私は現在、動的計画法を始めとした、競プロっぽい問題が全く解けません。

この問題は動的計画法で えい ってすれば解ける問題なんですが、なんせかけません。

Twitterは流れるし...うーんって考えた結果ここにメモっとこうかなっという発想になりました。

本当に何もわからない()

が、通っちゃいました(追記)

あ、ここで補足なんですが、私がDPといったときは動的計画法を指します。

メモ化再帰で書くDPはメモ化再帰、ループで書くDPはループDPなどと記すことが多いという注意書きをね。

メモ化再帰用関数の名前をDP、メモ用変数をdp...などと書く事が多いです。

問題概要。

JOI 2011-2012 予選 問題4

  1. パスタのメニュー、3種類を選びながら食べる
  2. N日目まで食べたとする。何通り?
  3. ただし、3日連続同じメニューの場合を除く。

めっちゃ簡単そう。に見えるじゃん?

できません。

私の考察。

  1. はじめにDP(x,y)=(x日目にyを食べたときの通り数)としました。
  2. 詰みました。(何もできなかったので)
    (eiyaさんが考察ツリーを作って突破していました...)
  3. で、考えを改め引数を増やしました。
  4. DP(x,y,z)=(x日目にyをとり,x-1日目にzを取ったときの通り数)としてみました。
  5. dp[x][y][z]=dp[x-1][z][i(1~3)]の和(ただしy==z==iの時を除く)
    その日食べれないものを指定していた場合は0を返す
    1日目は食べれるものを指定していた場合は1を、それ以外は0を返す
  6. というような感じになるように目指して、実装をはじめました。

書き上げましたが、思っている通りにかけてる気がしないですね...

状況遷移も怪しい動きをしているんですよね...

1通りしかないところ3通りとカウントしてるし

あ、見えたぞ(遅い。)

1日目の処理がおかしい。

あ、通ったwwwwwww

Submission #1477603 - WAソース

ここの差、0日目を1 2 3選ぶってことをカウントしていた模様。

それをif文で外しました

Submission #1477666 - ACソース

通っちゃったんだけど?

できました。(落ちねぇ....)

チラシの裏

どーでもいいことを書いていく記事1

とりあえずこんなアンケートやってたんだけどね

どっちも開催しろって言われて、嬉しくもあるし辛くもあるんだよね。

まぁ一応。思いついたこと書きなぐっときます。

晒しとく意味は無いんですが、忘れないように?

続きを読む

AGC018 参加記録

Nafmoさん決めました(嘘です

AGCが、直近過去二回ゼロ完太陽の私が!!!

23分で!!!解けた!!!(ただし2WA)

汚い解法書いて終わらせます。(嘘でした)

続きを読む

CombNaf-開催後記-

申し訳ございませんでしたああああ

はい。Nafmoです。

よければ、回答してください。

続きを読む

ABC 067 の解説?

ABCの解説書いて寝る

はい。CombNafの準備?知るかぁ!!!!

でも、CombNaf 来て!!!!

じゃあ書いちゃうよ()

A問題:

if(A%3==0||B%3==0||(A+B)%3==0)で終わり

B問題:

a[i]という配列にぶっこんでいきます

sort(a,a+N)します。

後ろからK個取って足して終わり。

C問題:

各要素を全部足します。

後ろから引いていきます。

引いたものを別の変数に入れて、和を求めていきます。

前の和-後ろの和ができるので、ひたすらmin()にかけました。

D問題:

脳死Dijkstra

まず1とNの距離を出します。

そいつを2で割ったあまりが偶数か奇数か出します。

奇数ならフェネックの勝ち

と思ったんだけど、それはこれで引っかかる

これですね

1とNの最短距離の間に他にも塗れるところがあったら死亡。

嘘解法でした☆

解説読んで☆

おまけ。レート