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

CombNaf2

懲りずに企画やるみたいです。

あ、どうも、Nafmoです。

 CombNaf2決まっちゃいました。告知と中身概要など必要なこと書きます。

待たせたな!!!(待ってない)

続きを読む

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

 

 

 わーい

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

1ヶ月前ですね....

正直100%グダるとわかってます。Nafmoです。

今回は前回よりまともにいきたいですね。怖い。

続きを読む

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人ほど現れないかだけ期待しています。

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