Atcoder Biginner Contest 184 (ABC184)振り返り
Atcoder Biginner Contest 184に参加しました。
atcoder.jp
A問題
A - Determinant
a×d-b×cを計算して出力。
#include <bits/stdc++.h> using namespace std; int main() { int a, b, c,d; cin >> a >> b >> c >> d; cout << a*d-c*b << endl; }
B問題
oならば持ち点を1増やし、そうでなければ1減らす。
持ち点が0より大きいときのみ減らせること注意して実装すればよい。
#include <bits/stdc++.h> using namespace std; int main() { int N, X; string S; cin >> N >> X >> S; for(int i=0; i<N; i++){ if(S.at(i)=='o')X++; else if(X>0)X--; } cout << X << endl; }
C問題
斜めに1つ移動するときマスの座標の偶奇が変わる。よって斜め移動を行うときには、現在いるマスに応じて
・A: (偶, 偶)→(奇, 奇)→(偶, 偶)→(奇, 奇)→……
・B: (偶, 奇)→(偶, 奇)→(偶, 奇)→(偶, 奇)→……
のAまたはBのどちらかのパターンで移動することになる。別の言い方をすれば、斜め移動では偶奇性(パリティ)の等しいマスにのみ移動できるということである。
上の図のマスAからマスBへの移動は同じパリティ間の移動なので2手で移動できる。パリティの異なるマスAからマスCの移動では高々3手で移動できるため、どのマスに移動する場合でも0~3手で移動できる。
・0手
移動前後が同じマスかを調べればよい。
・1手
問題文中に与えられた3条件のいずれかを満たせばよい。
・2手
1. パリティが等しい。
2. |r1-r2|+|c1-c2|≦6
移動できる距離が6になったので、3番目の条件式を6に変える。
3.斜め移動と3マス以下の移動の組み合わせ。1番目、2番目の条件と3番目の条件を組み合わせればよい。
高校数学で言うところの領域をイメージしてもらえると助かる。|y-x|=0 (またはy=|x|)と|y-x|≦3とか。
・3手
上記以外すべて。
以上の場合分けを行えば終了。
#include <bits/stdc++.h> using namespace std; int main() { int r1, c1, r2, c2, ans; cin >> r1 >> c1 >> r2 >>c2; if(r1==r2&&c1==c2)ans=0; else if((r1+c1==r2+c2)||(r1-c1==r2-c2)||(abs(r1-r2)+abs(c1-c2)<=3))ans=1; else{ if((r1+c1)%2==(r2+c2)%2)ans=2; else if(abs(r1-r2)+abs(c1-c2)<=6)ans=2; else if(abs(r1+c1-r2-c2)<=3)ans=2; else if(abs(r1-c1-r2+c2)<=3)ans=2; else ans=3; } cout << ans << endl; }
D問題
D - increment of coins
動的計画法(DP)を用いた期待値の計算を行う、という方向性はわかった。DPの実装方法も何を持っていればよいかもわからなかったため手が出せず。勉強と経験不足。
E問題
E - Third Avenue
幅優先探索(BFS)で解けばよい、という方向性はわかった。BFPの実装方法をネットで調べながらコードを書いていたが間に合わず。勉強と経験不足。
F問題
そもそも問題を見てない()。
感想
DE問題の難易度が高い(体感)。いえ、基礎的なアルゴリズムの実装力不足なのはわかってます。連休はDP, BFS, DFSあたりの勉強かな。
ブログを始めました
ブログを書き始めたので自己紹介もかねて適当に
ブログを始めた経緯
僕は最近、競技プログラミングというものを始めました。数学パズルプログラミングがごっちゃになった対戦ゲームみたいなものです。競プロ界隈にはTwitterやブログで情報を発信している人も多くいて、役立つ話が聞けます。僕も誰かの役に立つことを期待してブログを始めてみました。いつまで続けるかはわかりませんが、できるだけ続けていきたいと思っています。
自己紹介
突然ですが自己紹介です。
2020年5月末にatcoderに登録して競プロを始めたrxiveといいます。理系の大学に通っています。プログラミング初心者でC++入門 AtCoder Programming Guide for beginners (APG4b)でプログラミングを始めました。競プロ以外できません。頭を使うパズルが好きなので楽しくやってます。趣味です。研究が忙しいのでまとまった時間は取れませんが、今のところ楽しいので細々と続けていきたいと思います。
ブログのこれから
ブログには競プロ関連の内容を増やしていければいいなと思っています。コンテストの振り返りや成長記録として利用していくつもりです。高校数学くらいまでの基本的な内容も書きたいですが、内容があやふやなのでしばらく先延ばしになりそうです。内容に間違いがあればコメント等で指摘していただけると幸いです。
Atcoder Biginner Contest 183 (ABC183)振り返り
Atcoder Biginner Contest 183に参加しました。
atcoder.jp
A問題
A - ReLU
定義通りxが0以上と0未満とで場合分けする。
またはxと0の大きいほうを出力してもよい。
#include <bits/stdc++.h> using namespace std; int main() { int x; cin >> x; cout << max(x, 0) << endl; }
B問題
B - Billiards
壁や鏡で反射したり、川で水を汲んで運ぶ最短距離を求めたりするときには通る点の一方を壁に対して折り返す。
内分点の公式を用いれば求める座標が出る(公式解説の方法)。
本番では図の点A、B、Cが一直線上にあるような条件を求めた。この場合0除算に注意が必要なので公式解説のほうがスマート。後は適当な精度で出力。
#include <bits/stdc++.h> using namespace std; int main() { double Sx, Sy, Gx, Gy, ans; cin >> Sx >> Sy >> Gx >> Gy; if(Gy==Sy)ans=(Gx-Sx)/2+Sx; else ans=Sx-(Gx-Sx)/(-Gy-Sy)*Sy; cout << std::fixed << std::setprecision(15) << ans << endl; }
C問題
C - Travel
すべての都市の順列を考える。C++ならnext_permutation。
最近知ったばかりで一度も使ったため動くコードを書くのに30分かかった。反省。都市1から出発してすべての都市を回り、都市1に戻るまでの時間を足してKと比較する。
#include <bits/stdc++.h> using namespace std; int main() { int N, K; cin >> N >> K; vector<vector<int>>T(N, vector<int>(N)); for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ cin >> T.at(i).at(j); } } int ans=0; long long time=0; int now=0; vector<int>B(N); for(int i=0; i<N; i++)B[i]=i; for(int i=0; i<N-1; i++){ time+=T.at(B[i]).at(B[i+1]); } time+=T.at(B[N-1]).at(0); if(time==K)ans++; while(next_permutation(B.begin()+1, B.end())){ time=0; for(int i=0; i<N-1; i++){ time+=T.at(B[i]).at(B[i+1]); } time+=T.at(B[N-1]).at(0); if(time==K)ans++; } cout << ans << endl; }
D問題
D - Water Heater
0から200000秒までの各秒数における使用水量を求めようとするとTLEする(最大でO(NT)~O(4×10^10))。素直に実装するだけでは間に合わないときには(私の少ない経験上)適当な配列にメモしておくか適当な累積和を用意すればよい。今回は前者
#include <bits/stdc++.h> using namespace std; int main() { int N, W; cin >> N >> W; vector<int>S(N); vector<int>T(N); vector<int>P(N); for(int i=0; i<N; i++)cin >> S[i] >> T[i] >> P[i]; vector<long long>up(200010); vector<long long>down(200010); //少し大きめに用意する for(int i=0; i<N; i++){ up.at(S[i])+=P[i]; down.at(T[i])+=P[i]; } //各時間における使用増加量と減少量// string ans="Yes"; long long now=0; //問題の解答ans、ある時間での使用量nowを用意して for(int i=0; i<200010; i++){ now +=up.at(i); now-=down.at(i); if(now>W){ ans="No"; break; } } /*0から200000+α秒までの使用増加量と減少量を計算し続ける now>Wとなればans=Noとして終了*/ cout << ans << endl; }
E問題
E - Queen on Grid
単純に考える。あるマスに移動するにはそのマスの縦横斜め(上、左、左上方向)のマスから一手かかるので、それらのマスに移動する方法の和をとればよい。
しかし、すべてのマス(HW個)について縦横斜めの和(H+W+α)回計算しようとするとO(HW(H+W))~O(10^10)程度の計算量となるため当然TLE。適当な累積和をとれば計算量を抑えられそう。
実際に、あるマスまでの縦横斜めについての累積和を用意しておけばO(HW)で計算できる。
公式解説ではDP(動的計画法)で解いている。考え方は同じはず。たぶん。近々勉強したい。
#include <bits/stdc++.h> using namespace std; int main() { int H, W; cin >> H >> W; vector<vector<char>>S(H, vector<char>(W)); for(int i=0; i<H; i++){ for(int j=0; j<W; j++)cin >> S.at(i).at(j); } vector<vector<int>>A(H, vector<int>(W)); A.at(0).at(0)=1; //あるマスに到達する方法の数、(1,1)は1通り vector<vector<int>>tate(H, vector<int>(W)); vector<vector<int>>yoko(H, vector<int>(W)); vector<vector<int>>naname(H, vector<int>(W)); //縦横斜めについてあるマスでの累積和用の配列 for(int i=0; i<H; i++){ for(int j=0; j<W; j++){ //すべてのマスについて if(i>0){ A.at(i).at(j)+=tate.at(i-1).at(j); tate.at(i).at(j)+=tate.at(i-1).at(j); A.at(i).at(j)%=1000000007; } //そのマスの上方向の和をとり if(j>0){ A.at(i).at(j)+=yoko.at(i).at(j-1); yoko.at(i).at(j)+=yoko.at(i).at(j-1); A.at(i).at(j)%=1000000007; } //左方向の和をとり if(i>0&&j>0){ A.at(i).at(j)+=naname.at(i-1).at(j-1); naname.at(i).at(j)+=naname.at(i-1).at(j-1); A.at(i).at(j)%=1000000007; } //斜め方向の和をとった tate.at(i).at(j)+=A.at(i).at(j); yoko.at(i).at(j)+=A.at(i).at(j); naname.at(i).at(j)+=A.at(i).at(j); tate.at(i).at(j)%=1000000007; yoko.at(i).at(j)%=1000000007; naname.at(i).at(j)%=1000000007; //累積和をとり、常に余りの計算を入れる if(S.at(i).at(j)=='#'){ A.at(i).at(j)=0; tate.at(i).at(j)=0; yoko.at(i).at(j)=0; naname.at(i).at(j)=0; } //ブロックマスでは0として計算する } } cout << A.at(H-1).at(W-1) << endl; //右下(H,W)マスでの値が答え }
F問題
まるで分らない。
感想
BCでつまづいて時間がかかったのが反省点。最近は時間内にD問題まで解けるようになった。E問題の解法を終盤で思いついたが間に合わず、力不足を否定できない。次回失敗しなければ緑になれそうだがフラグか？
プログラミング経験ゼロの初心者が競プロを始めた話
競プロを始めてもうすぐ半年、かつもうすぐ緑コーダー(予定)なので今のうちに記事を書きます。
1. rxiveって何者？
こんにちはrxiveです。自分用のメモとして、そして競技プログラミング初心者の参考になればと思いブログを書き始めたので、ここで軽く自己紹介をしておきたいと思います。
- 理系大学院生
職業は学生です。理系の大学院生とはいっても情報系や機械系ではなく実験系の学生で、普段は研究室で引きこもりをしています。大学入試までの数学は一通り勉強したのである程度数学ができる人間に分類されると思います。
- プログラミング経験ゼロ
プログラミング経験はゼロです。嘘です。講義で少し触った程度で記憶に残っていませんでした。言語はわかりません。if文とfor文があることを知っている程度で全くの初心者でした。
- 2020年5月に競プロを始める
5月にatcoderに登録して競プロの世界に足を踏み入れました。
2. 競技プログラミングを始めたきっかけ
長年「プログラミングをやってみたい、できたら楽しそう」と思っていました。しかし、「何を勉強していいかわからない」「プログラミング言語がたくさんあるけど選ぶ基準が分からない」と誰もがぶつかる壁に阻まれて行動できずにいました。
2020年、新型コロナウイルスが流行しました。全国的に外出自粛、リモートワークの流れが生じて大学も閉鎖したため、私は暇を持て余していました。この時期に競技プログラミングとatcoderの存在を知りました。パズルやゲーム要素があり、レートで努力が可視化されているため飽きずに続けられそうだったし、無料で始められるのでやめてしまっても損はしないと思ったのでなんとなく始めました。
当初の目標としては(偏見ですがネット上で人権がありそうな)緑コーダーになることでした。数学の素養がないと厳しい(というか相当苦労する)という話をネットで見ましたが自分には当てはまらないと考えていました。
3. 茶コーダーになるまで
プログラミングに関して完全に無知だったのでC++入門 AtCoder Programming Guide for beginners (APG4b)でC++の勉強を始めました。大体第2章までしかやっていません。というよりも第3章以降が理解できませんでした。いつか理解できるといいと思っています。この時点で四則演算、文字列、if文、while文、for文、配列をなんとなく使えました。必要な時に参照できるようにメモ帳にコピペしたり、ページをブックマークしていました。コンテスト中はネット検索が認められているので助かります。
以下を参考に問題を解いて練習した後、
Atcoder Biginner Contestに参加しました。ABCのA問題は解けて、B問題は解法が思いつくのにコードが書けない状態が続きました。
単純に基礎ができていないと感じたので(今もできていませんが)夏休み期間に過去問を解きました。界隈で言うところのいわゆる"精進"もどきです(Atcoder Problemsを使いました)。Training のeasy100問を解き終わるころには安定してAB問題は解けるようになり、C問題も簡単なものなら解けるようになりました。ここでレートが大きく伸びて無事茶コーダーになりました。
4. 茶コーダーになってから
時間が取れなくなったので精進もどきは停止中ですが、毎週末のABCには必ず参加しています。8月半ばにレートが600を超えてから3か月じわじわと700後半まで上がってきました。この間、累積和としゃくとり法という手法を知りました。
緑コーダー射程圏内のときに一度、ARCにも参加して撃沈しています。後から落ち着いて考えればA問題は解けました。この時のマイナス分を取り戻すのに3回くらいかかりました。懲りたのでしばらくはABC相当のコンテストのみに参加します。
5. これから
年内、できれば11月中に緑に上がって界隈恒例の色変記事を書きたいです。と言っても言うべきことはありませんが。
典型アルゴリズムをはじめとした実力不足が感じられるので勉強します。以下の記事が大変参考になり、時間を作りつつ勉強していきたいと思います。
あとは成長日記もかねてコンテストの感想や考えたことについてブログでまとめられたらいいなと思っています。 というかこれを目的にブログを始めたので今回の記事はおまけです。たまに雑談もするかもです。
