怠惰の累積和

技術/競プロ/怪文書/虚無

JOI 2019/2020 一次予選 (第2回:10月27日(日))

はじめに

お疲れさまでした。6:08で全完でした。以下いつものように解法をば...



A - 試験 (Exam)

問題概要

　3回分の試験の得点が与えられる。成績は3つの内大きい方から2つの和で決まるから、大きい2つの点数を足した値を出力せよ。

問題URL

解法

　愚直にif文を書いたり任意の2得点の和の最大値を出力したりしても良いが多分3つの総和から最も小さい得点を引くのが最も楽。所要時間27秒。(以下ソースコードはmain関数のみ)

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	cout << a + b + c - min({ a,b,c }) << endl;
}



B - 文字列の反転 (Inversion of a String)

問題概要

　文字列SのA文字目からB文字目までを反転させるとどのようになるか。

問題URL

解法

　適当にやる。具体的には前から出力する区間2つと反転させる区間との3つに分けて出力してやる。添え字に注意する。所要時間2分39秒。

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	--b; --c;
	string h;
	cin >> h;
	for (int i = 0; i < b; ++i) { cout << h[i]; }
	for (int i = c; i >= b; --i) { cout << h[i]; }
	for (int i = c + 1; i < a; ++i) { cout << h[i]; }
	cout << endl;
}



C - 最頻値 (Mode)

問題概要

　要素数Nの数列Aから数列Bを新たに生成する(生成規則書くの面倒すぎるので割愛)。Bの最大値は幾らか。

問題URL

解法

　Aの要素を順に見て行き、各要素がどのくらい登場したかを記録しておく。後はその中での最大値を取ればよい。所要時間3分2秒(焦ったせいで変数名が(いつもだけど特に)適当になってしまった...)

int a, b, k[105], ans[105], aa;
int main() {
	cin >> a >> b;
	for (int i = 0; i < a; ++i) {
		cin >> k[i];
		++ans[k[i] - 1];
	}
 
	for (int i = 0; i < b; ++i) {
		aa = max(aa, ans[i]);
	}
	cout << aa << endl;
}

CodinGameを1週間やってみた

CodinGame、なに

　プログラミングでゲームをプレイする感じのサイト。説明が下手。まあやればどんなのかは分かると思います。URLこれ。定期的に大会も開かれているらしい。

www.codingame.com

　第2回高2駿台全国記述模試の前日に存在を知って勉強を止めてずっとCodinGameしてた。なおCodinGameとか打つの面倒なので以下こどげと表記。

 

1週間　なにした

　こどげはかなりたくさんのゲームがあり、1つ1つきちんと練られている感があるのでやってて楽しい。なのでひたすら色々なゲームをプレイしていた。全部に触れているとキーボードを打つ指が死ぬので主要っぽいものだけまとめ。

　

ⅰ)Coders Strike Back

　レーシングゲームで自機の動きをプログラミングする競技。これも説明が下手。まあやればどんなのかは分かると思います。

f:id:severrabaen:20191019234411p:plain

なんかこんな感じで旗っぽいのが描かれてる丸から1、2、3の順に巡って行って旗に戻るを3回する競技

　リーグが分かれてた。

f:id:severrabaen:20191019234800p:plain

Wood3→Wood2→Wood1→Bronze→Silver→Gold→Legend

　1週間でSilverリーグまで到達した。Woodの3から1は適当にやったら通って、Wood→Bronzeはちょっと応用効かせてローカルでテストしまくって通した。Bronze→Silverは割と大変だった。Steering Behaviorsってのを知って勉強して使った。

　最終的に世界9272位、日本国内76位になった。

f:id:severrabaen:20191019235234p:plain

国内ランキング

f:id:severrabaen:20191019235348p:plain

世界ランキング

 

ⅱ)CLASH OF CODE

　短い時間(15分位?)で競プロの問題を同じ部屋の人と競争して解く競技。部門は3つに分かれていて、始まるときにランダムで選ばれる。1つは速さ重視の部門で、普通の競プロチックなやつ。もう1つはコードの短さを競う部門。要はコードゴルフ。制限時間内にACすれば時間は順位に影響しない。そして最後に、問題文は与えられないが、入力例と出力例が与えられるので何をするコードを書けばいいのか推定してACを出す部門がある。これは速さ重視。たまに天才発想要求問が出てきてキレそうになった。思いつきませんが...

　なんか面白いので適当にやってた。記録によると50回くらいやったらしい。

　最終的に世界239位、日本国内9位になった。

f:id:severrabaen:20191020000535p:plain

国内ランキング

f:id:severrabaen:20191020000643p:plain

世界ランキング

 
　なんか上のみたいなゲームとかの成績に応じてポイントが貰えるらしい。これもランキングがある。順位に応じて称号的なのが貰える。今のところMentor(全体5000以内)。

f:id:severrabaen:20191020200719j:plain

f:id:severrabaen:20191020200903j:plain

あと1000人くらい抜かせばMasterっていうのらしい

f:id:severrabaen:20191020201113j:plain

1週間のランキング推移。大体1日毎に順位が更新されるらしい

 

　おわり。相変わらずの10分クオリティーの怪文書。 

AtCoder Beginner Contest 112 C - Pyramid

問題概要

　中心座標(C_X,C_Y)、中心の高さHのピラミッドがあったが、それらの値はわかっていない。座標(x,y)でのピラミッドの高さはmax(H-|C_X-x|-|C_Y-y|,0)で与えられることがわかっている。

　N個の「座標(x_i,y_i)でのピラミッドの高さはh_iであった(1≦i≦N)」という情報が与えられるとき、(C_X,C_Y)及びHを求めよ。

atcoder.jp

 

解法

　入力の制約に「ピラミッドの中心座標と高さをちょうど1つに特定することができる」とあるため、N個の情報の内、少なくとも1つはh_i>0となる情報が存在することがわかる。つまり、そのh_iはmax(H-|C_X-x|-|C_Y-y|,0)で計算されるがH-|C_X-x|-|C_Y-y|>0となっていることになる(そうでなければh_iは0になっているはずである)。

　よって、H-|C_X-x|-|C_Y-y|=h_iの式を変形すると、H=h_i+|C_X-x|+|C_Y-y|となるため、(C_X,C_Y)が判明すればHも判明する。

　0≦C_X,C_Y≦100であることが保証されているため、(C_X,C_Y)は全探索することができる。よって、(C_X,C_Y)を全探索して、そのループの内部で各情報について、それと上式での計算結果が正しいかどうかを判定してやればよい。

atcoder.jp

AtCoder Beginner Contest 142 D - Disjoint Set of Common Divisors

問題概要

　正整数A,Bの正の公約数の集合から任意の2つについて互いに素になるように要素を選ぶ時の要素数の最大値を求めよ。

atcoder.jp

 

解法

　まず、A,Bの公約数を全列挙する。これはA,Bのgcdの約数であるからgcdを求めた後にO(\sqrt{N})(NはA,Bのgcd)で求められる。

　この中から任意の2要素が互いに素となるように選ぶためには、素数である要素を選べばよいから、先ほど求めた集合を順に見ていくことで答えとなる数が求まる。

atcoder.jp

第一回日本最強プログラマー学生選手権決勝 A - Equal Weight

問題概要

　N個のシャリとM個のネタがある。それぞれには重さ(それぞれA_i,B_i)が割り振られており、シャリ1つとネタ1つで握りが1つ完成する。重さが同じ2つの握りを構成する方法があるなら示し、無いなら-1を出力する。

atcoder.jp

 

解法

　最初に十分な要素数を確保したpair型の配列を用意しておき、(-1,-1)等配列のindexとして存在しえない数値で埋めておく。

　次に、2重ループを回し、それぞれのシャリとネタの和のindexの要素を見て、初期値で無ければ既に今見ているシャリとネタの和と同じ重さの握りが存在することになるから適切に出力して終了。初期値だったら和のindexにシャリとネタのindexを格納する。最後まで見つからなければ-1で終了。

　一見O(NM)に見えるが、実際は2*10^6回の計算で終了する。1≦A_i≦10^6,1≦B_i≦10^6より、あり得るシャリとネタの和の範囲Wは2≦W≦2*10^6(なので最初に述べた十分な配列のサイズというのは2*10^6くらいが望ましい)。それぞれの和の候補について、上記のアルゴリズムでは高々1回しかアクセスしないため、最悪ケースでも2*10^6回しか見ないことになる。

　よって、上記を実装して、AC。

atcoder.jp

AtCoder Regular Contest 059 D - アンバランス / Unbalanced

問題概要

　文字列Sの部分文字列で、過半数がある１つの文字で構成されているようなものは存在するか。あるならその位置を示せ。

atcoder.jp

 

部分点解法(2≦|S|≦100)

　全探索をする。任意の２か所について見るのにO(N^2)、その内側で適する文字列かどうかを判定するのにO(N)。よって全体でO(N^3)で部分点は獲得できる。

 

満点解法(2≦|S|≦10^5)

　ある文字列が答えの条件を満たす文字列の場合、その部分文字列内には必ず"AA"(Aは任意のアルファベット１文字)か"ABA"(BもAと同じく任意のアルファベット)が存在する。

　このような文字列が存在しなければ、あるアルファベットで挟まれた部分文字列はその間にそれ以外のアルファベットが2つ以上存在することになるため、どのようにしても過半数という壁を超えることはできないからである。

　よって、Sを前から見ていって、"AA"か"ABA"に合致する部分文字列が存在すればその部分文字列は必ず過半数の条件を満たしているから出力すればよい。

　上記を実装して、AC。O(|S|)。

atcoder.jp

PCK2019 予選参加記

はじめに

 　2019/9/14 13:30(JST)から行われたPCK2019に僕とBwambocos(@babcs2035)の2人でチーム「Rate-Mikan」で出場しました。結果から言うと、8完2WAでした。以下に競技開始の少し前からの流れを大まかに書いていきます。尚、記憶が曖昧な為、もしかしたら時系列がぶっ壊れているかもしれないです。なので簡単に矛盾点を見つけられるかもしれないです。あとこれはいつもの事なんですが、脳死状態で文章を書いているので誤植がINF個ありそう。あとあと、Bwambocosっていちいち書いているのが面倒なのでBwamと略します。

 

競技開始前

　当日は文化祭だったが、競技開始1時間くらい前から部活の展示担当をサボり、蟻本を朗読したり、PCKの過去問を鑑賞したり予選下馬評の会場を見て「予想でもKMB86強いな～」と思うなどしていた。競技開始40分くらい前になり、コンピューター部の展示部屋から戦いの教室へプリンターとかPCとか考察用紙とか必要なものを運び込んだ。10分くらい学校のWifiに繋がらないトラブルがあり、キレた(Wifiを管轄している学校の部署を呼んで直してもらった)。

 

競技開始

　競技が開始されたので、前日に立てた作戦通りに、まずはDとEを印刷して、Bwamに渡す。僕はその後Aを見る。音読用の問題背景の文章を読んでいたら10秒くらい過ぎました。ただの加算なので書いて(PCKでは同完数内ではまずWAの数でソートされるので一応)テストケースを全部試して提出した。開始したばかりでジャッジが詰まっており、中々結果が出ない。まあ合っているだろと思いBを見る。

　場合分けコンテストであることが自明なので書く。書いてる途中で若干頭が無くなりよく分からなった(は?)。書いたので提出。

　Cを見る。えぇ。ただの2冪数の全探索なので書く。書いた。提出。ここでAとBがACな事を知る。しばらくしたらCもACだった(ジャッジが遅すぎる)。まあここまで0WAでよかった。

　BwamがDとEを見終えたのでPCを渡す。その際にFとGを印刷して、僕はFを見る。載っている図がgcdの説明でよく見る図みたいだなあと思った。各正方形の長さはフィボナッチ数列になって増えていっていることは分かるし、横方向と縦方向を分けて考えて良さそうかも。ただ縦横それぞれについて正負で大分規則性が違いそうだなあとなる。

 

えー

 

　なんか詰めきれないのでGを見てみる。lcm必須案件なことが分かる。当然答えの上界は2^N-1になるし、1≦N≦20なのでそこまで大きい数にはならなそうだからこの数からあり得ないケースを引いていって答えを求める方針で行きたい気持ちになる。

　BwamがDとEを提出。どっちも結果がすぐに返ってこない。BwamもFを見る。よく覚えてないけど2人して分からなくなった。4方向に分けて累積取って1足すと境界値になることは分かったりしたが所詮1次元での話なので今回の問題では意味がない。

　DとEはACだったらしい。同率1位。

 

　分からないのでFを飛ばした。G。ソートして順にLCM取っていけばよくない?となる。通す。

　Hを見る。なんか右端左端に寄せるのでよさそうってBwamが言ったけど、駒が追い越しできないことを完全に見落としていた僕がよくわかんないことを言ってしまう。ごめんなさい。確かにあなたの言う通りです。

　HができそうらしいのでIを印刷する。見る。幾何です。しかも3次元。なにこれ。とりあえず1人で考える。太陽と天空の城ツガル(この名前、怒られそう)のz座標が与えられていて、地面はz=0なので、ツガルが地面に作る影の領域は相似を使ってN時間かけると求められそうだなあとなる。

　出来た多角形内の適当な1点を選び、与えられるQ個の点それぞれについてその点と先ほど選んだ点を結ぶ直線と多角形の各辺の線分交差判定をすれば解くことはできそうだけどO(NQ)になり、確実にTLEしてしまう。

　多角形に点が含まれるかどうかの高速な判定ができれば勝てそうとは思ったので蟻本を開くけど無さそう。

　その頃BwamがHを提出する。WA。僕はI、BwamはHを考える。順位表を見ると、Iの提出率及び正解率が異常だった(はず)。魔境なのか?とは思ったけどワンチャンいけるので考える。Bwamが改善したHを提出する。WA。しかしforで探索する範囲を間違えて1つ少ない探索をしている説が浮上し、試しにそのような選択が最適であるケースを作って実験する。答えが異なるので探索範囲を変えて提出。AC。はいプロ。

　Iを2人で見る。Bwamも3次元ヤバいとか言ってた気がする。順位表を見てIを飛ばさない?というような空気になる。

　僕がこのセンスのない絵を描いてIの考察が終了した。

f:id:severrabaen:20190914214423j:plain

　なんか配点が同じだった(気がする)ので一応JとKとLを印刷する。たまに2枚目が白紙で出てくる。なんなのこれ(仕様なんですけどできれば問題PDFに白紙を追加しないでほしかった)。

　Lは問題名を見て来年はダンジョン4という問題が出ることを期待して読むのを止めた(PCKではこの3年連続でダンジョン1、2、3という問題名で問題が出ている)。

　Jを見るとグラフ問にならないかなあとかいう発想が生えた(なんか有効辺張って色々やればできそう)。Bwamも同じことを思ったらしい。ただ、Nは2冪じゃないし色々面倒だなあとなる。

　ここで時計を見ると残り時間が約30分だった。上記の通り現在は7完。順位表を見ると8完チームがまあまあ多いため、これは8完しないとヤバそうという感じになるため、Fを見る。4方向に10^6以下のフィボナッチを分けると1つ当たり高々9つになることが判明したため、シミュレーションできそうとなる。whileで回してひたすらシミュレーションする処理をBwamが書く。僕は横でデバッグ用の諸々を用意していた(ちなみに用意していたこれ、一部ミスっていた(ア(まあ後で割とすぐ気づいた)))。デバッグする。なんか挙動がおかしい。見た感じwhileの条件が間違ってそうと思ったので指摘してみる。違った。書き直す。デバッグ。合ってるっぽい。提出時間切れになるよりは提出した方が良いのは明らかなので提出。

 

 

。

 

。

 

。

 

 

 

AC。

　この時点で残り時間が12分くらいだったので他の問題を通すことは無理だろうと判断し(9がエグいのが割と堪えた)、もう凍結されている順位表を見たりしていた。凍結されている順位表では7完0WAで19位だった。8完になったのでもう少し上になっていてほしい感がある。

 

競技後

　16:30になり、競技が終わった。監督をしていた顧問と若干話したが文化祭での生徒の強制下校時刻が迫っているので話も早々にまたプリンターやPC等を持って民族大移動をした。

　コンピューター部の展示部屋に戻ると順位が実況されていた(去年はホワイトボードには書かれてなかった気がするけど)。尚、636チームになっていますが、本当は701チーム(単純に実況する人が0完が何人いるかを見ていなかったらしいので0完同率が圧縮されているから)。

 　差し入れとして置いてあったお菓子を食べて(某きのこと某たけのこもあったけどたけのこ派なのでたけのこを食べた)、適当に片づけをして、学校を出た。

　夕食を新宿で食べた。当初焼き肉の予定だったけど急遽ロイヤルホストになった。黒×黒ハンバーグというものを食べた。美味しかった。

 

おわり。