ABC115 あと8分あればD解けてた・・・

atcoder

beta.atcoder.jp

  • Cまでは一瞬で解ける
  • D問題
    • ハンバーガーの問題
  • ナイーブに生成すると250層に達する
    • long longには収まるが、再帰的に解けそう
  • ラスト2分でサンプル3が通り「できた！」と提出
  • 最後の4テストでWA

タイムアップ後

  • 簡単な例でテストを足してみると、間違う場合が再現できた
  • 再現できれば直せる
  • 直して提出、AC

解法

  • LVごとの層数、パティ数は事前にLV50まで求めておく
    • intではなくlong long
  • 対称性から「半分以上食べる場合」は「半分未満食べる場合」から求まる
  • 半分未満食べる場合、LVを1つ下げた問題に帰着する
  • 再帰的に関数を書けば解ける

順位

  • 2000人くらい参加
  • 600点/1000で950くらい。中間・・・
  • Dを解けていたら680位くらい
    • レートも上がっていただろう
  • レート 1061 -> 1037 落ちた・・・
    • しかし惜しかった。善戦した感はある。上達を感じる

参加しているのは学生が多い

  • 上位しか見ていないけど、東京大、東工大など
  • 年代は1990s, 2000sまでいる
  • 初心者しか参加していないと思ったが、上位はオレンジの人たちが沢山
  • タイムアタック的に楽しんでいるのだろう
    • 1位は9分でAからDまで解いていた
  • 私はCまでで17分
    • 手の速さに差がある
    • Dは分析までに時間もかかった。9分ってすごい

学び

  • 対称性により場合分けを単純化できた。バグも減る

【C++】warning: sizeof on array function parameter will return size of

cpp
  • c++でArrayを引数にするPrintArray(int a[])を作り、中でマクロARRAY_LENGTH(A)を使った
  • LENGTH分だけforする予定だったが、長さがちゃんと取れない
  • 引数がaというポインタで、ARRAY_LENGTHではsizeof(a)しているが・・・
    • これは配列の大きさではなくポインタサイズを返す
  • コンパイラもWarningを出してくれていた
  • 配列は面倒ということでvectorを使うようにした

English version

  • Use vector! :)

agc028 ローカルではsubtask含めて通るがサーバ側で通らず・・・

atcoder

問題

beta.atcoder.jp

提出

beta.atcoder.jp

ローカルでは全部通るがサーバ側では通らない

  • AtCoderはテストデータをDropboxで全公開している
  • それをローカルに落としてテストしたらAC
  • しかしサーバ側に提出するとRuntime Errorになるものがある
  • ロジックとして解けてはいるので、特に追いかけはせず..
  • 「次へ行こう」

学び

  • lcmはC++17なら関数であるようだがAtCoderではC++14 (GCC 5.4.1)で参加しているので定義する
ll gcd(ll a, ll b){
  if(b == 0) return a;
  return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
  return a * b / gcd(a,b);
}
  • lcmは大きな値になりうるのでllで書くべき
    • 今回も最初intで書いていたら無駄にエラー増やしてしまった
  • 積集合として intersection を初めて使った

【C++】cin高速化

cpp atcoder
  • たまに見かけるこのコード
cin.tie(0);
ios::sync_with_stdio(false);
  • cin高速化と呼ばれている
  • scanfの方が速いようだが、便利なのでcin使いたい人向け

使って計測してみた