2020-11-12

【FE】基本情報技術者　CBT受験　まとめ

Ruteです。

2020年11月11日に、基本情報技術者試験(以降はFEと略します)のCBT方式での実施についてIPA(情報処理推進機構)よりお知らせがありました。

www.jitec.ipa.go.jp

このお知らせの内容を端的に分かりやすくしたのがこの記事です。

今後令和2年度末までにFEを受験する方には見て欲しい記事ですので、これにあたる方はご覧下さい。

1.試験の実施期間は？
2.試験の申し込み受付期間は？
3.注意事項など
- 3-1.優先申込について
- 3-2.受験について(いろいろ)
4.最後に

1.試験の実施期間は？

午前試験	2021年1月5日（火）～ 2021年3月23日（火）
午後試験	2021年1月5日（火）～ 2021年3月28日（日）
午後試験（免除者）	2021年1月5日（火）～ 2021年3月23日（火）

※午後試験(免除者以外)の実施期間のみ異なっていることに注意して下さい。

2.試験の申し込み受付期間は？

午前試験	優先申込：2020年12月1日（火）10時～ 2020年12月20日（日）23時59分一般申込：2020年12月21日（月）0時～ 2021年3月18日（木）23時59分
午後試験	優先申込：2020年12月1日（火）10時～ 2020年12月20日（日）23時59分一般申込：2020年12月21日（月）0時～ 2021年3月23日（火）23時59分
午後試験（免除者）	優先申込：2020年12月1日（火）10時～2020年12月20日（日）23時59分一般申込：2020年12月21日（月）0時～ 2021年3月18日（木）23時59分

※これも、午後試験(免除者以外)の受付期間のみ異なっていることに注意して下さい。

3.注意事項など

3-1.優先申込について

優先申込とは、令和2年度10月FE試験に申し込みをした方のみ申し込みが可能な制度を指します。一般申込と日程が異なっていることに注意して下さい。

3-2.受験について(いろいろ)

受験申し込み回数は、申込期間内で1回です。

そのため、一般申込を2回以上申し込むことや、CBT試験受験で不合格となった後再度申し込みをすることは出来ません。お気をつけ下さい。

受験にかかる料金は現時点では決まっていません。

試験当日は必ず集合時刻(試験開始15分前)までに試験会場に行かないといけません。

集合時刻までに集合しない場合、そもそもの受験ができなくなるので気をつけましょう。

試験問題は非公開であり、持ち帰ることは出来ません。さすがに対策はされているとは思いますが、試験問題をSNSに投稿する　などの第三者に問題を開示する行為はやめましょう。(受験申し込み時に同意すると思いますが)

合格発表は受験した月の翌月中にされるようです。

試験会場は全都道府県において1カ所以上の試験会場が用意されます。自分の住んでいる都道府県の会場でなるべく受験しましょう。(おそらくコロナ対策もされるはず)

4.最後に

私Ruteも2021年冬にFEを受験したいと思っています。合格しましたらその合格記もブログに掲載したいと思っていますのでよろしくお願いします！

2020-10-19

オンゲキで銀Ratingになるまでに取り組んだこと

こんばんは。Ruteです。

さて、Twitterでも報告しましたが、この度私Ruteは銀Rating(13.00)に到達しました!!

銀Rating , ガチ勢の方からすると「ふーん」みたいな感じだとは思いますが、個人的にはこれまでの音ゲーの中でやりこんだ方だと思うので、評価して下さい(切実)

ここでは、私が銀Ratingになるまでに取り組んだことをまとめます。

(この記事は15分くらいの長さになっていると思います)

1. オンゲキのレーティングとは
- 1-1 レーティングの計算方法(AtCoderと比較して)
- 1-2.レーティングを上げるためには
2.レーティング・枠別対策法
3. 銀Ratingになるために必要な知識
4. LEVEL12おすすめ曲

1. オンゲキのレーティングとは

1-1 レーティングの計算方法(AtCoderと比較して)

オンゲキには以下の図のようなレーティングシステムが存在します。

(私は競技プログラミングもしているので、競技プログラミングコンテストサイトの1つであるAtCoderのレーティングシステムも一緒に掲載することにしました。)

f:id:Rute_programming:20201019185611j:plain

オンゲキのRatingは新曲15曲・BEST枠30曲・RECENT枠10曲　計55曲の曲別レートによって計算されています。

AtCoderではこれに加え参加回数が考慮されてレーティングが計算されますが、オンゲキではプレイ回数が考慮されることはなく、"曲別レート"でRatingが計算されます。

1-2.レーティングを上げるためには

曲別レートは、クリア時の評価と譜面定数というもので計算されます。

クリア時の評価は、評価が上の順にSSS+,SSS,SS,S,AAA...というようになっています。

一般的に、難易度がAの曲でS評価を取得すると、その曲の曲別レートはAになります。

SS評価だとこれに+1.0, SSS評価だとこれに+1.5 , SSS+評価だとこれに+2.0の曲別レートが加算されます。(SSS+,1007.5k以上は加算幅は上がりません))

逆に、AAA以下の評価になると、点数によって曲別レートはAから減少していきます。

S評価は970k , SS評価は990k, SSS評価は1000k, SSS+評価は1007.5kです。

(テクニカルスコアでの話です)

ここで気づいた方もいると思いますが、SからSSまでの20kの間で、曲別レートの変動幅は1.0違ってきます。SSからSSSまでの10kの間でも、曲別レートの変動幅は0.5違ってきます。

20k上げるだけで曲別レート+1.0です。970kから990kに上げるのは、プレイヤーによって差が出てくると思いますが、練習すれば自力で上げることが出来ると思います！

筆者も、最初S評価の曲をSS評価にして、レーティングを上げていたので

練習はレート評価を裏切らない。というものが顕著に表れていると思います。

2.レーティング・枠別対策法

2-1.新曲枠15曲:

とにかく新曲をプレイします。新曲15曲の曲別レートを上げることでこの枠は埋めることが出来そうです。

2-2.BEST枠30曲:

BEST枠は新曲枠以外の30曲で構成されます。これらの30曲については、基本的に変わることがほぼありません。ただし、変える方法がいくつかあります。

1番目の方法は、とにかく同じLEVELのプレイしたことがない曲を選ぶというものです。

筆者は当時、銅Ratingでしたが、LEVEL12の曲を、様々なジャンルから選んでいました。譜面によって得意な曲もあれば、苦手な曲もありました。しかし、プレイしたことがない曲を選ぶということで「自分に合った曲」が見つかる可能性は高いです。これによってBEST枠を上げることも可能なので、Ratingが上がらない方はプレイしたことがない曲を選ぶといいでしょう。

2番目の方法は、得意な曲をやりこむというものです。

この方法は、先ほどの方法より曲別レートは上がりにくいです。

ただ、得意な曲ということで、譜面が頭に残っていると思うのでその知識を利用しながらプレイすることで、ハイスコアを更新し続けることは可能です。

他にも様々な方法があります。オンゲキ界隈でこれについての議論が盛んになることを期待しております。

2-3. RECENT枠

RECENT枠は最近プレイした50曲(曲数要検証)の中で最も曲別レートが高い10曲の合計値によって計算されます。これは同じ譜面も含まれます。ただ、50曲の中で最も曲別レートが高い10曲の合計なので、かなり曲が拮抗する傾向になることが考えられます。これについての対策は簡単で、普段から曲別レートを一定の値以上にすることです。

例えば、銅Ratingを目指したい場合は、12.00に向けて、譜面定数11程度の曲でSS, 譜面定数10.5(10+)の曲でSSSをとり続けていればよいのです。

3. 銀Ratingになるために必要な知識

ここからは、銀Ratingになるまでに必要だった知識を紹介します。

まず、「レバーを右に倒す＋Rボタン」「レバーを左に倒す+Lボタン」は基礎知識であるといえるでしょう。このテクニックは、多くのLEVEL12,11+譜面で利用されているもので、慣れていくと簡単に感じます。

次に、両手でボタンを押す　というものです。

例えば、「Freedom Dive(EXP11+)」の譜面の一部を示します。

f:id:Rute_programming:20201019193533j:plain

引用元：nicovideo.jp/watch/sm35609181

このように、片手ではなく両手でのボタン操作が要求されます。私が初見でこの譜面をプレイしたときはミスを連発していましたが、今はそこまでミスをすることはなくなりました...LEVEL12の曲にはこのようなテクニックを求められるものが頻出しているので、覚えておきましょう。基本的には譜面の位置と同じボタンを押すと慣れると思います。

レバー高速移動もテクニックの1つです。これは、高BPMの曲ほど高速になる傾向があります。

これ以外にも様々なテクニックがあると思いますが、銀Ratingになるためにはこれくらいで十分だと思います。

4. LEVEL12おすすめ曲

最後に、筆者であるRuteが選びます、銀Ratingを目指すにあたってプレイして欲しい曲を紹介します。

4-1.PinqPiq (xovevox Remix) (EXPERT 12)

この曲は、基本的にはBPMはそれほど速くはなく、12入門曲としてプレイするのにおすすめの曲です。

序盤は基本的に1ボタン+レバー or 2ボタン+レバーというLEVEL10-11程度のテクニックで処理できますが、

赤青ボタンを押し続けたままレバーを動かす　

両手全部押し

片手でRorL + 緑青or 赤緑

というテクニックが要求されます。

譜面自体はそこまで難しくなく、リズムに乗れば楽しい感じの譜面だったりします。エンジョイ勢の私もこの曲をプレイするのが好きです＾＾

4-2.Red to Red (EXPERT 12)

こちらもLEVEL12入門曲としては良いものだと思います。

全体的にはノーツ数が少なめの印象です。

求められるテクニックとしては、

片手でRorL + もう片方の全押し

「レバーを右に倒す＋Rボタン」「レバーを左に倒す+Lボタン」

両方全押し

があります。

それ以外は、基本的に全押しorレバー操作が求められるくらいで、特に難しくはないと個人的には思います

4-3.SILENT BLUE (EXPERT 12)

この曲は、リズムが若干変則的になる部分もあります。が、LEVEL12にしては簡単な部類かと思います。私も初見でSSSを出しています。

この曲で求められるテクニックは

両手でボタンを押す(全押し以外)

くらいだと思います。

4-4. otorii INNOVATED -[i]3-(EXPERT 12+)

この譜面は12+ですが紹介します。BPMが早いので、高BPM曲の入門譜面にうってつけだと思います。

この譜面の特徴として、全押しが集中しているように思います。(中盤に長い両手全押しが1か所あり、終盤に全押しが集中しています)

この曲で求められるテクニックは

ｽﾞﾊﾞﾘ　高速でレバーを動かす、高速で手を動かす

ということに尽きると思います(MASTERだとこれが14+なので...)

高速でレバーを動かす、手を動かすというのは高LEVEL曲では当たり前になってくるので、この曲でそれをつかむといいと思います。

以上、オンゲキで銀Ratingになるまでに目指したことをまとめました！！

この記事が銀Ratingを目指しているオンゲキユーザーの目に留まることを祈っております...

(なお、私はエンジョイ勢なので、ひとまずは銀Ratingで精進を終了したいと思います)

2020-09-19

【お知らせ】競プロから一時的に手を退くかも知れません

こんばんは。Ruteです。ABC179に参加された皆さんはお疲れ様でした。

今回は皆さんにあるお知らせがあります。コンテスト中に書いた拙い文章、かつ長文に及ぶお知らせですが、読む気力のある方は読んでもらいたいと思います。

まず、私Ruteは今回のコンテストを持って、一時的に競プロから手を退きたいと決意することとしました。(手を退くといいましても、完全に競プロから手を退くというわけでなく、競プロへの参加頻度を減らすというものです)

様々な意見があるとは思いますが、とりあえず私の考えなどを聞いてもらいたいと思います。

最近、レーティング600台までレーティングを上げていたのですが、先日のコンテストで考察ミスにより灰パフォーマンス(111),そして今回のコンテストも知識不足で2完が精一杯でした。

また、コンテスト中になぜか片頭痛？のような頭痛を感じるようになっています。その時から集中力なども切れるようになり問題が解けなくなってしまいます。
(言い訳をしてしまいすみません...)

個人的に、これまで３完以上をしていた自分は「３完しないと責められる、３完しないと」と焦るようにもなってきました。しかし昨今の問題の難易度の上昇に耐えきれず最近は２完で止まることが多くなっています。

コンテストが終わった後自分を責め続けることも多くなってしまい、結果としてレーティングを上げることが難しい状況になりました...(上がっても下がる、という繰返しなので、このレーティング帯が適正なのかと思います)

競技プログラミングは中学2年生からプログラミングをしていた自分にとって一番興味を持った趣味であり、1年半続けていますが、昨今は問題を解けないとストレスが溜まることが多くなっています。ストレス発散のためにとても簡単な灰Diffも解いていますが、これも楽しめるという状態ではなくなってきました

【余談：競プロの数学について】

Ruteですが、一応数学オリンピックの受験をしたことがあります。(予選敗退でしたが)なので高校数学についてはある程度自信があったのですが、競プロの数え上げ問題は特に特徴的であり、式変形を誤ることも多くありました。シミュレーションで解ける数学

(ABC148 Double Factorial)もあるのですが、それ以外の数学では全敗しており、結果自分の数学力の弱さを露呈してしまうことになりました。

まもなく私の大学でも2年生の秋学期を迎えます。2年生の秋学期というと、ゼミ、固い言葉で言えば研究室選択に関して重要な学期であることは言うまでもありません。その勉強を怠けて競技プログラミングの問題を解き続ける、というのは自分の人生において誤った選択ではないかと考えるようになりました。2年生の秋学期に取得する授業は、ほとんどが専門科目であり、難しい内容です。

(当然、1年生春・秋学期、2年生春学期の内容を把握しての話ですが)

これらの授業を取らないと私の進路選択にも影響が及ぶ可能性があり、これについては真摯に向き合わなければならないと考えています。また、大学院試験を2年後に控えている今、競技プログラミング以外にもやることはあるのではないかと考えています。(自分にとってのターニング・ポイントであると考えています)

(基本情報技術者などの資格取得を行う、英語能力を上げるなど)

以上より、競技プログラミングを続けるコンディションとしては難しいと判断したため、上記のような決断をした次第であります。

これまで私を支えて頂いた皆さんに対しては、裏切りのような行為と見て取れるのかもしれないのですが、私の実力不足です...本当に申し訳ございませんでした。

今後ですが、以下のことを考えています

・将来への影響などを考え、競技プログラミングコンテストへの参加頻度を減らします。

・レーティングを確実に上げたいと思っているため、緑Diff ~ 水Diffの問題を解きたいと思います。ただ、これも頻度がこれまでより減ると思って下さい。

また、問題で分からない点等があったら、私から発信していくので教えていただけると非常に助かります...(解法や考え方等)

・コンテスト中にTLをあまり見ないようにします。これは、私が2完しかしていない状況で、3完した！4完した！などの情報が目に入ると焦るためであり、これらの情報をシャットアウトしたいと考えているからです。

・Twitterへの浮上率が低くなります。

皆さんへのお知らせは以上です。この記事に対するコメント(批評など)はおおいに結構です。

2020年9月19日

Rute記す

2020-07-28

M-SOLUTIONS プロコンオープン 2020　A ~ D解説(Python3)

ABC参加記

M-SOLUTIONS プロコンオープン 2020の解説です！

当日は都合により参加が出来なかったのですが、バーチャル参加しました！！

結果は4完40分程度でした。本番だと水パフォだったので参加したかった...

(この記事は解法を詳細に説明しているため約15分程度で読めます)

A問題-「Kyu in AtCoder」
B問題-「Magic 2」
- 問題概要:
- 解法:
C問題-「Marks」
- 問題概要(短縮):
- 解法:
D問題-「Road to Millionaire」
- 問題概要:
- 解法(取引日で行動を変える):

A問題-「Kyu in AtCoder」

問題URL : https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_a

問題概要:

最高レーティング $X$ が与えられるので、問題文のルールに従って保有する級を示す数字を出力せよ。

解法1:

愚直に、全ての条件を列挙し実装する方法です。プログラミング初心者の方は条件分岐を書く練習となり良い問題となったでしょう。

回答コード:https://atcoder.jp/contests/m-solutions2020/submissions/15498772

解法2:

実は、今回　求める級を $x$ とおくと、

$(10-X/200)=x$ という式が成り立ちます。

(ここで $/$ は小数切り捨ての割り算であることに注意して下さい)

よって、この式を出力してもAC(正解)することが出来ます。

回答コード:https://atcoder.jp/contests/m-solutions2020/submissions/15498809

B問題-「Magic 2」

問題URL : https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_b

問題概要:

整数 $A,B,C$ が与えられます。

以下の操作を考えます。

$3$ 個の整数うちいずれか $1$ 個の整数を選び $2$ 倍する。
これを $K$ 回行う。

$K$ 回以内の操作(0回でも大丈夫です)で、

$A＜B＜C$ が成り立つようにできるかを判定しなさい。

解法:

整数 $A$ に対する操作回数を $x$
整数 $B$ に対する操作回数を $y$
整数 $C$ に対する操作回数を $z$

とすると、

$(x+y+z) \leqq K$

が成り立ついずれかの $(x,y,z)$ で操作を行うことにより $A＜B＜C$ が成り立てばよい。

つまり、

$A*2^{x} ＜ B*2^{y} ＜ C*2^{z}$

が成り立つ組み合わせが1つでもあればよいということになります。

これは、制約が小さいことから全探索により解くことが出来ます。

回答コード:https://atcoder.jp/contests/m-solutions2020/submissions/15459754

C問題-「Marks」

問題URL : https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_c

問題概要(短縮):

評点が以下のようにつけられる。

直近 $K$ 回の期末テストの点数を掛け合わせたもの
(ただし $K-1$ 学期までの評点はつけられないものとする)

$K+1≦i≦N$ を満たすそれぞれの $i$ について $i$ 学期の評点が $i-1$ 学期の評点より真に高いかを判定し、その判定結果を出力せよ。

解法:

愚直に $K$ 回分の評定それぞれ求めようとすると、各計算に $K$ 回、その計算が $N-K+1$ 回繰り返されるので、計算量は $O(NK)$ となり、これは制約を考えると $4×10^{10}$ 回程度の計算量となるためTLE(実行時間制限超過)となります。

それどころか、 $A_i$ の制約に注目すると $1 \leq A_i \leq 10^9$ と言う表記がなされています。

仮に、 $N = 2000 , K = 1000$ で、全ての評定 $A_i$ が $10^9$ であった場合を考えます。

すると、 $10^9$ を $10^3$ 回掛けることになります。一般的にコンピューターは多倍長整数の計算が苦手なので $N$ が小さくてもこのような計算をすると時間がかかってしまいます。

ここでPoint。

Point【多倍長整数の計算】
コンピューターにとって多倍長整数(とても長い整数)のかけ算は苦手なので、時間が多くかかってしまう。

これは、オーバーフロー(int型の範囲を超える)とは違う意味なので履き違えないようにしましょう。(そもそも、Pythonはint型のオーバーフローが発生しないのでオーバーフローを考えなくても良いのですが...)

では、どのようにして計算量を減らすのでしょう。

分かりやすくするために、 $x$ 学期の評点を $M_x$ とおきましょう。

例えば、入力例1の場合

$M_3 = A_1×A_2×A_3$

$M_4 = A_2×A_3×A_4$

$M_5 = A_3×A_4×A_5$

となります。ここで、もう気づいた人もいると思いますが、それぞれの $M_i$ については共通項があります。

これを考えると、隣合う2つの $M_i$ について(以降 $L,R$ とおきます)

$R$ の最後の項が $L$ の最初の項よりも真に大きい時、 $R$ は $L$ より真に大きいということがいえるので

問題文における

$i$ 学期の評点が $i-1$ 学期の評点より真に高い　

という条件を満たすことになります。(公式解説を見た方が分かりやすいかも...)

そのため、これは $N-K+1$ 組ある

$A_i$ と $A_{K+i}$ の関係を調べれば良く、

計算量も $O(N)$ となります。

回答コード:https://atcoder.jp/contests/m-solutions2020/submissions/15459769

D問題-「Road to Millionaire」

問題URL : https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_d

問題概要:

問題文にあるとおりに株をうまく取引したとき、最終的な所持金は最大でいくらになるかを出力せよ。

解法(取引日で行動を変える):

取引日によって行動を変える貪欲法によって解くことが可能です。

(とにかく株を買えばお得になるように行動するということです)
行動パターンは以下の通りです。

$1$ 日目
株を買う、もしくは買わないの2択です。
ここで、(1日目の株価) ＜ (2日目の株価)が成り立っていれば株を買う
成り立っていなければ株を買わない　という行動が最適です
$i$ 日目 $(2≦i≦N-1)$
株を持っているか持っていないか・ $i+1$ 日目の株価との比較で最適な行動がそれぞれ変化します。
株を持っている場合
$i+1$ 日目の株価が $i$ 日目の株価より高い、または同じならば売らない
$i+1$ 日目の株価が $i$ 日目の株価より低いならば売る
という行動が最適です。
株を持っていない場合
$i+1$ 日目の株価が $i$ 日目の株価より高い、または同じならば買う
$i+1$ 日目の株価が $i$ 日目の株価より低いならば買わない
という行動が最適です。
$N$ 日目
株を売るか、株を所有していなければそのまま株を買わない
という行動が最適です。

幸いにも $N$ の制約は小さいので、このような複雑な貪欲法のシミュレーションを行うことにより解くことが出来ます。

回答コード:https://atcoder.jp/contests/m-solutions2020/submissions/15467841

以上、M-SOLUTIONS プロコンオープン 2020の解説でした！

公式解説にはこの他にも別の解法もあるので、実装できる人はやってみましょう！！

質問・指摘点などがあればコメントなどでお願いします...!!

2020-06-25

AtCoder Beginner Contest 170 解説(A~C)

ABC参加記

AtCoder Beginner Contest 170 解説

ABC170を終えて(感想と難易度の崖について)
コンテスト成績証
A問題 - A「Five Variables」
- 1.問題概要
- 2.解法
B問題 - B「Crane and Turtle」
- 1.問題概要
- 2.解法
C問題 - C「Forbidden List」
- 1.問題概要
- 2.解法
最後に) 皆さんに聞きたいことがあります

ABC170を終えて(感想と難易度の崖について)

Ruteです！AtCoder Beginner Contest 170 (A問題～D問題)について解説します。

私は、コンテスト中に3完しました！

コンテスト成績証

ユーザ名	Rute
コンテスト名	AtCoder Beginner Contest 170
順位	3692nd / 10521
パフォーマンス	862
レーティング	521 → 561 (+40)

発行日: 2020/06/14

今回はA(1:09),B(10:59),C(16:24)と3完16分でフィニッシュだったのですが、思ったよりパフォーマンスが高かったですね。

理由としては簡単で、D問題のDifficultyが緑色(1034)と、他の問題より高かったためです。

このような現象はここ最近ではABC164が当てはまりますね。

A問題:0　B問題:8　C問題:32　D問題:1204　E問題:1814　F問題:2777

(↑明らかにC問題・D問題間に"難易度の崖"が出来ています。)

これは、典型的な問題セットでは起こりませんが、数学的な問題が出題された・または難しいアルゴリズムを使う問題が出題された　場合に起こりやすいです。

もし3完・2完しかできていなくても、順位表を見るともしかするとパフォーマンスが思っていたより高い場合があるかもしれません。

では、各問題の解説に入ります！(今回はA ~ C問題です)

A問題 - A「Five Variables」

問題ページ: https://atcoder.jp/contests/abc170/tasks/abc170_a

1.問題概要

5つの変数 $x_1,x_2,x_3,x_4,x_5$ が与えられます。

最初、変数 $x_i$ には整数 $i$ が代入されていました。

以下の操作を1回行います。

・これらの変数の中から1つを選び、その変数に0を代入する。

操作を行った後の5つの変数が与えられるので、0を代入した変数がどれであったかを答えてください。

2.解法

解法としてはいろいろなものが考えられます。Python3を利用した3つの解法を紹介したいと思います。

2-1. 15から引いたもの

最初、5つの変数はそれぞれ1,2,3,4,5です。

ここで変数の和=15であることに着目すると、

(最初の5つの変数の和(つまり15)) - (操作を行った後の変数の和)

を求めることによって0を代入した変数がどれであったかを考えることができます

コード: https://atcoder.jp/contests/abc170/submissions/14673733

2-2.for文で0がある部分を特定する

A問題にあるまじき回答かもしれませんが、以下のfor文ループで解くことも可能です。

私もこの方法でACしました！

・(0,4)の区間で x[i] == 0 かを判定。もし0なら(i+1)を出力する

コード:https://atcoder.jp/contests/abc170/submissions/14284433

2-3.indexを利用する

この問題は1行で解くことも可能です。どうするかというと、Pythonのライブラリの1つであるindexを利用します。

ここで、(入力したリスト).index(0) + 1を出力すればよいです。

コード: https://atcoder.jp/contests/abc170/submissions/14673774

以上、A問題の解説でした。今後もA問題についてはACした回答以外に思いついた回答があれば掲載することにします。

B問題 - B「Crane and Turtle」

問題ページ: https://atcoder.jp/contests/abc170/tasks/abc170_b

1.問題概要

庭の動物の総数 $X$ , それらの脚の総数 $Y$ が与えられます。鶴の足の本数を2本、亀の足の本数を4本としたとき、この情報が正しいような鶴と亀の数の組み合わせが存在するか判定してください。ただし庭には鶴か亀しかいないものとします。

2.解法

鶴の数を $x$ 、亀の数を $y$ と置くと、以下の連立方程式が成り立っている必要があります。

$x+y = X$
$2x+4y = Y$

この等式を満たす $x$ , $y$ があるかを考えるのですが、今回は制約が

$1 \leq X \leq 100$
$1 \leq Y \leq 100$

という制約ですので、鶴と亀の数を全探索して求めるのがよさそうです。

以下のループを回します

$(0,X)$ で変数iを用いて以下のループを回す

　now = $Y$ - 2 * i とする(これは亀の足の本数)

　もし　now を 4 で割ったあまりが0なら

　　もし　nowを4で割った商が ( x - i)と一致したら(つまり、亀の足の

　　本数が $X-i$ と同数になったら

　　　"Yes"と出力する

　　　flag関数を+1する

　　　ループを終了する

もし、flag関数が0ならば、"No"と出力する

ここで、flag関数とは私が「フラグが立った」として定義している関数です。

コード:https://atcoder.jp/contests/abc170/submissions/14303527

C問題 - C「Forbidden List」

問題ページ: https://atcoder.jp/contests/abc170/tasks/abc170_c

1.問題概要

整数 $X$ と、長さ $N$ の整数列 $p_1,...,p_N$ が与えられます。

整数列に含まれない整数のうち $X$ に最も近いもの、つまり $X$ との差の絶対値が最小のものを求めてください。

2.解法

問題文を純粋に実装すればよいです。

まず、lsを[(i+1) for i in range(-1000,1001)]などで定義します。

(これが、出力する値の候補リストとなります)

次に、 $N$ 回以下のループを回します。

　・lsからp[i]を除外する(これは、p[i]が互いに異なるので実行できます)

その後、now = $10^5$ 、ans = -200などで定義します。

(nowが $X$ との差の最小値、ansが出力する値です)

以下のループを[tex;|ls|]回行います。

　・もし|ls[i]-X| < now]の場合

　　・now = | ls[i]-X | とする

　　・ans = ls[i]とする

最後に、ansを出力すれば、求めたい値、つまり $X$ と絶対値が最も近い整数を出力することができるでしょう。

コード:https://atcoder.jp/contests/abc170/submissions/14309381

最後に) 皆さんに聞きたいことがあります

ABC170の解説はここまでです。最後まで見ていただいた方、ありがとうございました！

さて、ここで私から皆さんにお聞きしたいことがあります。

これまでは、AtCoder Beginner Contestで私が解けた問題をすべて1つの記事で列挙していたのですが、おそらく"記事が長い"などと考える方もいると思います。十分承知です。

そこでですがいろいろと考えています

・問題別で解説記事を作成する

これは、単純に記事を短くして、1つ1つの記事で解説をより分かりやすいものにしたいと思ったからです。ただ、これによって記事間を遷移しないといけないというデメリットが生じます

・解法を大筋のみ書いて、後はリンク先のコードで解説をする

これは、記事の長さが短くなりますし、単純にコードに解説が書かれているので良い試みだと思っています。

その他、このブログに対して「こうすればもっと解説が読みやすくなる」という取り組みがあれば、コメント　または @rute_not_routeのツイッターにDMをして教えていただけると助かります！(ABC172の解説以降で繁栄予定です)

私としてはPython3をメイン言語にされている方にとってわかりやすい解説にしたいと思いますが、C++を利用されている方、Javaを利用されている方等も遠慮なく教えていただけると助かります！

皆さんのコメントを参考にして今後記事を書いていきます！よろしくお願いいたします。

2020-06-13

東京海上日動　プログラミングコンテスト2020　(A,B問題)解説

こんばんはー。最近レート降下中のRuteです。

今回は、AtCoder Beginner Contest ... ではなく

東京海上日動　プログラミングコンテスト 2020 の解説をまとめます。

(といってもA,B問題だけですが)

まず、私に足りないことが今回のコンテストでわかりました。

読解力不足です。(どういうことか知りたい方はこの後のB問題をご覧ください)

1. A問題「A - Nickname」
- 問題概要:
- 解法:
  - コーディング:
2. B問題「Tag」
- 問題概要:
- 解法: 読解力不足が及ぼした結果...

1. A問題「A - Nickname」

問題URL https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_a

問題概要:

長さが $3$ 以上 $20$ 以下の文字列 $S$ が与えられます。

$S$ から適当に連続する $3$ 文字を出力しなさい。

解法:

適当に連続する $3$ 文字ですから"先頭から3文字"を考えます。Pythonでは $S$ における先頭i文字をS[:i]で取得することが可能です。今回の場合はS[:3]で取得できるので、あとはこれを実装するだけです。

コーディング:

f:id:Rute_programming:20200613215111j:plain

回答コード:https://atcoder.jp/contests/tokiomarine2020/submissions/14218268

2. B問題「Tag」

問題URL https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_b

問題概要:

数直線上に、 $A$ に存在する点P, $B$ に存在する点Qが存在する。

点Pは毎秒 $V$ の距離を移動することが可能。

点Qは毎秒 $W$ の距離を移動することが可能。

点Pと点Qで鬼ごっこをするとき、 $T$ 秒間に点Pが点Qに追いつくかを判定せよ。ただし、点Pと点Qは最適な移動を常に行う。

解法: 読解力不足が及ぼした結果...

最初、提出したコードはこちらです。

f:id:Rute_programming:20200613215646j:plain

残念ながらこれではWAになりました。なぜWAの判定となるかわかりますか？この後説明します！

初めに、問題を整理すると(ここでは鬼役を点P,逃げ役を点Qとしています)

点Pの0秒での座標は $A$ ,移動速度は $V$

点Qの0秒での座標は $B$ ,移動速度は $W$

です。

解法(アルゴリズム的なもの)

$V≦W$ のとき、明らかに点Pは点Qに追いつけないので"NO"を出力します。

(V = Wかつ A = Bのときはすでに追いついていますが、制約上このようなケースは考えられないです)

そうでない場合は、

距離 = $A$ と $B$ の絶対値、速度 = $V$ と $W$ の絶対値

として以降話を進めていきます。

誤った解釈だとこうなる。

距離を速度で割ったあまりが0でない場合、「相手と同じ座標にいる」というのが不可能なので"NO"と出力する。

あまりが0の場合は、距離を速度で割った商が

・ $T$ 以内なら"YES",

・ $T$ より大きいなら"NO"

と出力する。

...という解釈で最初は進めていました。しかし、なぜかWAを連発します。ここで、問題文がよく分からなくなるといういつもの現象に.... (Writerさんごめんなさい

冷静に考えると、1秒単位で同じ座標にいるとき以外も考えられそうです。(例えば、「1.5秒で同じ座標にいる」という場合を考えることができます)

ちょっと不安だったのでclarを投げました。

f:id:Rute_programming:20200613220751j:plain

すると、答えが「Yes」として返って来ました。こうなると解釈が変わってきます！

正しい解釈

$V≦W$ での条件分岐はそのままで

距離・速度について

0 < 距離/速度 ≦ $T$ ならば"YES",

そうでなければ"NO"

を出力する。

これでようやくACを出すことが出来ました！

コーディング:

f:id:Rute_programming:20200613221138j:plain

回答コード:https://atcoder.jp/contests/tokiomarine2020/submissions/14237193

ちなみに読解力不足が招いた代償として4回のWA...(うち1回はコピーミスによるRE)

まぁ読解力不足ということで、次回以降は気をつけます。

以上、東京海上日動　プログラミングコンテスト2020のA問題、B問題の解説でした！

明日のABCではRatingを上げられるようにしたいです！

2020-05-31

AtCoder Beginner Contest 169 (A~B)解説

ABC169が 2020/05/31 21:00 - 22:40の期間で行われました！

皆さん、お疲れ様でした！

今回の問題、正直なところこれは知識がかなり必要だったのかなと思っています。

Writerさんには新たな知識を与えていただいたということで感謝しています。ありがとうございます。

そして、B.C問題が解けないからといって　順位表以外の内容をTwitterで言及している方が見られたようです。正直これはWriterさんに失礼だと思いますし、解いている方に対しても失礼だと思います。unratedになる可能性がある行為ですのでやめましょう。

問題について振り返っていきます。

A問題 - A - Multiplication 1
B問題 B - Multiplication 2

A問題 - A - Multiplication 1

https://atcoder.jp/contests/abc169/tasks/abc169_a

もはや簡単。 $A×B$ を出力するだけの簡単なお仕事　世界一簡単な問題　FA10秒　私は19秒

コード : https://atcoder.jp/contests/abc169/submissions/13774212

B問題 B - Multiplication 2

問題概要:

$N$ 個の整数で構成された数列 ${A_1 , A_2 , ... A_N}$ がある。

この時、 $A_1 × A_2 × ... A_N$ を出力せよ。

ただし　 $10^{18}$ を超える場合は"-1"を出力せよ。

私が最初に提出したコードがこれです。

https://atcoder.jp/contests/abc169/submissions/13781425

f:id:Rute_programming:20200531222641j:plain

判定はWAでした。このコード、いくつかの点で計算量を削減できたのにそれを無視している点があります。さて、どこでしょうか。

では正解(ACした)のコードです。

https://atcoder.jp/contests/abc169/submissions/13812984

f:id:Rute_programming:20200531224944j:plain

画像について誤りがあったので変更しました。 (22:50)

いくつか計算量を削減できるコツがあるので説明します。

ｺﾂ1. 降順ソート

これはTLEになってからいろいろ考えたのですが、大きい方から貪欲的にかけていけば掛ける回数を減らせるのではないかと考えました。よって、A.sort()→A.reverse()ではじめに降順ソート(大きい順にソート)しました。

ｺﾂ2. 0があった場合

数列 $A$ に0があった場合、どのみち解は0です。ただし、愚直に0が出るまでかけていくと、計算量が増えてしまうので駄目になります。そのため、0が数列に出現していた場合、その時点で0を出力しその後の処理をしないようにしました。

ｺﾂ3. 10^18で処理終了

最後に、乗算し続けた値が、 $10^{18}$ より大きくなったら処理をやめて"-1"を出力しました。これは単純に計算量を減らすためです。

このように、計算量を減らすテクニックは競プロの問題でも頻出です。例えば、かの有名な「Otoshidama」問題であったり、私が先日GCC002のE問題で出題した問題では、全探索を行っても実行時間制限を超過してしまうので、変数を1つ固定するなどして、計算量を減らすテクニックを利用すればACすることができます。

GCC002 - E - Combination

https://www.hackerrank.com/contests/gcc002/challenges/combin

Otoshidama(ABC085)

https://atcoder.jp/contests/abc085/tasks/abc085_c

大量データを処理する現代にとって、高速で動くアルゴリズムは重要ですから　今回のコンテストのみならず　なるべく高速に動作するようにプログラムをコーディングするのが大切だと思っています。

以上で、B問題の解説を終わります。

C問題

最終的にはこのようなコードでWAでした。

https://atcoder.jp/contests/abc169/submissions/13857616

(誤差をなるべくなくすために小数の桁数を無理やり多くしましたが、駄目だったようです)

以上、ABC169 (A~B)の解説でした。今回は教育的な問題が多くて良かったと思います。