純粋培養競技プログラマが基本情報技術者試験を解いてみた話

参考: d.hatena.ne.jpこんにちは。たまには有機的な投稿をします、tozangezanです。twitterで基本情報技術者試験、というものが話題に上がっていたので、過去問を解いてみることにしました。 筆者紹介 大学4年。中学2年のときに競技プログラミングを始める。…

四国フォトギャラリー

2017年2月に四国に行きました。そのとき撮った写真のうち、見せたいものをただひたすら張り続けます。 番号が汚い ラスボスがいそう 高松からは離島行きフェリーがたくさんある セルフの醍醐味 さぬきうどん駅 徳島。駅の隣に山がある サラダ 阿波池田。寂し…

英単語の覚え方

7000語くらい知ってる人(大学受験でそんなに苦労しないレベル)が15000~20000語くらい知ってる人になるための方法です。自分の体験にしか基づいていないので、これが多くの人に適用可能かとかそういうことは一切考えてないのであしからず。 文脈で覚えるべき…

Wolf Sotheとは?

決して暇ではないし、なんか節目の時期であるわけでもなく、Advent Calendarシーズンですらないのに、唐突に変な記事を書きます。 Wolf Sotheとは? 昔のITMO Universityのアイスホッケーチームのユニフォーム。Edmonton Oilersと同じカラーリング。このブロ…

SRM186 Div1 Hard

昔の問題は変な意味で面白い。プログラミングコンテストの問題の題材としてアイスホッケーが出題されることは少なくありません.しかし,活動時間の全てをオンラインジャッジにつぎ込む生活では,アイスホッケーを想像することができず,問題の理解に困って…

最大独立集合 速め

696Mediumで書いたもの。38頂点を1000回実行して200ms弱と相当速い。 s[i][j]: 隣接行列 S[i]: 隣接行列を詰め込んだもの v[i]: 頂点の利用状況 val: 答え uk: v[i]=0のiを詰め込んだもの n: 頂点数 int s[40][40]; long long S[40]; int v[40]; int val; in…

698F: Coprime Permutation

素因数→素因数の写像が何通りあるかと、それぞれの素因数内で数の並べ方が何通りあるか掛け算する。 前者は、同じ回数出現する素因数が自由に入れ替えられるので、それぞれの素因数に対して、indexにその素因数をもつ場所のgcdを求めて、対応をつけると自由…

Codeforces Round #348 (VK Cup 2016 Round 2, Div. 1 Edition)

何だこのセットは......。難問が誰にも存在しないセットだと、簡単が速いから勝ててしまう。 A B C D E F Place 00:13 00:06 00:34 (+1) 00:48 - - 4th A: 逆からやるだけ。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string> #include<string.h> #include<vector> #include<set> #incl</set></vector></string.h></string></queue></algorithm></math.h></stdio.h>…

第3回 Dwangoからの挑戦状 Finals

えええ....。せっかくの優勝チャンスを逃した。 A B C D Place 118:47 70:40 (+2) 47:52 (+2) - 5th A: ずっと前から見てて解けないと思ってトイレにいったら後ろからやるだけだった。こういうのが遅いのはダメでしょ #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #</queue></algorithm></math.h></stdio.h>…

Codeforces Round #349 (Div. 1)

いつもと同じ死に方。成長が見られない。相変わらず注意力が灰底辺。 A B C D E Place 00:48 (+1) 00:35 (+4) 01:59 (+1) - - 59th A: メモ化再帰するだけ。メモ化し忘れて1TLE。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string> #include<string.h> #include<vector> #include<set> </set></vector></string.h></string></queue></algorithm></math.h></stdio.h>…

Codeforces Round #352 (Div. 1)

心が折れた。 灰コーダー並みの注意力だったのも悪いけど、サンプルも弱いし罠も多すぎだと思う。 A B C D E Place 00:28 (+1) 00:14 (+2) -5 - - 105th A: 嫌なケースが多すぎる。returnを忘れた。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> </vector></string.h></queue></algorithm></math.h></stdio.h>…

Codeforces Round #359 (Div. 1)

面白いかどうかはさておき、教育された感がある。普段Aからやってると抜かされるのでBからやったら大失敗した。 A B C D E Place 01:01 00:48 - 01:35 - 57th A: やるだけ。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> #include<map> #incl</map></set></vector></string.h></queue></algorithm></math.h></stdio.h>…

Codeforces Round #360 (Div. 1)

初全完。全完ゲーはHack上乗せ勝負なのでVirtual Participation勢には不利。 A B C D E Place 00:07 00:17 (+1) 00:27 00:50 01:39 16th A: よくある二色塗りのUFを書いたら他の人に取り残されたんだけど、簡単な解法があるのかな。 #include<stdio.h> #include<math.h> #incl</math.h></stdio.h>…

Codeforces Round #362 (Div. 1)

解けたのに虚しくなる意味不明なセット。面白くはない。 A B C D E F Place 00:10 (+1) 00:17 00:38 01:14 - - 37th A: 辺を全部mapで更新する。何も考えずにやったらオーバーフローした。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> </set></vector></string.h></queue></algorithm></math.h></stdio.h>…

Codeforces Round #363 (Div. 1)

一体何をやっているんですかね...... A B C D E F Place 00:031 00:21 00:39 (+3) 02:07 (+7) - - 26th A: Div1...? #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using namespace std; const long long mod=10000000</stdlib.h></map></set></vector></string.h></queue></algorithm></math.h></stdio.h>…

Codeforces Round #364 (Div. 1)

遅いのとA,B逆なことを除けばうまくいった? A B C D E Place 00:26 00:33 01:28 - - 20th A: 全然わかりませんでした(オイ バス乗車時間を二分探索。式もなんだか難しい。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h></stdlib.h></map></set></vector></string.h></queue></algorithm></math.h></stdio.h>…

Codeforces Round #366 (Div. 1)

コンテストのバランスを全く考えていない難問セットなのですが、一つ一つはICPCの大変な問題(しかもサンプルも弱い)のような存在で、ただ実装が辛いだけでした。 ちなみにMARVELはヴェノム派です。 A B C D E Place 00:16 (+1) 00:53 (+3) - - - 33rd A: な…

AIM Tech Round 3 (Div. 1)

Virtual Participationはオンラインジャッジではありませんが...... 他の参加者全員が知っている典型を知らないとどうしようもなくなる好例。しっかりと典型を強くしておくことが求められるセット。AとかBとかかなりいやらしいけど。 A B C D E Place 00:02 …

Codeforces Round #371 (Div. 1)

ク ソ コ ン テ ス ト A B C D E Place 00:04 00:37 00:20 01:36 - 7th A: もちろんmultisetなぞ必要なく、偶奇の組み合わせごとに何個あるか持っておけばよい。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using n</stdlib.h></map></set></vector></string.h></queue></algorithm></math.h></stdio.h>…

Codeforces Round #372 (Div. 1)

単純に2時間コンテストとは思えないほど難しい。 A B C D E Place 00:08 00:44 - - - 56th A: (i+1)^2(i+2)^2にしてからsqrtを使う。(i+1)^2(i+2)^2はlong longに入らないが、あらかじめ(i+1)で割っておけば対処可能。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> </queue></algorithm></math.h></stdio.h>…

Codeforces Round #373 (Div. 1)

紫コーダーはDiv1のwriterやるのやめてほしい。 A B C D E Place 00:13 削除*1 01:02 -4 - 42th A: 一番左に出てきた5を四捨五入していく。ひどい実装問題。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> #include<stdlib.h> using namespace std;</stdlib.h></set></vector></string.h></queue></algorithm></math.h></stdio.h>…

2017年の目標

去年は実験的に目標を立てなかったのですが、なんかいまいち何もできませんでした。今年は逆に努力系の目標を立ててみることにします。 競技プログラミング Div1 Hard のAC数を450以上にする 現在、306。ここ2年間と難しい時代のはまだまだたくさん問題が残…

Intel Code Challenge Elimination Round (Div.1 + Div.2, combined)

これはどうするべきだったのだろうか...... A B C D E F Place 00:03 00:07 00:18 00:31 -5 - 154th 順位が低いのは、本番がHackゲーだったからなので仕方がないが、仮にHackできる環境だったとしても50位くらいだと思う。Eが解けてないのが大問題。A: 空気…

Good Bye 2016

思えば3年前、Good Bye 2013では問題もろくに解けずHackすることだけしてレートを減らしていました。 tozangezan.hatenablog.com3年後、Codeforcesをやる気になったためついに戻ってきました。 A B C D E F G H Place 00:24 00:10 00:06 00:21 01:09 - - - 4…

Codeforces Round #380 (Div. 1, Rated, Based on Technocup 2017 - Elimination Round 2)

なぜに6問...充実しすぎて2時間でやるなら5問でも十分だと思えるセット。 A B C D E F Place 00:19 00:28 00:37 01:49 (+2) - - 34th A: Aですらいつもより難しい。短すぎるものを除けば一次式になるのでうんたらかんたら #include<stdio.h> #include<math.h> #include<algorithm> #inclu</algorithm></math.h></stdio.h>…

SRM 704

7ヶ月ぶりにTopCoderに出た。300: これはAGC005のCと全く同じ。 // I like wolves!! #include <vector> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <sstream> #include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include …</ctime></cstdlib></cmath></cstdio></iostream></sstream></algorithm></bitset></stack></deque></set></map></vector>

Codeforces Round #381 (Div. 1)

Dが難しすぎてCがクソゲー。レッドコーダー的にはつまらないセット。 A B C D E Place 00:03 00:18 01:42 (+1) - - 51st A: 簡単すぎて逆に焦るやつ #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> using namespace std; const long long </set></vector></string.h></queue></algorithm></math.h></stdio.h>…

Codeforces Round #382 (Div. 1)

結果もあれだがひどいセット。 A B C D E Place 00:09 (+1) 00:16 01:02 (+1) (-1) - 57th A: Fibonnacci heapのあの図みたいな配置。2^nではない。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> using namespace std; const long long </set></vector></string.h></queue></algorithm></math.h></stdio.h>…

Codeforces Round #383 (Div. 1)

A B C D E Place 00:06 00:14 01:03 (+1) (-2) - 35th 悪くはないと思うんだけどね......A: サイクルさがしてLCM. #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> using namespace std; const long long mod=1000000007; const long long </set></vector></string.h></queue></algorithm></math.h></stdio.h>…

Codeforces Round #385 (Div. 1)

Codeforces初めまして。 A B C D E Place 00:08 00:18 00:48 - - 14th A: 算数と変な実装。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; int p[11</set></vector></string.h></queue></algorithm></math.h></stdio.h>…

レッドコーダーからtarget/LGMには3ヶ月でなれるか?

https://t.co/zV5iCKXjge こんなものが最近話題になっている。https://www.amazon.co.jp/dp/B01J9QIGF6/ あとこんなのも最近話題になっている。そろそろ何もやってない気持ちでいっぱいになってきたし、競技プログラミングでこれを実証するのもいいんじゃな…

Interview with Top-Level Competitive Programmers World-Wide

For Japanese readers: さすがにこれ全部和訳するのは大変すぎるのでこのままでゆるしてください。最近Google翻訳が大幅に改善しましたし。This is the 20th article of Competitive Programming Advent Calendar 2016. I interviewed some coders from seve…

JMC2016-2017 問題4

余談: タイトルバーには JMC2015-2016 と書かれています。明日はJOIの予選だそうで、今日はその模擬予選というのをやっていたようです。皆さん満足いく準備はできましたか?明日の予選では実力を発揮できそうですか?IOI2012に参加した僕からの一言アドバイ…

競技プログラミングをやっている人に読んでほしいかと言われればそうだと思うが実際あんまり関係のないなぐり書き

これはsugimさんが数分前に言及していたCompetitive Programming Advent Calendar 2016(不真面目)の一環です。 誰かカレンダーを作ってくれたら適当な日にリンクはっつけられます 競技プログラミングの"まわり"の話。もう個々のテクニックについて書いても…

IIDX DPの攻略オプションを眺める

この記事は #音ゲーマー達の発信所 (1枚目) Advent Calendar 2016 - Adventar の5日目ハードクリアした曲のうちオプションが独特と感じたものを書き並べていきます。 Do it!! Do it!! [DPA] R乱 / R乱 ここに癖がつきます。この曲はこの後の発狂は白い縦連打…

Google 翻訳

試しに使ってみる。 競技プログラミングの解説のような文章 AGC007のEの解説みたいなのを日本語で書いてみたので、これを英語に翻訳してみる。 まずは答えで二分探索。この判定においては、データ構造をマージする一般テクなテクを使う。それぞれの再帰の中…

KUPC 2016

解ける問題がなくて暇なのでコンテスト中ですがブログを書いています。 A - バリケード 呼吸。 #include<stdio.h> #include<algorithm> using namespace std; int main(){ int a,b,c;scanf("%d%d%d",&a,&b,&c); int ret=0; for(int i=0;i<a;i++){ int p;scanf("%d",&p); if(p<b||p>=c)ret++; }printf("%d\n",ret); } B - 作</a;i++){></algorithm></stdio.h>…

ARC053 D: 2 つの山札

こういう後から合流して重複しうるものをうまく重複しないような汎用的テクとして、1ステップ進むときに追加する文字が同じなのに到達先が違う、というケースがないように、同じ文字で複数通りの結果に分岐するときはそれらを集合として状態に持っておく、と…

SCPC2016 本選

Sorry for foreign coders, I'm writing this blog in Japanese. ;(8/18 に 第2回삼성대학생프로그래밍경진대회という大会があったので、観光も兼ねて行ってきました。韓国に行くのは初めてです。8/16 出発日 また成田空港に行きます。今回は交通費が出ない…

Distributed Code Jam 2016 Finals

memo: FHC 2015 Finals の参加記的なのも書いてないらしい。さすがに昔すぎて今から書く気になれない。今年のGCJ、DCJのFinal roundはGoogle New Yorkで開催されました。8/3 出発 成田空港にはなんかいろいろ店が出来ている ホテルから見える光景。この時点…

天下一プログラマーコンテスト2016 予選A

反省点がないので文章はほぼないです。Irrelevant: #include<stdio.h> #include<algorithm> using namespace std; int main(){ int ret=0; for(int i=1;i<=100;i++){ if(i%3&&i%5)ret+=i; } printf("%d\n",ret); } #include<stdio.h> #include<algorithm> #include<vector> using namespace std; vector<int>g[1100</int></vector></algorithm></stdio.h></algorithm></stdio.h>…

SCPC2016 2차예선

문제1. 별로 너무 어렵지는 않지만 실행 제한시간이 좀 짧다. 적당한 정수배 고속화를 해서 만점을 얻었다. #include<stdio.h> #include<algorithm> #include<vector> using namespace std; vector<int>id[5100]; int X1[5100]; int X2[5100]; int Y1[5100]; int Y2[5100]; pair<pair<int,int>,int> p[5100];</pair<int,int></int></vector></algorithm></stdio.h>…

CODE FESTIVAL 2015 Exhibition B: TRAX

流行のゲーム。 3つのパターンに場合わけして頑張って数えるだけだけど、白と赤がついているせいでうまく数えにくい。 多分こういう系(2次元のグリッドに変なのを並べる方法を数える)の数え上げ得意なんだろうと思う #include<stdio.h> #include<algorithm> #include<vector> using names</vector></algorithm></stdio.h>…

ICPC2016 国内予選

www.youtube.com必死に英語の練習をしているのでなんかどうすればいいか教えて今までちょっと忙しかったけど明日から真面目に動画上げます....... (こういうタイトル詐欺結構ためらわれる!!!!!!)

Distributed Code Jam 2016 Round 2

通過したのでオンサイトです。去年のFHCもそうだし、こういう解法易実装力本質一発AC難みたいなコンテストはオンラインジャッジ勢にとっては一番希望がありますね。 事前準備とか 今年はある程度は真面目に対策しました。 やったこと ちゃんと環境が動いてい…

AOJ 1256: Crossing Prisms

AOJ

頑張る。 全面と側面で同じ形であることを知らなくて無駄にコードを書きすぎた。 #include<stdio.h> #include<algorithm> #include<vector> #include<math.h> using namespace std; int X[2][5]; int Y[2][5]; int L[20]; int R[20]; double EPS=1e-9; int ABS(int a){return max(a,-a);} int mai</math.h></vector></algorithm></stdio.h>…

AOJ 2686: Unfair Game

AOJ

幼稚園児でも解けるような問題だった。具体的には、 A=Bの時 山が一つでA>Bの時 山が一つでA たくさん山があり、A,B>>石の個数の時 を考えてみれば自然と答えは見えてくる。 #include<stdio.h> #include<algorithm> using namespace std; int p[110000]; int main(){ int n,a,b; </algorithm></stdio.h>…

AOJ 1360: Bringing Order to Disorder

AOJ

上手いこと探索。 半分全列挙をmap DPで早くしたらオーバーキルみたいな感じになってしまった。上手いこと探索系は苦手なのでしょうがない。 #include<stdio.h> #include<algorithm> #include<map> #include<string.h> using namespace std; char in[20]; map<int,int> dpL[8][3][71]; map<int,int> dpR[8][3][71];</int,int></int,int></string.h></map></algorithm></stdio.h>…

AOJ 2688: Card Game Strategy

AOJ

AOJに戻ってみた。知識ゲーだと思って解説読みましょう。こんなDPは他に見たことがない。 実装はそこまできつくない。 #include<stdio.h> #include<algorithm> #include<vector> using namespace std; int p[610]; short dp[2][610][180010]; short rev[2][610][180010]; int dist[180100</vector></algorithm></stdio.h>…

DDPC2016 Final

A: おはよう #include<stdio.h> #include<algorithm> using namespace std; int t[]={100000,50000,30000,20000,10000}; int ans[200]; int main(){ int a;scanf("%d",&a); for(int i=0;i<min(a,5);i++){ int b;scanf("%d",&b);b--; ans[b]+=t[i]; } for(int i=0;i<a;i++)printf("%d\n",ans[i]); } B: 誤読した #include<stdio.h> #…</min(a,5);i++){></algorithm></stdio.h>