いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

ABC015 C.高橋くんのバグ探し

飛ばしてたので解きなおしました
C: 高橋くんのバグ探し - AtCoder Beginner Contest 015 | AtCoder
選択肢k個がn回与えられるのでそれらの排他的論理和が0ならバグがあると判定する
排他的論理和を気合で求めてやるもんだと思ってたんですが"^"で出来るそうですねぇ、、、
あとは実装するだけだと思ったけど全探索しかないなぁと思ってたら制約が小さいことに気づいたのでそれでいいっぽい
dfs書いたらAC
最近よくdfs書いている気がするので慣れてはきたかなという感じ
使える技を増やしていこうな
Submission #1320754 - AtCoder Beginner Contest 015 | AtCoder

AOJ-ICPC 100 Next Mayor書いてたらコーディングでやらかしてた話

Next Mayor | Aizu Online Judge
実装力が足りないと思ってとりあえずAOJ端っこから解いていくかなって思ってる
で、この問題を実装していたらよくわからないことが起きて頭を抱えた
書いたソースがコレ

#include<iostream>
using namespace std;
#include<vector>
 
int main(){
  while(1){
    int n,p;
    cin>>n>>p;
    if(n==0&&p==0)return 0;
    vector<int> a(n,0);
    int pool=p;
    int i;
    while(1){
      for(i = 0;i<n;i++){
        if(pool==0){
          pool+=a[i];
          a[i]=0;
        }else{
          pool--;
          a[i]++;
        }
        if(a[i]==p)break;
      }
      if(a[i]==p)break;
    }
    cout<<i<<endl;
  }
  return 0;
}

2重ループの抜け方が酷いが楽してしまったのが悲劇だった
これで問題のテストケースを投げると1か所だけ通らない
その箇所単体で投げたら通る
初期化ミスしか思い浮かばなかったが見当たらない
コーナーケースを考えてもどうあがいてもわからなかった
隣に座ってた友人に聞いたら配列外参照をしているとのこと
じっくり考えたら気づいた、forループをi=n-1で抜けるとi=nの状態で次の行に入る
で、そのまま抜けてしまうのでテストケース3 3の場合i=3でループ抜けしていることになる
その時たまたま配列外参照したポイントが正解とかぶってしまったのでループを抜けてそれが答えになっちゃったらしい
伝わりにくいけどそういうことらしい
なのでループ部分を改善したらAC

#include<iostream>
using namespace std;
#include<vector>
#include<cassert>
 
 
int main(){
  while(1){
    int n,p;
    cin>>n>>p;
    if(n==0&&p==0)return 0;
    vector<int> a(n,0);
    int pool=p;
    int i=0;
    while(1){
      for(i = 0;i<n;i++){
        //assert(0<=i && i<n);
        if(pool==0){
          pool+=a[i];
          a[i]=0;
        }else{
          pool--;
          a[i]++;
        }
        //assert(0<=i && i<n);
        if(a[i]==p)break;
      }
      //assert(0<=i && i<n);
      if(a[i]==p&&i<n)break;
    }
    cout<<i<<endl;
  }
  return 0;
}

最初からまじめにフラグとかで実装すればよかったなぁ
assertはその値の範囲から逸脱していた場合処理を停止してくれるというものらしいです
割と便利だなぁと思った

・追記
修正すべき箇所が残っていたのをすっかり忘れて2人から同じ指摘をしていただきました

if文やその他の条件式は前から処理されるので

if(a[i]==p&&i<n)

としてしまうと先にa[i]がpと一致するか調べ(ここで配列外参照が起きる)、その後iがnより小さいかを判定するので

if(i<n&&a[i]==p)

とすることで先にiがnより小さいかを判定し、負ならそのまま判定を終了してくれるので配列外参照が起こらないって話でした

こう言うことをちゃんと覚えるための忘備録なので気を付けようと思います
短絡評価というのは知らなかったなぁ

ABC054 C.One-stroke Path

C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder
解きました
蟻本を買ったのでその力を見せつけていきたいです

難しくて数日頭の中で考えて友達にギャーギャー言ってわからなくて
蟻本読んで改めて実装してみようと思って書いたら通りました
単純にdfsであったのですが、訪問済みかどうかの扱いをどうすればいいか、dfsの書き方をどうすればいいか、再帰の書き方がわからない等で頭を抱えていました
訪問済みかどうかは元の地点まで戻ってきた時に解除していけばいいやという事と、再帰の書き方が少しわかったのでそれだけで十分かけました
他者のソースを読むって大事だとよくわかりました
蟻本を少しずつ読み進めていこうと思います
Submission #1305867 - AtCoder Beginner Contest 054 | AtCoder

AtCoder Beginner Contest 062(ABC62)

AtCoder Beginner Contest 062 - AtCoder Beginner Contest 062 | AtCoder
出ました
恒例になりつつある感じで大学の友達と6人で図書館で一緒に出ました
結果は3完、時間がもっとあれば部分点くらいは狙えたかなぁという感じでした
周りに聞いた感じCは難しいらしいので嬉しいけどやっぱりなんだか悔しかった
WA4回も出してしまったのでもっといい順位狙えたなぁという感じ

A.Grouping
[1,3,5,7,8,10,12][4,6,9,11][2]の3グループがある
x,yが与えられるから同じグループか判定する
考えるより手を動かそうと思ってif文でごり押してAC
後で友達に配列をつかって[0,1,0,2,0,2,0,0,2,0,2,0]みたいな感じで放り込んでおけば短く済むよう
なるほどなぁ

B.Picture Frame
与えられた文字列を"#"で囲んで写真のフレームを作ろうみたいな
もう決め打ちみたいな感じで入力の両サイドに#出したらすぐできた

C.Chocolate Bar
長方形の長さH,Wが与えられる、しっかり整数の長方形に3分割したときに面積のmax-minが最小の時の値を出力
分割の種類はどんなのがあるかなって考えたら「目」のように分けるか「T」のように分けるかの2通りのみで、入力例でほぼ網羅されていた
なのでh,wどちらかが3で割れれば0を出力
割れなければTだと思って、実装を始めた
Tの時は最初の分割部分を全探索してやると、あとは2分割する箇所は真ん中で1つに求まるのでオーダーも間に合う
縦横でこれを行った
これで提出するとWAが2つ出た
あちこち探して出しても変わらず考察をし直した

考えたら「目」の時は3で割れた時しか弾いてないじゃないかと気づいた(偉い!)
という事で2通り追加して実装ミスってWAだしてw,hで小さいほうを入れればいいやと気がついてAC
WA出さずに通せたなぁと思いつつも時間もないし通せただけ嬉しいので次へ

D.3N Numbers
数字が3N個で構成される数列が与えられる
この数列からN個数字を削除したのち、(前のN個の合計)-(後ろのN個の合計)が最大になるような数字を出力
見た瞬間頭を抱えた、周りはCがわからんなぁとぶつぶつ言っていたけど焦りを感じた
何をやっていいか全くわからない、とりあえず例を書いたり図を書いてみたりした
何がわからないのかといえば真ん中付近の数字は、数字の削除具合によって前にも後ろにもなりうるという事だ
とりあえず9の場合について整理した
書いた図は「〇〇〇△△△□□□」こんな感じ
両サイドのN個は含まれる部分は決まっているが真ん中のN個はどっちに含まれてもおかしくない
つまり仕切る部分を△の区間で全探索すればいいんだと思った
時間が足りず実装が間に合わなかったので書けてる分でとりあえず投げたらまあそりゃWA
後半はTLEだったので実装を工夫する必要があるなぁって思って終了

後で聞いたらほぼ正解だったっぽい、データ構造についてもっと知識を深めればACまでたどり着けたかもねとのこと

緑コーダーになりました
f:id:ratetion:20170521015249p:plain
AtCoder
これからも頑張っていきます
更新が最近少ないのはC問題埋めに苦戦してるからです
AOJで典型を解く練習をしてはどうかと言われたのでしばらく1日1回C解いてあとはAOJにしようかなと

AtCoder Beginner Contest A,B問題全問ACしました

とりあえず終わりました
かかった日数は39日間のようです
途中でC問題解いたりいろいろやってたりで頑張ればもっと早くできるとは思うけど地道にやれたのはよかったなぁと思います
今後はABCのCとARCのAをちょっとずつ埋めていけたらなと思います
f:id:ratetion:20170516014358p:plain
AtCoder Problems

AtCoder Beginner Contest 061(ABC061)

AtCoder Beginner Contest 061 - AtCoder Beginner Contest 061 | AtCoder
出ました、結果は3完、Dは解けるかと思ったがだめ、Cはもっと早く解きたかった
友達と大学のスペース使って出たのでとても楽しかった
なんだかんだ誘ったらみんな出てくれて刺激的で向上心がグイグイでうれしい

A.Betwee Tow Integers
整数CがA以上かつB以下であるかを判定
YES,NOじゃなくてYes,Noだったのでちょっと危なかったが普通にAC

B.Counting Roads
N個の都市とM本の道路が与えられる
各都市が持ってる道路の本数を順番に出力していく
すぐに書こうと思って気が付いたらsetをincludeしていた
何かがおかしいと一旦落ち着いてvectorに数え上げて入れていったらAC
特にどの都市とどの都市がつながっているとか考える必要がなかった
が、問題文からはちょっとわかりにくかったので冷静に考えれてよかった

C.Big Array
数字と個数がたくさん与えられるのでn番目に小さい数字を出力する
制約見ていけると思って全部vectorに突っ込んだらREの嵐が吹き荒れた
何故いけると思ってしまったのか
格納しないなら実装地味に難しいなぁって思っていろいろ考えたけどmapが丸いと思って書いた
個数を足していってkを超えたらその時の数字を出力するだけだったのでちゃんと考察すれば実装も簡単ですぐできそうだった
制約の1≦K≦b1…+…bnの部分が最初意味が分からなかったがよく読めばこれはbの総和であり、桁数が指定されていない
実際このkはintでは収まらずそこに気づくまでにかなり時間をロスしてしまった

D.Score Attack
N頂点M辺の重み付き有向グラフがある
1から移動を始め、通った辺の重みがスコアとして加算され、ゴールのマスでゲームを終了してもよい
スコアが最大になるときのスコアを出力、同じ辺を通ってもいいので無限に増加するならばinfを出力する
なんでもいいから全探索を2回行ってスタートからゴール、ゴールからゴールの最高スコアの経路を求めようと思った
分岐はそれほどでもないと思ったが全探索をどうするかでとまどってる間にタイムアップ
後で友達に聞いたら名前だけ聞いたことあるベルマンフォードを紹介され、更に最大値は正負逆転して最短経路にすればいいと教えてくれた
実装力も足りないと思ったしどのみち解けてなかったようだった

全体を見るとCでのタイムロスがとにかく痛かった
もうすぐABCのABが埋まるのでCとARCのAを中心に埋めてアルゴリズム力も養っていこうと思った

ABC048 C.Boxes and Candies

C: Boxes and Candies - AtCoder Beginner Contest 048 | AtCoder
解いた
数列とある数xが与えられる
数列の隣り合った2数の和がx以下になるように全ての数から引く
引いた数の合計を出力
やばい問題かと思ったが、正解の数値は一つだが、目標の状態はいくつか存在していいとわかった
先頭から順番にやっていけばその状態の一つは必ず作れるので差を数え上げていけばよい
説明が下手な感じがするがあとは数式を立てて”冷静に”書くだけ
合計は実は大きくなるのでintだと足りなかったみたい
わかりやすいWAの出方ですぐ気づけて助かった
Submission #1273097 - AtCoder Beginner Contest 048 | AtCoder