harurun競プロ

python勢

ICPC Asia Yokohama Regional 2023 参加記

チーム

Pech1(青,M1)

Eringi(緑,B2)

harurun(現在水,B4,これ書いてる人)

velocityというchatgptに決めてもらったチーム名 で出ました。

国内予選

書いたつもりが書いてなかった。 幸い4か月失踪してたおかげでTwitter遡るのが楽だった。

ICPC 3完53位
A Eringiさんが通した
B 担当。dpした
C Pech1さんが天才生やした

D 色々やったけど通らず
E dpっぽかったけどわからず
F 解けない
G m個選んで部分和のやり方がわからんかった
H 見てない

https://twitter.com/harurun_p/status/1677300084629983233

日程的に外部院試、ICPC国内予選、学内院試が1週間に全部あったらしい。よく出たな。

このあと青から水に転落しました。

地区

戦略

day1

英語担当欠席

英語全部頼る気だったからやばかった。harurunはTOEIC600未満だしPech1は500未満。オワタ......。

産賀ホールではなく産貿ホール

どうりで変換出てこないわけで......。

プログラムのローマ字読んで気が付いた。

ちなみに既に直ってた。

ライブラリを取りに

家から1時間半で会場に着くのに学校にライブラリを置いてきていたため、家を9時に出ることに.....。

受付~リハ前

欠席は連絡してもらってたが直前のため受付以外に共有できてなかったらしく、写真撮る人とか交通費渡す人に説明するのが大変だった。 英語力、ください。

あと二人ともEnvelopeの意味がわからなかったが、わからねーみたいな話をしてたらマイクを持った人が真横で封筒を見ながら言ってくれたのでなんとなくわかった。 Envelopeは中学英語らしいです。

リハーサル

問題が読めない......。

AとBは練習問題なので。まぁ。

Cは2019A、見たことあるが解くのやめた問題だったのでPech1にぶん投げた。貪欲だったらしい。

Dは去年のAらしい。Parallelは平行。これは研究分野的に読めないとまずいが読めました。誤読してバグらせたけど。

チーム紹介

貸し1でharurunが喋りました。ボールペンすら持ってきてなかったのでメモなし。何喋ったかは覚えてません。

この貸しは欠席者のTシャツと名札をPech1が持って帰ることで相殺されました。

他のチームは"こんにちは"とくまぁぁのとこだけ印象残ってる。

夜ごはん

中華街に行ったが、決められずになぜかガストへ。

めっちゃ空いてた。

なんとなく赤レンガ撮って帰宅。

日本大通りから急行に乗らずに渋谷まで行ったら1時間以上かかったらしく、Pech1がABC出れなくなってた。 harurunはずっと寝てた。

22時とかに家に着いてそのまま寝た。

day2

英語担当降臨

受付

名札とTシャツと学生証は無限回確認した。

8時集合にしたのにharurunは8時30分に着きました。ごめんなさい。 秋葉原の構造が記憶と違いすぎてトイレ探すのに手間取りました。

普通に間に合った。

トイレ

本番中は手挙げてスタッフ読んでトイレ行きたいですを英語で言う必要がある。

restroomかtoiletが入ってれば伝わるはず......。

受付した場所でMale/Female聞かれてついて行ってもらう感じだった。

I want to restroom.(これやばすぎ)

I go restroom.

とか言ってた気がする。

本番

開始してすぐにパスワード2回打ち込んで面倒だった。

codium立ち上げてAを読み、実装へ、が、眠くてよくわからなくなりPech1へパス。

Pech1が実装してる間にharurunはBを読んでたっけ?覚えてないや。

EringiがC以降の翻訳作業に入ってた。

harurunはCを見てやばそうって思ってた。

Pech1がAの実装をバグらせる。深さ優先したら無限ループしてたらしいが面倒だったのでharurunが変わって書き直した。

dpして提出。36分でAC。

Pech1とEringiでBに取り掛かってた。harurunはEringiから問題前半の概要を聞いた。

Bを提出したらWAだったらしく、harurunにPCが変わる。

Dが簡単そうだなと思って実装するが考察ミス。またPech1に変わってBがWA。絶望してた。

そんなこんなしてたら昼飯が届いたのでPech1がEの実装をしてるあいだに食べた。

Eはバグが取れずやばかったらしい。

harurunはBに取り掛かり、cの制約的に2c-1回見ればいいでしょとか言い出し、Pech1からPC奪ってACした。2時間51分。

順位表見たらFがうち以外ほとんど解いてたので取り掛かるが、harurunはこの手の問題が苦手なため解けない。

やばそうなので順位表からKを見る。インタラクティブで行けそうみたいな話でPech1がFをやってる間にEringiに三分探索の回数を数えさせてた。

harurunは何してたっけ......。

結局、開始3時間半くらいでharurunが方針聞いて二分探索で行けるみたいな話になってPech1が実装する。 インタラクティブの手元での動かし方がわからず四苦八苦する。

入力ファイルいるなんて知らなかったので無限にエラー吐いてた。(リハのときいらなかったので)

四苦八苦してる中、コードのバグを見つける(代入忘れ)。

直して、手元で実行どうするかってなったが、Eringiのおかげでどうにかなった。

半径が答え-1で出力されたので+1にしてお祈り提出したらAC4時間29分。

順位表を見るとFが自チーム以外解かれててかなり焦った。

Pech1がいつの間にか実装してたがWAが続き、EもREとTLEで通らなかった。

結局そのままABK3完で終了。

問題講評

ドーナツが配られた。コーチ不在だが4つ入ってた。

F<Bになったらしく、F解かれすぎって思った。

後半は寝てたから知らない。

YES/NO

目が覚めた。

この時点で凍結前2完のチームが全チーム提出してたのでワンチャン最下位あるなと思ってた。

YES/NOで最初にACで拍手起こってビビった。 (F通してないチームがK通してるなんて思わないもんな)

3ninn_oranwa_bokeを何回も読ませたの最高だった。

Closing Ceremony ってどうやって訳すんですか

ドーナツ食べた。

ビュッフェ

リュック重すぎワロタ。もらった水とかお茶とかほとんどもらっていれてパンパンになってた。

移動して食べた。持ち前のコミュニケーション能力の低さでチームでまとまってるだけだった。

エンカ募集とツイートしたらtake000さんが来てくれた。アイコンルービックキューブの人とも話した。

野生のchokudaiさんを見たが話しかけれなかった。残念。

眠くなったので終わる前に帰った。

懺悔

国内でやらなくてよかったね。

地区総評

全体58チーム中54位だったけど3完したから自分的には満足。(ブラックフライデー?知らないね)

だけどPech1がかなり悔しがってた。

戦略はよかったのであとは地力かなぁ。

英語、二日目は英語トイレしか使ってない気がするから喋れなくてもチームメンバーが喋ればなんとかなる。

おわり

来年は某大学院に行くので出れるかはわかりませんが、人集まったらまた出ようと思います。 Pech1が早生まれで来年も出れるらしいので倒したい。

入青

この記事は 競プロ Advent Calendar 2022 - Adventar の6日目です。色変記事です。

色落ちが怖いのでひよって日程変更しました。

harurunさんのトヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)での成績:192位 パフォーマンス:2190相当 レーティング:1528→1614 (+86) :) Highestを更新し、2 級になりました! #AtCoder #トヨタシステムズプログラミングコンテスト2022(ABC279) https://atcoder.jp/users/harurun/history/share/abc279?lang=ja

宣伝

adventar.org

人がいないのでぜひお願いします!!

いつもの

入水が2021年8月8日なので1年と3か月かかりました。

(昨年の秋学期は忙しくてRated出ていませんでしたが)

前回から(AtCoderでは)450問程度しか解いていません。

やったこと・できるようになったこと

  • 簡単なDP

  • ICPC国内の過去問C~Eあたりまで

  • 安定した5完

  • 簡単なアルゴリズムの深い理解

やろうとしたのにやってないこと

  • フロー系全部(簡単な問題なら使えるけど......)

  • 2-Sat

  • 文字列系アルゴリズム

  • ARC埋め(時間取れない......)

FAQ

質問募集中です。

marshmallow-qa.com

競プロに関係ないことでもよいです。

  • ARC/AGC出ないんですか?

    日曜バイトなので物理的に出れません。青後半になったら出たいのでバイト辞めます。はやくなってバイト辞めたい

おわり

ICPC 2022 国内予選 参加記

結果

108位 ABC3完で通過ならず

チーム

Nanashimaさん(緑)とPech1さん(青)とチーム「Go2Heaven」で出ました。

今年がチーム最後でした。悲しい。来年1人募集中です。

(去年の: ICPC2021 国内予選参加記 - harurun競プロ )

模擬国内

1完で終わってた。C通さなければいけなかった。

本番

15時に3限終わって集まった。

色々準備しながら腹が減ったのでパンを2つ食った。

ちなみに準備が良いので手軽に食べられるチョコも持ってきてた。

ホワイトボードをキレイに(と言っても汚かったが)したり、jagのチーム一覧に書き込んだり、色々やってたら16時半になった。(ちなみにコメントはNanashimaさんが書き込みました)

16時半になってコンテストが始まった。去年や一昨年のようにこどふぉらなかった。

担当 A: Pech1, B:Nanashima, C: harurun

A

Pech1さんが簡単だと言って4分くらいで通してた。神。

B

貪欲だったらしいが、バグらせてAを終えてD以降を読んでたPech1さんに投げてたらしい。40分くらいで通ってた。

C

始まってすぐに方針が立たず。

取りあえず、サンプルを全て手動で解いてみた。

サンプルの最後がわからずbit全探索を書いて調べた。(このときすでに体感30分くらい経ってた。マジで焦ってた)

サンプルから練習は一か所に多く、休息はばらけさせたほうが良いことがわかる。

「休息日をi個もしくはi-1個ずつのグループに分ける。練習日は休息日の間に入れて、1か所だけ多くする。」

という方針が立った。

これが諸悪の根源だった。戦犯。

これだと練習日が3、休息日が9のときに休息日を3,2,2,2に分けられないとか書こうとしたけど分けられる気もしてきた。眠すぎて何もわからん。

とにかく方針を

「休息日をi個のグループにわけたとき........」

に変更した。

そしたら通った。デバッグにつき合わせちゃってめっちゃ時間つかってしまった。(1時間半くらい)

D

で、Dは必ず分けなければいけないところと分けれる場所を探して組み合わせするだけという方針を立てた。

が、サンプルの5個目が0にならずに絶望。Pech1さんから分割部分のコードをもらうが変数が衝突しまくって終わった。

一応サンプルが通ったので投げるが通らず。Pech1さんのdp?方針も合わず。

ここでコンテストが終わってしまった。

で、さっき解説を見たわけですが、「そもそもどのように区切っても目標の列を作れない場合は 0 を返すことには注意する必要がある.」という点以外方針同じなんですよね。たぶんだけど分割したあとにシュミレーションしていけるか判定すれば通ってたと思う。まじで悔しい。去年と同じことしてる(去年はEの"="抜け)。

感想

2年連続やらかして申し訳なさすぎた。これは行けてたって去年も言ってた気がする。

来年は2人とも黄色になって横浜行きます。

ABC243E - Edge Deletion をダイクストラ法で通す

atcoder.jp

問題文

N 頂点 M 辺の単純連結無向グラフが与えられます。 辺 i は頂点 A_i と頂点 B_i を結ぶ長さ C_i の辺です。

以下の条件を満たすようにいくつかの辺を削除します。削除する辺の数の最大値を求めてください。

  • 辺を削除した後のグラフも連結である。
  • 全ての頂点対 (s,t) について、頂点 s と頂点 t の間の距離が削除前と削除後で変化しない。

制約

  • 2≤N≤300
  • N−1≤M≤N(N-1)/2
  • 1≤A_i<B_i≤N
  • 1≤C_i≤109
  • i≠j ならば (A_i,B_i)≠(A_j,B_j)) である。
  • 与えられるグラフは連結である。
  • 入力はすべて整数である。

方針

(制約的にワ―シャルフロイドなのだろうと思いながら)

問題文を言い変えると、

各頂点から各頂点への最短経路で使われなかった辺を削除するときの削除する辺の数の最大値を求めよ

である。

頂点 i から各頂点への最短経路は ダイクストラ法で O(MlogN) であり、i を 1∼Nまで変化させるので、合計で O(NMlogN) である。

どの辺が使われたかについては、直前の頂点を覚えていればO(N)で判定可能である。

これを実装すると以下になり、WAを喰らう。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

struct Dijkstra{
  private:
    long long INF=1000000000000000000LL;
    std::vector<std::vector<std::pair<long long,long long>>> G;
    int V;
    inline void _add(long long s,long long t,long long c){
      G[s].emplace_back(std::make_pair(t,c));
    }
  public:
    Dijkstra(int N):V(N) {
      G.resize(V);
    }
    void add1(long long s,long long t,long long c){
      _add(s,t,c);
    }
    void add2(long long s,long long t,long long c){
      _add(s,t,c);
      _add(t,s,c);
    }
    std::vector<long long> run(long long s){
      std::vector<long long> res(V,INF);
      vector<ll> pre(V,-1);
      std::priority_queue<std::pair<long long,long long>,std::vector<std::pair<long long,long long>>,std::greater<std::pair<long long,long long>>> que;
      res[s]=0;
      que.push(std::make_pair(0,s));
      while(!que.empty()){
        std::pair<long long,long long> p=que.top();
        que.pop();
        long long v=p.second;
        if(res[v]<p.first){
          continue;
        }
        for(const std::pair<long long,long long>& e:G[v]){
          if(res[e.first]>res[v]+e.second){
            pre[e.first]=v;
            res[e.first]=res[v]+e.second;
            que.push(std::make_pair(res[e.first],e.first));
          }
        }
      }
      return pre;
    }
};

int main(){
  ll N,M;
  cin>>N>>M;
  Dijkstra ijk(N);
  ll A,B,C;
  for(int i=0;i<M;i++){
    cin>>A>>B>>C;
    ijk.add2(A-1,B-1,C);
  }
  vector<vector<ll>> d(N,vector<ll>(N,0));
  for(int i=0;i<N;i++){
    auto res=ijk.run(i);
    for(int j=0;j<N;j++){
      if(res[j]!=-1){
        d[res[j]][j]++;
        d[j][res[j]]++;
      }
    }
  }
  ll ans=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      if(d[i][j]!=0){
        ans++;
      }
    }
  }
  cout<<M-ans<<endl;
}

atcoder.jp

原因

3 3
1 3 3
1 2 1
2 3 2

のような入力があったときに、頂点 1 から 頂点 3 までの最短経路が2通りできてしまい、処理順により答えが変わってしまうことである。

これを解決するためには、頂点 v から 頂点 u への最短経路は、最短経路上により多くの頂点を含むように実装すればよい。

(u から v への最短経路上の隣接する頂点を p,q とすると、多重辺がないため、辺(p,q)は必ず使われることになる。よって頂点をより多く含むほうを最短経路とすれば良い。)

これを実装すると以下のようになり、ACが得られる。

なお、Pythonでは計算量が怪しく、TLEするかもしれないのでC++などの高速な言語を使ったほうが良い。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

struct Dijkstra{
  private:
    long long INF=1000000000000000000LL;
    std::vector<std::vector<std::pair<long long,long long>>> G;
    int V;
    inline void _add(long long s,long long t,long long c){
      G[s].emplace_back(std::make_pair(t,c));
    }
  public:
    Dijkstra(int N):V(N) {
      G.resize(V);
    }
    void add1(long long s,long long t,long long c){
      _add(s,t,c);
    }
    void add2(long long s,long long t,long long c){
      _add(s,t,c);
      _add(t,s,c);
    }
    std::vector<long long> run(long long s){
      std::vector<long long> res(V,INF);
      vector<ll> pre(V,-1);
      vector<ll> cnt(V,0);
      std::priority_queue<std::pair<long long,long long>,std::vector<std::pair<long long,long long>>,std::greater<std::pair<long long,long long>>> que;
      res[s]=0;
      que.push(std::make_pair(0,s));
      while(!que.empty()){
        std::pair<long long,long long> p=que.top();
        que.pop();
        long long v=p.second;
        if(res[v]<p.first){
          continue;
        }
        for(const std::pair<long long,long long>& e:G[v]){
          if((res[e.first]==res[v]+e.second && cnt[e.first]<cnt[v]+1) || res[e.first]>res[v]+e.second){
            pre[e.first]=v;
            cnt[e.first]=cnt[v]+1;
            res[e.first]=res[v]+e.second;
            que.push(std::make_pair(res[e.first],e.first));
          }
        }
      }
      return pre;
    }
};

int main(){
  ll N,M;
  cin>>N>>M;
  Dijkstra ijk(N);
  ll A,B,C;
  for(int i=0;i<M;i++){
    cin>>A>>B>>C;
    ijk.add2(A-1,B-1,C);
  }
  
  vector<vector<ll>> d(N,vector<ll>(N,0));
  for(int i=0;i<N;i++){
    auto res=ijk.run(i);
    for(int j=0;j<N;j++){
      if(res[j]!=-1){
        d[res[j]][j]++;
        d[j][res[j]]++;
      }
    }
  }
  ll ans=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      if(d[i][j]!=0){
        ans++;
      }
    }
  }
  cout<<M-ans<<endl;
}

atcoder.jp

追記

O(N2) のダイクストラ法を使えば O(N3) になるとの指摘があったので追記。

これならPyPyでも間に合う。

class dijkstra_V2:
  def __init__(self,V):
    self.INF=float("inf")
    self.cost=[[self.INF]*V for _ in [0]*V]
    self.V=V
    return

  def add1(self,s,t,v):
    self.cost[s][t]=v
    return

  def add2(self,s,t,v):
    self.cost[s][t]=v
    self.cost[t][s]=v
    return

  def run(self,s):
    ret=[self.INF]*self.V
    ret[s]=0
    used=[False]*self.V
    pre=[-1]*self.V
    cnt=[0]*self.V
    while 1:
      v=-1
      for u in range(self.V):
        if (not used[u]) and (v==-1 or ret[u]<ret[v]):
          v=u
      if v==-1:
        break
      used[v]=True
      for u in range(self.V):
        if (ret[u]==ret[v]+self.cost[v][u] and cnt[u]<cnt[v]+1) or (ret[u]>ret[v]+self.cost[v][u]):
          ret[u]=ret[v]+self.cost[v][u]
          pre[u]=v
          cnt[u]=cnt[v]+1
    return pre

import sys

def main():
  N,M=map(int,sys.stdin.readline().split())
  ijk=dijkstra_V2(N)
  for i in range(M):
    A,B,C=map(int,sys.stdin.readline().split())
    ijk.add2(A-1,B-1,C)
  d=[[0]*N for i in range(N)]
  for i in range(N):
    res=ijk.run(i)
    for j in range(N):
      if res[j]!=-1:
        d[min(res[j],j)][max(res[j],j)]+=1
  ans=0
  for i in range(N):
    for j in range(i+1,N):
      if d[i][j]==0 and ijk.cost[i][j]!=ijk.INF:
        ans+=1
  print(ans)
  return

main()

atcoder.jp

さらに追記

O(NMlogN) でもPyPyは間に合いました

atcoder.jp

ランダムテストケース生成をしよう

この記事は、競プロ Advent Calendar 2021の24日目の記事です。

はじめに

みなさん、ランダムテストケース生成してますか?私はしています。

提出コードのバグがどうしてもわからない場合はかなり有効な手です。

今回の記事では私が普段やってるランダムテストケース生成の方法を紹介します。

1. 愚直解を書く

O(N3)でもO(2N)であろうがO(N!)であってもとりあえず書いてください。

このコードがバグっているといけないのでサンプルは確認しましょう。

提出した言語と愚直解の言語が異なっていても構いません。

2. ランダムテストケース生成 & 実行

Pythonを使ってランダムテストケース生成 & 実行します。

以下では提出したコードの実行ファイルをmain.exe、愚直解のコードの実行ファイルをsimple.exeとします。

Pythonの場合は hoge.exeの部分をpy hoge.pyに置き換えてください。(他のスクリプト言語の場合も同様に実行コマンド スクリプトファイルに置き換えてください。)

ランダムテストケース生成コード

A - Welcome to AtCoderを例にとって説明します。

import random

def generate():
  with open("input.txt",mode="w")as input_file:
    a=random.randint(1,100)
    input_file.write(f"{a}\n")
    b=random.randint(1,100)
    c=random.randint(1,100)
    input_file.write(f"{b} {c}\n")
    s=[]
    length=random.randint(1,100)
    for i in range(length):
      s.append(chr(random.randint(ord("a"),ord("z"))))
    s="".join(s)
    input_file.write(f"{s}\n")
  return

愚直解で瞬時に終わる程度のランダムテストケースを生成します。

各行の改行を忘れないようにしましょう。

実行 & 比較

import os
import filecmp

def is_same():
  os.system("main.exe < input.txt > out1.txt")
  os.system("simple.exe < input.txt > out2.txt")
  if filecmp.cmp("out1.txt","out2.txt"):
    return True
  else:
    return False

普通は上のコードでいいのですが、セキュリティソフトが勝手に実行ファイルを削除してくる場合は以下のコードを使います。

import os
import filecmp

def is_same():
  if not os.path.isfile("main.exe"):
    os.system("g++ main.cpp -o main")
  if not os.path.isfile("simple.exe"):
    os.system("g++ simple.cpp -o simple")
  os.system("main.exe < input.txt > out1.txt")
  os.system("simple.exe < input.txt > out2.txt")
  if filecmp.cmp("out1.txt","out2.txt"):
    return True
  else:
    return False

ファイル全体

まとめると以下のようになります。

import random
import os
import filecmp

def generate():
  with open("input.txt",mode="w")as input_file:
    a=random.randint(1,100)
    input_file.write(f"{a}\n")
    b=random.randint(1,100)
    c=random.randint(1,100)
    input_file.write(f"{b} {c}\n")
    s=[]
    length=random.randint(1,100)
    for i in range(length):
      s.append(chr(random.randint(ord("a"),ord("z"))))
    s="".join(s)
    input_file.write(f"{s}\n")
  return

def is_same():
  if not os.path.isfile("main.exe"):
    os.system("g++ main.cpp -o main")
  if not os.path.isfile("simple.exe"):
    os.system("g++ simple.cpp -o simple")
  os.system("main.exe < input.txt > out1.txt")
  os.system("simple.exe < input.txt > out2.txt")
  if filecmp.cmp("out1.txt","out2.txt"):
    return True
  else:
    return False

def main():
  while True:
    generate()
    if not is_same():
      break

main()

ランダムテストケースでもバグが見つからないときは

コーナーケースを見逃している可能性

例えば、N=1のときなどを試してみるといいかもしれません。

そもそも誤読している可能性

一度心を落ち着かせて問題文を声に出して読んでみましょう

図を紙に書いて確認してみても良いです。

おわりに

この記事ではランダムテストケース生成について書きました。

読んで頂いた方ありがとうございました。

ICPC2021 国内予選参加記

2021/11/05にあったICPC国内予選に参加して、全体127位で敗退しました

ちなみに酔っ払いながら書いてるので誤字脱字などは悪しからず(ほろ酔いで酔うな)

模擬 のように、チーム「HigaKoder」でNanashimaさん(緑)、Pech1さん(水)と一緒に参加しました。

コンテスト前

15時までわたしが授業だったので15:30くらいから作戦会議的なものが始まりました。

一通り終わった後暇だったので https://jag-icpc.org/?2021%2FTeams%2FList に載せるひとことどうするてきな話になり、共通点を探すことに。 共通点が見つからなかったので麻雀って共通点にしようということになったが、学内ネットからじゃんたまに繋がらず断念。 私が「学内1位目指します!」でいいのではというとACした。(*弊学は1チームのみ)

コンテスト

い つ も の

去年の参加記を読み漁ってたのでF5リロードしてました。 いきなり始まるのも去年と同じ。

AをPech1さん、BCを僕とNanashimaさんが見ることに

C

問題が長すぎたのでまずはサンプルを読んだ。

どうやら構文解析っぽかったので他の人にCが構文解析であることを伝える。

問題を読むが解法が生えず、5分で捨てた。

B

Bが詰まってそうだったのでBに行く。

考えてるうちにAが通ってた。

縦と横と全体を管理して幅優先の実装してたら全体の初期値が-1ではまずいことを指摘され101に直す。

Pech1さんが先に実装終わって出してWA。たぶんunionfind木?実装覚えてない。

そうこうしてるうちに実装終わって出したらWA。

Pech1さんがすぐに縦or横に何もないときが一意に定まらないことに気が付き自分が直してAC。

E

Bをやってる間にDを読んでいてくれたらしいので後ろの問題を読むことにする。

Eダイクストラじゃね?と言って実装を始める。

pariotity_queueにλ式入れられるかわからなかったので比較演算子オーバーロードした。これが大戦犯。

拡張ダイクストラっぽいことをしたのにWAが出まくって焦る。

Dもバグってるらしくめっちゃ焦った。

2時間くらいデバッグしたのに解けずに終了。

原因は 待った回数が50を超えたときの比較で同じときを考慮していなかった。

https://gist.github.com/harurunrunrun/9653d8b0260d56e116814b0d301e565c

の59行目が戦犯です。

if(A.cnt==B.cnt){return A.cost<B.cost;} else {return A.cnt<B.cnt ;}

に変更するとACになると思います。知らんけど

感想

実力不足でした。来年はこのメンバーで出るラストチャンスらしいので頑張ります。

メンバーのお二方とコーチを引き受けてくださった先生ありがとうございました。来年もよろしくお願いします!

ICPC 模擬国内予選 2021 参加記

2021/10/24にあったICPC模擬国内予選2021にチーム「HigaKoder」でNanashimaさん(緑)、Pech1さん(水)と一緒に参加しました。

コンテスト前

12時に3度寝から起床した。

何をトチ狂ったのか前日のABCのHを見て心を落ち着かせようとしたが逆効果だった。

一番にdiscordに入ったのにコンテスト始まるまで何も喋れなかった。コミ障...

コンテスト

コンテストが始まった。

担当は A:Pech1さん B:Nanashimaさん C:harurun

Cを開いてすぐに「Hanjo」だとわかるが実装ができない。

Aは実装が大変そうみたいなのを聞いていたら10分くらいでAが通される。

Bはにぶたんらしいが入力でバグらせて30分くらいかかってたが通せてた。

そしてC。まじで実装が出来なかった。愚直解枝狩りで間に合うだろ~とか言いながら無限場合分け実装してたら先にNanashimaさんがDFSで通してくれた。1時間くらい。

水コーダーなのに再帰DFSができないと申します...

Dを見る。

ここまで空気なので頑張りたいところ...

先輩2人がDPで実装してる間に自分は貪欲を書いてました。

バグりにバグらせ経過2時間くらいで疑心暗鬼になりながらACしました。

Dのコード

貪欲の正当性未証明...

残り1時間でEを見る。

先輩2人が転倒数とかを出して相談してる中、わからないので他の問題を見に行く。

Fを見る。何書いているかわからなかった。

Gを見る。フローで解けないかな~と色々試案して30分、全方位木DPだなぁとなる。

一旦Hを見るが解けそうにないのでGに戻る。

残り10分くらいでN回木DPすればいいじゃんと思いつくが実装ができなかった。

このあとは何もなく終了

結果は(Guestを抜いて)56位。学内は1チームしか出てないのでまずまずでした。