ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

ICPC2017 国内予選

まえがき

このストーリーはrianの書いたストーリー
rian.hatenablog.jp
に出てくるIQ1の物語です.
IQ1視点のサイドストーリーという形になります

前日談

~ チーム登録 ~
icpcたいてっく予選には登録が必要である.そして僕らは待っていれば唐突にコーチが生えてきて全ての登録に必要なことをやってくれると思っていた...しかし,東工大は引き継ぎに失敗していて次のコーチが決まっていなかった...

そう、コーチがいなかったのである

去年はM2のはどろりさん,とこはるさんたちがコーチをやってくださっていた...しかし,先輩方が卒業してしまったいま,東工大M2にコーチをしてくれそうな人がいなかった...そしてこれに気がついたのが6/20だった.登録が6/29あたりまでで焦り始め,とりあえずはどろりさんに助けてーって言う.
そしたらshimomireさん,assyさんがまだ大学にいると教えて頂きtwitterで連絡が取れそうなshimomireさんにコーチをお願いして引き受けてもらう(shimomireさん突然twitterで連絡してすみませんでした.そしてコーチを引き受けて頂きありがとうございます).

~ チーム編成 ~
チーム名はIQ1。メンバーは吹雪(kuwaさん),睦月(すごぷろさん),夕立(ちゃっく)での編成になった.睦月(すごぷろさん)には去年も組んで頂いた.

チーム内の役割は吹雪ちゃんと睦月ちゃんが問題を解いて夕立はお茶を汲むって感じ

あらすじ

(先に上に書いたりあんのブログを読むことを推奨します) IQ1視点
icpcたいてっく予選は本来,大魔王yosupotにより人間軍は虐殺されてしまうはずだったがyosupotは力を溜めるための眠りについたため,今年は穏やかな時が流れる.そう信じていた...しかし後輩に次世代魔王n_ari(rickytheta)が誕生してしまった...この次世代魔王n_ariの左右には「部分文字列にGODを持つgoodbaton」「忍者の家系ninja」が控えており,人間軍は魔王に立ち向かうことを諦めた.

そして予想される残りの枠は1つ.この枠を巡ってkurukuru-sushiと人間同士の醜い争いが始まる...

国内予選開始前

とりあえずラボで必要な物の印刷を始める.夕立はIQが1しかないので何故か国内模擬用のIDとパスワードを印刷してたことに吹雪ちゃんが気がつく.ビビる.

計算機室でログインしようとしたらログインできなくなってた.理由は不明だが前回はログインできたのに今回はできなかったので,もしかして夕立が計算機室の飲食禁止のルールを回避するために片足だけ計算機室から出して水飲んでたりしたのが理由だろうか...(違うと信じたい)

  • 開始3分前 -

計算機室のPCにpython3がないことに気がつく(ワォ).
python3の使用を諦め,python2を使用することにする.

国内予選

とりあえずA問題を夕立が5分ちょいで通しBを吹雪ちゃんがとく.
Bを吹雪ちゃんが解いてる間に僕はDを読み「恐らくDP,ちがったらマッチング」みたいな適当なことを言いながらDPが得意そうな睦月ちゃんに投げる(練習で睦月ちゃんがDPに強そうな気がしてた).夕立はEを読むが全く解ける気がしない.蟻本のSATを眺めてみるがさっぱりできる気がしない.気がついたら吹雪ちゃんがB終わってた(BのFAかと思ったがもっと早い所あった).吹雪ちゃん練習のときはC++使ってたのに本番で突然pythonを使いだしてびっくりした.睦月ちゃんがCを通し終えてDを考えてる間に,吹雪ちゃんにE問題を説明する.構文解析がでたらすぐに吹雪ちゃんに投げる方針だったが構文解析の後が難しそうだった.
睦月ちゃんがD問題を通す.この時点で順位はめちゃくちゃ良くて4位とかだったと思う.
夕立はEを諦めてFを読み始め,吹雪ちゃんと睦月ちゃんにEを頑張ってもらうがEの方針が吹雪ちゃんと睦月ちゃんで衝突してた.
夕立はFをまとめてたらEが完全に沈黙してそうだったので睦月ちゃんにFを相談する.吹雪ちゃんはEをヒューリスティックに解き始める.

kurukuru_sushiと魔王軍(ninjaribaton)に抜かれてて夕立は焦り始める.

この時点で多分残り40分くらい.

睦月ちゃんが考察終了したのが多分残り10分ちょい.Eはペナルティが大きすぎて通しても意味がなさそうなので睦月ちゃんがFの実装に入る.
一度バグってダメかと思ったが残り1分弱でサンプルが合う.大急ぎで提出する.1回目の提出で「接続中」とかではじめてキレそうになるが,なんとかラスト1秒で提出成功してAC
睦月ちゃんかっこよすぎるっぽい~~~!

f:id:chakku000:20170715035759p:plain
提出時間2:59:59

懇親会

味庵に行きました.何故か僕だけ子供用に椅子に座ってました.夕立なので...

assyさん懇親会を企画してくださってありがとうございます.

感想

学内3位....やはり魔王軍は倒せなかったっぽいけどkurukuru_sushiにも勝てなかった...でも全体20位なので望みはあるらしいっぽいよ!
夕立は役に立てなかったけど睦月ちゃんと吹雪ちゃんはすごかった~

あと、チームIQ1を応援してるってツイートを見てとってもとっても嬉しかった!

ICPC国内模擬2017

ICPC国内模擬2017にチームIQ1で参加しました
メンバーはkuwaさん,すごプロさん,僕で行動指針としては最初3完してあとは適当にって感じを予定してました

開始前

誰も蟻本を持ってきていない←???
TLE本も持ってきてない←まあしょうがないか

コンテスト

開始直後問題が開けない...

とりあえず印刷してる間に僕がAを読んで通す.その間にkuwaさん,すごぷろさんはB,Cの方針を考えてAが終わり次第B,Cを通す.kuwaさんは僕がAやってる間にD問題を読んでいたっぽい?

kuwaさんがDをやるがなかなか答えが合わない.僕はEを読むが無理.Fを読む.
その間にすごぷろさんにE,Fの相談.Eは完全にすごぷろさんに投げてFは「フローじゃないかなぁ」となり蟻本を眺めたくなるが眺められない.そう誰も蟻本を持ってきていないのである.

kuwaさんがDでバグるので,コーディング交代してすごぷろさんがEの実装を始める.
なんかちょこちょこkuwaさんと交代したりしながらしてた(?).

気がついたら提出障害を乗り越えてkuwaさんがD通してた

僕はF眺めてる間に貪欲でいける気がしてきてサンプル5が貪欲で行けそうだったので完全に間違った方向へ突っ走って「考察は終わりました」とか意味不明なこと言い始める

すごぷろさんはEがバグり残り20分くらいでコーディングを交代しながら書いてったら30分延長した.
30分延長したがFの実装でもバグってサンプルが合わないがデバッグするほどの時間は残ってなかった.

終わってrickytheta氏にFの解法聞いたら貪欲じゃなかった....なんか危険なケースを聞いたけどよくわからない...

感想

Aしか通してないので僕は実質お茶汲み係をしてました

チームIQ1なので勝手に東大のIQ94ってチームを敵視してたが結果としては全く格が違って敵視してたことが恥ずかしい.94倍のIQの差では勝てない...

すごぷろさんが幾何でつらそうにしてたので実体のあるTLE本がほしい...
ライブラリほしい...

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

Codeforces #418 Div2 C An impassioned circulation of affection

コンテスト中に解けなかったやつ...

Problem - C - Codeforces

概要

文字列sが与えられる.(sの長さ\leq1500)
クエリがq個飛んでくる(q\leq200000)
各クエリはm(1\leq m \leq n)と文字cが与えられる.
文字列sの文字のうちm個をcに書き換えた場合,部分文字列でcのみからなるも文字列の最長の長さを求めよ

解法

1.各文字cに対してs[0..i]に含まれるcの個数の累積和を求める.
2.累積和を用いて各文字cに対して,「長さi」のcからなる部分文字列を作るのに書き換える必要のある文字の数を求める
3.各クエリに対して「書き換える必要のある文字の数がm以下になっている最大の長さ」を(2)で求めた結果から計算する

計算量はO(|s|q)でギリギリかな

コード

int n;
string s;
int q;
int m;
char c;

int main(){
    cin >> n >> s >> q;

    vector<vector<int>> cnt(26);
    for(char c='a';c<='z';c++){
        int i = c-'a';
        cnt[i] = vector<int>(n+10,0);
        for(int j=0;j<n;j++){
            if(s[j]==c) cnt[i][j+1] = cnt[i][j]+1;
            else cnt[i][j+1] = cnt[i][j];
        }
    }

    vector<vector<int>> need(26,vector<int>(n+10,0));
    for(char c='a';c<='z';c++){ //26
        for(int i=1;i<=n;i++){  //1500
            int mn = 0;
            for(int j=0;j<n;j++){
                int s = j;
                int t = s + i;
                if(t>n) break;
                // s[s..t)
                int num = cnt[c-'a'][t] - cnt[c-'a'][s];
                mn = max(mn,num);
            }
            need[c-'a'][i] = i-mn;
        }
    }

    rep(loop,q){
        cin >> m >> c;
        int ans = 0;
        for(int i=0;i<=n;i++){
            if(need[c-'a'][i] <= m) ans = i;
        }
        cout << ans << endl;
    }
}

感想

qの値が微妙だから計算量から方法思いつきにくい気がしたけど前計算が必要なことは分かりそうなのでこのくらいは解きたかった...

あと問題文に化物語が使われてるけど西尾維新の作品て外国人が読んでも楽しいのかな...?同音異義語で遊ぶような作品だから言語が変わるとその面白さはなくなりそうだよね.

ABC060D Simple Knapsack解いたんだよ

dp解

 dp[i][j] := i個使用して重さの総和が j+w_0 iとなるときの価値の最大値
とする.
ここで重さを直接持つと配列に収まらないのでw_iの代わりに w_i - w_0を使用することで配列に収まるようにできる

注意点

内部のループは逆に回さないと同じ荷物を何度も使用できてしまうので注意

コード

ll N,W;
ll w[128],v[128];
ll dp[128][512];
 
int main(){
    cin >> N >> W;
    rep(i,N) cin>>w[i]>>v[i];
 
    ll sum=0;
    rep(i,N){
        ll ww = w[i]-w[0];
        // 荷物iを複数回使わないように逆に回す
        for(int j=i;j>=0;j--){  // 荷物iを含まないでj個
            for(int k=sum;k>=0;k--){    // 荷物iを含まない時の重さがk
                dp[j+1][k+ww] = max(dp[j+1][k+ww],dp[j][k]+v[i]);
            }
        }
        sum += ww;
    }
 
    ll ans=0;
    for(int i=0;i<=N;i++){
        for(int j=0;j<=sum;j++){
            if(w[0]*i+j>W) continue;
            ans = max(ans,dp[i][j]);
        }
    }
    cout << ans << endl;
}

感想

想定解を最初に思いついたがdp解で通してるひとが結構いたのでやってみた
想定解のほうが思いつきやすいと思うけどナップサックだからdpのほうがイメージしやすいのかなぁ

C++のmapの最大のキーをとる

C++のstd::mapのキーで最小のキーはbegin()を使用し,最大のキーはrbegin()を使用すればよい.

間違えて最大のキーを取得する際にend()を使ってしまったのでメモ.
endは最終要素の次にアクセスしてしまうので値が不定になる(多分).
未定義動作になるらしいです
map::end - C++ Reference
実際に" It does not point to any element, and thus shall not be dereferenced."とある.

#include <iostream>
#include <map>

int main(){
    std::map<int,int> mp = {
        {2,20},
        {5,50},
        {4,40},
    };

    int minv = mp.begin()->first;
    int maxv = mp.rbegin()->first;
    std::cout << minv << std::endl; // 2
    std::cout << maxv << std::endl; // 5

    int e = mp.end()->first;
    std::cout << e << std::endl;    // 3 (最後の要素の次を指してるので何が入ってるか不明)

}

修正

上の赤字で示した部分修正受けました.ありがとうございます
ピーー☆━━━━━…‥‥(・_・ヽ) アリガタビーム!!

RUPCに参加してきました

RUPC2017に参加してきたので参加記を...

~前日~
前日まで大学の友人と旅行をしていたので昼神温泉から中津川まで車に乗せていってもらい、中津川からはrian,葦くんとともに名古屋→京都に行く.
京都でちょっと観光してからホテルに向かおうということで伏見稲荷大社を訪れて山登りしたが僕の体力が底をついて途中リタイア


京都駅で夕食を探して歩き回るも何も見つからずラーメン街へ
その後瀬田駅まで行ってホテルへGO.

~1日目~


余裕を持って?到着。立命館大学では卒業式をやっていたらしく大量に人がいた.
--コンテスト--
コンテストではらてさんと葦くんと同じチーム(Achalatte)になり、僕はまずAを担当したがRE.どうもAOJはC++でreutrn 0をしないとREになるらしく再提出→WA.バグらせた。なんか実装ミスってたので葦くんにコーディング譲ってその後にAC.次にEを担当し、DPだとはわかるが状態の持ち方が悪くてTLEしそうなのでらてさんにアドバイスもらって書く.最期見る所を間違えてサンプルとおらないがらてさんに教えてもらってAC.気がついたら葦くんがCをACしてた.
あとはらてさんが無双して全完.すごかった...

解説聞いたらAで無駄なことしまくってて泣いた.

~2日目~
---コンテスト---
rianと葦くんと「1回はこの三人ででたいよね」という話をしていたのでこの3人で組んだ.トイレから帰ってきたらチーム名がtaitekku_000で決まってて笑った.
最初A,B,Cをぱぱっと通していこうということでrianがAをサクッと通せば良くない?(結論)みたいな会話が行われrianがAを通す.僕はBを担当したが問題名が「GPAじゃんけん」で2週間後くらいにほんとにGPAじゃんけんすることを思い出して泣く(どうでもいい).Bを通した後にD,Eを読むが無理そうなので葦くんに渡してFをやる.Fは「壁が4つあって実装めんどいな...」って言ってたらりあんに「右下と左上だけでよくない」と言われてコーディング開始.最初dfsで書いてたらバグったのでbfsにしたらxとnxを間違えたり,bfsで訪れたところのチェックミスったりしてTLEやWAを連発しまくるもりあんデバッグしてもらいながらAC.こういうミスをやめたい...
Fでコーディング時間を無限に奪ってしまったのが申し訳なかった...

---懇親会---


~3日目~
---コンテスト---
rian,葦と出てもよかったがせっかくなのでチーム決めに参加した.kawabysさんとRIKAさんとチームckrででた.
とりあえずRICAさんA,僕B,kawabysさんCで...ということになったが問題読んで僕とRICAさんがA,Bを交換.気がついたらkawabysさんがC問題を通しててプロかった.そして僕はAを書くがWAしてkawabysさんに手伝ってもらいながらデバッグするも通らないのでkawabysさんに投げる.D,Eがダイクストラとセグ木かなって話になりセグ木を書き始めるが計算量的に無理だと気が付きkawabysさんに相談すると遅延セグ木と言われたがそんなものは知らないのでDを書き始める.拡張ダイクストラは書き慣れていたのですんなりかけてAC(オーバーフローしたくせにすんなりとは...).RIKAさんがBをとおしてkawabysさんがAをとおして終わり.
Aを投げてしまったのが本当に申し訳なかった...


---帰路---
帰るときに京都によって昼飯を食べることに...四条に行ってみたが「ビジネス街やん!」ってなってぶらぶらしながら昼飯を探し適当にラーメン屋に行ってみる.濃口醤油というのが美味しかった.
京都駅に戻って「抹茶スイーツを食べないと...」という使命感にかられるもどこも人が多くて新幹線の時間に間に合わなさそう....なので諦めかけたら西尾の店に入って抹茶パフェを食べることができた...よかった...


~~~~~~
RUPCとても楽しかったです!運営の方々ありがとうございました!

BCU30に参加したっぽい?

3/11にBattle Conference U30にプロコン枠で参加しました.
(行くぞ~)
浜松町から思ったよりも遠くてお昼ごはんの時間がなくなった...
のでコンビニを探したがなかなか見つけられなくて日の出駅?の近くでローソン?を見つけてお昼ごはんを買う.


(会場到着)
なんか14:00までに入場かと思ってたら13:30らしいという噂もあって遅刻かとおもったけど入れた...

今回のプロコンは3人1チームで2時間で6問を解くことになりチームはmkiken氏,HORI氏とのチームになりました.
とりあえず問題を割り振り、なんか適当に順番に振り分ければいいかってなり
mkikenさん: A,D
僕 : B,E
HORIさん : C,F
と担当し分からなければお互いに教え合うことにしました.

(コンテスト開始)
とりあえず開始したらmkikenさんがAを通し次に僕がBのコーディングするがコピペしたあとにインデックス直しわすれて3WAだしてしまった....

ここでHORI氏がCに詰まっているのでmkikenさんがDをコーディングして通す.僕はEを考えるがO(N^2K^2)の解法しか思い浮かばない...
のでこれを提出してみると2ケースがTLEになるだけなので定数倍高速化で通せるのでは?と判断し高速化を始める.

一旦コーディングを交代してHORI氏がC問題を実装+AC.

Fはどうしようもないと判断しE問題を高速化(cin,coutをやめたりinline関数にしたり...).. 5回くらいTLEした後に残り5分でAC.

(コンテスト終了)
(解説)
どうもEはやはりO(N^2K^2)は想定解でなかったらしい。C++が好きになった.

(起業ブースめぐり)
色々な起業から色々頂く.個人的にサイボウズさんのサイボウズキャンディーが面白かった.
あとabemaTVのシール!abemaTVでアニメ見まくってるので嬉しい

(懇親会)
なんかあちこちから🍣がすごいとの噂を聞いていたらすごかった.マグロの頭が置いてあった...
あとホットドック食べた.ソーセージ2本刺したらなんか嬉しくなった.

(帰宅)
家に帰ったら誰もいなくて鍵も持ってないのでカラオケにいった.楽しかった


(___)
プロコンしてたのでバトルトークみれなかったのが残念だった...
いくつか見たかったのあった...