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

あの水色ってきれいだよね。(競プロ!! AdC)

競プロ、それは魔窟。

何言ってるかわかりませんね。私もわかりません。どうもNafmoです。

今回は競技プログラミング Advent Calendarに参加させていただくことになりました。これは16日目の記事です。

続きを読む

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倍したらいい感じになる。...さて。私は別の解き方でときました。

Nafmo's Answer (ソースコード)

私は普通にいもす法をした後に、開始終了時刻をチャンネルごとに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全探索を書きました。

 参考情報

D問題

問題概要と解釈

  1. 書いてあるすべての数を1にしたい。
  2. 全体でいくらコストかかるか求めよ。
  3. 1になれるのはすべての数。
  4. コストが羅列されている
  5. こんな感じなのが全てに生えていると言える
    すべての数に魔法が使えてなれるので
    (中心が変わったものが全てにある)

  6. あれ?これ、グラフっぽくないか?
  7. 一番小さいコストを求める、ということは、
    どこか経由してもいいから、結果1にできればいいよね。
  8. あれ?全部の頂点との最短距離求められるのでは?

  9. 各頂点から1までの距離が、コストでは...?
  10. できるじゃん!!!

というわけで、ワーシャルフロイド書きます。

で、ワーシャルフロイドの解説は別で書くかもしれません

 このリンクのソースは私のソースだった()

ワーシャルフロイド回して、d[a][1]を平面操作します(aは書いてある数値(-1はスルーする))

これで通せます。

おまけ。レート。Highest

 

 

 わーい

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!