JOI本選'21 敗退記

JOI人生も今日で終わりです。委員会の皆様3回と5年間ありがとうございました。

挙動

1番を開く。とりあえず山の頂点を固定してやればよさそう？

->左を単調増加にするにはX回必要で.. .みたいなのを求める

->真っ赤な嘘で1時間近く溶かす

仕方ないので2番に行く 床を動かすイメージを作ると解けてしまった。 1:14:53 AC

1番の解法が思いつく。確かに階差取れば終わりだ 1:24:20 AC

3番を見る。「順列は挿入DP！」というわけで挿入DPを疑うと，挿入の条件が厳しいので解法が生える。 配列外参照でWAを出すが修正して無事AC

2:08:38 AC

4番を見る。適当に周りの色を管理しながらダイクストラをすればいいのでは？と嘘を書き，結構な時間を溶かす。 結局0点で5番を見る。小課題1はダンジョンそのものだったので解法を検索し，少し考え直すと解けた。 priqueと遅延セグ木を書くとTLEし，20分ほど格闘したがTLEが取れず0点。

というわけで300点です。何だかなあ...

JOI 2013本選4 JOIOIの塔 遠回りな解法

遠回りな解法で解いたので，記録します。

共通考察

JOIとIOIは「OI」の部分を共有しているので，OIから考える。

まず，OIの「I」の部分はできるだけ後ろから取っても損しない。 (ここを前に残しても選択肢が少ないので)

そして，OIの「O」の部分は各「I」より前にあるもので，「I」に最も近いものを取ればよい。(同上)

また，「OI」グループはOが後ろにあればあるほど使いやすい。

想定の賢い方法

「OI」を何個使うかで二分探索して，JとIを適当に結合させる。

Rhoの賢くない方法

「J」とOIに結合できなかった「I」のindexの集合を とし，「OI」の「O」のindexの集合を とする。 の小さい方から何要素かを から削除し，各「O」に付随する「I」のindexをそれぞれ に挿入する。 そうして作った と で となるようにマッチングを組むとき，最大で何本組めるか？という問題になる。

から1要素削って に追加した時，減るマッチングはYの要素が減ってあぶれた高々1個である。また，1要素増えることもある。よってこれは凸関数で，三分探索ができる。 計算量がちょっとやばめだが，通る。

感想

想定解賢すぎるだろ

JOI2020予選敗退記

ああああああゴミカスーーーーーーーーーーーーーーーーー

100+0+43+100+7=250です

非公式順位表見た感じだと門番の位置です。追い出されるか入れるかどうか...

コンテスト中のムーブ

カス

最初10分

Aを見る。いつもより難しくない？と言いながら現在地の左右で分けて実装。O(N)

この時点で0:08:02

▶クリックで展開

#include <bits/stdc++.h>
#include "atcoder/all"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> P;
constexpr ll inf=1ll<<61;
constexpr ll mod=998244353;

int main(){
    int n,a;cin>>n>>a;
    string s;cin>>s;
    deque<int>Q1,Q2;
    rep(i,n){
        if(s[i]=='#'){
            if(i<a)Q1.push_back(i);
            else Q2.push_back(i);
        }
    }
    ll ans=0,cur=a-1;
    for(int i=0;;i++){
        if(Q1.size()+Q2.size()==0)break;
        if(i%2==0){
            if(Q2.size()){
                ans+=Q2.front()-cur;
                cur=Q2.front();
                Q2.pop_front();
            }
            else{
                ans+=n-cur;
                cur=n;
            }
        }
        else{
            if(Q1.size()){
                ans+=cur-Q1.back();
                cur=Q1.back();
                Q1.pop_back();
            }
            else{
                ans+=cur+1;
                cur=-1;
            }
        }
    }
    cout<<ans<<endl;
}

間100分

Bを見る。 何これ。 下の方はいじらずに済む、ランレングス圧縮すれば同じ... などと色々考えてみるも全く分からない。困ったのでCを見る。何これ。 一見DPだがよく見ると不可能そうに見える。Dを見る。 自明。 とりあえずBを考えるだけ考えると、以下のような解法 (※嘘です！！！) が思いつく。

• 操作を逆から見ても、先頭からある部分までをひっくり返すという動作は同じである。
• 後ろの方の一致している部分はいじらずに済むので、その部分は適宜切り捨てる。
• 同じ文字をつないでいるところを切っても嬉しくないので、操作回数はランレングス圧縮した後の文字列-Xである。このXは完成時の文字列に異なる文字の接合部がどれだけ入っているかによって決まる定数である。

これを実装するとサンプルが通るので投げる。WA。 (0:56:35)

少し列挙してみると、ACBのようなケースでバグることがわかる。確かに前後の情報までは持てないので、諦めてDへ行く。

Dを見た瞬間二分探索がわかるので、書こうとする。実装することは単純だが、打ち切りの条件や計算量削減のために複数人をまとめて処理するパートで頭が破壊され、バグにバグを重ねて書き上げたのは 1:51:49 の時点だった。書いている途中は「このままだと2回予選に通って尚且つ黄色コーダーなのに予選100点という情けない成績で最後のJOIを終えてしまうかもしれない......」と焦りに支配されていて、まともにコードが書けなかったように思える。

デバッグ用に上限を100にしていて1ペナを食らうが、再提出したら無事に通った。70分を残して200点を取れたので、ひとまず再起可能であることを信じて安心する。

▶クリックで展開

#include<bits/stdc++.h>
#include"atcoder/all"
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
typedef vector<ll> vi;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
constexpr ll inf=1ll<<61;
constexpr ll mod=998244353;
ll a[100006],b[100006],cpb[100006];
int main(){
    ll n,k;cin>>n>>k;
    rep(i,n)cin>>a[i];
    rep(i,n)cin>>b[i];
    ll lb=0,ub=2e18;
    while(ub-lb>1){
        ll mi=(ub+lb)/2;
        ll res=0;
        rep(i,n){
            if(a[i]>=mi)res++;
            cpb[i]=b[i];
        }
        if(!res){
//         cout<<"-----"<<mi<<endl;
            int now=0,cur=-1;
            ll nk=0;
            while(now<n){
                ll tm=0;
                cur=-1;

                do{
                    if(cur==-1)tm+=a[now];
                    else tm+=a[now]-a[now-1];
                    if(tm>=mi){
                        nk++;break;
                    }
                    ll d=mi-tm;
                    if(cpb[now]<d){
                        tm+=cpb[now];
                        cpb[now]=0;
                        cur=now;
                        now++;
                        if(now==n){
                            nk++;break;
                        }
                    }
                    else{
                        cpb[now]-=d;
                        nk++;
                        if(cur==-1&&d){
                            nk+=cpb[now]/d;
                            cpb[now]%=d;
                        }
                        if(cpb[now]==0)now++;
                        break;
                    }
//                 cout<<nk<<' '<<tm<<endl;
                }while(tm<mi&&now<n);
            }
//         cout<<nk<<endl;
            if(nk>k)res++;
        }
        if(res)lb=mi;
        else ub=mi;
    }
    cout<<ub<<endl;
}

ラスト70分

ノータッチだったCをよく読むと、43点まではセグ木で取れることが分かったので、適当な提出からセグ木をコピーしてきて書き始める。DPの境界を合わせるのに苦労し、何とか2:27:17 時点で43点を獲得。このまま100点を目指しても時間が無いと思ったので、あらかじめ見ておいたEの自明部分点をお守りに取りに行く。焦りからか大量の誤読を発生させ、書きあがったのは 2:44:25時点だった。この時点で250点だったので、最後を信じてCへ戻ると、N<=4000制約の残り35点がすぐに思いついた。10分で書けるところまで書こうとしたものの、ちょうど全体像が書きあがった時点でタイムアップとなってしまった。

コンテスト後

全完や407点、300点台も大量にいたので半ば諦めていた。実際に今も半分諦めている。

もうどうにもならん

競技くそなぞなぞerとして考えていること

この記事は、くそなぞなぞ Advent Calendar 2020 の2日目 (12/1 不在により実質1日目) の記事として書かれました。

自己紹介

くそなぞなぞコンにたまに参加しているRyotori と申します。現在のレートは1501です。

この記事では、くそなぞなぞの問題に共通する特徴をピックアップして難易度別に分類・整理することを目標とします。ネタバレを存分に含むのでご注意下さい。

言い換え (100 pt. ~)

くそなぞなぞの基本かつ根源です。全てのくそなぞなぞは言い換えによって成り立っていると言っても過言ではありません。以下の例を見てみましょう。

壊れて動かなくなった調味料ってなーんだ？ (くBC 010-A 100pts)

「壊れて動かない」を「故障」と読み替えれば答えは「こしょう」だとすぐにわかるでしょう。

そこそこ頻繁に見るテクニックとして、英語への言い換えがあります。

古典的な病気の倉庫ってなーんだ？ (くSC-C 300pts)

「古典的」を 「Classic」 に、「病気」を「Sick」に変換することで「くらしっく」が見えます。実際はどちらか片方の変換さえ気づけばほぼ解けるでしょう。

言葉の一部を改変 (200 pt. ~)

このタイプの問題も多く、他のテクニックとも組み合わされやすいです。

逆らうハンコってなーんだ？ (くBC004-B 200pts)

言うまでもなく答は「はんこう (反抗)」です。このタイプの問題の注意点として、問われている対象と答えが一致しないことが非常に多いことです。

実際にこの問題でも、質問の対象はハンコですが回答はハンコではないものとなっています。

検索&全列挙 (400 pt. ~)

いらすとやが原因で起こった大火災ってなーんだ？ (くRC001-D 700pts)

「いらすとや」が気になるところですが、まず「大火災」から考えてみます。

有名な大火災があるのでしょうか、「大火」で検索してみるとWikipediaのページが見つかります。すると以下のような記述が...

1657年3月2日（明暦3年1月18日） - 明暦の大火。江戸(現在の東京都)で発生した大火。江戸の三大大火の1つ。 別名振袖火事。死者推定6万名以上。

ここで「いらすとや」が繋がってきて、「フリ素」と言い換えればよさそうです。結果答えは「ふりそでかじ(フリ素で火事)」となりました。

対象が限定しやすいもの、範囲が限られるものであればWikipediaの一覧ページを用いて全探索するのも一つの手段として通用します。他にも国名を問うような問題でも検索して列挙するのが有効だと思われます。

単語パース (500 pt.~)

雨を避けることを法で禁止されている親友ってなーんだ？ (くBC006-E 500pts)

酷い問題だ

問題文が怪文になっている場合、以下のように問題文中の各要素をひとつずつ言い換えてあげる必要があります。今回の例では、

「雨を避けることを」→「傘」

「法で禁止されている」→「違法」

「親友」→「知己」

と分解し、つなげることで「かさいほうちき」となります。このような出題のされ方では答えとなるものが問題文で問われているものと離れたものになりがちですが、くそなぞなぞなので問題ありません。 (実際に、火災報知機は親友ではありません)

解説放送での呼称から「青梗菜メソッド」と呼ばれることもあり、作問においても有用なテクニックの一つです。

要求語彙 (500 pt. ~)

花や枝を取る布製品ってなーんだ？ (くBC003-E 500pts)

どちらから攻めても解答まではすぐですが、「手折る」という動作を知らなければ永遠に答えは出ません。

3級の童謡ってなーんだ？ (くBC004-F 600pts)

「3級」→「ターシャリー」、「童謡」→「nursery rhyme」の二重の言い換えを経て答えは「たーしゃりーらいむ」ですが、このように前提となる語彙が難しい場合答えにたどり着けないことも多々あります。

さいごに

このようにレベル感とともに分類しましたが、結局は閃きが結果を左右します。語彙を増やすのが恐らく一番有効な手段だと思います。

くBCもっとやってほしいですね

PCK2020 もうひとつの本選 参加記

PCK2020もうひとつの本選に参加して、11完76点でもうひとつの本選内1位でした。PCKは同校制限を撤廃しろ

もうひとつの本選優勝です！ ありがとうThistle！ pic.twitter.com/P4tLkREIGj

— †ρ (@Rho4913) 2020年11月14日

本選3位相当です。(2位が86点、3位が変わらず75点)

相方の記事はこれ

thistleprogram.hatenablog.com

戦略&タイムライン

とりあえずThistleに前の方見てもらう。その間にぼくが4番以降の傾向を一通り確かめる。

この時点で機械的にThistleに7番と8番を振り、自分は6番と10番の幾何+9番のad-hocを回収することにする。

Thistleが8番を通してくれた後はグラフとデの11,12,(13)のうち好きなのを持って行ってもらった。そうしたらなんか12を通してきて、その後で11も通してくれたので大感謝　13はちょっと考えてすぐに捨てたらしい

結局割り振りは以下のようになった。

Rho: 4,5,6,10,(9)

Thistle: 1,2,3,7,8,11,12

0:02:50 問題1 AC

0:05:33 問題2 AC

0:12:09 問題4 AC

0:13:49 問題3 AC

0:16:41 問題5 AC

0:52:41 問題7 AC

1:26:15 問題6 AC [ペナ1]

1:31:28 問題8 AC [ペナ1]

1:59:15 問題10 AC ←？？？？？？？

2:50:40 問題12 AC [ペナ4]

3:40:46 問題11 AC [ペナ2]

やったこと

10番で区分求積を投げたら通りました (あの！？) TL見た感じ誤差がキツイようでしたが私は 分割したので特に苦しみませんでした

▶クリックで展開

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
#define double long double
double x[3],y[3];
const double h=0.000025;
double andlen2(double p1,double q1,double p2,double q2){
    double res=min(q1,q2)-max(p1,p2);
    return max((double)0,res);
    }
double andlen3(double p1,double q1,double p2,double q2,double p3,double q3){
    
    double res=min({q1,q2,q3})-max({p1,p2,p3});
    return max((double)0,res);
    }       
int main(){
    double r;cin>>r;
    rep(i,3)cin>>x[i]>>y[i];
    double ymin=min({y[0],y[1],y[2]})-r;
    double ymax=max({y[0],y[1],y[2]})+r;
    
    double ans=0;
    for(double Y=ymin;Y<=ymax;Y+=h){
        double p[3],q[3];
            q[0]=sqrt(max(r*r-(y[0]-Y)*(y[0]-Y),(double)0));
            p[0]=-q[0];
            p[0]+=x[0];q[0]+=x[0];
            q[1]=sqrt(max(r*r-(y[1]-Y)*(y[1]-Y),(double)0));
            p[1]=-q[1];
            p[1]+=x[1];q[1]+=x[1];
            q[2]=sqrt(max(r*r-(y[2]-Y)*(y[2]-Y),(double)0));
            p[2]=-q[2];
            p[2]+=x[2];q[2]+=x[2];
        double d=q[0]+q[1]+q[2]-p[0]-p[1]-p[2]-andlen2(p[0],q[0],p[1],q[1])-andlen2(p[1],q[1],p[2],q[2])-andlen2(p[2],q[2],p[0],q[0])+andlen3(p[0],q[0],p[1],q[1],p[2],q[2]);
        ans+=h*d;
    }
    printf("%.11Lf\n",ans);
    
}

10通した後はずっと9でくすぶってました　辺を貼るという発想が無かった...

感想

ありがとうThistle

もうひとつ優勝したんだしなんか商品くれ～

PCKは同校制限を撤廃しろ

PCK2020 予選敗退記

ま～た同校制限かよ こわれるなあ

9/12(土)のパソコン甲子園にチーム「アザミ工場」で参加してきました。今年も本校からは合計4チーム出ていて、全員黄色以上なので何とかして打ち破らねば本選へ行けません。

今年の戦略

今年は2台のPCが使えるので、若干無茶ができます。

最初に1~5は相方Thistleに任せた。そして私は6以降に目を通し、機械的に分配した。その結果私は6,9,11を、Thistleは7,8,10,12を担当することとなった。

タイムライン？

私が6で苦戦していると、Thistleが1～5を書き終えたので一通りまとめて出してもらう。その結果1でCE, 4と5でWAが返ってくる。(ペナ+3)

1と5はすぐに治ったが、4が正しいようにしか見えなかったのでdefineの悪さを疑い、私が代わりに書くとなぜか通った。その後何とか6を通し切り、9の考察を始める。

最初に幾何的考察を試みるが、どうもうまくいかない。ここで制約を見て方針転換すると、各格子点を頂点とするグラフのダイクストラ法が適用できることに気づく。 として頂点数が [tex: O(N²)] で辺数が[tex: O(N³)] なので適当に書いて出す。→TLE

真面目に計算すると頂点数は約90000で辺数は90000600で5.410⁷, doubleの計算もあるので間に合うわけがない。また少し考察すると、スタートとゴールのbounding boxより外へ行く移動は無駄だとわかるのでそれを適用する。→TLE

また、いったんゴールに近づいてまた離れる移動も無駄であることもわかる。→TLE

ここで定数倍高速化としてintをshortに、doubleをfloatに変えるなどあがいてみるがTLE。その間にThistleは7, 8, 10をペナルティ1で通し切っていた。このままでは4と6だけしか通してない実質マスコットになってしまうと焦る。

さらに考察をすると、スタートからゴールまで直線で行ったときに x=(整数) やy=(整数) の地点とぶつかるような点の付近で曲がるのが最適だとわかるので、交点の近傍だけを採用して辺数を減らすことにした。 近傍のパラメータを調整し続けて、終了10分くらい前にWAとTLEの間のACを無事掴み取ることができた。そこまでに要したペナルティは 13回！ これぞ執念...

結果

Thistleは結局12を通せず、10完74点で終わった。全体で見ればよい成績なのだろうが、他の3チームが11, 11, 10完だったので負けは自動的に確定する。悲しい...

感想

同校制限なんとかして(N回目)

PCK2016 Virtual

Thistle 今までPCKで煽っててごめん

今回はチーム戦をしました。

結果

ooooo ooooo 全完100点 (154分, ペナルティ1)

ムーブメント

今回は相方に最初の5問を解かせ、その間に6~10を機械的に割り振って分担しました。私は7番と8番を担当しました。

問題について

1~5は無なのでどうでもいいです。

6は見た瞬間DPが見えて、よく考えたら貪欲が行けるかもしれないと思いましたが面倒なので相方にやってもらうことにしました。

7は文字列で、一瞬ロリハかと思いましたがそうではありませんでした。文字列なので一応自分で回収しましたが、実際は超典型DPでした。

8は幾何が見えたのでこれも回収しておきました。凸包を書くのが1年半ぶり... あと問題文許してない

9はデータ構造なので投げました。10はDPとフローを半々で疑っていましたが、相方がなんか解いてくれました。

問題の問題について

8番の日本語が壊滅的に読みづらく、題意を理解するのに20分かかりました。

具体的には、「境界線をできるだけ短く」「すべての集落の間を行き来できる状態を維持しつつ、境界線上にない道を廃止する」と書いてあるのに求めるものは「境界線上に道を置き、かつ、すべての集落が行き来できるようにした場合の、道の長さの合計の最小値を計算する」ものなのでとても混乱しました。

ついでに10番も

「アイテムは所持金が十分であれば好きな時刻に好きな数だけ購入することができますが、残っているアイテムの中で番号が小さいものから順に選ばなければなりません。各アイテムは１度購入すると消滅します。」 とあるのですが、同じアイテムを複数買ってもよいように読み取れてしまう(かもしれない) ので、これも個人的には嫌です。

なんで数学的に問題文を書かないんでしょうね？