ボーダーは360点らしく、ギリギリアウトです。ここで、「問題6を無理に満点解法狙うんじゃなくて、ケース1に特化した解法で書いておけば良かった...」と後悔してももう遅い。1年の努力をしょうもないミスで水の泡に変えてしまった自分でした。1番気に食わないのはボーダーが360ということは問題4がO(N^2)解法でも問題3まで全部合っていれば本戦に行けてしまうということですね...しかし、終わったことは仕方ない。自分の実装力と運が不足していた。全部コードも出して解説しておきたいと思います。Subjects)この問題、入力の内容を読まずに解きました。最初に全教科を足し、そこから理科の最低点、社会の最低点を引くだけです。...解けないやつが居るのか?という感じでした。Bibs)N,M≦100なので愚直にシミュレーションしてやりましょう。Flag)これも普通に白の下限、青の下限を全部試してO(N^2M)でもいいのです。この問題、見た瞬間に「各行に赤青白がいくつあるか」が分かれば列は関係ないことに気付きました。いうより気付いてください。いうことで予め各行に赤青白がいくつあるかカウントしてあげてからやればO(N^2)か。0;}ここまで15分しか経って無いし、楽勝!と思ってたんですがね...上のコード、ケース1しか通りません。tmpが初期化されずに一方的に増え続けています。いうことでループ内をこんな感じにしてれば本戦に行っていました。Kingdom)アルゴリズムは一瞬で浮かぶ。実装に苦労させられました。移動前の位置をソートしてあげて、そこから全員衝突を無視して最後の地点まで歩かせる。元の位置関係と逆になっていればその人達は衝突しているはず。衝突地点は2人の座標の平均値なので、衝突地点に合わせて、「ぶつかった」というフラグを立てておく。フラグが立っている人と衝突してたらフラグが立っている方に合わせて上げればOKです。一応全員の位置のソート、そして家の番号と座標の組み合わせの探索にO(NlogN)です。自分はてっきりfind関数がO(logN)で働いてくれると思っていたので、ケース4であれ?となっていました。仕方無く絶対一致する値があるのでlower_boundに任せたら数秒で終わりました。0;}なかなか複雑でしたね。自分もdistanceは知っていながらも初めて使わされました。posは移動前の座標に移動方向をくっつけたもの、endposはposからT秒経った状態。endはposとaを使って求めたaの人の順に並べた最終地点です。この3つの情報をどうソート前後で組み合わせるかに悩まされました。Island)がっこうぐらし!からすればゾンビに侵略された島に宿泊出来ないなんて甘いんでしょうけど...予め危険区域に指定された街がどれか知っておきたいですね。いうことでダイクストラです。危険度をゾンビに侵略された島はs+1として、そこから島を1つ渡る毎に危険度が1減るように設定します。すると危険地帯でないところの危険度は0。危険度が0か正かで判別できるようになりました。自分はダイクストラ大好きなので連続で使用。危険度=s+1であるところはゾンビに侵略されているので入れません。0;}出来た!例題通った!大丈夫!と出しました。気付いて下さい、自分。sが使われてないでしょ。i=0;i<k;i++){cin>>c[i];c[i]--;dan.push(make_pair(s+1,c[i]));danger[c[i]]=s+1;}となり、更に2回目のダイクストラの位置がif(danger[e[from][i]]==s+1)continue;//ゾンビが侵略済みのため進行不可となってやっとAC。stalls)これは見た瞬間に「ハイハイbitDPね」の流れでしたね。6問目はbitDPだろうと予測してたんです。ケース1では店が20店舗しか無いらしいので全店舗にbitを割り振れば通ると思います。他のケースを考えると、下の画像のようなwの字型にbitを取るのが良さそう...と思って実装していたのですが、実装が重い。書き終わった!実行!としたらAbort喰らいました。残り時間5分だったのでそのまま挫折。これはソースコードがあまりに汚く、自分でも読めるか怪しいので割愛します。(そもそも実行できません。)現在地点を★とすると、現在地と次の地点で関係があるのはこんなもんでしょう。現在の場所より先(左と下)の店には絶対訪れることが出来ません。よって必要なbitデータは上の五ヶ所でしょう。(模範解答はよく見てないので分かりません)それでもbitデータを3×3のデータに直し、それをもう一度bitデータに戻すなんて荒業をやっているから大変でしたね。こんな実装ミスで本戦に進めなかった自分を恨んでますね。競技中はWAでないことを祈って出したんですが。自分の1代下に4完してくれてる後輩がいるので、そちらの指導でもしようかなと思っています。今後、競プロは完全に趣味として、受験もあって優先順位はどうしても低くならざるを得ませんが続けようと思っています。目指せRedCoder。因みに余談ですが、科学の甲子園といい、日本学生科学賞といい、今回のJOIといい。全部全国の1歩手前(科学賞は予備審査まで行きましたが)でやられているんですよね...まるで呪われているかのよう。...「3月中に毎日1問解いて黄色になろう!」キャンペーン8問目。日)ネットの海に生息するらしいバーチャルグソクムシ。競プロとCTFをメインに、たまにEsolangを混ぜます。(7)月別アーカイブリンクGitHubはてなブログをはじめよう!Hyogaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。