仮のブログ

仮です

UTPC2023 参加記

day0

　夜行バスにて仙台を発つ. 直前まで呑気にyukicoderの準備をしていたらバスターミナルに着くのがぎりぎりで危うくUTPC0次round敗退となるところだった.

day1(コンテスト前)

　夜行バスの新宿着はAM5:00. いくら東京と言えど, この時間にやることは無い. 仕方がないので新宿から会場の日比谷まで散歩することにした.
国立競技場や国会議事堂のそばを通り抜け, 会場の位置の把握をしたのち, 東京駅に7:00前に着いた.

流石に歩き疲れたので東京駅前の広場で朝ご飯を食べつつUTPCの過去問を振り返る. 過去に解けていない問題を何問か考えたが, 紙もPCもない状態で解ける代物ではなかった.
しばらくすると近くの丸善が空いたので散策. 今回の旅のどこかで『エレガントな問題解決』という本を入手するのがサブクエストとしてある. 丸善内を隅々まで探し回ったが, どうやらおいていなさそうだった. 探索中にいくつか欲しい本はあったが, それらは他の書店でも買えそう&今荷物を増やしたくないという理由でパス.

　時間も大分いい具合になってきたので会場への道中にあったタンメン屋で腹ごしらえをして, 会場入り.

会場は MC Digital のオフィス. 内装等にどこまで触れて良いのか分からないのでざっくりと述べると, とてもIT系らしいオフィスという感じがしてとても良かった.

　他の参加者と談笑したり即席チームを組んだりchatGPTにチーム名を決めてもらったりしていたらあっという間にコンテストの時間となった.
チームメンバーは kiyoshi0205, karinohito, siganai の3名. チーム名は「無限の風」である. チーム名の深い意味はGPT君に聞いてください.

day1(コンテスト)

　問題が難易度ソートされていないとのことで私は真ん中から見始めることにした.
最序盤にしたことと言えば, Fを見る→分からないのでGに行く→分からないのでHに行く→分からないのでIに行く→分からないのでJに行く→分からないのでKに行く→困るというムーブのみである.
　順位表に動きが出るまでとりあえず設定が面白そうな I を眺めることにした. 結果的にはIは唯一の0AC問題だったのでそういった意味では外れ運だったかもしれない. 愚直を書いて見て, oeisに目ぼしい情報はない, 規則性がありそうで分からないという結果を得たところで, EにパラパラとACがあった. Eは得意な構築系だったので意気揚々とそちらへ向かう.

E問題

　まず M 偶数の時はOK. M 奇数, N 偶数の時不可というのはわりかし簡単に分かる.
問題は共に奇数の時である.
　この手の場合は特殊な場合から考えると良いので, N=M の場合を調べる. これは魔法陣の拡張の弱体化?になっているので, 魔法陣の構築を調べると, いい感じの構築が見つかる. 残るは N\neq M の場合であるが, N\lt M の場合は N=M から 2 列ずつ伸ばすことで簡単に派生させられる.
しかし, N\gt M への自然な拡張が見つからない.
困ってしまったので, N=M からの派生を諦めて, 2 列ずつ伸ばすの方に着目することにした. M=1 の時は明らかに不可なので, M=3 が作れるかがカギとなる. いくつか試してみると, 汎用的な構築が見つかるのでこれにて解決.

J問題

　その後また数問ふらふら見た後, 解かれがちだったJに腰を据える. 条件をぐっとにらむと, A_{i+1}/A_{i} 進法のようなものを考えると綺麗にまとまりそうである. 碌に証明はしなかったが, 方針は合っていると直感が告げていたのでそのまま実装. 後で高速化しようと思っていた場所を直し忘れてペナったものの, AC.

B問題

　次にBを見る. 何となく, ほとんどの場合で損失は0になりそうである. excelで色々試すうちに, 長方形の塊を作って境界をギザギザさせると良さそうと気付く.
長方形のサイズや外周に沿った部分のギザギザ感によって黒マスの個数を調整しやすいのがありがたい. 都合の良い長方形を探す部分をプログラミングに任せると, 2ケース+ N=2 の場合だけ弾かれる. 仕方が無いのでこれらのケースを人力で構築して例外処理をする. 人力パートは小さいケースのみなのでさくっと見つけて完了.

H問題

　ここで, siganaiさんからH問題が冪級数列の漸化式となったがそこで詰まっているという話が飛んできた. 見ると確かに厄介そうな形をしていたが, 一応閉じた形までは持っていけそうであった. そこから私が式変形をして, siganaiさんが途中経過を実装して合っているか確認ということをしばらくして, 無事に閉じた形に持っていけた. 別方針で変形をしていたkiyoshi0205さんとも一致したので式自体は合っていそう. 後は本当にあっているかやTLがほほ笑むかを祈ると, 無事にACとなった.

　その後はC問題と格闘していたが全く本質にかすれずに終了. チームとしては10完12位. 今年も難しかったが解きごたえのある問題ばかりで面白かった.

day1(コンテスト後)

　解説や懇親をするが5時起き2万歩walking5時間contestで流石に疲労困憊. 部屋の後ろの方でまったりとしていた. 会終了後時はその場にいた人達と夕食を食べに行くことに. その日はARCがあった上, その日の内に帰宅する人たちもいたため, さっくりと食べようとなる. すぐ入れそうなところに入るとそこは男性7名がパパっと食事をするのには似つかない空間が存在した. しかしそんなことより帰宅時間やARCの方が大事な人々なので急いで食事(これ自体は美味しかったです.)を平らげて解散.

宿をとっていなかったので最寄りの快活クラブへと向かうも満席. 私はARCを完全に諦め, ふらふらと上野の方へ向かった.
もうどうせARCには間に合わないので開き直って夜の上野をうろうろした. 夜の東京はうっかりするとデリケートなゾーンに侵入してしまいそうになるが, 若めのカップルが徘徊しているあたりなら一人でほっつき歩いても大丈夫そうという事で上野公園を少し散歩した.

いい感じの時間になったので上野の快活クラブへ. こちらは無事に入室できたのでそのままウトウトして一日が終了した.

day2

　夜間8時間パックに間に合うようにむくりと起床. 近くのパン屋でパンを買って西郷隆盛のお尻を見ながら朝食をとる.

　今日は17:00にバスタ新宿に行くまでの予定を何も決めていなかったので, とりあえず神保町に歩いて向かう. 神保町は案外近く, 書店群が開く前の時間帯についてしまう. 仕方が無いので江戸城に向かう. 9時開園まで時間があったので近くのベンチでセミナーの準備を少々する. 9時になったので再度入り口に向かうも開く気配なし. 改めて看板を見ると何と月曜は開かないと書いてある.
すごすごと元のベンチに戻り数学の続きをして時間をつぶす.

　1時間ほどで神保町にある三省堂の本店が開く時間になったのでそちらに戻る.
三省堂は現在改修中だかで仮店舗になっていた. これはこれでレアなのでラッキー. 仮店舗と言えど, 中はちゃんと多フロアあり, 十分楽しめた.
ここで目当てであった本を見つけ, ついでにこれまた気になっていた『アルゴリズムの乙女たち』を購入した.
その後は明倫館や書泉グランデをはじめとして何店舗か回りながら適当な本を購入. 流石に歩き疲れてしまったので, 時間には早いが新宿へ向かう事とした.
疲れていると言えどWalkaholicな私は当然のように徒歩を選択. 新宿駅まで1時間半位の散歩をした.
追加でいくつか新宿駅周辺を散策した後, バスタ新宿から帰路につく.

　ところでこの日は風が強かった. あまりに風が強いと首都高はとまり, 首都高がとまると迂回路の交通量が増えて事故も起きる. さらに時間は夕刻. 一般道は家へ帰る車でいっぱいである. こうして過去一番低速な高速バスの旅が始まった. さらに不運は重なるもので, あるところから全てのPA/SAが大型車満車であった. これでは休憩もできない. しかしバスの規定上定期的な休息は義務付けられているらしく, 予定外のPA/SAに入っては満車で素通りを何回か繰り返した. こうしてついに仙台の一つ手前のPA/SAまで来てしまった. 規定がどうなっているのかは知らないが, どうしても休憩を取らないといけないようで, ついに満車の中トイレ休憩に向かう人だけ降ろしてその間バスはどうにかするという手段がとられた. なんやかんやの果てに仙台駅に到着したころには終電もなくなっており自宅まで1時間弱のwalkingが追加されたのであった.

TUPC2023 開催記

はじめに

　東北大学プログラミングコンテスト2023を開催した. この記事はその開催記録と感想である.

atcoder.jp

コンテスト概要

　東北大学プログラミングコンテスト(TUPC)は東北大学プログラミングサークルPuzzleknotが主催するコンテストで, 今年で三回目. 第一回はAOJ上で, 第二&三回はAtCoder上で開催させていただいている. また, 第二回以降は東北大学キャンパス内に会場を設け, オンサイトコンテストも開催した.

準備について

　準備のスケジュールは以下の通り.

2023年7月頃

　TUPC2023というdiscordサーバーが生える. これ以降, 各自が作問をある程度の形まで生やす→discordでチャンネルを作ってTesterを募集→魔改造や洗練といった流れで各問題を作っていく.
問題の管理はGithub&rimeで行い, それとは別にスプレッドシートで各問題の進捗状況を管理した.
なお, 問題作成自体はこれ以前にもパラパラとは行われていた. 例えば, Do Not Turn Back (TUPC2023-N) に関しては5月頃には解法含めて問題が生えていた.

2023年10月頃

　この時点で17問の問題が提案されており, 一旦各問題の準備を進める流れとなった. 実際にはこの後7問+簡単枠数問が新規に提案された.

2023年12月頃

　問題の選定, AtCoderと話を付ける, 大学と話をして教室を借りる等のコンテスト及びイベント全体の内容の骨組みはこの月に一気に進んだ.

2024年1月頃

　オンサイト募集を開始したり, AtCoder上に問題をアップしたりした.
また, 1月末には部内の青～黄コーダー3人に声を掛けて, チーム戦を想定してセットを走ってもらった. 色々な意味で5時間が暇にならないかや部分点の付き方は適切かなどを見てもらった.
また, この時期にはWriter陣がこれまで見ていなかった問題にも目を通し始め, それによって様々な問題で魔改造が起こった.

2023年2月頃

　全体Testerのhenoさんとkotasugameさんに問題を解いてもらい, 指摘事項を修正という事をした.

2023年3月頃

　validatorの最終check等をして, コンテスト本番を迎えた.

今年から導入して良かったもの

  • チームTester: サークル内で, 作問作業に関わっていない3人に頼んで, 本番さながらに走ってもらい, 部分点の付き方が適切か等を見てもらった. この作業はより広いレート帯の人が暇にならないコンテストの実現に大事っぽい気がした.
  • チーム作問: ある程度問題が固まった時点でのTester募集とは別に, 原案や解法の途中経過等を気軽に投げられるチャンネルをdiscordに作った. そこそこ機能したし, 何より楽しい.

問題の感想

以下は各問題のネタバレや解法を大いに含みます.

B: 012 Grid (Writer)

　Writer枠1. この問題は, LGV公式を使う問題を作りたいという気持ちから始まった. そこから1か月位ひたすらLGVっぽい原案を生やし, 解けずを繰り返してやっと綺麗かつまともに解けたのがこの問題である.
　解くのも一筋縄でいったわけでは無く, まず右上左下1固定verのみが解け, これを設定に付すとわざとらしすぎるために一旦没にしていた. その後, 一般の場合でも解けることに気づき, さらには最終的に畳み込みで準線形まで高速化に成功したため出題に至れた.
　結果としても難しい数え上げ枠をはれたので良かったと思う. (簡単なのに順位表で見つかってなくてビックリという言及も見かけたけどマジ?)
　実はOEISを探し回るとヒントや大ヒントが得られてしまうのだが, コンテスト中にはあまりバレなかったようで良かった.

F: Hotel (Writer)

　Writer枠2. 昨年のTUPC2022が上から下までAdhocな感じだったので, 今年は一問くらいABClikeな問題を作ろうとして作った問題.
　また, ABC-like作問と相性が良さそうということで, 題材を決めてから作問という流れを初めてしてみた.
　題材候補として数学の辞典や資料をパラパラして, 題材自体が比較的わかりやすく+問題が作りやすそうなものを選んだら今回のHilbertの無限ホテルに行き着いた.
　概ね意図した通りの問題が完成し, 実際コンテスト上でもそのように機能してくれたというのが自己評価である.

その他の問題

　Testerをしたりいくつかの問題では解法や別解を提案した. それぞれの問題の詳細は恐らく各writerから語られるであろうのでそちらに譲ることとする.

　以下Writerによる開催記. (2024/03/20現在. 観測次第随時更新)

おわりに

　快くサイトを利用させていただいたAtCoderの皆様, 昨年に引き続き快く全体テスターを引き受けていただいたhenoさん, コンテストに参加して盛り上げていただいた皆様, ありがとうございました!!
　来年もTUPC2024の開催を目指しています. その折には是非ご参加ください!!

橙コーダーになりました.

ARC172で橙コーダーになりました. やったね～

レート遷移

AtCoder色の軌跡

2020/04/01 競プロを始める.
2020/04/04 初rated参加.
2020/05/02 茶色到達
2020/05/17 緑色到達
2020/07/25 水色到達
2021/02/13 青色到達
2021/09/20 黄色到達
2024/02/19 橙色到達

AC数状況

diff別精進量

サイト別AC数(LCは40)

このほか, BOJ(168問), ProjectEuler(133問), その他もろもろ.

最近の精進状況

  • AtCoder&Codeforces コンテスト: 予定が合えば参加.
  • Codeforces バチャ: バチャをやるサーバーに入っているのでそこから参加したり勝手に走ったり. 最近はdiv1を中心に解いている.
  • Universal Cup: 大学同期3人で出ている. 2週間に一回くらいの参加頻度.
  • 上で取りこぼしている問題や過去問: 気が向いた時に1問単位で解く.

その他レートに寄与していそうな活動

  • 作問: 主にTUPC
  • OMC: Online Math Contest 数学版AtCoder. 数学特化だが頭の使い方は競プロに似ている.
  • 有志コン: 最近だと Maxmumcup, JAG夏, OUPC に現地参加. モチベ向上につながるし強い人から直接アドバイスがもらえる.

今後

5年以内に赤.

OUPC2023参加記

はじめに

　2024/1/6,7の2日間にわたって大阪にて行われたOUPC2023に参加してきました. これはその参加記です. コンテスト外のことも書いたので日記に近いです.

参加の決意

　もともと有志コンが好きなので都合が合えば行こうと思っており, 特に大阪は観光にも行きたいと思っていた場所でした. 実家(浜松)からそのまま行けそうだったこともあり参加を決めました.

day1

コンテスト前

　AM5:20起床です. 青春18切符で開場に間に合うことに気づいてしまったことが早起きの原因ですが, 旅費が浮いたので無問題です. 仙台~浜松間の移動も18切符で強硬したので実質5000弱で仙台から大阪まで行けました.

　11:00 頃に最寄り駅についたので, そのままお昼ご飯を食べに行くことに. 夜居酒屋昼定食屋の良さそうなお店を下調べしてあったのでそこを目指すことにしました. 着いた時には開店前だったので一度コンテスト会場の下見に行き, 開店時間に店に戻りましたが, 店が開く気配がありません. たまたま店主らしき方がお酒を運んでいたので尋ねたところ, 新年は1/9からの営業とのこと. 悲しみに打ちひしがれましたが, 下調べばっちりな私は代替案として近くのラーメン屋を2件ほどあたりを付けていました. 時間も迫りつつあったので速足でそこに向かうと, 一軒目は12:00開店で, 二軒目は混んでいてどちらも12:30の集合に間に合わなさそうでした. 結局コンビニでおにぎりを買ってそこら辺のベンチで食べました.

　12:00過ぎに会場である大阪大学中之島センターへ. 何かお高いホットドッグの売られるこじゃれたカフェが一階に入るおしゃれな建物でした. その後は適当に時間をつぶしていたらほどなくしてチーム決めの時間に. day1はチームを何も考えていなかったので, ランダムで決める勢に混じりました. 結果, KumaTachiRenさんとStronさんと組むことになりました. チーム名は「 🐈🐕🦉」. KumaTachiRenさんとクリスマスコンでチームを組んだ時に, KumaTachiRenさんが最近使っているらしい🐈名義に私が🐕をくっつけ, 今回さらに🦉がくっついた形です. 動物が賑やかだし順位表で目立つので良い名前でしたが名札に上手く書けずに困りました.

コンテスト(阪大セット)

　最初StronさんのWifi接続が上手くいかず, 私とStronさんで対処をしつつ, その間にKumaTachiRenがCを読んでいました.
なんとか接続できたっぽいので, StronさんにA,Bを任せて私は後ろの方を眺めました.

　一通り概要をつかんだ後順位表を見るとLが解かれ始めていたので, まずそれを解くことに. 一瞬45度回転させて座標を分離する典型が頭をよぎりますが, 冷静になると対称性から一発であると分かります. こういう問題, ギャグと言われがちですが実は結構好きです. さくっと実装してAC. ここまでの間にチームメイトがC,Jを通していました.

　その後, Kが解けそうなのでKを解くことに.
やりたいことはすぐにわかりましたが, 実装が中々込み入りそうで苦手なタイプです. どうせ時間はたくさんあるので, 適宜デバック出力で確かめたりコード量が増えてもバグらせにくい書き方にしたりなどまったりコーディング. その甲斐あってコンパイルが通ってからは一発でサンプルが合い, そのままACできました. ほどなくしてStronさんがAを通したのでその後の作戦会議を軽くします. StronさんにはそのままBに挑んでもらうことにして, 私は残りの問題を考えることになりました.

　序盤から解かれがちだったのはD問題でしたが, 私もKumaTachiRenさんも文字列苦手と言って回避をし続けていたためほぼ手つかずでした. AC数も増えてきて流石に解かなければマズいということでDに本腰を入れることにしました.
まず各バーガーの様子がつかめないので適当に具体例を拵えると, 隣り合う文字を貪欲に消していけば判定問題が解けることに気づきます. ここまで来てしまえば構築は簡単で, stack等を使えば末尾に付けなければいけない文字が分かり, それが最短となります. よってサクッとAC, したかったのですが, 全バーガーでないといけない事を忘れていたり, そのための場合分けにミスを埋め込んだりして時間を取られてしまいました.

　その後は私がHで嘘を生やしたり, Iで部分点を取ったり, それを無理矢理枝刈りで通そうとして通らなかったり, KumaTachiRenさんがQを通したりしましたが, その後はパタリと進展が途絶えました.

　何とかHをbitset高速化で無理矢理通したり部分点をかき集めたりしましたが, そこまで点を伸ばせずday1はチームで9完+5点でした. コンテスタント面ではもっと解けるべき問題があった気がしますし, チーム関係面では競プロ始めたてだったStronさんにもっと声かけをすべきだった気がするのが反省点です.

コンテスト後

　開場に残って感想戦やら駄弁りやらをしていたらいい感じに夕食会が生えたのでそれに参加しました.

　大阪らしいものが食べたいという要望を受けて大阪らしいものが食べられる居酒屋をkotamanegiさんがchoiceしてくださいました. 串カツやとん平焼きやお好み焼き等が食べられて大満足でした. その後は向かう方向が同じ人と談笑しながらホテルへ. この日はHello2024があったので, 出る気満々でレジの画面を開いたところで一旦お布団にダイブしてしまい気付いた時には夢の世界へ...... 先にレジっていなくて良かったです.

day2

コンテスト前

　この日は午前にday1阪大セットの解説会が開かれました. day1は考えが足らずに解けていない(:=粘れば収穫がありそう)問題がそこそこあるように感じたので, 私は解説には参加せずに気になった問題の解説だけ見るようにしました. という訳で午前はしっかりめに睡眠をとったり散歩をしたりして, お昼ご飯は鯛ラーメンを食べに行きました. 大阪らしいのかは不明ですが, 前日にtkoさんが食べていて美味しそうだったのでそこに行きました.

　普段なら4桁円するラーメン(セット)はまず食べないのですが折角の旅でお財布が緩くなっていたので迷いなく鯛担麺&鯛めしセットを注文. ちゃんと美味しかったので満足です. その後前日同様中之島センターに向かい, 適当に過去のHCPCの問題を解いて時間つぶし. day2は事前にtkoさんとsuisenさんと組むと取り決めをしていたので, 合流.

コンテスト(北大セット)

　まずsuisenさんがAをさくっとAC. 私は後ろの問題から見て行って, Iが簡単だったので実装権をもらって実装. ちゃんとACLは展開しているはずなのにCEが出て, 慌ててACLを使わない方にしてみましたが, やはりCE. 結局言語設定がC++17でなくC++になっていただけで, 無駄な時間を使ってしまいました.
　その後はそれぞれが解けそうな問題を一通り解く流れに. Bが構築だったので私はBに目を通しました. 紙に書いて考えているうちに, 2を最小化というのを段々と忘れていき, 解けたと思った頃には完全にそれを失念していました. 当然失念したままのコードでACを取れるわけもなく, 考察のし直し. 幸いにも修正の考察もすぐ終わったので, 実装が空くまで他の問題にも解くことに. その前にtkoさんとEを軽く考えていて, 大体二項係数になるはずだけど細部が合わないというところまで来ていたので, それを詰め切ることにしました. 概ねは経路問題に帰着されますが, B側の数列を全て使い果たす場合に確率がそれまでとズレるのが合わない原因でした. Bを使い果たす場合もそれはそれでいい感じに立式できるので, それをtkoさんに投げて無事AC. この時点で, ABCDEIKを通し, 残りはF,G,J,Hの4問です.

　G,Jはライブラリ強々なチームメイト2人に任せて, HとFを並列で考えます.
　Hは何でも出来そうな制約でいて何もできません. 何度か考察を生やしましたが, 結局最後まで嘘考察か実用的でない考察しか生えませんでした.
　Fの方は部分問題がいい感じに解けて, 後は頑張るといったところまでは辿りつけましたが, 計算量がかなり怪しい解法です. 実装はG,Jで使われていたので, その間に計算量のボトルネックを削る案を紙上で考えますが, 難しい.

　Gの最初に考えていた解法は実装したところ上手くいかなかったようです. 一旦Jに実装をパスという流れになったので, 私もGを考察することに. 上手いこと考察ほぼなしの人員が加わったのが功を奏したのか, 直径の端点だけに注目する解法を生やすことに成功します. いい感じの正当化をみんなで考え, 無事AC. その前に通していたJも併せて, 残りはF,Hの2問に.

　とりあえず計算量の怪しいままでFを実装してみますが, やはりTLE. 誤差に収まることを期待して枝を狩ると今度はWA. bit全探索の順番を意識して, 計算量から一つ n を追い出すことで, 少しテストケースが進むがそれでもTLE. さらに定数倍高速化をして, AC. チームが湧きました.

　その後はHを考えたり考えなかったりしてコンテスト終了. 10完で13位.

コンテスト後

　day2はそのまま解説会に移行しました. Fは考察をもう一歩進めると X を何個かの \log に落とせるようで, 全く気付きませんでした.
解説会後は昨日に引き続き懇親会です.

　今日は何人かがボードゲームを持ってきていたので観戦や参戦をしました.
ケーキを切ったり集めたりするゲームでは最終局面で定石とは一見外れた妙手を決めることができ, 芸術点の高い勝ちを収められたのでso happyでした.

　その後は残った人々で夕食を取りに行こうとしましたが, かなり人数が膨れ上がっていたため, 店舗に入るのは断念して梅田のフードコートに行きました.
[ここに入れる予定だった天丼の写真は取り忘れた]
　昨日もそうでしたが精進方法について強い人たちから話が聞けたのが良かったです.

　uetaさんと梅田地下ダンジョンで迷子になりつつホテルに戻って2日目も終了.

day3

　帰りは新幹線を使う予定で時間に余裕があったのでホテルから歩いて難波方面に向かいました. 数日分の着替え+ノートPC+数学書数冊を持ったままだったのでそれなりにきつかったです.
当初は難波でたこ焼きでもと思っていましたが, 落ち着いて食べられそうな場所は混んでいたためそそくさと退散して新大阪駅構内に目標を変更しました. しかし, 当然のように新大阪駅も激込みで, 結局売店で志津屋のパンをゲット. 大阪というよりは京都な気もしましたが美味しかったのでOKです.
　行きに計17時間かかった道のりも新幹線なら3時間半で仙台へ到着. いつものアンパンマン像は幼い子がアツい抱擁をしていて写真を撮れる感じでなかったので近くのバイキンマンの写真をとってこれにて私のOUPC2023は終了しました.

最後に

　今回も様々な方と交流でき, また精進のモチベーションを得ることができて素晴らしいオンサイトでした. また機会があれば各地のオンサイトに顔を出したいです.
　最後にこそっと宣伝ですが, 2024/3/9には東北大学キャンパス内にオンサイト会場を設けてTUPC2023を開催予定です. 是非お越しくださいませ.

応用情報技術者試験合格体験記

はじめに

　2023/秋の応用情報技術者試験(通称 AP)を受験し, 無事合格したので体験記を備忘録として残します.

受験時のスペック

  • 普通科高校→理学部数学科現4年
  • 理学部向けの情報系の講義は一応とった.
  • AtCoder黄
  • 開発系のアルバイト等の経験なし

受験理由

　開発系のアルバイトやインターンがしたくなり, 資格をひとつもっておくとアピールしやすそうな気がしたので. 後は院試勉強に飽きた時の息抜き用に.

買った参考書

honto.jp

　本屋で適当にパラパラみて自分に合いそうなものを選びました.
結局本はほとんど使わず, 最後の最後に図表だけばーっと眺めるのに使いました.

勉強法

www.ap-siken.com

　ここで午前の過去問をやりました.
　どかっとまとめてセットをやったのは5回ほどで, 後は地下鉄移動中にちまちまとやったりしていました.
この道場には問題ごとに簡単な解説も載っているのでかなり効果的だった気がします.

当日までの過去問解きの様子

　午後に関しては何もしなくて良いと聞いていたので勉強は何もしませんでした. 一応事前に昨年の問題をみて, どのような問題が出るのかだけは把握しておきました.

当日

　会場につくと思ったよりも人がいました. 年齢層も予想よりは若めでした.

午前試験

　午前は4択式*80問で, 6割が合格ラインです.
最初に一通り見て行って, 分かる問題を回収していったら4割程埋まりました.
残りの問題にもう一度目を通して, 2割程の問題は2択くらいまで絞れました. この時点で, 残りを完全ランダムとした時の正答率期待値が, 0.4*1+0.2*0.5+0.4*0.25=0.6 なのでラインぎりぎりといった感じです. とは言え知識問題を考え続けて突然分かるものでもないため, 適当に択を絞ったり可能性の高そうな択を見繕ったりしました.
試験時間が150分もあり, ちゃっちゃか解いていると時間がかなり余ったので途中退出しました.

お昼

　時間が結構空いたので一旦帰宅して家でお昼ご飯を食べました. お昼を食べながら, 午後の選択で何を選ぶかぼんやりと考えていましたが, 結局全部目を通してから決めることにしました.

午後試験

　午前は記述や単語解答式で, 必答大問1個と, 残る大問10個の内4つを選んで解答する形式です.
最終的に選んだ選択問題は以下の通りになりました.

情報セキュリティ

　必答枠です. 電子メールの安全性のような話でした. 問題文に書いてあることと朧気な情報系の講義での記憶から解答欄を埋めましたが出来は悪そうです.

プログラミング

　選択枠です. 一番競プロな問題がこの枠です. 今年は二分探索木の問題で, 流石にすらすらと解けました.

システムアーキテクチャ

　選択枠です. さらっと読んだ時に問題文中に答えが書いてあるタイプの問題っぽかったので選ぶことにしました. 実際, 問題文を注意深く読むことで最後の記述問題以外は埋まりました. 記述は適当にそれっぽいことを書いておきました.

データベース

　選択枠です. これもさらっと読んだ時に問題文中に答えが書いてあるタイプです. こちらに関しては記述式が一切無かったので全て埋まりました.

組込みシステム開発

　選択枠です. 二番目に競プロを感じました. 問題文が長くてだるかったです.

　午後もかなり時間が残りました. 見直しをそこそこに切り上げて帰宅しました.

自己採点

午前の自己採点結果が48/80(60%)でした. 負の方向に採点ミスをしていたら終わりです.

結果

午前 62.5点 午後 80点 で合格していました.
結局午前は正の方向への自己採点ミスで助かりました.
午後は細かい得点がでない上に特に自己採点もしていないので完全に体感ですが,

ぐらいな気がします.

感想

かなり雑な勉強状態で試験に臨みましたが案外何とかなりました.
午前はかなりひやひやしましたが, 午後は問題との相性が良く, どうやら午後だけで見ると上位5%(午前で60%に達した人中)に入ったらしいです. やったね.

問題文読解が得意な人は午前の過去問をひたすら解いていれば午後はどうにでもなるという先人の教えはあながち間違っていないように思いました.

特にこの先の上位試験のことは考えていません. 折角APの結果を使えば午前試験の一部が免除になるらしいので何か狙ってみようかなとも思いましたが面倒になって結局やらなさそうです.
とりあえずは何かしらこっち系のアルバイトに応募してみようと思います.

Codeforces Round #218 (Div. 2)(バチャ), Codeforces Round #392 (Div. 2)(バチャ), Codeforces Round #903 (Div. 3)(本番参加)

バチャ記録再開

Codeforces Round #218 (Div. 2)(2023/10/11)

A: K-Periodic Array

\mod k 毎に出現頻度を数え, \min を足し上げればよい. https://codeforces.com/contest/371/submission/227629368

B: Fox Dividing Cheese

\gcd にするのが最適. 後は愚直に 2,3,5 で割ればよい. 読解にちょっと時間がかかった. https://codeforces.com/contest/371/submission/227629873

C: Hamburgers

二分探索して予算内に作れるか判定する. 場合分けとかを頑張れば二分探索が不要そう.
https://codeforces.com/contest/371/submission/227630478

D: Vessels

いっぱいになっていない容器の番号をsetで管理しておくと, 水があふれた場合どこまであふれるかが高速で求まる.
一回の注ぎで探索する容器の数の総和は高々 N+M 個.
https://codeforces.com/contest/371/submission/227631040

E: Subway Innovation

座標が連続した駅を選ぶのが最適.
コストの総和を毎回計算するとTLEなので上手く差分を更新していく.
最初駅がソートされてると思いペナ. https://codeforces.com/contest/371/submission/227632389

総括

29分全完1ペナ2位. 短時間で走るために簡単そうな昔の回を選んだら思ったよりも簡単でさくっと終わった.

##Codeforces Round #392 (Div. 2)(2023/10/11)

A: Holiday Of Equality

\max との差分を足し上げる.
https://codeforces.com/contest/758/submission/227678230

B: Blown Garland

周期4となるので, 各箇所が何になるべきかが確定する. よって, 各 ! を何にすれば良いか分かる.
https://codeforces.com/contest/758/submission/227678848

C: Unfair Poll

指名は M(2N-2) 周期( N=1 の時は若干違うので場合分けをするが方針自体は同じ). よって, 大体何回当たるかをこれで求めて置いて, 端数はシミュレートすればよい.
https://codeforces.com/contest/758/submission/227680096

D: Ability To Convert

下の位から, 貪欲に今見ている桁の数に含められるかを判定し, 含められなくなったら桁の値を確定する.
例えば, 問題文中のサンプルなら,

  1. 16^0 の位を 11311 と出来るか? →出来る.
  2. 16^0 の位を 11311 と出来るか? →出来る.
  3. 16^0 の位を 11311 と出来るか? →出来ない. 16^0 の位の数は 11 で確定.
  4. 16^1 の位を 11311 と出来るか? →出来る.
  5. 16^1 の位を 11311 と出来るか? →出来る.
  6. 16^1 の位を 11311 と出来るか? →出来ない. 16^1 の位の数は 13 で確定.
  7. 16^2 の位を 11311 と出来るか? →出来る. これが最上位なので, 16^2 の位の数は 1 で確定.

といった感じ. 但し, 各位の数の最上位が 0 とはなれないので, この場合は判断を持ち越すといった処理が必要. 判断を持ち越す場合に判定用の数がオーバーフローしないように注意.

https://codeforces.com/contest/758/submission/227683837

F: Geometrical Progression

Fの方が得意な見た目だったのでこちらに特攻.
項数と各項の範囲が与えられるので等比数列としてありえるものの数え上げ.
まず N=1,2 の場合は簡単なので別途処理をしておく.
そうでない場合, 初項を a, 等比を互いに素な正の整数 p/q と表すと, q^{n-1}\mid a である必要がある.
よって, q の取りうる候補は O(R^{\frac{1}{n-1}}) 個.
おのおのに対して, a の取りうる候補は O(R/q^{n-1}) 個.
おのおのに対して, p の取りうる候補は O((Rq^{n-1}/a)^{\frac{1}{n-1}}) 個.
互いに素の判定の前計算などを適切に行えば, これらを全て走らせても間に合う. (計算量がどれくらいかは不明)

https://codeforces.com/contest/758/submission/227690236

E:

間に合わなかった.
以下はあっているか不明だがバチャ中に考えたこと.
各枝について, 部分木の重さを最大まで減らした場合に, 自身の重さをいくら減らせるかを持たせる.
部分木の重さを減らしたくなったら葉に近い方からボトムアップに重さを上で求めた値まで減らす.
この際, 部分木の重さを減らし切った頂点があれば, その頂点も重さ減らし候補に新たに加える.
これを木DPで行うわけだが, 遷移の際に今見た部分木のどの辺の重さを減らせるかというのを持たせなければいけない.
この情報のマージにはマージテクを行えばよい.
持たせる情報や遷移に気を遣っていたら時間が足りなくなってしまった.
解説の計算量だけみたら O(n) とあったのでもっと賢い方法がありそう.

総括

5完16位. 点数差があったこともあり, F特攻が正解だった.

##Codeforces Round #903 (Div. 3)(2023/10/13)

A: Don't Try to Count

n,m がやたら小さいので, 適当な回数操作をして判定をすれば良い. 回数適当にしすぎてセルフhack出来てしまった 上手くやれば O(|T|) とかで解けそう.
https://codeforces.com/contest/1881/submission/227830383

B: Three Threadlets

雰囲気で最大のものから最小のものを切り出すのが良さそうで, 雰囲気でコーディングして, 雰囲気でペなって, 雰囲気で直して雰囲気でAC.
2つに分けた数の片方しか現状の数の集合に戻していなかったのが原因.
https://codeforces.com/contest/1881/submission/227834613

C: Perfect Square

回して数えて足し上げる.
https://codeforces.com/contest/1881/submission/227839248

D: Divide and Equalize

総乗が n 乗数となる事が必要十分. そのまま総乗はもてないので素因数分解形で持つ.
https://codeforces.com/contest/1881/submission/227841811

E: Block Sequence

DP \lbrace n\rbrace: n 項目をブロックの末尾にする時に消す数の最小値としてDPを回す. 今見る要素を使わないか, ブロックの先頭にするかの選択肢がある.
ブロックの中身を考えないために, ブロックの先頭に使う場合はブロックの末尾へDPを配る.
https://codeforces.com/contest/1881/submission/227845455

F: Minimum Maximum Distance

ぱっと見で二分探索がしたくなったがうまくいかず, さすれば全方位木DPかと思ったがこちらもパットは上手くいかず.
また, メタ的思考だがこの位置に全方位は出なさそう. よって考察不足な感じがするが分からなかったので一旦Gへ逃げた.

G: Anya and the Mysterious String

典型の組み合わせといった感じ?

典型1. 部分文字列に回文を含むかは高々長さ3の部分文字列を調べればよい.
典型2. 区間に対する加算操作は差分をとれば2点への加算/減算操作となる.

を用いる. ある文字をほぼ中心として回文が存在するかというのは差分の高々2要素をみればよい.
よってどこに回文があるかを, 一点更新, 区間和取得ができるデータ構造でもてば, 各変更クエリごとに数要素変更すれば事足りるようになる.
https://codeforces.com/contest/1881/submission/227883585

F: Minimum Maximum Distance

Gがさっくり解けたので安心して戻ってきた.
冷静になると何も難しいことは問われておらず, ほぼ木の直径を求めるだけで良い.
ざっくりとした言い方をすると, 印のついた頂点の内側(上側?)だけを木と思って直径を求めれば良い.
https://codeforces.com/contest/1881/submission/227893145

総括

全完1時間20分2ペナ70位.
Fの一回目でかなり時間を取られたのがもったいない.
数十分悩む暇があったらGを先に観るべきだった.

JAG夏合宿2023 参加記

9/16,17,18の3日間でJAG夏合宿2023 2023/Practice/夏合宿/案内 - ICPC OB/OG の会 に参加しました. これはその参加記です.

day -inf~day 0

今年は数年ぶりに夏合宿が復活するというアナウンスがなされる. 存在は認知していて復活を待ち望んでいたので嬉しい. 横浜大会には通っていないが, 例年枠は余裕があるらしいので参加することに. このイベントが院試後のご褒美としてかなり院試勉強のモチベに貢献した.

day 1

コンテスト前

最初は夜行バスで向かうつもりだったが, 安くなかったので新幹線課金をして当日出発することにした. 最寄り駅に降り立つと競プロerらしき人がたくさんいた. 適当に近くで昼食(何かやたらとしょっぱく感じた蕎麦)をすませ, オリンピックセンターに向かった.

受付やら合宿のガイダンス等を済ませ, 早速1つ目のコンテスト直前となった.
ICPCのチームからはsota君と私が合宿に参加しており, もう一人チームに加えられるという事で, その場で同じくチームメンバーを探していたhourenさんと組み, 3日間の即席チームが完成した.
チーム名は, 双方の所属チームから一部をとってマージした, 「Aobayama_rHAPsody」 となった.
奇しくもメイドラの主題歌『青空のラプソディ』のもじりっぽくなっており, 気に入っている.

コンテスト

day1は韓国regionalの問題であった. 全11問で, 3時間. 同時コーディングや検索は禁止.
難易度がランダム順だったので, 3人でそれぞればらけたところから問題を眺めた.
A,Fをそれぞれsota君とhourenさんがすぐ解ける感じだったようだ. 私もKの方針が立ったのでサクッとACして早々にチーム3完をした.
その後はDとJが得意そうな見た目をしていたのでしばらく考えていたが, 進展無し.
それでもチームメイトが順調にC,E,Gの解法を生やしたらしかったので気楽に考察を続けられた.
コンテスト時間も残り少なくなってきたので, sota君も合流してJを考えた.
似たような問題の解法で平方分割を使うものがあった記憶があったので, 解法の見えぬまま平方分割というワードを出したところ, これが正解だったらしく, sota君が解法の形までもっていってACまで取ってくれた.
コンテスト時間も残りわずかだったため, お菓子を食べながら感想戦をして終了.
day1は7完6位.

コンテスト後

時間の都合上, 解説前半と後半の間に夕食が挟まった.
夕食は, 「青少年自然の家系統で出される夕食」として想像通りのものであった. 普段の学食がこれだとちょっとうーんとなるが, このような場所では寧ろ気分が出てこれで良いのだという気持ちになった.

解説会後はABCに出るか迷っていたが, 同部屋の人がボドゲをすると言っていたのでABCをさぼってそちらに参加することにした.
やったボドゲは ito, 犯人は踊る, なんじゃもんじゃ, テストプレイなんてしてないよ等. ほかにもやった気がするが思い出せなかった.
全員競プロ経験者という共通項があるので, itoやなんじゃもんじゃでそのようなワードを使うことが出来てとても楽しかった.

日が変わる直前くらいに解散して就寝.

話の流れ的に部屋や風呂について書けなかったのでここに書いておく.
部屋は4人相部屋で, 必ず他大学の人と組むようになっていたらしい. 部屋の内装としてはベッド, 机, 椅子が人数分あるだけの簡素なものであった. 競プロができるだけの机があったのが良かった.
風呂は宿泊棟2棟分の合同風呂で, 入浴のために棟を出て外を歩いていくのは少し面倒だった.
時間帯にも依るのかもしれないが, 大して混雑もしておらず, 快適に入れた. 印象的だったこととしては, シャワーの水圧がとても強く, ちゃんと持っていないとシャワーヘッドが吹っ飛んでいくほどであった.

day 2

コンテスト前

6:00 前くらいに自然に目が覚めた. 折角なので散歩にでも行くかと思って着替えたところで二度寝をしてしまい, 7:00に再起床.
その後は朝食を取ったり売店によったりして, コンテスト会場に向かった.

コンテスト

今日は有志セットで, 全12問5h. ルールは昨日同様.
開始直後にCを見ると, 円周角を見ると一発の問題であった. 実装も軽いのでコードを書き始め, FA. 特にday2全体のFAであった. 嬉しい.
次にAを見ると, これまた数学での典型問であったため, 手元で軽く確認した後実装し, AC.
次にHにとりかかる. 問題文の条件を整理すると, 二次方程式を解けばよいと分かる. 平方根操作が入るので, 誤差にやられないように丁寧目に実装してAC.
その後はKを書いていたsota君からhelpが飛んできたので, 全員でdebugをした. ほどなくしてヤバそうなところを見つけたので伝えたところ, 現在の方針ではすぐには修正できない感じらしい. しかし, すぐにhourenさんから別の解法が飛んできて, 無事ACした.
その前後に考えていたBも, 全てが計算できる形に収まった. 添え字合わせに若干失敗したものの, 丁寧に書いてACできた.
残りでは F,J が私担当かつ可能枠に見える. しばらく考えていたが, Fは考察が完全にとまり, Jも手元だけでやるには限界が来た. Dがいい感じになったらしいのでぼーっと話を聞きながらお菓子を食べていたら無事に通って, そこでほぼ時間終了.
day2は6完7位.

コンテスト後

夕食を食べたり入浴したりボドゲしたりARCで冷えたりARCの感想戦をしたりARCのWriter&Testerの話を聞いたりして0時ころ就寝.

day 3

コンテスト前

朝食を取ったり部屋を撤収したり売店に行ったり.

コンテスト

今日はJAGセットで, 全11問5h. ルールは昨日同様.
3日間で初めてA,Bに簡単枠があるとのことで, (Atcoderでない)じゃんけんをして, A: sota君, B: hourenさん担当で, C以降を私が見ていくことになった.
CDEFに998244353があったので, これを中心に眺めたり, サンプルを手で計算したりする. この4問で一番進展がありそうなのがCだったので, まずCにはりつくことにする.
2乗の計算量まではぱっと立式できるが, それ以上の高速化が難しい. そこで, 各項の直接計算は難しいが, 隣接項の差分計算は簡単なんだろうと思い, パスカルの三角形を書いたところ, 本当にその通りであることに気づく. 紙に解法をまとめ, デバッグ中だったPCを借りて実装, AC. その後, Iも直ったらしく無事通り, この時点でABCIJの5完となった.
Eを考えていたsota君から, 余事象を考えると見通しが良いと言われる. 確かにその通りで, 面倒な部分もかなり整った形にできそう. sota君から考察を引き継ぎ, 立式をしたのち実装. AC. この時点で, 順位表の上位はほぼ動きが停止していた. KにACが出ていたくらいで, 他の問題は提出すらなかったと思う.
どれを見ても激ムズだろうということで, 各自思い思いの問題を眺める.
私はFを眺めることにした. 4乗解はほぼ自明に生え, 差分更新を頑張れば3乗までは落ちる. しかし, この方針では2乗までは落ちそうに無い. このあたりで, 極大長方形や小さい領域のスコアの展開式を書くことなどを試したが, もう一閃きが足りず, 進展が無くなった.
Kは方針が立ったが通らないという事で, 全員でデバッグをすることにした.
解法も合っていそうだし, コードを見てもバグが分からない. しばらくして, 連結性の判定がおかしいことが判明した.
頂点倍化の方針をとっているので, サイズによる簡単な判定ができないことにチーム全員全く気付いていなかったのだ.
簡単な解決策が思いつかなかったので, 連結性判定用にもう一本ダイコネ作っちゃえをして無事AC.
順位表的に解けてももう1問くらいだろうということで, Hを考えることにした.
k=1の場合は, Trie木を作ればよい. しかし, そうでない場合が全く分からない.
しばらく唸っていたが, 各uは|s|の最大値で打ち切ってしまってよいことに気づく.
考えれば当たり前のことではあるが, |u|の総和のデカさに困っていたのでこの気づきが進展となった.
|s|の最大値でuが切れるなら, |s|が短ければ, trie木を辿っても, 現実的な時間で探索が終わる. |s|が長い時, そのようなsは少ないので何とかなりそう.
その後, そのような場合はロリハ+二分探索で行けると分かり, sota君に実装を任せる.
2.5secとはいえ, 平方分割+Trie木+ロリハ+二分探索で計算量がヤバい.
どうにかして定数倍高速化でもよいので改善方法を考えていたら, hourenさんから公式解説1にあったような方法が提示される.
議論を経て, どうやらその方針が正しそうである. 時を同じくしてsota君が実装を終えたので, ダメ元で一回出してみることに.
結果, AC. 歓喜感激.
解説会で聞いた話によると, TLを2.0secか2.5secか迷って2.5secにしたところそれに救われた提出が1チームあったらしいが, 我々のことだろうと思う.

残った時間はFの3乗解を投げてみたり, お菓子を食べたりしてまったりしていたらコンテスト終了.

day3は8完4位.
3日間を通じて, 6位→7位→4位と安定して好成績を取れてよかった.
3日間とも, 3人がそれぞれ強みを生かせたのが良かったと思う. 私自身も私が解くべき問題は概ね解けたのではないだろうか.

コンテスト後

解説会をして, そのまま解散.
夜行バスまで時間があったので, 東北勢数人と代々木公園で作問したりラーメン屋で作問したりマックで作問したりした.

さいごに

刺激的でとても楽しい3日間でした.
JAGスタッフの皆さん, 交流をしてくれた参加者の皆さん, ありがとうございました.