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

JOI 2010 本選 3 つらら

え?私覚醒した?

†DP†で通しました。

解法書きまーす

問題概要

  1. N本つららが並んでいます
  2. 両脇のつららよりながければ、1cm/hで伸びる
  3. Lまで行くと折れる
  4. さて全部折れるまで何時間?
  5. https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf

解法

両脇が折れる時間+L-今見てるところの長さでその見てるところの長さは出せる

じゃあどうするか。再帰っぽい。

あれ?DPじゃね?

空からDP解法が降ってきた。

両脇より高ければ L-A[i]でreturn

どっちも高かったら低い方だけ見ればいい

どっちかだけ高かったら高い方だけみればいい

みたいなことやって全探索したら幸せになれました

Submission #1681110

DP解、つらい。

でもなんかできて嬉しかった。

プライオリティーキュー解もあるのでそっちも考えてみるといいかもです

 

 

ABC 075 参加記録

まじで、意味がわからん。

 

なんでBにバグ埋めて30分戦うんだよおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお

原因不明!(どうせお前が悪い)

 

さてさて。

A問題

sort(A,A+3);

A[0]==A[1]?A{2]:A[0]

B問題

謎。

解法を変えずに別アプローチで通したけど...意味わからん

全部のマスに対して8回ループ回しただけなんですがなんででしょ。

Submission #1683199

助けて()

C問題

辺を一つなくした時、どこかの頂点に行けなくなれば良い。

そのために最短経路探索をします。

各頂点の距離がINF担ってないか確かめます。

いままで持った辺のコストを1、辺X[0~M-1]のコストをINFとしてダイクストラ方をやりました。

M回ダイクストラを回してINFがあったらans++;をすると通ります。

Submission #1684150

D問題

5重ループ全探索らしい

くっそおおおおおおおおおお

おまけ。

水色、見えてきた。

 

なんか上がってるんだけど? 1070 -> 1083(+13,Highest)

わーい

 

CODE FESTIVAL qual B 参加記録(解説ではない)

CODE FESTIVAL qual B

B問題に時間かけてしまった。

レート落ちるぞ~

今回はいつも以上に雑です。

A問題。

後ろ7文字入りません。

REP(i,(signed)S.size()-8)cout<<S[i];

B問題。

どっちもソートします。

二重ループ回して、見なくていいところを省略しつつ、全部見ます。

終わり。

mapの使い方、だれかおしえて(

低数倍重かったら死んでたなぁ

C問題

なんかよくわからなかった。

二部グラフを疑うだけ疑った。おわり。

解けるようになりたかった。

おまけ。


1055->1070(+15)(Highest!

 

DDCC 2017 予選 参加記録

DDCC 2017予選に出たよ

DISCO presents ディスカバリーチャンネル コードコンテスト2017

という名前のコンテストですね。で、私はなかなかない好成績を(大嘘)出しました。

10分三完は頑張った!!!

231位ですね。

では解法の話をね

 

A問題:DDCC型文字列

substr(0,2)==substr(2,2)?Yes:No;

1WA!!!!

問題をよく読みましょう

substr(0,2)==substr(2,2)&&S[1]!=S[2]ですね

B問題:鉛筆

鉛筆 1 ダースは 12 本、 1 グロス144 本、 1 グレートグロス1728 本です。

1728*A+144*B+C*12+D

終わり。

C問題:収納

二分探索とか言う強い人もいますが...私は断然ソート+貪欲です。

見てみましょうか。

問題概要

  1. a+b+1<=Cなら2本それ以外なら1本入る棒がある
  2. 箱少なくしよう!!!
  3. (詳しくは読んで...)

私の解法

  1. sortします。
  2. 後ろから要素を見ます
  3. L[i(N-1~0まで回す)]+L[prev]+1<=Cなら
    F[prev]というもうすでにしまったことを表すフラグをtrueにします。
    でprev++します。
  4. F[i]はtrueに。
  5. ans++
  6. このループを繰り返します。終了条件はi=0まで行くか、F[i]==trueになるかのどっちかです。
  7. 詳しくはソースをご覧くださいな
  8. Nafmo's submission

感想。

いや、貪欲が秒で実装できてよかった。

あと本選辞退する人が100人ほど現れないかだけ期待しています。

それでは。今回はここらで

CODE FESTIVAL qual A 参加記録(解説ではない)

こどふぇす!

参加資格もないしあっても通りませんが、書きましょう。

A問題:Snuke's favorite YAKINIKU

文字列をStringで受けて

(S.substr(0,4)==”YAKI”)?Yes:No;

B問題:fLIP

全探索しました。

1~N行ひっくり返して1~M列ひっくり返したときにKと同じになりますか?だけ試して終わりにしました。

っていうのに時間を溶かしました

M*i-(j*i)+j*(N-i)==Kみたいなことやった

ウソっぽい…?

 https://beta.atcoder.jp/contests/code-festival-2017-quala/submissions/1617321

C問題:

えぇ、なんか(0,0)から順番に対応するところ埋めていけ!wとか思ったんですが、反例が出たので死ですね。

 

レートの上がりは謎。下がる気がする

おまけ。レート。

更新を確認し次第画像が貼られます


f:id:nafmo17:20170923232304j:image
キメた

1041->1055 (+14) Highest!!!
perf.1166
やったぜ。