いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

ACPC2017Day3参加記

AIZU ONLINE JUDGE

起床ACした、もう勝ったも同然

Yazaten氏(@Yazaten)とらてあ宅で二人で出ました
チーム名は某氏のaotenjouを意識してyazatenjouで出ました
ABCD4完16位でした


Aを僕が、DをYazaten氏が、その後は随時って方針で
これ結構よかった説

A.A-Z-
文字列の大小比較をして現在のマス<=次のマスならインクリメントしといた
こんな簡単でええんかホンマか?って思って不安だったけど投げたらAC、まあはい

B.えびちゃんと数列 - Ebi-chan and Integer Sequences -
三角形みたいなの書いて反転分を2倍して同じ数字を加算して求めようとしてた
三角形が微調整が必要とか頭を抱えていた
Yazaten氏がDを通してくれたので相談すると、なんか別の方針を投げてくれてそれなら解けそうだと思う
とても辛いが、何とか等差数列で表せることが分かった
しかし愚直に求めるとTLEが見えるので考えて、適当に等差数列の和をググって式を作る
僕は辛いので途中まで考えて、コーナーケースとか投げてYazaten氏にお任せ

C.たったひとつの部分列 - Unique Subsequence -
簡単そうって思ったけどわかんない
全探索をするより良い方法が思いつかなくて、辛い
多分全探索のループ回数が10^5-1までの和とか、おわおわり
うーんうーんって悩んでたらYazaten城がB問題をWAしており、問題概要を伝えた
しばらく虚空を見つめ霞を食べた
唐突にYazaten城から解法が降ってきた
f:id:ratetion:20170921015932p:plain
前から取ったインデックスと後ろから取ったインデックス比較すればいいとの事、聞いた瞬間ACした、もちろん嘘だ
実装を任せてくれるとの事で、フォローもらいつつ実装、スタックを久々に使ってツライだね
なんとかなったのでAC

Bに戻って2人でツライした
コーナーケース探して、式を見直して、mod確認とかして、場合分けし直して
こんなケースはどう?って投げまくってたらmod取れてないケースがあった
場合分けした時の数値がそのままだった
modを取ったらAC

残り時間は45分で、後半の3問を眺めてどれもどうとか話してた
G問題が無茶苦茶楽しそうだったので考察でも練り続けたい
お疲れさまでした


Codeforces Round #431 (Div. 2)

Dashboard - Codeforces Round #431 (Div. 2) - Codeforces

出ました、ミクさん回と言う事で各問題のタイトルがミクさんの曲でした

A.Odds and Ends
ハイ名曲
数列を奇数で始まり奇数で終わる奇数個の部分列に分割してくれって問題
よくよく考えたら分割しなくても1個成り立てばよいことがわかるので奇数で始まり奇数で終わる奇数個の数列が与えられたらYesを出力したらいいっぽい
時間はかかってしまったし読解が難しかった


B.Tell Your World
ハイ名曲
座標がいっぱい与えられるけど、それの全ての接線を2本平行なものだけ引けるか判定しようって感じ
時間かけて考えたら、与えられる座標は必ずx座標が1ずつ増えるので、隣接2点の差を取ればそれが各隣接2点の傾きだとわかる
ので傾きの種類を数えたら2-3種類であれば条件を満たすと思ってコーディングした
提出したら通ったがハックされていた、辛い
後でコーナーケースに気付く
多分こんな奴
f:id:ratetion:20170902002530p:plain
傾きの種類は3種類だけどどう頑張っても3本平行な線を引かないとダメなパターン
これ以外にもあったら教えて下さい、多分これでおちたんだと思う
これが分かったからと言ってどうすればよいかわからずタイムアップ

C.From Y to Y
ハイ名曲
正直わからんかった、問題文が
文字列を最初は1文字ずつ分割されてるものとして、結合をしていく
その時に同じ文字を含むある条件でコストがかかるっぽい
このコストの式の文字cが意味が分からんかった
考えて頭抱えてるときにBが落とされそれどころじゃなくなってしまって完全に戦意喪失してしまっていた、ぐぬぬ


前回と同じ程度の順位を取ったのでレートがどうなるんだろう、なんか過大評価されてる感じがしなくもない

AtCoder Grand Contest 019(AGC019)

AtCoder Grand Contest 019 - AtCoder Grand Contest 019 | AtCoder
touristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtourist!!!
出てました、いまさら感ありますがせっかくのtourist回なので
前回のABC/ARC解説配信で次回は歴史的な回になるとか言われたのでまあ予想通り(?)でした

結果は2完、CとDがまるで分らず、辛かったのは考察を練れば解けるのか、アルゴリズムを知らないと解けないのかわからないこと
それなのに考え続けるしかないこと

A.Ice Tea Store
Nリットルのアイスティーを買う
0.25L,0.5L,1L,2Lずつでしか売られてなくてそれぞれ値段が違う
”ちょうど”Nリットル買いたいとき必要な最低金額を出力

最初はDPかと思って焦ってしまった
買い方パターンは実際は少なくて
0.25をNになるまで買う
0.5をNになるまで買う
1をNになるまで買う
2をNになるまで買う or N-1まで買って残り1L分だけ上の3つのどれかで埋める
なので7通り
全て求める式を書いてminとってオラァって投げたら通りました


B.Reverse and Compare
英小文字からなる文字列がある
区間を選んで1回だけその区間を反転させる事ができる
何通りの文字列が出来上がるか答える

どうしていいかわからなかったのでとりあえずサンプルをノートで実際にやってみた
反転する箇所を選ぶ通りはn*(n-1)*0.5通りあることが分かったため文字が被らなければそれが答えであると分かった
また回文を反転させると同じものが取り出せるので、全通りから回文の個数を引いて出力すればいいのでは?と思ってコードを書いた
コードを書く前に試せばよかったがサンプル3が当然合わない、親切流石tourist
サンプル3をノートで試していると「abca」のような文字列があったときに
1-4で反転したものと2-3で反転したものが同じであることが分かった
つまり同じ文字で囲まれた区間は反転すると同じものが取れる、これは回文でも同じように出来るっぽい、証明は自信がない

例えば「abcadeafga」のような文字列だった場合
f:id:ratetion:20170901040554p:plain
こんな感じで同じ文字の間が出現する
のでこの場合は全通りから6を引けば答えになる
これを全探索したらTLEした、馬鹿である

各文字の出現回数を全て求めて、n個だとすると(n-1)+(n-2)+...+2+1をそれぞれ足し合わせて全通りから引いたらAC
500点問題だったのでそこそこ嬉しかった
Submission #1541862 - AtCoder Grand Contest 019 | AtCoder
ノート
f:id:ratetion:20170901040908j:plain
こんな感じでほとんど回文についてとサンプルについて考えてた、気づけば早かったらしい

この問題は是が非でもサンプルに「tourist」を入れるべきだった、許さない

f:id:ratetion:20170901041819p:plain

C.Fountain Walk
900点問題だしここまでかなぁって思ったけどとりあえず開いた
グリッドの街があって各通りに多くて1個噴水がある
スタート地点からゴールまで歩くんだけど噴水があったらその周りを通る
最短距離を出力

噴水は1/4歩く場合は近道になって、1/2歩く場合は遠回りしていることがわかる
また1/2は、条件から各通りに噴水が1個と分かっていることを考えるとせいぜい1回通るか通らないかだと思った
ただ1/2を2度通っても1/4いっぱい通ったほうが得とか、そんな状況はあり得るかわからなかった
方針としては通れるだけ1/4を通ってなるべく1/2を避けるルートを選び、通った個数だけ直線での距離から変更を加えてやればいいと思った
通りの本数がでかいので単純に経路探索は無いだろうという感じ
うん、わからない
終わってから解説読んでもさっぱりじゃった、そうじゃった、、、
いつかチャレンジしなおします



水色になりました
8月中に水色を目標にしてたので嬉しいです、運がよかった
f:id:ratetion:20170901041549p:plain
AtCoder

Educational Codeforces Round 25(ECR25)

出ました
Educational Codeforces Round 25 - Codeforces

こどふぉは前から出てみたいと思っていたので適当にググって参加方法を参照して登録して参加した
以前SRMにも出たので同じ感じで(結果がしょっぱかったので参加記書くか迷って書かなかった)

A.Binary Protocol
1の個数がその桁の数字を表すので数えて出力したらAC
問題文の理解ができなくて最初普通に二進数を十進数に直すコードを書いてそりゃ合うわけないわなって言ってた
なんでだ

B.Five-In-a-Row
5目ならべ、次の1手で勝てるかどうかを判定する
とても愚直に全探索を実装した
これに時間がかかったしバグ生えたしまだまだだなと思い知らされた
実装力が足りなさすぎる

C.Multi-judge Solving
通せませんでした
問題を誤読しているのかもしれない

nは問題数
kはすでに解いた問題の最高難易度
以降aはそれぞれ問題の難易度
で、解ける問題はそれまでに解いた問題の最高難易度*2以下の問題
解けない問題はいくつありますか?

だと思ってたらテストケース6が通らず
で、解けない問題をカウントして解いたことにして進めたらテストケース7が通らず

#include "bits/stdc++.h"
using namespace std;

int main(){
	long long int n,k;
	cin>>n>>k;
	
	long long int cans=k;
	vector<long long int> a(n);
	int ans=0;
	
	for(long long int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a.begin(),a.end());
	
	for(long long int i=0;i<n;i++){
		if(cans*2<a[i]){
			ans++;
		}
		cans=max(cans,a[i]);
	}
	cout<<ans<<endl;
	return 0;
}

そんなところでタイムアップだった
次回以降も出ていきたいし英語問題にも慣れていこうと思う
明日はTwitterでいいねしていただいた数だけAOJ自明埋めていきます

ぜひいいねして私を追い込んでください

ACM-ICPC 2017 国内予選 参加記

Yurahuna氏、Yazaten氏と共に参加しました「sparsely_populated_regions」というチーム名で参加しました
飲んできたので覚えてないとかを言い訳に雑に書きます

会場に集まったら各チーム準備をしていた
開始したらまず画面にB,C問題を表示して下の方でテンプレを写す部分を担当する予定だったが、開始直前でプリンターの動作が怪しいとかでA,Bを表示してYazaten氏がテンプレを担当に、私はAを読むことに変更した
時間がない中でうまく回ったのですごいと思った

A問題は読んだら二分探索をしそうだと思ってしまったが、メンバーに説明する段階でそれはないと言われ、説明中に全探索で行けることも気づいたので後は実装するだけだった
二人はもう少しで何とかなりそうって感じだったので実装をした
コードはささっと書けたがcinを忘れるとかやらかしてサンプルをバグらせていた、緊張し過ぎである、開始前には反復横跳び等をしていた人物もいた

軽くYazaten氏がフォローしてくれてAC
どうすればいいか二人を見てみるとYurahuna氏がBを書ける、Yazaten氏がC解けそうだったのでDを印刷して読むことに

D問題は読んだ感じ自分では無理だと思った、無理だと分かった事を褒めよう(?)
誤読をしないように丁寧に読み直してサンプルをすべて図示した
そこで多分bitDP(書けない)を使うんじゃないかと思ったがこれを伝えて固定観念を与えてしまって違った時が痛すぎると思ってノートに書いた文字を消した
制約が妙だったのでしっかりメモしておいた
f:id:ratetion:20170714231559j:plain
そこら辺でYurahuna氏がBをAC、Dを聞きに来てくれた
丁寧に読んでいたので説明がスムーズに出来たようでよかった
再確認とかをしていたらYazaten氏がCをAC、Dを聞きに来てくれたので二人にDを任せてE,Fを読みに行った

Eは構文解析で、論理回路っぽい問題だった
論理回路をしっかり理解してなかったのでやばいと思ったが、説明自体はそれほどでもないので軽く読む程度にしておいた

Fはなんだかひたすら考察をしそうだと思ったので、サンプルを図示した上で、紙を実際に折って確かめ、全分岐を3回分まで図示した
なにか法則っぽいものが見えたが難しい
f:id:ratetion:20170714231618j:plain

二人がDを通してくれた、この時点で100分経過程度だったと思う
割とDを通してるチームが多く、もう1問無いと危険かもしれないという空気が流れていた
Yazaten氏にEを説明、Fの方が解けそうにも見えたので聞いてくれないかと言ったがEが解けそうらしいので信じることにした
二人が分担して実装と考察をしていたのでそれのフォローに入った
こんな方針でやろうと思ってるけど違和感あるかとYurahuna氏が問うてくれたのでそれに関しては平気っぽそうだと思った
テストケースを書いたり確認したりひたすらしていたら、Yazaten氏が実装をかなり進めていてよさそうな雰囲気だったがタイムアップになった

4完じゃ怪しいと思っていたので微妙に悔しいような感覚だった
結果は4完の35位でした
最初の3問を素早く通せたのがよかったっぽい
しかし自分はAでくだらないミスをしてしまったし、WAを吐いていればかなり順位が落ちていたっぽいので反省しかない

それでは2次会へ行ってきます
今日はお疲れさまでした

ICPC模擬国内予選2017参加記

2017/Practice/模擬国内予選 - ACM-ICPC Japanese Alumni Group

本番に出るチームで参加しました
結果は4完でした
チーム名はsparsely_populated_regions(限界集落)(575)
チームメンバーの開始直前のツイートです



時系列で書いた方が面白いかもしれないのでそのように
内容は忘備録程度なのでいつも通り雑に書きます

二人がライブラリを印刷していたが、自分はまだ全域木とかしか無いしそのような実装は時間がかかりすぎて任せるしかないので、基本的だけど書き方に自信がない物だけ用意しようと思った
印刷場所が遠いので手書きにした


事前に私がA,ゆらふな氏がB,やざてん氏がCと決めていたのでまずA問題を読んだ
みんな読み終わった段階で私だけ理解できてなかったのでもう一回読んだらすぐ解法が浮かんだ

A:問題がn個与えられる、それぞれの難易度が1~mで与えられる
各難易度から1問ずつ出題し、合計でm問出題する
しかし各問題には推薦度が決められておりそれが最大になるようにする
配列でmaxを持っておしまい
だったけど添え字をミスったのでサンプルが通らなかった
二人が声をかけてくれてゆらふな氏が指摘してくれてAC

ゆらふな氏が読んでたBのヘルプに入る
問題文の解釈がややこしくて二人で相談しているうちにやざてん氏がCを通してくれていた
後で問題の概要を聞いたけどどうも混乱しそうだった

やざてん氏の手が空いたのでゆらふな氏にDを頼んでBをやざてん氏に読んでもらった
先に問題の概要を説明しようとしたが、問題を理解してないのに説明しても意味がないと後で思ったしその時本人が止めてくれた
この隙にBのサンプルを図示しようとした
読んでもらったらすぐ実装できそうとのことで実装を頼んで、図示が終わり次第Dを読み始めた

Dもまた問題文がややこしいけどなんとなくわかったなぁと思っていたらゆらふな氏がサンプルの動作を実際に説明してくれたのでわかりやすかった
なんとなく二分探索しそうだなぁと思ってたらゆらふな氏が同じことを言っていた
クリアできないケースについては整理でき説明できたのでよかった
しかし本当に二分探索でいいと言い切れず、二人がDPを使ってはどうかと言い始めたあたりで話について行くのがやっとだったので離れて別の問題を読むことにした

Eを開いたら数学っぽくて今まで解いたことのないジャンルだと感じたので読まずに飛ばした

Fはマトリョーシカ風に立方体を入れ子にしてなるべく一番外の立方体の体積の合計を小さくする問題だった
条件は直感的でわかりやすいし伝えやすい、後は何か具体的なアルゴリズムを知っていれば解ける系なんじゃないかと感じたのでやざてん氏に相談したら解けそうとの事で考察を任せ、サンプルを図示し始めた
二人とも多分Dから離れゆらふな氏はEの考察をしていたと思う
この図示が難しくて妙に時間がかかったがミスするよりはいいと思った

図示の合間にやざてん氏がFで使うらしいライブラリの写経を少し手伝った
キーボードがHHKBかmacbookのJISを用意していたがHHKBの十字キーがわからずmacbookを使って書いていた
緊張してミスタイプが多かったので確認してすごく遅い写経になってしまった

やざてん氏の考察が終わったので写経を代わってもらって終わり次第実装に入ってもらった
私は図示の続きと確認をして納得がいったので後半の問題で優しそうなのがないか探していた
f:id:ratetion:20170702232910j:plain

やざてん氏がバグを吐いていたのでヘルプに入った
バグが起こってそうな部分を雰囲気だけで伝えてみたが、どんな実装なのかあんまりわからなかったので下手なことをいうより考えてもらった方がいいと思ったので端的に伝えて答え合わせとかの準備をしていた
答え合わせが多少スムーズになったので悪くはなかったと思った
時間かけてバグを取ってAC、ここで4完、残り30分弱だったと思う

ゆらふな氏がEが解けるとの事で使うライブラリの写経を投げてきたのでどこを写すか整理してやざてん氏に投げていた
写経速くてやべえと思った、やべえ
写経が終わったらゆらふな氏が実装に入ってくれたので写経部分のミスをひたすら探すお仕事をした
2個ほど見つけられたのでまあやることがあってよかったなぁと思った
実装間に合わずタイムアップ
ABCFの4完でした

自分はほとんどキーボードに触れず考察と図示サポートをしていたので、問題や解法をうまく伝える能力がもっと必要だなと感じた
また添え字ミスとか露骨なミスを減らさないといけないなぁと思った

3日連続でSRM,ARC,模擬国内と出たので充実した3日間だった
おわり

AtCoder Regular Contest 077(ARC077)

AtCoder Regular Contest 077 - AtCoder Regular Contest 077 | AtCoder
出ました、出ました
自宅で4人でオンサイトごっこしながら出ました
結果は1完の終了後にDも通しました

C.pushpush
数字がn個与えられる、これを

1,数字を後ろにくっつける
2,逆向きに並び替える

という操作を繰り返していく
最初は文字列にして処理してやろうかと思ったけど、よく考えたら
1,2,3,4,5,6と与えられた場合
6,4,2,1,3,5
という風になる
出力順を見れば後ろから1個飛ばしで出力したのち前から1個飛ばしで出力している
これをループさせてAC
終わった後で友達がTLEを吐いていたので聞いてみると先頭に追加していたが、その部分ですべての要素を1ずつずらす処理が入るためだった
dequeueを思い出したので勧めたらACしていたのでよかった
思考放棄かとも思うが速いので

D.11
n+1の数列が与えられる、その要素はn以下の数をすべて使っているので1つだけ2回登場する数がある
これらの部分列の個数を1~n+1までそれぞれ求めて出力
しばらく考察をした
同じ数を見つけてそれの左にある数字の個数と右にある数字の個数をそれぞれ数えて組み合わせを全体から引けばいいと思った
組み合わせだと思ったのでとりあえずABCの問題を探した
C: 経路 - AtCoder Beginner Contest 034 | AtCoder
フェルマーの小定理を使わないと1e9+7で割ったあまりをうまく求められないことを覚えていたので(今後当たり前になるらしいのでテンプレ化予定で)
なんとなく理解しそれとなく実装しておいた

で、実装するとかなり惜しい答えが出たが合わない
あちこち見直し頭を抱えてたらタイムアップ
終わったらY氏が華麗に解説してくれた

例えば
1234567489を考える
4が同じ数なので左の4の左に数字が3つ、間が開いて右の4の右に数字が2つ
2数からなる部分列でダブるのは14,24,34,48,49となる
この場合は私の実装でもうまくいく
しかし3数以上を考えるときダブるのは124,134,234,489まではいいが、4の外を両方使ったを使った148,149,248,249,348,349が数えられてない
なので正しくは左から選ぶ通り、右から選ぶ通りではなく、左右の合計から選ぶ通りを引けばよかった

実装したら通らなかったのでTwitterに投げたら、c++では負の値の余りを計算すると正にはならないらしく、負のまま出力されていたらしい
1e9+7を足したうえで余りをとるように変更したらAC
ありがとうございました

学ぶことが多くていい回だったなぁと思いました