ABC 080 参加記録。
ごめんなさい。
ちょっと今回は雑です。時間ないので。
A問題
ans=min(B,N*A);
B問題
cin>>S; N=stoi(S); for(auto x:S){ A+=int(x-'0'); } cout<<(N%A==0?"Yes":"No");
C問題
日本語読めませんでした。
要はやるやらないを10コマ試せば良い
2^10(ただし全部やらない1通りを引く)分だけ全探索。
Bitですね。
D問題
これを丁寧に書きたい。
いもす法 を使って終わりですね。(いもす法解説ページのリンク)
0.5なので、2倍したらいい感じになる。...さて。私は別の解き方でときました。
私は普通にいもす法をした後に、開始終了時刻をチャンネルごとにsetにぶち込み、録画が終わる時間で、次の録画が同じチャンネルかどうかをsetで調べました。
同じでない場合はtemp++をして加算します(録画機を増やすしかないため)
最後は ansとA[i]+tempで最大値比較
とやるとかぶりを発掘できてうまくやれます。
暇ができたら丁寧に書きますね。
わからなかったら @Nafmo2 まで聞いてくださいな。
おまけ。レート。
はい。
perf. : 1370
rate : 1176 (+24) highest!!
ABC 079 参加記録
全完じゃああああああああ
お久しぶりです、全完さん。
わかりやすさを心がけていきたいですね。
デザイン簡略化していきまーす
A問題
後ろ3桁は1000で割ったあまり。
前3桁は10で割ればいい(切り捨てなので)
三項演算子を用いて
((A/10)%111==0||(A%1000)%111==0)?"Yes":"No";
B問題
素直に書きました
if(0,1)だけ例外処理
ans=a+b
b=a,a=ans;
を回しまくります。
long longに変数を統一しないとオーバーフローします(int 混ぜないでね)
C問題
A+-B+-C+-Dを素直にべた書きしてください。こっちのほうが早いです。
私は、Bit全探索を書きました。
scanf("%1d%1d%1d%1d",&a,&b,&c,&d);
— 竹雄@CODE THANKS FESTIVAL2017 (@takeo1116) 2017年11月18日
で1文字ずつ取っていけ
参考情報
D問題
問題概要と解釈
- 書いてあるすべての数を1にしたい。
- 全体でいくらコストかかるか求めよ。
- 1になれるのはすべての数。
- コストが羅列されている
- あれ?これ、グラフっぽくないか?
- 一番小さいコストを求める、ということは、
どこか経由してもいいから、結果1にできればいいよね。 -
あれ?全部の頂点との最短距離求められるのでは?
- 各頂点から1までの距離が、コストでは...?
- できるじゃん!!!
というわけで、ワーシャルフロイド書きます。
で、ワーシャルフロイドの解説は別で書くかもしれません
https://t.co/Bn2UViFKP7
— eiya@受験競プロC++ (@eiya5498513) 2017年11月18日
このコードコメントがあって分かりやすいです。
ワーシャルフロイドはDP[i][j][k] = 頂点[1,k],i,jのみを使ったときの、i->j最短路です。
なので、DP[i][j][k] = std::min(DP[i][j][k], DP[i][k][k-1]+DP[k][j][k-1])になり、これにメモリ節約テクを使うとああなります。
このリンクのソースは私のソースだった()
ワーシャルフロイド回して、d[a][1]を平面操作します(aは書いてある数値(-1はスルーする))
これで通せます。
おまけ。レート。Highest
わーい
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)
わーい