競プロ日記

競技プログラミング超初心者の日記です

きょうのまなび(AOJ)20210505

今日もAOJの問題を解きました

ITP1_9_C:文字列の比較
ITP1_9_D:文字列変換
ITP1_10_ A:距離
ITP1_10_B:三角関数
ITP1_10_C:標準偏差
ITP_1_10_D:ミンコフスキー距離

以下それぞれの雑記

ITP1_9_C:文字列の比較

C++の文字列って<=>の記号で辞書比較できるんだって初めて知った

ITP1_9_D:文字列変換

replace関数のことをすっかり忘れて、for文で地道に解いてた

string使ったけど、reverseとかreplace使うのには配列の方が扱いやすかったかもしれない

ITP1_10_ A:距離

出力時の桁数指定のために使うfixedとsetprecision()をそろそろ諳んじたい

「桁」っていうイメージを強く持ちすぎているせいか、「精度」って意味のprecisionがなかなか思い出せない

prec...まで思い出せれば予測変換でどうにかできるんだけど

トイレにでも貼っとくかな

ITP1_10_B:三角関数

sin(),cos()関数の()の中に入るのがラジアンっていうの忘れてたから、テストしたらとんでもないことになって焦った

忘れないようにメモしておこう

角度からラジアンの変換
M_PI/180.0 * angle

ITP1_10_C:標準偏差

いい感じにfixedとsetprecision()の復習になった

while()文のもっといい書き方ないかなあ、自分の書き方にセンスをあんまり感じないんだよね

あと、久しぶりにaccumulate()使った

調べてみたら文字の連結にも使えるみたい

第4引数についていまいちわかってないけど、使えたら便利そうだからまた勉強しよう

accumulateメモ
accumulate(v.begin, v.end(), 初期値)

ITP_1_10_D:ミンコフスキー距離

ミンコフスキー距離って何?ってなったけど、わかりやすい問題文のおかげでそんなに躓くことなく進んだ

ただ、n乗根の計算の時にpow()でのn乗根で下のような計算の違いが出てちょっと引っかかった

pow(10,1.0/3.0)
→2.1544346900(正解)

pow(10,1/3)
→1.0000000000(不正解)

double N = 1.0/3.0
pow(10,N)
→inf(不正解)

2番目は1/3がint型で計算された結果、小数点以下が切り捨てられて0乗根になったんだろう

でも、1番目と3番目はどう違うんだろう?

解決したらまた追記したい

きょうのまなび(AOJ)20210503

今日はAOJの次の問題を解きました

ITP1_6_D:ベクトルと行列の積
ITP1_7_A:成績
ITP1_7_B:組み合わせの数
ITP1_7_C:表計算
ITP1_7_D:行列の積
ITP1_8_C:文字のカウント
ITP1_8_D:リング


以下それぞれの雑記

ITP1_6_D:ベクトルと行列の積

こっちだと文字化け?の影響で読みにくくて飛ばしてた問題
行列って毎回考えすぎて行と列がゲシュタルト崩壊しそうになるから、もう手を動かして体に行と列を覚え込ませるしかない

提出履歴を確認したらCE、RE、WAをかましている

行列に対しての苦手意識が見え見えでちょっと笑ってしまった


ITP1_7_A:成績

数学の試験は毎回ひどい点数だったなと回想しつつ解く

場合分けがめんどくさいなと思ったので自分の納得のいくシンプルさを追求したい


ITP1_7_B:組み合わせの数

Hintにあるように3重ループで解ける問題だけど、もっと計算量を落とせるはず…と考えた結果

これは、atCoderでしばしば見かける主客転倒テクとやらで解けるのでは!?とか予想してたけど、全然違った

言葉は頭に入っていたけど、中身に関する理解が浅すぎることが自覚できたからよし(まだ完全理解はしていない)

physics0523.hatenablog.com


ただ、計算量を落とす方法はどこかで見かけたはず…と思い出したのが蟻本に載っていた二分探索

が、この問題を解いているときに睡魔に襲われていたので3重ループに甘んじてしまった

後日、二分探索にチャレンジしよう


ITP1_7_C:表計算

前問の眠気を引きずったまま続けて解いた問題

実装自体はすごくシンプルなのに、すごく時間がかかってしまった

C++だとvectorの宣言の関係でCEになるっぽいので、C++11で判定

「解ければ良かろうなのだ」の精神でいるけれど、なんでC++だとダメでC++11だとOKなのかはいつか理解したい


ITP1_7_D:行列の積

n×mとm×lの行列の積がn×lになるのを習った時、まるで真ん中のmが中和されてるみたいに消えてしまうのを綺麗だなと思ったのをなんとなく覚えている

まあ、ITP1_6_Dにも書いた通り、苦手な分野ではあるのですが…

ちなみに、こちらも漏れなくWA、CEをかましている(REしなくなっただけ成長と考えることにしよう)


ITP1_8_C:文字のカウント

これまたCE、WA、PEのオンパレード

複数の行の入力方法が分からなくて迷走しているのが手にとるようにわかる

なんでwhile(cin >> c)でEOFまで入力を続けてくれるんだろう?とか、自分のXcode上だと何で入力が止まらないんだろう?とか悩みに悩んだ結果、未来の自分に期待することにした(頑張れ、未来の自分 この文章を読んで鼻で笑うくらい成長していてくれ!)

ただ、後半は疲れすぎてやけになって提出を繰り返しているので、こうなる前にさっさと仮眠取るべきでした


ITP1_8_D:リング

問題を最初に読んだ時は、『配列の循環?螺旋本に載ってるリングバッファってこれ?』なんて思ってしまった

けど、制約を再確認して、別のシンプルな解法を思いついた時はとってもスッキリして嬉しかった

自分で気づくってどんなことにも変えられない喜びだなあと思う

(ABC199-A) Square Inequality

  • 考え方

問題文通りに条件を設定してあげればOK

  • 感想

かなりサクッと解けた問題
逆に何か罠があるんじゃないかと提出に慎重になってしまったから、自信持って提出しよう


#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)

using namespace std;
 
int main() {
    
    int A,B,C;
    cin >>A>>B>>C;
    
    string ans = "No";
    if((A*A+B*B)<(C*C)) ans = "Yes";
    
    cout << ans <<endl;
    
    return 0;
}

(ABC198-C) Compass Walking

  • 考え方

(X,Y)まで最短で近づいて、ちょうど到達しない場合には最後の2歩で調整したらいい
※ただし、1歩で(X,Y)より先に行ってしまう場合は2歩で調整

コンテスト中は※の考え方がすっぽ抜けてWAになってしまった

 

  • コーディング

コンテスト後に解説読んでコーディング。

ユークリッド距離をdouble型にしたものの、最初のR,X,Y入力をint型にしていた関係でWA連発


こういう小数が出てくる問題の場合にはdouble型で揃えておくべき、という学びを得る

 

  • 感想

上にも書いたけど、※の場合まで詰めれなかったのが悔しい
しばらくはC問題までをコンテスト中に解くのが個人的な目標で、今回近いところまでいけたような気がするからまた次回まで過去問解いたりして対策しよう

 

atcoder.jp

Palindrome with leading zeros (ABC198-B)

回文の問題

 

  • 考え方

0は先頭からしか追加できないから、

後ろから連続する0を取り除いた数が回文かどうか判定

1文字の時はもう回文が成立してるから、2文字以上の時だけ考える

 

  • コーディング

0を消すのはeraseを使ってサクッと消せたんだけど、回文判定に骨が折れた。
先頭と最後尾から文字がそれぞれ一致しているかを真ん中まで確認することにしたんですが…

 

 

  • 感想

コンテスト後、hamayanhamayanさんのユーザー解説を読んでやっとreverseの存在を思い出しました

ショックすぎたから次似たような問題が出てきた時は絶対に忘れないと誓う

atcoder.jp

Div (ABC198-A)

2人でお菓子を分ける問題


atcoder.jp


この問題の個人的ポイントは2つ

  • ふたりとも1つ以上のお菓子をもらう
  • お菓子に区別はない

左がA君、右がB君のものだと考える。

仕切りを置ける場所はN-1個なので、答えはN-1になる。


高校数学でいったら数学Aの内容かな?


コード貼りたかったけどインデントが消えるので一時断念。

初ブログ記事だ〜
競プロレベルアップのために続けていけたらいいな