JOI 2010 本選 3 つらら
え?私覚醒した?
†DP†で通しました。
解法書きまーす
問題概要
- N本つららが並んでいます
- 両脇のつららよりながければ、1cm/hで伸びる
- Lまで行くと折れる
- さて全部折れるまで何時間?
-
https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf
解法
両脇が折れる時間+L-今見てるところの長さでその見てるところの長さは出せる
じゃあどうするか。再帰っぽい。
あれ?DPじゃね?
空からDP解法が降ってきた。
両脇より高ければ L-A[i]でreturn
どっちも高かったら低い方だけ見ればいい
どっちかだけ高かったら高い方だけみればいい
みたいなことやって全探索したら幸せになれました
DP解、つらい。
でもなんかできて嬉しかった。
プライオリティーキュー解もあるのでそっちも考えてみるといいかもです
ABC 075 参加記録
まじで、意味がわからん。
なんでBにバグ埋めて30分戦うんだよおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお
原因不明!(どうせお前が悪い)
さてさて。
A問題
sort(A,A+3);
A[0]==A[1]?A{2]:A[0]
B問題
謎。
解法を変えずに別アプローチで通したけど...意味わからん
全部のマスに対して8回ループ回しただけなんですがなんででしょ。
助けて()
C問題
辺を一つなくした時、どこかの頂点に行けなくなれば良い。
そのために最短経路探索をします。
各頂点の距離がINF担ってないか確かめます。
いままで持った辺のコストを1、辺X[0~M-1]のコストをINFとしてダイクストラ方をやりました。
M回ダイクストラを回してINFがあったらans++;をすると通ります。
D問題
5重ループ全探索らしい
くっそおおおおおおおおおお
おまけ。
水色、見えてきた。
なんか上がってるんだけど? 1070 -> 1083(+13,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問題:収納
二分探索とか言う強い人もいますが...私は断然ソート+貪欲です。
見てみましょうか。
問題概要
- a+b+1<=Cなら2本それ以外なら1本入る棒がある
- 箱少なくしよう!!!
- (詳しくは読んで...)
私の解法
- sortします。
- 後ろから要素を見ます
- L[i(N-1~0まで回す)]+L[prev]+1<=Cなら
F[prev]というもうすでにしまったことを表すフラグをtrueにします。
でprev++します。 - F[i]はtrueに。
- ans++
- このループを繰り返します。終了条件はi=0まで行くか、F[i]==trueになるかのどっちかです。
- 詳しくはソースをご覧くださいな
感想。
いや、貪欲が秒で実装できてよかった。
あと本選辞退する人が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とか思ったんですが、反例が出たので死ですね。
レートの上がりは謎。下がる気がする
おまけ。レート。
更新を確認し次第画像が貼られます
キメた
1041->1055 (+14) Highest!!!
perf.1166
やったぜ。