2021-09-07

nitic-ctf2 writeup

2021/8/5~2021/8/6まで、nitic-ctf2が開催されました。

どうやら、ctfでは、コンテスト後に解けた問題について、どうやって解いたたかをwrite-upに書くのが定番なので、私も初参加の記録として、書いてみます。

web

web_meta

添付ファイルをプレビューで開いてみると、このようにnitic ctf2しか表示されません。

f:id:nabefuta_KP:20210907002146p:plain — nitic ctf2と書かれたwebページ

しかし、ファイルの中身を見てみると、ヘッダー部に欲しい情報が入っています。

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta name="description" content="flag is nitic_ctf{You_can_see_dev_too1!}">
    <title>nitic_ctf_2</title>
</head>

よって、この問題のFlagはnitic_ctf{You_can_see_dev_too1!}です。

long flag

同じく、添付ファイルを開いてみると、次のようになります。

f:id:nabefuta_KP:20210907002430p:plain — Long Flagと書かれた文字と　怪しげな矢印

このflagではさまれた間が怪しそうなので、開発者ツールで見てみましょう。

<p id="flag" onmousedown="return false;" onselectstart="return false;">
    <span>n</span><span>i</span><span>t</span><span>i</span><span>c</span>...(略)...<span>3</span><span>}</span>
  </p>

このままでは、<span>が邪魔なので、コンソールを使って、文字を抜き出してしましましょう。

ちょうど<script>でflagを取得しているところがあるので、これを借ります。

> e.textContent
< '\n    nitic_ctf{Jy!Hxj$RdB$uA,b$uM.bN7AidL6qe4gkrB9dMU-jY8KU828ByP9E#YDi9byaF4sQ-p/835r26MT!QwWWM|c!ia(ynt48hBs&-,|3}\n  '

あとは、これの余計な空白部分を取り除けば、Flag:nitic_ctf{Jy!Hxj$RdB$uA,b$uM.bN7AidL6qe4gkrB9dMU-jY8KU828ByP9E#YDi9byaF4sQ-p/835r26MT!QwWWM|c!ia(ynt48hBs&-,|3}になります。

Pwn

pwn monster1

まずは、普通にやってみましょう

nabefuta@LAPTOP-RD6M1S1K:~/ctf$ nc 35.200.120.35 9001
 ____                 __  __                 _            
|  _ \__      ___ __ |  \/  | ___  _ __  ___| |_ ___ _ __ 
| |_) \ \ /\ / / '_ \| |\/| |/ _ \| '_ \/ __| __/ _ \ '__|
|  __/ \ V  V /| | | | |  | | (_) | | | \__ \ ||  __/ |   
|_|     \_/\_/ |_| |_|_|  |_|\___/|_| |_|___/\__\___|_|   
                        Press Any Key                            


Welcome to Pwn Monster World!

I'll give your first monster!

Let's give your monster a name!
+--------+--------------------+----------------------+
|name    | 0x0000000000000000 |                      |
|        | 0x0000000000000000 |                      |
|HP      | 0x0000000000000064 |                  100 |
|ATK     | 0x000000000000000a |                   10 |
+--------+--------------------+----------------------+
Input name: nabefuta
+--------+--------------------+----------------------+
|name    | 0x617475666562616e |             nabefuta |
|        | 0x0000000000000000 |                      |
|HP      | 0x0000000000000064 |                  100 |
|ATK     | 0x000000000000000a |                   10 |
+--------+--------------------+----------------------+
OK, Nice name.

Let's battle with Rival! If you win, give you FLAG.

[You] nabefuta HP: 100
[Rival] pwnchu HP: 9999
Your Turn.

Rival monster took 10 damage!


[You] nabefuta HP: 100
[Rival] pwnchu HP: 9989
Rival Turn.

Your monster took 9999 damage!


[You] nabefuta HP: -9899
[Rival] pwnchu HP: 9989
Lose...


nabefuta@LAPTOP-RD6M1S1K:~/ctf$

負けました...

そこで、添付ファイルのソースコードを見てみましょう。

(略)

typedef struct {
 char name[16];
 int64_t hp;
 int64_t attack;
} Monster;

void print_monster_infomation(Monster monster) {
 printf("+--------+--------------------+----------------------+\n");
 printf("|name    | 0x%016lx | %20.8s |\n", *(int64_t*)monster.name      , monster.name);
 printf("|        | 0x%016lx | %20.8s |\n", *(int64_t*)(monster.name + 8), monster.name + 8);
 printf("|HP      | 0x%016lx | % 20ld |\n", monster.hp                , monster.hp);
 printf("|ATK     | 0x%016lx | % 20ld |\n", monster.attack            , monster.attack);
 printf("+--------+--------------------+----------------------+\n");
}

void give_monster_name(Monster* monster) {
 printf("Let's give your monster a name!\n");
 print_monster_infomation(*monster);

 printf("Input name: ");
 scanf("%s%*c", monster->name);


(略)

どうやら、モンスターにかかわる情報は構造体で取っているようです。

つまり、名前を入力する際に、17文字以上の文字を入れれば、体力などのほかの情報に干渉できそうです。

そのため、名前を不必要に長くしてみます。

nabefuta@LAPTOP-RD6M1S1K:~/ctf$ nc 35.200.120.35 9001
 ____                 __  __                 _            
|  _ \__      ___ __ |  \/  | ___  _ __  ___| |_ ___ _ __ 
| |_) \ \ /\ / / '_ \| |\/| |/ _ \| '_ \/ __| __/ _ \ '__|
|  __/ \ V  V /| | | | |  | | (_) | | | \__ \ ||  __/ |   
|_|     \_/\_/ |_| |_|_|  |_|\___/|_| |_|___/\__\___|_|   
                        Press Any Key                            


Welcome to Pwn Monster World!

I'll give your first monster!

Let's give your monster a name!
+--------+--------------------+----------------------+
|name    | 0x0000000000000000 |                      |
|        | 0x0000000000000000 |                      |
|HP      | 0x0000000000000064 |                  100 |
|ATK     | 0x000000000000000a |                   10 |
+--------+--------------------+----------------------+
Input name: 123456789012345678901234567890
+--------+--------------------+----------------------+
|name    | 0x3837363534333231 |             12345678 |
|        | 0x3635343332313039 |             90123456 |
|HP      | 0x3433323130393837 |  3761405300628338743 |
|ATK     | 0x0000303938373635 |       53022314411573 |
+--------+--------------------+----------------------+
OK, Nice name.

Let's battle with Rival! If you win, give you FLAG.

[You] 123456789012345678901234567890 HP: 3761405300628338743
[Rival] pwnchu HP: 9999
Your Turn.

Rival monster took 53022314411573 damage!


[You] 123456789012345678901234567890 HP: 3761405300628338743
[Rival] pwnchu HP: -53022314401574
Win!

nitic_ctf{We1c0me_t0_pwn_w0r1d!}

ということでこの問題のFlagはnitic_ctf{We1c0me_t0_pwn_w0r1d!}です。

pwn monster2

先ほどと同じ方法でやってみましょう。

nabefuta@LAPTOP-RD6M1S1K:~/ctf$ nc 35.200.120.35 9002
 ____                 __  __                 _            
|  _ \__      ___ __ |  \/  | ___  _ __  ___| |_ ___ _ __ 
| |_) \ \ /\ / / '_ \| |\/| |/ _ \| '_ \/ __| __/ _ \ '__|
|  __/ \ V  V /| | | | |  | | (_) | | | \__ \ ||  __/ |   
|_|     \_/\_/ |_| |_|_|  |_|\___/|_| |_|___/\__\___|_|   
                        Press Any Key                            

Welcome to Pwn Monster World!
I'll give first monster!
Let's give your monster a name!
+--------+--------------------+----------------------+
|name    | 0x0000000000000000 |                      |
|        | 0x0000000000000000 |                      |
|HP      | 0x0000000000000064 |                  100 |
|ATK     | 0x000000000000000a |                   10 |
+--------+--------------------+----------------------+
Checksum: 110
Input name: 123456789012345678901234567890
+--------+--------------------+----------------------+
|name    | 0x3837363534333231 |             12345678 |
|        | 0x3635343332313039 |             90123456 |
|HP      | 0x3433323130393837 |  3761405300628338743 |
|ATK     | 0x0000303938373635 |       53022314411573 |
+--------+--------------------+----------------------+
Checksum: 3761458322942750316
Detect cheat.

nabefuta@LAPTOP-RD6M1S1K:~/ctf$

ズルがばれてしまいました...

ここで、添付ファイルのソースファイルを見てみると、Cheaksumは次のように計算されていることがわかります。

 int64_t checksum = monster->hp + monster->attack;

 printf("Checksum: %ld\n", checksum);

 printf("Input name: ");
 scanf("%s%*c", monster->name);
 
 print_monster_infomation(*monster);

 printf("Checksum: %ld\n", monster->hp + monster->attack);

 if (monster->hp + monster->attack != checksum) {
  puts("Detect cheat.");
  exit(1);
 }

つまりは、モンスターのhpと攻撃力の総和を変えずに何とかいじれば、うまくいけそうです。

また、攻撃時の終了判定についてみてみましょう。

bool battle(Monster my_monster, Monster rival_monster) {
 bool my_turn = true;
 while (1) {
  printf("[You] %s HP: %ld\n", my_monster.name, my_monster.hp);
  printf("[Rival] %s HP: %ld\n", rival_monster.name, rival_monster.hp);
  
  if (rival_monster.hp < 0) {
   puts("Win!");
   return true;
  }
  if (my_monster.hp < 0) {
   puts("Lose...");
   return false;
  }

  if (my_turn) {
   puts("Your Turn.");
   printf("Rival monster took %ld damage!\n", my_monster.attack);
   rival_monster.hp -= my_monster.attack;
  } else {
   puts("Rival Turn.");
   printf("Your monster took %ld damage!\n", rival_monster.attack);
   my_monster.hp -= rival_monster.attack;
  }

  my_turn = !my_turn;
 }
}

このことから、モンスターの最初の体力は正である必要がありそうです。

また、モンスターの体力と攻撃値はint64_t=signed long intなので、オーバーフローをさせて、マイナスにさせても行けそうです。

そのため、VSCodeの拡張機能であるHex　Editerを使って、入力をバイナリ単位で調節します。

f:id:nabefuta_KP:20210907002634p:plain — cat.outの中身

この内容をパイプを使って、標準入力に入れてみます。

nabefuta@LAPTOP-RD6M1S1K:~/ctf/pwn_monster_2$ cat cat.out | nc 35.200.120.35 9002
 ____                 __  __                 _            
|  _ \__      ___ __ |  \/  | ___  _ __  ___| |_ ___ _ __ 
| |_) \ \ /\ / / '_ \| |\/| |/ _ \| '_ \/ __| __/ _ \ '__|
|  __/ \ V  V /| | | | |  | | (_) | | | \__ \ ||  __/ |   
|_|     \_/\_/ |_| |_|_|  |_|\___/|_| |_|___/\__\___|_|   
                        Press Any Key                            

Welcome to Pwn Monster World!
I'll give first monster!
Let's give your monster a name!
+--------+--------------------+----------------------+
|name    | 0x0000000000000000 |                      |
|        | 0x0000000000000000 |                      |
|HP      | 0x0000000000000064 |                  100 |
|ATK     | 0x000000000000000a |                   10 |
+--------+--------------------+----------------------+
Checksum: 110
Input name: +--------+--------------------+----------------------+
|name    | 0xffffffffffffffff |             �������� |
|        | 0xffffffffffffffff |             �������� |
|HP      | 0x7fffffffffffffff |  9223372036854775807 |
|ATK     | 0x800000000000006f | -9223372036854775697 |
+--------+--------------------+----------------------+
Checksum: 110
OK, Nice name.
Let's battle with Rival! If you win, give you FLAG.
[You] �����������������������o HP: 9223372036854775807
[Rival] pwnchu HP: 9999
Your Turn.
Rival monster took -9223372036854775697 damage!
[You] �����������������������o HP: 9223372036854775807
[Rival] pwnchu HP: -9223372036854765920
Win!
nitic_ctf{buffer_and_1nteger_overfl0w}

*** stack smashing detected ***: terminated
Aborted (core dumped)
nabefuta@LAPTOP-RD6M1S1K:~/ctf/pwn_monster_2$

スタックは壊れましたが、この問題のFlagはnitic_ctf{buffer_and_1nteger_overfl0w}です。

Misc

Excel

添付ファイルを開くと、このようにセルだけの画面が広がっています。

f:id:nabefuta_KP:20210907002918p:plain — セルだけがあるエクセルファイル

そこで、エクセルの検索機能を使い、nitで始まるセルを探してみます。

f:id:nabefuta_KP:20210907002841p:plain — 検索画面

すると、白文字で書かれていました。

ということで、この問題のFlagはnitic_ctf{plz_find_me}です。

image_conv

まずは、添付ファイルを開いてみます。

f:id:nabefuta_KP:20210907002804p:plain — 白く見える画像

すると、白に近い文字で何かが書かれているように感じます。

そこで、Wordで問題の画像を貼り付け、この画像にアート効果にチョーク:スケッチを加えます。

f:id:nabefuta_KP:20210907002949p:plain — アート効果を加えた後の画像

このとおり、はっきり見えました。

よって、この問題のFlagはnitic_ctf{high_contrast}です。

Rev

protected

まずは、添付ファイルの拡張子がないので、どのようなタイプかを調べます。

nabefuta@LAPTOP-RD6M1S1K:~/ctf/protected/protected$ file chall 
chall: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=34e0075bd7d601785c00143e049a88c6ec927e50, for GNU/Linux 3.2.0, not stripped

どうやら、このファイルは64bitのELFで、Linux系の実行ファイルのようです。(https://eng-blog.iij.ad.jp/archives/3376 より)

そのため、このファイルを実行してみます。

nabefuta@LAPTOP-RD6M1S1K:~/ctf/protected/protected$ ./chall 
bash: ./chall: Permission denied
nabefuta@LAPTOP-RD6M1S1K:~/ctf/protected/protected$ chmod u+x chall 
nabefuta@LAPTOP-RD6M1S1K:~/ctf/protected/protected$ ./chall 
PASSWORD:

やろうとしたが、権限がなかったので、権限をあたえて、再び実行したら、パスワードを聞かれました。

そこで、このファイルを開き、パスワードらしきものがないか調べてみます。

f:id:nabefuta_KP:20210907003014p:plain — challの中身

すると、怪しげな文字列が出てきました。そこで、その文字列であるsUp3r_s3Cr37_P4s5w0Rdを入力してみると、

nabefuta@LAPTOP-RD6M1S1K:~/ctf/protected/protected$ ./chall 
PASSWORD: sUp3r_s3Cr37_P4s5w0Rd
nitic_ctf{hardcode_secret}

無事、Flagを抜き出せました。

Crypto

Caesar Cipher

フラグの中身をシーザー暗号で暗号化したものがfdhvduだそうです。

そのため、次のようなコードを書いて、あり得る候補を探してみます。

#include <stdio.h>
#include <string.h>
char str[] = "fdhvdu";

int main() {
 for (int i = 'a'; i <= 'z'; i++) {
  for (int j = 0; j < strlen(str); j++) {
   str[j]++;
            if(str[j] > 'z'){
    str[j] = 'a';
   }

  }
  printf("%s\n", str);
 }
}

nabefuta@LAPTOP-RD6M1S1K:~/ctf/seeeser$ gcc see.c  -o see.out
nabefuta@LAPTOP-RD6M1S1K:~/ctf/seeeser$ ./see.out 
geiwev
hfjxfw
igkygx
jhlzhy
kimaiz
ljnbja
mkockb
nlpdlc
omqemd
pnrfne
qosgof
rpthpg
squiqh
trvjri
uswksj
vtxltk
wuymul
xvznvm
ywaown
zxbpxo
aycqyp
bzdrzq
caesar
dbftbs
ecguct
fdhvdu

この中で、意味がある文字列はcaesarです。

よって、この問題のFlagはnitic_ctf{caesar}です。

ord_xor

添付ファイルを見てみると、flagは次のような方法で暗号化されているようです。

import os
flag = os.environ["FLAG"]


def xor(c: str, n: int) -> str:
    temp = ord(c)
    for _ in range(n):
        temp ^= n
    return chr(temp)


enc_flag = ""
for i in range(len(flag)):
    enc_flag += xor(flag[i], i)

with open("./flag", "w") as f:
    f.write(enc_flag)

どうやら、flagのi番目の文字は元の文字にiをxorした後の文字になっているようです。

そして、できたflagが次のようになるそうです。

nhtjcZcsfroydRx`rl

ここで、xorの演算は、a xor b =cが成り立つとき、a = b xor cが成り立ちます。

つまり、できたflagを先ほどのコードを同じようにすれば、複合できそうです。

inv.py

flag = "nhtjcZcsfroydRx`rl"

def xor(c: str, n: int) -> str:
    temp = ord(c)
    for _ in range(n):
        temp ^= n
    return chr(temp)


enc_flag = ""
for i in range(len(flag)):
    enc_flag += xor(flag[i], i)

print(enc_flag)

nabefuta@LAPTOP-RD6M1S1K:~/ctf/ord_xor$ python inv.py 
nitic_ctf{ord_xor}

ということで、この問題のFlagはnitic_ctf{ord_xor}です。

nitic-ctf2に参加してみて

今回のctfは、初参加なので、すべての分野の~200点問題+競技プログラミングに近いCryptoの300点問題を解くことを目標にして、すべての問題の~200点問題は解けましたが、Cryptoの300点問題がとけなくて、悔しかったです。(特に3問目がグラフ理論系だったので、とても悔しい)

また、全体をとおして、まるで宝探しをしているような感覚で楽しかったです。

最後に、この企画を提案された、茨城高専の有志の方々、ありがとうございました!

2021-09-06

競技プログラミングで2年ほどでやったこと

ここまで競技プログラミングプログラミングでやってきたことを日記風にまとめておきます

また、競技プログラミングに参加しようかと考えている人向けに後半に何をやるべきか書いたので、時間のない人は、そこだけ見てください

競技プログラミングとの出会い・paizaランクA取得まで
- やったこと
- 習得したアルゴリズム・データ構造など
atcoder参戦 ~ 茶コーダーまで
- やったこと
- 習得したアルゴリズム・データ構造
茶コーダー　~ 緑コーダー　まで
- やったこと
- 習得したアルゴリズム・データ構造
緑コーダー ~ 水コーダー　まで
- やったこと
- 習得したアルゴリズム・データ構造
水コーダー ~ 現在
- やったこと
- 習得したアルゴリズム・データ構造
これから参加する人が上達するために

競技プログラミングとの出会い・paizaランクA取得まで

私の競技プログラミングの出会いは、部活でC言語講習での部員からの紹介です。

ここでpaizaさんのコード・ガールコレクション(https://paiza.jp/cgc)を知り、ここでPythonを習いました。

また、暇があるときにこれらの実践でプログラミングスキルチェックに挑戦して、D,C,Bランクとステップアップしていきました。

当時は問題に応じて、CとPythonを変えていました。

その後、エンジニアでも恋がしたい！〜転職初日にぶつかった女の子が同僚だった件〜 | paizaオンラインハッカソン（POH）(https://paiza.jp/poh/enkoi)などのプログラムエンタメに取り組み、その中で尺取り法を習得しました。

そして、2019年の2月にAランクを取得しました

やったこと

paizaのスキルチェック問題のAランクをクリアする (Aランクの問題を1問、想定解答時間以内(多くは2時間以内)に提出し、おおむねすべてのテストケースに正答する)
paizaの想定paizaランクB以上対象のプログラムエンタメに挑戦し、何らかのアルゴリズムを身に着ける

習得したアルゴリズム・データ構造など

尺取り法
C言語の基本構文(if,for,while,配列,入出力)
計算量の見積もり
標準入力から文字列を受け取る方法
数字とアスキー文字との関係

atcoder参戦 ~ 茶コーダーまで

その時は、paizaのスキルチェックSランクをとってから参戦しようと考えましたがSランク問題がなかなか解けず、埒が明かないと判断して、6月にatcoderに参戦しました。

その時に、直大さんのブログ(https://chokudai.hatenablog.com/entry/2019/02/11/155904)によると、エンジニアとしてもある程度の安心感がある緑コーダを目標にしました。

当時は、ABCが6問体制になってから間もなかったため、初めてのコンテストまでにABC127,128のA,B,C問題を解きましたが、ABC128のCが解けず不安になりました。

そうして、ABC129でデビューをしました。

その時にA,B問題は解けましたが、C問題で時間切れ、その問題の解説を見たら、DPを使う問題で、その時からDPに因縁を持っていました。

(当時のコンテスト成績表)

atcoder.jp

その次の週、ARCクラスの企業コンテストに参戦しました。

このコンテストではA問しか解けず、レートが下がると思っていたが、まさかの茶perfでびっくりしました。

また、翌日のABCでは、先週のABCと違ってスムーズに進み、特にC問題で考察中心の問題が出て、びっくりしました。また、D問題で尺取り法を使う問題が解けて、パフォーマンスももう少しで水色の1164でうれしかったです。

今後もABCはほぼ毎回参加し、A,B問題が解けて、C問題が解けるか解けないかのレベルでした。

また、途中にあったAGCに参加したが(当時は灰コーダでも参加できた)、1問も解けず、そのことがきっかけでAGCには出ないと決めました。

そして、2019年07月のABC135で茶コーダになりましたが、その時に解けなかったD問題で、今度もDPだ!と思ったら、今度は桁でDPをとるものでした...

(その時のコンテスト成績表)

atcoder.jp

やったこと

ABCに毎週参加する
時間があったときにABCのA,B問題を解く

習得したアルゴリズム・データ構造

特になし

茶コーダー　~ 緑コーダー　まで

これまで2度もDPに阻まれたのをきっかけにEducational DP ContestのE問題までを解きました。

しかし、ABC141のD問題で、優先度付きキューを使う問題が出て、それがC言語では提供されていないことがきっかけで、そこで競技プログラミングでC言語、さらにはPythonも捨て、C++一本で競技プログラミングに取り込むことを決めました。

まもなく、部活でのコンテストの最後の追い込みで半月間、競技プログラミングに触れられない日々が続きました。

そして、部活でのコンテスト終了後、C++になれるため、APG4bを解き、C++のライブラリに少しずつ慣れていきました。

このころから、精進の手段として、Atcoder ProblemsのRecommendationを使うようになり、有志が開くバーチャルコンテストに参加するようになりました。

このころから、アルゴリズムなどをライブラリにまとめ、コードを書くときに、すぐ引き出せるように整備しました。

あるとき、ABCのD問題で自分では互角だと思っていて、解けた問題のdiffを見たら、青diffで驚き、それと同時にここから自分の可能性を信じるようになりました。

しかし、グラフの問題は大の苦手で、気づいた瞬間、避けていました。その一方で、その判断が吉となり、結果として、水perfを取ると同時に、目標が水コーダーに変わりました。

しかし、それではいずれ足かせになると思い、Webの記事などで幅優先探索、深さ優先探索を習得し、グラフに慣れました。

あるときのABCでこれまでかけたはずのDPが書けなくなり、これがきっかけでC++でEDPCを解き直しました。

2020年02月のABC154で緑コーダーになりましたが、ここでも(事実上の)桁DPに阻まれました。

(その時のコンテスト成績表)

atcoder.jp

やったこと

ABCに毎週参加する
時間があったときにAtcoder ProblemsのRecommendationにある問題を解く
バーチャルコンテストに参加する

習得したアルゴリズム・データ構造

累積和
mod10⁹+7で二項係数を求めるアルゴリズム
mod10⁹+7でべき乗を高速に計算するアルゴリズム
mod10⁹+7での加減乗算
最大公約数を求めるアルゴリズム(ユークリッドの互除法)
bit全探索・bitを用いた状態の保存
C++でのプログラミング全般
for文を使った幅優先探索
再帰関数を使った深さ優先探索
整数に関する知識(素因数分解、素数判定など)

緑コーダー ~ 水コーダー　まで

ここら辺から1年近く、毎日1問は新規ACをするようになりました。

また、2月の終わりからe869120さんのレッドコーダーが教える、競プロ・AtCoder上達のガイドライン(https://qiita.com/e869120/items/eb50fdaece12be418faa)の分野別　初中級者が解くべき過去問精選 100 問を解くようになりました。

さらに、コロナによる休校+遠隔授業も重なり、競技プログラミングに専念できるようになり5月ごろには、9割前後をACしました。

ここで、panasonic2020のC問題(https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_c)などの浮動小数点の誤差に注意する問題が多くなり、苦戦しました。

また、4月から、バチャであさかつ・よるかつ/くじかつに参加するようになり、これによって、時間内にどう立ち回るかを鍛えられました。

このバチャは序盤に相対的に解いていない灰diffが出るため、ステークを重ねやすくなりましたが、すでに解いていた問題の場合、日が変わるまでに解けない可能性が高いため、バチャ前にステークを重ねるようにしました。

おまけに、解けない問題に出会える機会が増えたため、解説を読んで、手が届きそうならば、実装するというのをするようになり、ダブリングなどをこの方法で習得しました。

また、PASTが無料で受けられるのを聞き、第三回アルゴリズム実技検定に挑戦しました。

(当時のツイート)

コロナウイルスの状況を鑑みて、アルゴリズム実技検定PASTを無料で提供することになりました。強制的に5時間ステイホームしてもらう試験です。ぜひぜひ受けてみてくださいな！https://t.co/LQnX4DbY3n
— chokudai(高橋直大)🍆 (@chokudai) 2020年5月5日

それに先立ち、第1回と2回目の過去問に挑戦したところ、セグメント木を使えるかどうかが中級への鍵だと考え、セグメント木を勉強しました。

本番では、セグメント木こそは使わなかったが、時間を配分を間違い、これが解けたら中級だと思って解いたら、すでに中級が確定していたなどのハプニングがありましたが、最後から3番目の問題の複数のアルゴリズムを使って解く問題が解けて、実力の向上を感じました。(ちなみにあと一問解けてたら上級でした)

ここら辺から、問題を解く時に、似たような問題を思い出し、その思い出をだとって解いたりするようになりました。

2020年の6月当たりからABC170のD問題などで(https://atcoder.jp/contests/abc170/tasks/abc170_d)エラトステネスの篩を使う問題が出てきたのを感じ、エラトステネスの篩を習得しました。

2020年の8月から、コンテスト後に解説を書き始めました。解説を書く時に気を付けたのは次の3つです。

できるだけ速く解く
わかった問題は、どのように考えて、どのような方法で解くか
できなかった問題は、どこまでできたか、どこでつまずいたかを書く

2020年9月にACLが導入されました。

2020年12月のABC185でE問題のDPが解け、初めての全完&水コーダになりました。

やったこと

e869120さんのレッドコーダーが教える、競プロ・AtCoder上達のガイドライン(https://qiita.com/e869120/items/eb50fdaece12be418faa)の分野別　初中級者が解くべき過去問精選 100 問を解く
時間があったときにAtcoder ProblemsのRecommendationにある問題を解く
バーチャルコンテストに参加する

習得したアルゴリズム・データ構造

答えに貢献する量から答えを求める
セグメント木
エラトステネスの篩
二部探索
区間DP
bitDP
ダイクストラ法
ワーシャルフロイド法
プリム法・クラシカル法
mod10⁹+7での除算
グラフの取り扱い(隣接行列・隣接リストへの変換)
Disjoint Set (Union Find)
半分全列挙
imos法
ダブリング
座標圧縮
木の直径

水コーダー ~ 現在

ABC189のE問題で初めてアフィン変換を知りました。

また、2021年5月のABCクラスの企業コンで青diffだと思って解いたF問題が黄diffになり、初めての黄perfを取りました。

また、その解法で、論理回路のベイチの図を使ったため、学業も競技プログラミングの役に立つと感じました。

遅延評価付きセグメントのライブラリを作るように

ABCが8問体制になったころから、学業に時間をとられ、精進はできていませんが、ABCトーナメントに参加し、対象となるABCには出ています。

現在は青コーダーを目指して頑張っています

やったこと

とくになし

習得したアルゴリズム・データ構造

遅延評価付きセグメント木
アフィン変換

(ここからは用語は知っているが、実装はできないアルゴリズムたちです)

高速ゼータ変換
行列累乗
きたまさ法
拡張ダイクストラ法
中国剰余定理
最大流・最小カット
全方位木DP

これから参加する人が上達するために

~灰コーダ

まずは、一つの言語でif,for,while文などの基本構文を習得しましょう。

私のお勧めはpaizaさんのコードガールこれくしょん(https://paiza.jp/entertainment)などで一通りクリアしたのち、スキルチェックでCランク問題を3問程度クリアです。C++なら、APG4B(https://atcoder.jp/contests/apg4b)もお勧めです

~茶コーダー

ABCのA~C問題を解いて、Atcoderに慣れましょう。ABS(https://atcoder.jp/contests/abs)がお勧めです

また、計算量に関する知識と全探索を身につけましょう。 e869120さんが書いた「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】」の全探索の問題 (https://qiita.com/e869120/items/f1c6f98364d1443148b3#%E5%85%A8%E6%8E%A2%E7%B4%A2%E3%81%AE%E5%95%8F%E9%A1%8C)がお勧めです。

また、計算量に関する知識に関連して、disjoint-setや、調和級数になるループ、エラトステネスの篩を習得するのをお勧めです。

また、ここら辺から、自分がどうやって解いたか、もしくは、どこまでは考えついたかを書き起こしておくことをお勧めします。

~緑コーダー~水コーダー

ここからになると、レートを上げる方法は大きく分けて2通りの道があります。

問題を速く解く
問題を多く解く

1はレートを安定させるのに役立ちます。自分と同じか一つ下の色の問題を解くのがお勧めです。 2は高いレートを取るのに役立ちます。分野別の学習はe869120さんの「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】」分野別　初中級者が解くべき過去問精選 100 問(https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)やアルゴ式(https://algo-method.com/)がお勧めです。アルゴリズムのverifyには、aize online judge(https://onlinejudge.u-aizu.ac.jp/home)もお勧めです。アルゴリズムの引き出す力の習得には、競プロ典型 90 問(https://atcoder.jp/contests/typical90)がおすすめです。

1,2共通で時間があるときにバチャに出ましょう。私のお勧めは毎日21時から行われるくじかつです。

2021-03-03

プリキュアをプログラミングで再現してみる(キュアサマー編)

プリキュア x プログラミング

nabefutaです。

今回は、キュアサマーの変身部分と攻撃の部分をJavaを使って書いてみました。

注意:コードは https://github.com/nabefuta220/precure_reproduct からでも見ることができます。

今回作ったコードの説明

今回は変身部分は、Javaなどのクラスの宣言で使われるコンストラクタを使った方法と、アニメで言うときと同じようにした方法と、道具をセットする方法の3つを用意しました。

また、技を使う時は、今回は、アニメで言うときと同じようにした方法のみを用意しました。

例:

import precure_root.*;
import tools.*;
import tropical_rouge_precure_root.*;

public class Main {
    public static void main(String[] args) {
        Precure precure = new Precure();
        // transfromation
        // cure.Summer summer = new cure.Summer();// (a)

        // tropical_rouge_precure summer = Precure.tropical_change("CureSummer");// (b);

        Heartcle_pact pact = new Heartcle_pact();
        tropical_rouge_precure summer = pact.setKey(Heartcle_ring.CureSummer_key);// (c)

        // cure
        precure.otento_summer_strike(summer);

    }
}

今回使ったコード

今回は、キュアサマーの他にも、道具などのファイルを作り、大分長くなったので、割愛します...

(コードは

github.com

でも見ることができますので、こちらも参考にしてください。)

今回で、トロピカルージュプリキュアの基幹的な部分はできたので、追加は今週ほどにはかからなそうなので、今時点で発表されている4人が出そろった時点で、また、実装仕様と思います。

2021-02-26

プリキュアをプログラミングで再現してみる(準備編)

プリキュア x プログラミング

nabefutaです。

今回は、プリキュアをプログラミングを使って再現するのに、準備として、変身部分と簡単な攻撃の部分をJavaを使って書いてみました。

注意:コードは https://github.com/nabefuta220/precure_reproductからでも見ることができます。

私が考えるプリキュアの定義について
今回作ったコードの説明
今回作ったコード

私が考えるプリキュアの定義について

まずは、「プリキュア」という定義について私なりの解釈を書いておきます。*1

変身時の挙動がある
1つ以上の技が使える
変身ができるかどうかは高々個人の状態、妖精、変身アイテム(必要に応じて他のプリキュアに変身する人物、そして、同時に変身する)のみに左右される

ひとまずは、このように認識しています。

逆に言うと、この条件さえ満たせば、性別を問わず、だれでもプリキュアであると、考えています。

今回作ったコードの説明

今回は、ひとまず、cure.Nabefutaとしてつくり、次のような技を実装しました。

precure.action (特に意味も無ければ、効果もありません...)

今回は、使う時に、cure.(名前)のようにしたり、技を使う時にprecure.(技名)のようにして、アニメ上で言うときと同じようにするのを心がけました。

例:

public class Main {
    public static void main(String[] args) {
        cure.Nabefuta nabefuta = new cure.Nabefuta(5);
        new precure.action(nabefuta);
        new precure.action();
    }
}

今回作ったコード

src/cure/Nabefuta.java (cureNabefutaを実装したもの)

package cure;

public class Nabefuta {
    private int flag;

    public Nabefuta(int num) {
        this.flag = num;
    }

    public int getFlag() {
        return this.flag;
    }
}

src/precure/action.java (precure actionを実装したもの)

package precure;

public class action {

    public action() {
        System.out.println("NA");
    }

    public action(cure.Nabefuta a) {
        System.out.println("action :" + a.getFlag());
    }
}

この調子で今週のプリキュア放送後には、キュアサマー(cure Summer)を実装しようと思います。

*1:この分野については、論争が激しいため、あくまで、一個人の意見として読んでください。

2021-02-25

一人のプリキュア視聴者としての自己紹介

自己紹介プリキュア

nabefutaです。ここでは、一人のプリキュア視聴者としての詳しい自己紹介をしていきます。

(このツイートの詳細部分を話していきたいと思います)

プリキュアにはまり、離脱するまで
- プリキュアを再び知るまで
  - おジャ魔女どれみとの出会い
  - プリキュアとの出会い再び
- プリキュアを再びリアル視聴するようになるまで
私が考えるプリキュアの魅力
プリキュアシリーズの視聴状況
好きなプリキュアソング
フォローNGについて
- 頭ごなしにプリキュアを否定する人
- 公式の発表前にプリキュアストーリーに関するネタバレをする人
好きなプリキュアエピソード
- ハートチャッチプリキュア第28話
- HUGっとプリキュア第49話

プリキュアにはまり、離脱するまで

私が初めてプリキュアを知ったのは、2007年のYes!プリキュア5の時でした。

当時は妹*1につられて見ていました。

そのため、当時は流し読みならぬ流し見のような感じで、大切なことも心に残っていない状態でした。

唯一覚えているのは、シリーズが変わって、フレッシュプリキュア!になったときに、「あれ?キュアドリームはどうしたの?」となったことです。

このような視聴スタイルはハピネスチャージプリキュア!までは続いていましたが、

新シリーズとして、プリンセスをモチーフにした、Go!プリンセスプリキュアから、プリキュアを見ることに恥ずかしさが芽生え、プリキュアから離れました。

しかし、新シリーズについては、ニュースでも出ていたため、題名だけは知っている状態は維持していました。

プリキュアを再び知るまで

おジャ魔女どれみとの出会い

時は流れて、2019年の2月頃、YouTubeで偶然、おジャ魔女どれみ全シリーズお着替え・変身まとめ*2たるものを見つけました。

そこから、おジャ魔女どれみを知りました。

それに、当時プログラミングを勉強していたこともあり、この作品のテーマである魔法がプログラミングによって書き表せるという思いを持ち、おジャ魔女どれみにはまりました。

プリキュアとの出会い再び

プリキュアを再び知るきっかけになったのも、またYouTubeでした*3。

それ以来、プリキュアシリーズのうち、気に入った物の感想記事を読むことに明け暮れていました。

プリキュアを再びリアル視聴するようになるまで

2019年の12月にTVerでアニメの見逃し配信を見るときに、たまたまスター☆トゥインクルプリキュアの42話があることに気づきました。

実際にリアルタイム視聴を始めたのは、45話でしたが、その回でデネブ*4を取り巻く星が長い年月を経て変化するという台詞が私が知っていた、北斗七星の形が長い年月を経て変化するという知識と結びつき、プリキュアという存在がアニメから、学校では教えてくれないことを教えてくれる課外授業に変わりました。

私が考えるプリキュアの魅力

私が考えるプリキュアの魅力は作中での情報がこれまでに学んだ知識と結びついたり、思いもしないことに興味をもつことができる点です。

プリキュアを再びリアル視聴するまでで上げた例だと、「星座は時を経て変わる」という星座の知識とスター☆トゥインクルプリキュア45話の「デネブを取り巻く星が長い年月を経て変化する」という知識が結びつくきました。

逆に、HUGっと!プリキュア35話では、帝王切開による出産による安全性による話題がでて、詳しく調べるきっかけができました。

しかし詳しく学ぼうとすると、話の内容はあくまでも「子供向け」に作れている関係ですこし簡単になっていることがあるため、

作中で描かれていない情報は、自分で調べたりするのが大事だと考えています。*5。

プリキュアシリーズの視聴状況

プリキュアシリーズのうち、気に入った物の感想記事を読むことに明け暮れていた関係もあって、基本的は、気になった回をDVDをレンタルして見る、というのが中心で、これで、HUGっと!プリキュアは見ていました。

いまは、Amazon prime videoでプリキュアシリーズが配信されたことに伴い、Amazon prime videoで見ることが中心となっていて、現在はハートチャッチプリキュア!は全話視聴済み、Yes!プリキュア5を視聴です。

それとは別に、スター☆トゥインクルプリキュアの終盤以降は、リアルタイムで見ています。

好きなプリキュアソング

自己紹介シートにはメモワール・ミルフィーユ、イマージュの翼、ZUTTO 在るココにの3つを挙げましたが、実際はもっとたくさんあって、Aileやもう一度、あの空の先へなども好きです。

全部と書くことも考えましたが、まだすべてのすべてのプリキュアソングを聴いているわけでもないので、特に好きな3曲を上げておきました。

フォローNGについて

頭ごなしにプリキュアを否定する人

私としては、プリキュアは一つの学習教材として捉えていることもあって、プリキュアを見ている大人の男性はキモいなどの視聴者に対する誹謗・中傷のコメントはNGです...

それと同じように、プリキュア内の登場人物が取った行動などに理由を入れずに批判をするのもNGです...

ただし、「自分(自分が(人名))だったらこうする」と言う内容はOKです。

いわゆる個人を尊重して欲しい、といった内容です。

公式の発表前にプリキュアストーリーに関するネタバレをする人

いわゆる早バレです。

私としては追加戦士や新たな浄化技、フォームなどは考察のし甲斐があるため、公式の発表前では、内容の考察程度にとどめて欲しいです*6。(考察なら大歓迎です!!)

例えば、

ハピネスチャージの新フォーム、羽が生えたりするのかな?

程度なら許容範囲ですが、

ハピネスチャージの新フォーム、イノセントフォームらしいよ

や画像の公開はNGです...*7

つまり、想像力を膨らませる時間が欲しい、ということです。

好きなプリキュアエピソード

ハートチャッチプリキュア第28話

夏休みの宿題回です。

この回は、題材として、夏休みの宿題なんてやりたくない!という、小学生によくある事例を取り合げて、

同じく宿題をやっていない主人公:来海えりかが怪物:デザトリアンの主張に一瞬は納得しようとするが、戦闘をへて改心し、

同時に夏休みの宿題の意義や助け船もあるよと示すところが良い意味で教育的で良いと思いました。

おまけに、アバンでの「やることやらないで遊んでばかりいるとデザトリアンになっちゃうわよ」と言う台詞がプリキュアの世界だからこそできる脅し文句だと思いました。

HUGっとプリキュア第49話

HUGっとプリキュアの最終回です。ですが、私はあえて総まとめ回と呼んでいます。

と言うのも、この回は過去と未来が現在を経てつながる回だと思っているからです。

ここで言う、過去、現在、未来とは、2030年(Bパート)からみたもので、

それぞれ、次のようなイメージを持っています。

過去:生まれ育った懐かしい町。過去の体験したこと、経験したもののすべて
現在:長い長いトンネル。暗く、ただ、自分の足音が響くなかで自分や仲間を信じ、自分で決めた先へ進む
未来:トンネルを抜けた先にある輝く世界。一見、(過去寄りの)現在と変わらなく見えるが、過去の経験を生かすことで、ずっと進んだ世界に見える

劇伴音楽上では、

キミとともだち :過去
We can!!HUGっと!プリキュア(サビあたりまで) :現在
その後 :未来

というイメージを持っています。

また、このシリーズについて、最終回==終わりと言うイメージがあまりなく、むしろ始まりというイメージがあると言う点でも好きです。

*1:年齢は伏せておきます...

*2:ここでのお着替えとは、プリキュアでいうところの変身です。

リンク:https://www.youtube.com/watch?v=SWUcxz0EUD0

*3:きっかけになった動画のタイトルは【公式】ふたりはプリキュア第1話「私たちが変身!? ありえない！」です。

リンク:https://www.youtube.com/watch?v=EtXI6Ta5dVE

*4:はくちょう座にある恒星、夏の大三角形の一つ

*5:いわゆる大学の授業言うところの自習です

*6:そもそも早バレを拡散する時点でアウトですが...

*7:もちろん、公式の発表後はOKです!

2021-02-22

競プロerとしての自己紹介

競技プログラミング自己紹介

ここでは、競技プログラマーとしての自己紹介をしていきます。

ユーザーネーム・競プロ歴
AtCoderに出会うまで
- プログラミングとの出会い
- 競技プログラミングとの出会い
  - paizaとの出会い
  - AtCoderとの出会い
AtCoderで主に使っている言語
印象に残っているアルゴリズム・データ構造

ユーザーネーム・競プロ歴

nabefutaです。

競技プログラミングは2018年の11月にpaiza*1で知り、2019年の6月にAtCoderのBeginner Contest に参加して以来、2021年の3月で1年と9ヶ月、途中休止をはさみながら、主に週末にAtCoderのBeginner Contest に参加して現在、水コーダーです。

AtCoderに出会うまで

ここでは、AtCoderに出会うまでを時系列にまとめていきます。

プログラミングとの出会い

プログラミングとの出会いは、私が小学4年生だったときの夏休みにある学校のオープンスクールです。

そのときに、ドリトル*2でMYUロボを動かしたのが初めてのプログラミングでした。

その後、中学3年の頃にiOSのアプリ:Swift Playground‪sをきっかけにSwift*3を知り、その翌年には部活でC言語を知りました。

競技プログラミングとの出会い

paizaとの出会い

部活でC言語について学んだあと、自習の手段として、paizaのコードガールこれくしょんを紹介されました。

そのときに「もっと難しい問題も解きたい!」となってHAEDモードを選んだのですが、その当時はPython3版しか実装されていませんでした。しかし、やっていくうちに、Python3でも簡単なプログラムならば書けるようになりました。

それとほぼ同時にスキルチェック*4にも挑戦するようになりました。

最初は、「標準入力って何?」といった感じで、Dランクすら獲れなかったのですが、標準入力の代わりに入力値となっている問題でDランクを獲ってからは、暇なときにはスキルチェックに取り組み、2019年の2月には、Aランクを獲ることができました。

AtCoderとの出会い

2019年の3月に関東での交流会でAtCoderを知りました。

そのときから、C言語でもAtCoderに参加できることは知っていましたが、当時は実力が余りついていなかったと思い、paizaランクSランクを獲ってから参加しようと思っていましたが、獲れる気配がなかったため、2019年の6月に初参加しました。*5

AtCoderで主に使っている言語

AtCoderに参加して以来しばらくは、主にC言語、処理の内容によって、Python3を使っていました。しかし、ある問題*6をきっかけにC++一本に切り替えました。

印象に残っているアルゴリズム・データ構造

動的計画法(DP)*7です。

私にとって、動的計画法は宿敵ともいえる関係で、最初に参加したコンテストでも、これに引っかかり、それ以来、節目節目で出くわしていて、印象に残っています。

*1:ITやWebエンジニアに特化した転職・就職・学習サイトです。　その中でも、paizaラーニングでは、C、Java、Python3など、7言語のプログラムの基礎をWeb上のエディタを使いながら学ぶことができ、また、スキルチェックで腕試しができるので、私はAtCoderを始める前に使い、基礎的な知識を習得しました。リンク:https://paiza.jp/

*2:日本語を使って書くことができるプログラミング言語です。ドリトルの情報ページ: https://dolittle.eplang.jp/

*3:主にiOSのアプリの開発で使われているプログラミング言語です。2014年と比較的最近登場したのに伴い、他の言語に似たところがあります。

*4:問題が出題されるので、その問題に答えるプログラムを規定時間内に提出して、プログラミングの提出までの時間と解答の正確さによってpaizaランクが与える仕組みです。

下から2番目のDランクは標準入出力、基本的な構文を知っていれば突破できますが、一番上のSランクになると、普通にプログラグを組むと実行時間制限を越えてしまうため、工夫なしには突破できません。

公式ページの解説: https://paiza.jp/guide/career#outline

*5:ちなみにpaizaランクSランクを獲ったのは、2020年の4月のことでした。

*6:その話については後日上げる予定です

*7:ある大きな問題を解くのに、いくつかの小さな問題に分け、その結果をまとめて大きな問題を解く手法です。

2021-02-21

自己紹介 + このブログについて

自己紹介

nabefutaです。

2019年の6月にAtCoderに初参加し、その道中にプリキュアにはまった、変わった人です。

このブログにはAtCoderの問題の考察と、プリキュアの考察(主に変身シーンとパワーアップ関係)を投稿する予定です。

web

web_meta

long flag

Pwn

pwn monster1

pwn monster2

Misc

image_conv

Rev

protected

Crypto

Caesar Cipher

ord_xor

nitic-ctf2に参加してみて

競技プログラミングとの出会い・paizaランクA取得まで

やったこと

習得したアルゴリズム・データ構造など

atcoder参戦 ~ 茶コーダーまで

やったこと

習得したアルゴリズム・データ構造

茶コーダー ~ 緑コーダー まで

やったこと

習得したアルゴリズム・データ構造

緑コーダー ~ 水コーダー まで

やったこと

習得したアルゴリズム・データ構造

水コーダー ~ 現在

やったこと

習得したアルゴリズム・データ構造

これから参加する人が上達するために

~灰コーダ

~茶コーダー

~緑コーダー~水コーダー

今回作ったコードの説明

今回使ったコード

私が考えるプリキュアの定義について

今回作ったコードの説明

今回作ったコード

プリキュアにはまり、離脱するまで

プリキュアを再び知るまで

おジャ魔女どれみとの出会い

プリキュアとの出会い再び

プリキュアを再びリアル視聴するようになるまで

私が考えるプリキュアの魅力

プリキュアシリーズの視聴状況

好きなプリキュアソング

フォローNGについて

頭ごなしにプリキュアを否定する人

公式の発表前にプリキュアストーリーに関するネタバレをする人

好きなプリキュアエピソード

ハートチャッチプリキュア第28話

HUGっとプリキュア第49話

ユーザーネーム・競プロ歴

AtCoderに出会うまで

プログラミングとの出会い

競技プログラミングとの出会い

paizaとの出会い

AtCoderとの出会い

AtCoderで主に使っている言語

印象に残っているアルゴリズム・データ構造

茶コーダー　~ 緑コーダー　まで

緑コーダー ~ 水コーダー　まで