R6春-応用情報技術者試験 参加記(純粋培養競プロer)
はじめに
先行文献を参照してください
きっかけ
Twitter(X)を見ていると競プロerの人たちが無限人APをとっていたので、せっかくならとりたいな～と思っていました
今年の冬休みがあまりに暇だったので春に受けるかーと思って申し込むことにしました
試験前のスペック
大学生で学部は理系ですが情報系ではないので、ネットワークとかセキュリティに関する知識はほとんどありませんでした
競技プログラミングをやっている(AtCoder 黄色)ので、プログラミングだけは多少できるかなという感じでした
使った参考書
キタミ式がいいという話を聞いていましたが、近くの本屋になかったので2,3個みてよさげなのを選びました
ニュースペックテキスト応用情報技術者 | TACの高校生向け資格教材
あんまり比べていないのでよくわかりませんが、まあ普通にわかりやすいと思います
各分野につき10問程度過去問が載っているのですが、直前に見ていたらそこから結構出たので助かりました
試験勉強(午前)
2年前くらいに少しやる気になって0.7周くらいテキストを読んでいたのですが、もう忘れていたのでとりあえずもう一回テキストを1周しながら、わからないところをメモしていきました
春休みに頑張ろうと思っていたらいつの間にか3月が終わっていたので、4月頭くらいから進めました
プログラミングだけはほとんど知っていそうだったので読んでいません
一周してからは知識の確認+試験に慣れるため過去問道場で問題を解きました
4/8~17で午前問題は全部解きました(2000問くらい？)、正解率は分野にもよりますが70~85%でした
これで試験直前になったので、テキストをざーっと2周くらいみて軽く復習をして本番になりました
試験勉強(午後)
午後に手をつけはじめたのが試験1週間前くらいだったので、いけそうな分野をいくつか絞ってやることにしました
選択としては以下の通りです
絶対選択：セキュリティ(必須)、プログラミング(得意)
この中から問題を見て選ぶ：経営戦略、組込みシステム開発、プロジェクトマネジメント、サービスマネジメント、システム監査
選ばない：のこり
セキュリティ、プログラミングについては選ぶ以外の選択肢がなかったので特に考えていませんでしたが、ほかのものは過去問をちょっと見て、読解主体で戦えそうなものを選びました
2年分くらい解いてみた感じとしては経営戦略・システム監査が比較的得意そうだったので、そこをメインにして残りは雰囲気で決めることにしました
解いたのはセキュリティ6年分くらい、ほかは2,3年分くらいでした
試験当日
試験場までもろもろ90分くらいかかるので、6:00くらいに起きて準備しました(つらい)
都会だと脱落率が高いのかもしれませんが、田舎だと割とみんな受けてました
空席は10%あるかないかくらい？
午前
午前は6割切ることはないかな～と思っていたので多少気楽に受けました
序盤はわりとサクサクいくんですが、中盤に怪しいゾーンがあって、後半はいけてそうって感じで進みました
1時間15分くらいで退出して午後に備えることにしました
昼休み
近くに店がない(!?)ので、コンビニで買っていたおにぎりを食べながらテキストの午後対策をみていました
解答速報があるらしいというのをTwitterでみたので入力しました
67/80らしいのでさすがに速報といえど大丈夫だろうと思って安心します
午後対策をやっていたんですが、これ意味ある？？となったので最後はぼーっとしていました
午後
絶対に選ぶセキュリティ・プログラミングをさばいてほかに向かうことにします
1. セキュリティ
解くしかないので解きます、そんなに複雑なシステムではなさそうなので少し安心しながら進めていきます
選択問題・記述問題は雰囲気でいけてそう+ゼロトラストは知ってたので、意外と点数あるかも？となります
セキュリティは10点くらいの想定だったのでいい感じ～
3. プログラミング
O(N^2)のDijkstraやるだけ、競技プログラミング最高！余裕でした
経営戦略の穴埋めが微妙かなと思ったので、組込みシステム開発を先に解きました
7. 組込みシステム開発
ちょっと悩む問題も多かったですが、何回もゆっくり問題文を読むとだいたいわかりました
最後の問題はよくわからなかったけど、7割以上はありそうなのでこれを選択することにしました
プロジェクトマネジメントをみると穴埋めが経営戦略以上にわからないので捨てることにします
10. サービスマネジメント(結局選ばなかった)
ある程度解けそうなので解き進めるんですが、bに入れるものに確信が持てません
対応が落ち着けばいいよね～というのはわかるんですが、これを抜き出してくれ！みたいなのを感じ取れなかったのでちょっと嫌な気持ちになります
設問3の「展開管理」というものが指しているものも自信がなかったので逃げることにしました
11. システム監査
これ難しかったらまずいな～と思っていたんですが、関連しそうなところを抜き出すとだいたい字数が合うのでいいんじゃね？と思って選択しました
2. 経営管理
穴埋めは微妙ではあるんですが大外しはしなさそうなのでこれを解くことにします
勉強不足でb,cの自信がないですが、あとはそれっぽいことを書きました
もう疲れたので残り30分くらいで軽く見直して1,2,3,7,11で提出しました
試験対策・テクニックについて
いろいろなところで書かれているとは思うんですが、重要だなと思ったことをメモしておきます
・計算問題は得意だと結構アドバンテージありそう
計算問題は定義を覚えれば(何なら覚えなくても単位や用語の雰囲気で)パターン化されて解きやすい問題が多いです
ここが得点源になるとかなり楽です
・用語のニュアンスをくみ取る
知らない用語でもそれぞれの単語の意味や英語の内容がわかっているとかなり絞りやすいです
今回の午前だと
問19(犯罪捜査とかのプロファイリングのイメージ)
問49(アセスメントがわかるとそれっぽい)
問50(ドキュメントジェネレータ=ドキュメントを生成する、がさすがに正解)
問71(マスカスタマイゼーションとあるのでカスタマイズしてそうなもの)
などが直接知らなくても拾えると思います、全部拾えなくてもこのうち2,3個とれるだけでも大きいので知らない用語でも考えることが大事そうです
・変なひっかけはない(？)
大学入試の問題だと「だいたいはあっているけど細かい用語を変えて×にする」選択肢がちょくちょくあるんですが、応用情報だとそういうのはほとんどないと思います
ふわっとしたイメージがあればそれに近いものを選ぶとよいと思います
逆にだいたいあっているけど...という時に変に疑わないほうがよさそうです
・午後試験で逆張りやうがった見方をしない
あくまで「試験」なので、正答になる解答には正答になる根拠があります
国語の試験でもありがちなんですが、「Aって書いてあるけどBかもしれない」ときにAを捨ててBを書く理由は基本ありません
試験であるということを忘れて午後の試験で、自分がなんとなく思ったことを書くと点数を失います
知識を要求する問題はしょうがないですが、そうでない問題は必ず本文に根拠があるので本文からできるだけずれない解答をしましょう
正直ほぼ抜き出して字数を調整するくらいでちょうどいいんじゃないかなと思います
結果報告
午前90点、午後93点でした
<午前詳細>
ストラテジ 95%、マネジメント100%、テクノロジ86%
<午後詳細(予想)>
1. セキュリティ 20/20
2. 経営戦略 18/20 「代替」ミス
3. プログラミング 20/20
7. 組込みシステム開発 17/20 最後ミス、記述1問△
11. システム監査 18/20 aミス？
まとめ
午前はひたすら過去問、午後の文系問題は抜き出し
受験される方は頑張ってください！
DDCC2024 参加記
参加の記念にメモ程度ですが残しておきます
予選
しれっと応募が始まって予選の一週間くらい前には終わっているので忘れないようにしましょう
過去問を見てもらうとわかるんですが、謎の入力形式になっています
終わるまで気づかなかったんですが、そのままソースコードに貼ることを想定していそうです(文字列が""で囲んであったり、vectorなどにしやすそうなものが{}で囲んであったり)
これをいちいちパースしているとそれだけでも時間がかかるので、特に非就活枠の人はあらかじめどう取り組むか決めておいた方がいいと思います
手元実行をするタイプですが入力のサイズがかなり小さいので、AtCoderのコードテストで全然いけます
予選問題(覚えている範囲で)
Q1 なんか愚直でいける簡単な問題でした、覚えてません
Q2 時刻の足し算を要求された気がします、ド典型なんですがめんどくさい
Q3 N(N≦10)個の点が与えられて、巡回セールスマン問題の逆(最大化)みたいなことをやりました、点をまたいではいけないというルールがあったんですが、制約が優しいので順列全探索 + 距離を愚直に判定で通りました
Q4 体感1600diffくらいのナップサックDP亜種、何種類か荷物のカテゴリが分けられているのでそれぞれについてDPで最適解を求めて、それを合体させるみたいなことをすると解けました
パースに時間がかかった + コロナ明けで瞬発力がなかったのもあって90分くらいかかってしまいましたが就活枠なら通過していました
全完すれば就活枠なら通過は確定でそうでなければ早解き勝負ぽかったです
本戦
就活枠+遠方なので、移動費と前日分の宿泊代が支給されました(ありがとうございます)
宿泊はDISCOさんから指定された会場に近いところに泊まりました
ダブルの部屋で広くて楽しかったです
今年の問題も2021,22と傾向は同じで、穴とバーのあるパチンコ台のようなものを操作して球を入れていく装置実装問題でした
1. シミュレーション
そこまで時間がなかったので、とりあえず直線的に射出するプログラムを書きました
最上位が27000点くらいで、自分が18000点くらいでした
-昼食-
お弁当を自由に選んでねと言われたので、牛とろろ弁当みたいなのにしました
賛否両論というところのお弁当だそうで、食材として苦手なものも割と食べられておいしい店ってすごいな～と思いました
nok0さんやmilkcoffeeさんたちと談笑していました
2. 実機確認1
スコア計算もまともに読めていなかったので、スコア計算をもとに改善を考えます
横方向の傾きは考慮すると頭がバグりそうだったので縦方向の傾きとバーの向きで加点できるようにしました
実機確認はシミュレーションのコードを使うのでまあそうだよな～という結果でした
あとあと考えれば、シミュレーションであまり点を取らなくても傾き方だったり反射だったりのデータを得ていた方がよかった気がします
3. 実機確認2
とりあえず簡単な穴には入りそうだったので、そうでない穴に入れる方法を考えて反射を実装してみました
ただ反射の計算が意外と面倒で実装するだけでほとんどまるまる使ってしまいました
多少時間が余ったので軸の向きをギリギリにして点数を上げられるようにしました
確認フェーズは2のコードを使うんですが、バーに当たって入っていないものがあったのでそこを何とかしようと思っていました
-会社説明・見学-
DISCO主催の大会なので会社説明と見学が計1時間弱くらい？ありました
福利厚生というか職場の中にリラックスできそうな空間があるのすごくうらやましいなと思いました
病院にもダーツとプールを置きましょう
4. ファイナル
エンタメ色が強めの大会で演出や実況解説の存在にびっくりしていました
適当にしゃべったインタビューが放映されてそういうことか...となりました
ファイナルの結果はカスで、直前に実装した反射がうまくいかなかったのと軸の角度を攻めすぎて入らなかったのでボロボロでした
実機確認1まででやりたいことの80%くらいは実装しないといけなくてそこから微調整するのがよさそうだったんですが、そもそも時間が足りずやりたいことができませんでした...
そもそも上位陣がほとんど反射を使わず傾きで戦っていたので、単純に戦法をミスっていたんだなと思います(これ知ってるかだけでも情報アドバンテージになりそう)
あとは表彰式をやって終了という感じでした
nok0さんが優勝していてマジですごい
来年機会があればリベンジしたいです
DISCOさん楽しい大会をありがとうございました
医学部CBT 参加記【IRT 750↑】
いつも競プロの記事を書いていますが、せっかくそれなりに頑張ったので残しておこうと思います
守秘義務とかがあってあまり細かいところは述べてはいけないので、勉強ペースとか解き方テクニックとかが主になります
問題の物量で殴って高得点！という感じなので効率はよくないかもしれません
結果
IRT 750+ちょっとでした(おそらく95%くらい？)
やったこと
まず前提としてCBT以前にどの程度勉強しているかが、対策にかかる時間・内容に影響してくると思います
普段の学校の勉強はそこそこやっていて、GPAだと学内3~5位くらいです
使用した教材
・QB CBT (メイン)
・Q Assist
・問トレ
・(病気がみえる) ←たまに確認する辞書的なポジション
スケジュール
完璧に仕上げるまではいかなくても、せっかくやるならそれなりの点数をとって受かろうというくらいの気持ちで準備しました
もっと点数を積むには、もっと時間を割かないとだめだったかなと思います
3年1月 ~ 4年7月：授業が忙しいのでテスト勉強中心、テスト勉強がひととおり終わったらその範囲のQBをとりあえず解く
力試しに解いていた感じで、そのときの得点率は70~80%だったと思います
この段階ではQBの問題をまとめたりはしていません
4年8月~9月：夏休みで時間があるのでQBの基礎を解く + 授業が始まったらゆったり臨床科目(↑で解いている)をもう一回解いてみる + (9月)同じ範囲の問トレをする
このときにやったこと
・基本的にQB + 問トレを解き進める
・Q Assistは得点率が低かったり、自分の中で分かってなさがやばいところを見る
・わからないところはとりあえずまとめノートに雑多に記録する
・授業は半分くらい聞きながらひたすら問トレをしていました(こっちはまとめノートなしで知識の確認)
====この時点でQBの進捗2000問くらい====
4年10月上旬：臨床が解き終わりかけたので、そこから公衆衛生・多選択などを解く
4年10月中旬：1週間弱で4連問をががーっと解く、MEC模試を解く(10/10くらい)
この時点で基礎医学2周 + 臨床2周(てきとうな1回 + ちゃんとやる1回) + 公衆衛生以降1周の状態
4年10月下旬：まとめノートで復習しつつ、QB模試を受ける(10/23)
模試はQBと先輩からもらった2,3年前のMEC模試を解きました
模試の感想
・MEC : 知識問題にたまに難しいのはあるけど基本的には知識で瞬殺できる簡単なのが多い、特に多選択が超簡単であんまり参考にならなかった
・QB : うってかわって知識瞬殺は少なめ、雰囲気で推測できるけど自信ないみたいな問題がかなり多い、自分の結果はかなり2択が上振れてる(が、2択などに絞れてる状況に持ち込めてるのが学習の成果ともとれる)
結果：どちらも94%くらいでした
4年11月：ある程度の知識は身についているのでまとめノートの見直し + 5日くらいで問トレを全部解きなおした
前日は自分が間違えたQBの問題をひととおり解きなおした
11/7が本番です
最終的にやったこと
QB： 基礎 + 臨床3周、公衆衛生以降 2周
Q Assist : 苦手なところだけ見る 循環・産婦人科を主に見ました
問トレ：全体2周
模試：QB + MEC
テクニックなど
勉強のしかたは人それぞれだと思うので、QB, 問トレで演習している中で大事だなと思ったテクニックや雑多なコメントを書いておきます
※あくまで試験で点数をとることを目的としているので、医学的に正しいかは知りません
①臨床問題では年齢がめちゃくちゃ大事です、かなり絞れるので見ないとすごく難しくなります→直感でもいいのでざっくりの好発年齢がわかるとよいです
②体系的な理解が大事なのはそうですが、どうしてもテスト問題にする都合上特徴的なキーワードや病態で決め打てる問題は多いです
代表的な臨床問題だと、だいたいエピソードも共通しているのでそういうところから攻めるのは良いと思います(ex. 何週間か前にこけた→ほぼ慢性硬膜下血腫)
③4連問でしっかり点を取ろうと思うと、1問目の時点で具体的な鑑別診断が挙がることが望ましいです
それができると、症状も具体的に考えることができるので、選択肢を絞りやすくなります
④産婦人科はとりあえずエコーで解決！！(正直迷ったらエコーでいいです)
⑤QB・問トレどっちも一定数かなり難しい or 細かい問題が入っています
個人的にはQBの基礎は難しすぎるのでは？と思っています
難易度判定はなかなか難しいと思いますが、ひたすら問題を解く or 勉強している友達に聞くなどすると、大事な知識か細かい知識か分かる(はず)
→ここができるとできないとで効率はかなり変わると思います
重要そうな問題はがんばって、そんなーみたいなのは適当でいいです
結構時間かけてるけど点数が微妙だなみたいな友達の話を聞いていると、全部同じ強さで勉強していてパンクしているというのが多い気がします
⑥問トレの必要性ですが、QBのあとに復習するという意味なら使う価値はあると思います
個人的には難易度はQBよりやや簡単と思います(が、そうでないという意見も多い)
変な問題がたまにあるのはそうですが、それはQBもいっしょ
⑦個人的な考えですが、1周目から知らないことを全部メモすると膨大になるので、1回てきとうに解いてなんとなく理解してから、もう1回解くときにまだ覚えていないことをちゃんとメモするのがいいかなと思います
最後に
QBと問トレをぶん回せばなんとかなるという感じでやってきて、まあまあいい感じの点数になりましたが、もっと高得点を取るには病気がみえるとかの網羅性が高い勉強が必要なんじゃないかなと思いました
ある程度の水準に到達するまでは、100%を目指しすぎず知識を少しずつ積み上げていって「なんとなくわかる！」という範囲を広げていくのがいいと思います
それなりに大変な試験ですが、うちの大学ではQB1周が間に合った人はほとんど合格していたのであまり気負わず頑張ってください！
第四回最強プログラマー学生選手権決勝 参加記
参加してきました
コンテスト以外のことも書きます
Day0
たまたま午後の授業がなかった(夏休みは1カ月前に終わっている...)ので、15:00くらいの飛行機で東京へ
編入前の友人と会ってハンバーグを食べて英気を養う
データサイエンティストになりそうと言ってたので、AtCoderをやってほしいな～と思いながら...
前も誘って緑くらいで忙しくてやめちゃってたので復帰してほしいけど、大学院がすごく大変そうだった
その後は友達の家に泊めてもらってゆっくりねた
Day1
気合入れようと思って友達とお昼から焼肉を食べた、おいしかった
泊まっていたのは大塚だったので山手線で田町まで
ちゃんと場所が見つかるか不安だったけど、近くの建物にkaedeさんがいて案内してくれた
会場で受付をして、スポンサーのサントリーさんから飲み物をもらって着席
半分ちょいくらい人がいたのでちょうどいい時間だな～と思いながらゆっくりした
席にはクリアファイルとかシールとかがあって置いてあった
みんなそれなりに早く来ていてakenshoさんがびっくりしていた
ちゃんと来ているのに遅刻オッズ1位のnoimiさんかわいそう
スケジュールに開会式って書いてあったからどんなものかなと思っていたけど、ふつうにchokudaiさんがしゃべってゆる～く終わった
特にやることもないのでライブラリとかをみながら時間を待ってコンテスト開始
A Apple Addiction
300点ね～、OKと思っていたけど開いてみると、典型だけど明らかに300ではなさそうな問題が置いてあります
気持ちを落ち着けながら考察を進めていると、周りが爆速でタイピングし始めてびっくりします
考察はそんなに重くなくて、どうせdp[i] := i番目を食べたときのmaxなので、遷移を詰めていきます
長さKはかぶってもよくK以上に言い換えられるので、そのまま伸ばす or 新しく長さKの区間をとるのどちらかをすればよく、
dp[i] = max(dp[i-1] + A[i], max(dp[0] ~ dp[i-K]) + sum[i-K+1 : i] )
という遷移になります
なんかうまいことできそうだな～と思うんですが、セグ木で自明にできるのでmaxのセグ木を使って遷移を書きます
多少バグらせるけど直すとサンプルも普通に合うので提出してAC
(AC 22:03)
B Max Degree Sum
600はさすがに解かないとまずそう + 解けそうなので次はBに行きます
最初とっかかりがなくてどうしようと思いますが、いろいろいじっていると
・両方の端点がk以下
・片方の端点がk以下
・両方の端点がkより大きい
の優先順位で結ぶのがよさそうだと思います
両方の端点がk以下となる辺はどんどん増えていって消えることはないので、これをとりあえずつなげていくUnion Findを準備します(木にしないといけないので閉路を防ぐ)
これで「両方の端点がk以下となる辺」の数はわかるので、この辺数 × 2が答えに加算されます
ほかに答えに関係するのは「片方の端点がk以下となる辺」です
これは「k以下の頂点から伸びている辺」なので、k以下の頂点から1手で到達できる頂点を列挙しておきます
ここにある頂点にはとりあえず伸ばすのが最善なので、到達できる頂点数分増えるのかな～と思って実装します
これは実装するとサンプルが合いません
もう少し考えると、同じ頂点に複数本伸ばしても閉路にならないことがあるなと思います
今までは「到達可能な頂点」を考えていましたが、逆に「到達不可能な頂点」を考えると、その頂点と連結にするために1頂点につき1本辺が必要なので、「到達不可能な頂点」の数を引けばいいかな？と思います
実装するとサンプルが合うので提出するとWA
後半パートがちょっと怪しそうなのでもう少し考えます
上の実装は、到達できない頂点以外は「片方の端点がk以下」の辺を使うことを前提としています
ただ、手元でグラフを作っているとその前提を満たせないケースがあります
そのような場合は「両方の端点がkより大きい」辺で結ぶことになります
このような辺の数は、k以下の頂点から伸びている辺をすべて使った別のUnion Findを用意しておき、その連結成分数をみる(=1でなければkより大きい頂点同士で連結にするしかない)ことでわかります
これをまとめて
(両方の端点がk以下で使う辺) × 2 + (木にするためにまだ必要な辺) - (1手で到達できない頂点の数) - (2つめのUnion Findの連結成分数 - 1)
で求めることができます これでAC
(AC 46:20)
E Min Subtraction
Cを解こうか悩んだんですが、もうかなり解かれていて賞金を狙うには900必須(ワンチャンABD, ABEでいけない？)と思ったので、どっちかというと解けそうだと感じたEをやります
まず1回の操作で少なくとも1つは0になります
おきもちとしては、左から右に進めていくように連続して0をつくっていけると結構得する + 最終的に両方0がつくれるとアツいと思います
操作を始める場所を決め打つと、偶奇を分けたときに開始位置からの和の大小関係が単調増加 or 単調減少になっているといいことがわかります
このあたりをうまく使おうと思っていたんですが、始点が変わると大小関係も簡単に変化してしまってどうしようもなくなってしまいました
クリティカルっぽい考察も生まれなかったので賞金はあきらめてCを解くことにしました(1時間~1時間30分くらい消費)
C Power Convergence
700だし苦手よりな数学問だしな～と思って避けていたんですが、Eが虚無すぎたのでCを解くことにします
とりあえず移項すると x^k (x-1) ≡ 0 (mod N)になるので、うまくできそうな気がします
すぐに気づかなかったんですが、よくよく考えるとxとx-1は互いに素になるので、mod Nで0(Nで割り切れる)になるためにはNの素因数をxとx-1に割り振る必要があります
そうすると以下のような条件を満たす数を見つけることになります
・xとx-1は互いに素である (常に満たされる)
・x-1はNの素因数のうちいくつかを持つが、Nの素因数の指数以上でなければならない
(12 = 2^2 × 3なら、 2^1はダメで2^2でないといけない)
・xはx-1に含まれないNの素因数を持たなければいけない
(こちらはk乗するので、指数が足りていなくてもOK)
ざっくり考えると、x-1側を決め打つとxに含まれないといけない素因数がわかるので、x-1を決め打とうと思います
これは、x-1がAで割りきれる = xをAで割るとあまり1、xはBで割り切れるという2つの条件になるので、CRTを使うと該当する数を求めることができます
具体的なものも書いておきます
N = 12とすると、 N = 2^2 × 3なので考えられるパターンは以下の通りです
・x-1が1で割り切れる xが6で割り切れる -> f(x) = 2
・x-1が1で割り切れる xが12で割り切れる -> f(x) = 1
・x-1が3で割り切れる xが2で割り切れる -> f(x) = 2
・x-1が3で割り切れる xが4で割り切れる -> f(x) = 1
・x-1が4で割り切れる xが3で割り切れる -> f(x) = 1
・x-1が12で割り切れる xが1で割り切れる -> f(x) = 1
※x-1が2で割り切れるというのは、素因数2があまってしまうのでダメ
これらそれぞれについて、CRTで該当する数を求め和を取ればいいのですが、実はかぶりがあります
・x-1が3で割り切れる xが2で割り切れる -> f(x) = 2
・x-1が3で割り切れる xが4で割り切れる -> f(x) = 1
このようなものを数えようとすると、xが2で割り切れる数にはxが4で割り切れる数も含んでいるので、いい感じに処理しなければいけません
＝＝＝コンテスト中ここまで＝＝＝
これは典型的な問題で、大きい方から除原理のように解いたり、約数の高速メビウス変換をしたりなどで、重複を取り除けます
除原理をすると、x-1を決め打つパートがあるので、見た目的には約数の個数をDとしてO(D^3) になるかもしれませんが、適切に枝を刈るとO(D^2)になる(と思います)
(AC --:--)
コンテスト後
Cを解ききれず、う～んと思いながら企業プレゼンを聞いた
普通に内容はおもしろかったけど、ヒューリスティックの方が大事そうだなと思った
そもそも今のところ入学枠の都合で一般企業への就職がダメなので、そういう人で申し訳ないなと思いながら聞いた
表彰式は観客としてワクワクしながら見てた
tatyamさんでも10位なのか～と思っていたら、vwxyzさんが6位ですごーとなった
vwxyzさんの名前が呼びにくそうだった
3~5位はいつもの強い人たちだな～という感じで、1,2位は順位表的にpotatoさんとSSRSさんの争いぽかったのでどっちなんだろと思っていたら、SSRSさんが優勝していた
初観測したのでこんな人なんだと思ったけど、感想とかしゃべってもらって人柄をざっくり把握したかったな～
懇親
ご飯を食べながら懇親会で何人かお話しした
Twitterで見たことある人じゃないとしゃべりづらい...
karinohito, sotanishy, nok0, zkou, nawa, AngrySadEight (敬称略) + UNICORNやALGO ARTISの社員さんと話した
ALGO ARTISの人になんであんなに優秀な人ばっかりなんですか？って聞いたら、全力の引き抜き + 盛んな社内勉強会でレベルアップというのを聞いて、すごくいい環境だな～って思った
懇親会後はnok0さん、zkouさん、karinohitoさんと4人でガストに行った
ハイライト
・緑~水色のころコードを見ていると、同じBFS記事をコピペしていて無意味すぎるコメントが一致
・zkouさんがnok0さんに「これ解けないのやばいよ～」と詰められているのを観測
・ABC見ながら「Dやばいよね」ってみんなでわちゃわちゃする
みんなFPS分野が強くてぼくも逃げてられないなと思った
22:00すぎくらいまで色々話して解散
浜松町にホテルを取ってたので向かって就寝
春にはオンサイト(UTPCとか？)ありそうで学校も休みなので、競プロしに行こうかなと思ってます
交流してくださった方、開催してくださったAtCoder社そのほかありがとうございました！！！
ARC165 参加記
A~C 3完 66:05 247位
B通されすぎてやばかったけどCを瞬殺してプラス
A Sum equals LCM
ARCはAからちゃんと考察しないといけない
Sumの部分については、+1を繰り返すことでLCMを変化させずに1ずつ調整できるので、問題は「LCM=N, Sum ≦ Nにできるか？」に言い換えられます
これは、LCM = NとしたときにSumを最小化してくださいということなので、最小化を考えます
Nを素因数分解して、N = 2^3 × 5^2のようになったとすると、2^3, 5^2は必ず必要で、逆にそれだけ存在していればよいです
つまり、Sumを最小化しようとすると、素因数ごとに必要なものを足していくことになります
これを愚直にやるとO(√N)で通ります
もう少し考察すると解説みたいに素数のべき乗か否かになるけど、そこまでしなくてOK
(AC 4:57)
B Slinding Window Sort 2
通されすぎ～～～～
一つ一つ考察していきましょう
まず、選んだ区間は昇順ソートするので、もともとの数列より辞書順で小さくなることはありません
なので、「どこまで損をしないようにできるか？」の勝負になります
とりあえずいろいろ考えていると下の2つに気づきます
・一番後ろの区間を選ぶのはそれなりに強そう → P1 ~ PN-Kまでは動かさなくてよいからそこまでで損するパターンすべてに勝てる
・区間の中身が単調増加になっているものがあれば、そこを選ぶともとの順列と変わらないので最適となるものの1つ
ここまででそれなりに解けていそうですが、{3,2,5,4,1} (K = 3)のようなケースで困ります
これは最後の区間で操作すると、{3,2,1,4,5}になります
しかし、最善なのは[2:4]で操作した{3,2,4,5,1}です
このようなパターンはなぜ起こるか考えます
まず、最後の区間([3:5])を選んだ時にそれ以前のところは変化しない必要があります
よって、[2:4]の例だと、[2:2]にあたる区間は以下の条件を満たす必要があります
・単調増加である
解説ではこれを満たす最も左の区間にすれば最善であると示していますが、それが示せなかったのでもう少し工夫をしました
「区間[i:i+K-1]と区間[j:j+K-1] (i < j)を比較した時、どちらが辞書順で大きくなるか？」をO(logN)程度で求められればよいので、それを考えます
先ほどの議論と同様に、[i:i+K-1]で操作した方がよいのは、以下の条件が成り立つときです
区間がかぶっていない時
・[i:i+K-1]は単調増加
区間がかぶっている時
・[i:j-1]は単調増加
・[i:j-1]の最大値 < [j:i+K-1]の最小値
よってこれを実装すると、最適なものの1つであるiが求まるのであとはそこの区間でソートしてあげればよいです
(AC 50:14)
C Social Distance on Graph
こっちのほうが簡単だと思ったけど...
2色に塗るということでまず二部グラフだったらどうなるか考えます
直感的には二部グラフで同じ側にあるものを同じ色で、違う色にあるものを違う色で塗るのが最善な気がします
↑では同じ色のところに到達するまで2手かかりますが、そうでないとすると1手で到達する箇所ができてしまうので損するだろうなと思うので、二部グラフの時は解けた(ということにします)
では、二部グラフでない一般のグラフの時を考えます
二部グラフで最善っぽい解が出ているので、二部グラフに帰着させたくなります
二部グラフに帰着させるためには、いくつか辺を取り除かなければいけませんが、その辺は同じ色同士を結ぶ可能性があるので、wiが大きいものから取り除いていくのが最善になります
よって二分探索を用いて、「重みK以上の辺を取り除いたときに二部グラフになるか？」を求めればよいです
これを満たす最大のKがわかったならば、答えはmin(K, 取り除いたグラフでの最小値)になります
取り除いたグラフでの最小値は単純で、二部グラフであることは保証されているので、それぞれの頂点についてつながっている辺の重みをソートして、小さいもの2つの和を計算すればよいです
(AC 66:05)
D Substring Comparison
めっちゃ2-SATみたいな見た目してる～
→うまく辺つなげばいけそうだけど思いつかない...
→2-SATじゃありませんでした (完)
全然解けなかった...こういうの解けると強いな
総括
ARCちょっとずつ勝てていい感じ
ABC314 参加記
7完 92:25 84位
2連続2桁でいいかんじ
発想+感想中心でCから書きます
C Rotated Colored Subsequence
よくあるやつ、各文字ごとにみればOK
左シフトと右シフト間違えて時間ロス...
(AC 18:39)
D LOWER
更新するやつ典型その1「最後だけわかればいい」
前からみて解いたんですが、「文字の変更」「大文字・小文字の変更」の2つが最後にいつ起こったか管理しておけば解けます
「大文字・小文字の変更」がそもそもない場合がコーナーになるかもなので注意
実装としてはそんなに変わらないと思うんですが、
更新するやつ典型その2「後ろから確定させる」
を使っても解けますね
(AC 29:12)
E Roulettes
期待値DPの鉄則「ゴールから考える」
これに尽きます
とりあえず期待値DPをすると考えると、
dp[i] := 今のポイントがiのとき、Mポイント以上になるために必要な金額の期待値
と定義したくなります
遷移を考えてみます
ルーレットのどの目が出るかはわからないので、「どのルーレットを使うのが最善か？」を考えることになります
そうすると、あるルーレットを使った時の期待値を遷移先から計算できます
たとえば、1と3が出るルーレットなら
dp[i] = (dp[i + 1] / 2 + dp[i + 3] / 2) + Ci
になります
このdp[i]が最小になるルーレットを見つけてあげればよいです
ここまでできれば水diffくらいあると思うんですが、今回は0が入っているのでもう少し複雑になります
たとえば、0と3が出るルーレットなら先ほどの例と同様に
dp[i] = (dp[i + 0] / 2 + dp[i + 3] / 2) + Ci
になるんですが、dp[i+0] つまり dp[i]がわかっていないので右辺が計算できません
このように両辺にdp[i]が出てくる場合は、典型処理としてdp[i]を移項させます
dp[i] - dp[i]/2 = dp[i+3] / 2 + Ci
1/2 dp[i] = dp[i+3] / 2 + Ci
dp[i] = 2(dp[i+3] / 2 + Ci)
と式変形することができるので、これで求めることができます
(AC 41:18)
F A Certain Game
むずかしかった...
解説にある通り「Union Find の過程をマージする木」を使うと簡単な問題に帰着できるのですが、思いつかなかったので自分なりの解法を書きます
まず、操作をかみ砕くと
「大きさaの連結成分に含まれる各頂点にa/a+bを足す、bも同様」
ということになります
各頂点にそのまま足していくと2乗のオーダーになってしまうので回避する方法を考えます
発想としては、逆から見てあげることで「それぞれに足す」というのを「結んだ2つの頂点に足す」に簡略化できるかな～という感じです
まず、辺をマージするときにそれぞれの代表元を記録しておき、UnionFindでマージします
これを逆にたどることで各頂点に足すべき値を伝播させていきます
具体例をだすと
1-2, 2-3と結ぶ場合には
・代表元1, 2にそれぞれ 1/2, 1/2を足す -> マージした後の代表元は1(になったとする)
・代表元1, 3にそれぞれ 2/3, 1/3を足す -> マージした後の代表元は3(になったとする)
を逆からたどります
dp[i] := その時点での頂点iの答えと定義します
・dp[1], dp[3]にそれぞれ 2/3, 1/3を足す
・dp[1], dp[2]にそれぞれ 1/2, 1/2を足す、さらにdp[2]には本来足すべきだった2/3(=1/2を足す前のdp[1])を足す
というような操作をしました
解説よりは複雑ですが、実質的にやっていることは同じになっているはずです
Submission #44525435 - AtCoder Beginner Contest 314
(AC 71:24)
G Amulets
単純なところから考えていきます
K=0はさすがに自明なので、K=1を考えます
モンスターiを倒せるかどうかは、1~iまでのモンスターの体力をタイプごとにわけて、
「1~iまでのモンスターの体力の総和」- 「最大となるタイプの体力の総和」がHより大きくなるかを判定すればわかります
つまり、i番目までに登場したモンスターで「それぞれのタイプの体力の総和」がわかれば、その最大値を引けばいいことになります
これはvectorなどを使えばO(N)でできそうですが、Kが大きくなった場合を考えていきます
結局、i番目までに登場したモンスターで「体力の総和が大きいタイプ上位K個」がわかれば、その和を計算することで判定することができます
これはmultisetなどを使って実装できます
上位K個を入れるmultiset A, 下位M-K個を入れるmultiset Bを用意しておいて、それぞれのモンスターに対して該当するタイプを更新していけばよいです
これで、Kを固定したバージョンが解けるのですが、ほぼ同じでK = 0, 1, ... , Mが解けます
もしK個で無理になったら、そのときに上位K個のmultisetを上位K+1個に変更していきます
倒せるモンスターの数には単調性があるので、K個で突破できるものはK+1個でも突破できて、ダメになったところから考え始めるとしても問題ありません
(AC 92:25)
総括
F完全に忘れていた典型だった
ABC309 参加記
6完 38:32 + 1ペナ 185位
イコールの有無で30分溶かしてかなしい
A Nine
3で割った商とあまりで位置が特定できるので、愚直に判定すればいいですね～
WA(え？？？)
上下も入れてました...
(AC 4:46)
B Rotate
これむずかしくない？250点
時計回りに通るマスを列挙します
右向き・下向き・左向き・上向きの順でたどります
列挙したマスについて、1個先のマスに移していくことを丁寧にやるとできます
(AC 13:12)
C Medicine
350点でまた重実装かと思ったらそんなことはなかった
i日目に飲む薬の数は広義単調減少なので、値が変わるところだけ調べればよいです
(日数、個数)のpairをソートして、順にみていけばOK
最初からK以下なのがコーナーっぽいけど優しいのでサンプルにある
(AC 16:16)
D Add One Edge
条件がちょっと複雑そうな見た目ですが、簡単に言うとN1個の頂点からなる連結グラフとN2個の頂点からなる連結グラフがあって、この2つは連結でないということになります
1からN1+N2に動こうと思うと、1からAに行く、AからBに行く、BからN1+N2という3ステップになることがわかります
よって求めるべきdは「1から最も遠い点の距離」 + 1 + 「N1+N2から最も遠い点の距離」になります
ここまでくると、BFS / Dijkstraなどの最短経路を求める手法を適用してあげればよいです
(AC 24:19)
E Family and Insurance
これっぽさを感じた
各保険ではある頂点iから下に向かって対象者が広がるので、根をスタートして子に向かう方向で計算していくとよさそうだなと思います
公式解説と同じことしか言うことがないのですが、あと何代先まで補償できるか？という値をもってDPすれば解けます
(AC 28:53)
F Box in Box
典型詰め合わせセット
まず前提として、{hi, wi, di}はソートしておいてよいです
今回の hi < hj のような大小関係があるものを数えたい・求めたいときの典型テクニックとして、「ソートして大小関係を自明にする」というものがあります
今回ではhiをもとにして、それぞれの組をソートするとhi < hjという条件を直接調べずとも、i < jという条件とほぼ同一視できます(同じ値はうまく処理するとして)
i < jという条件は、普通にfor文を回すと「今まで出てきたものだけ見ればよい」ということになるので、かなり扱いやすくなります
これで一次元落とすことができるので、二次元のverを考えていきましょう
つまり以下の問題を考えます
wi < wj かつ di < djを満たす(i,j)の組は存在するか？
これはいわゆる「平面走査」というテクニックで解けます
Segment Treeをつくって、それぞれの葉ノードにwiを対応させます
葉ノードの値は、そのwiにおけるdiの最小値とします
こうすると、wi < wj かつ di < djを満たすかどうかの判定は
seg.prod(0 ~ wj) < dj であるか？ (prodはSegment Treeでの区間の演算)
で行うことができます
ということで、hiでソートしたうえでどんどんとSegment Treeにおける葉ノードを更新していけば、3つの条件すべてを満たすものが存在しているかわかります
2D Segment Treeとかで数え上げもできるのかな？(よくわかりません)
(AC 38:32)
G Ban Permutation
めっちゃこれ
上のネタバレになっちゃいますが、i-X ~ i+Xのどれを使ったか？を情報として持つといいんだろうと思います(制約が明らかにそう言ってるので)
普通に考えるとdp[i][bit] := i番目まで見て使ったものがbitであり、条件を満たすものの通り数としたくなります
しかし、「bitの範囲のものを使わない」としたときに使える個数が何個残っているかわからないので遷移ができない気がします
そこで
dp[i][j][bit] := i番目まで見てj個以上違反箇所があって、使ったものがbitである通り数
と定義します
「j個以上」というのが不思議かもしれませんが、これは包除原理を使うことを前提としているためです(j個違反するのが確定していると考えることもできます)
誤った記述だったので修正しました(参考)
包除原理をするときは「合計で i 個以上」ではなくて「特定の i 個を選んでそれらが hoge (選んでいないものについては何も言っていない)」であることを意識するのが重要
— SSRS (@SSRS_cp) 2023年7月10日
dp[i][j][bit] := i番目まで見てj個違反箇所として決めていて、使ったものがbitである通り数
と定義します
遷移は公式解説の通りです
自分がやらかしてたんですが、問題文の条件は|Pi - i| ≧ Xなので、違反する条件は|Pi - i| < X(イコールが入らない)ことに注意しましょう
(AC 111:11)
総括
実装で無駄に詰まるのかなしすぎる
