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

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

JOI AtCoder 競技プログラミング

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

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

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

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

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

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

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

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

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

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

問題概要。

JOI 2011-2012 予選 問題４

  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日目の処理がおかしい。

あ、通ったｗｗｗｗｗｗｗ

Submission #1477603 - WAソース

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

それをif文で外しました

Submission #1477666 - ACソース

通っちゃったんだけど？

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

チラシの裏

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

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

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

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

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

続きを読む

ABC 067 の解説？

ABC AtCoder 競技プログラミング

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の最短距離の間に他にも塗れるところがあったら死亡。

嘘解法でした☆

解説読んで☆

おまけ。レート

CombNaf タイムテーブルと諸注意

CombNaf

10日前ですね....

七夕だ！お願いするのはもちろん

  • CombNafが失敗に終わりませんように...っと。

正直うまくやらないと100％グダると確信しています。Nafmoです。

今回はタイムテーブルになりたかった何かと諸注意を描かせて頂きました。

タイムテーブル(随時更新)

とても表で貼りたいけど、空白が多すぎて貼れないので...

  1. はじめに

  2. LTの部

    発表者リスト(敬称略)

    1. rxon
    2. sksat
    3. Yk0n
    4. Miare
    5. 弓箭
    6. kemo_friends(bot)
      • 休憩(30分程度(時間調整有))
    7. E869120
    8. Soichiro Yoshimura
    9. Keidarou
    10. eiya
    11. もやし先輩
    12. Azaika
  3. おわりに

  4. 時間が余ったら...懇親会的な何かができればいいな...と
    (要するに自由時間(競プロの問題用意してたり...?) / ～17：00)

LTは10分で収めてください。

LTタイトル。早めに渡して欲しいです

諸注意

  1. 参加者は、ATNDの登録、アンケートの回答にご協力ください。
    • ATND
    • アンケート

  2. 参加〆切は 7/16 23:59 とします。
  3. LT は 締め切りました。
    ただし、受付だけはします。(できる保証はいたしかねます)
  4. http://sekico.co/zaseki/804

  5.  電源タップを持ってこれる方はお持ちください

  6. ドワンゴの勉強会の会場 | Doorkeeper

    電源は3席に1つの割合（しかもMacのアダプタが刺さらない）
  7. 飲食は可能ですが、軽食程度にしてください
    (ガッツリ昼食とかやめて)
  8. ゴミはお持ち帰りください。
  9. LTをする際にスライドを使う場合は
    PCを持参するか、事前に私までデータを渡してください。
  10. (LTをされる方は)LTの所要時間をNafmoまでお伝えください
  11. プロジェクター対応端子はHDMI,VGAです。
  12. PC持ってくんの忘れたああああああ！！！！
    という苦情は一切受けません。
    が、持ってきていいことがあるかどうかわかりません。
  13. この注意は随時追記されることがあります。

 

ABC 066 参加記録(大嘘)

ABC 競技プログラミング

今回はARCに出ました。

Cが解ければパフォーマンスいいらしいですし（

A問題：ringing

全部足して

a+b+c-std::max({a,b,c});

B問題：SS

#include<iostream>
#include<string>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
string S;
int main(){
    ios_base::sync_with_stdio(false);
    cin>>S;
    int siz=S.size();
    REP(i,siz){
        //奇数文字列 or 一文字も消していない場合は当てはまらないためスキップ
        // siz-i = 今見ている文字列の長さ
        if( (siz-i)%2==1 || i==0 ){
            continue;
        }
        // 初めから (siz-i)/2 文字分をaとする
        // 同じく、aの後ろから(siz-i)/2 文字分をbとする
        // abcabcd siz-i=6のとき a=abc b=abc のように
        string  a=S.substr(0,((siz-i)/2)),
                b=S.substr((siz-i)/2,(siz-i)/2);
        // a==b なら条件を満たす。
        if(a == b){
            cout<<siz-i;
            break;
        }
    }
    return 0;
}

 

C問題：pushpush

偶奇っぽいのでといた。

偶奇全滅してから嬉しい()

まず、はじめの数を置く。

次に置く数は 前か後ろにくっつければいい
(N-i)%2==1ならばpush_front(a[i])、そうでなければ、push_back(a[i])

(ここでのiは0~N-1まで)

でおしまい。

らっく～

D以下解けないもんね()

おまけレート


f:id:nafmo17:20170701225633j:image

861→888 +27 (highest!!!)

ゾロ目だー